Classical

Data Structures - Sorting & Searching

36:  

 The average number of comparisons performed by the merge sort algorithm, in merging two sorted liss of length 2 is

A.

8/3

B.

8/5

C.

11/7

D.

11/6

 
 

Option: A

Explanation :

Merge-sort combines two given sorted lists into one sorted list. For this problem let the final sorted order be- 1, b, c, d. The two lists (of length two each) should fall into one of the following 3 categories.

(i) a, b and c,d  (ii) a, c and b, d  (iii) a, d and b, c

The number of comparisons needed in each case will be 2, 3, 3. So, average number of comparisons will be (2=3+3)/3= 8/3

Here is a better way of doing;

Let list L1 have the items a,c and L2 have the items b,d.

sorting tree

The tree drawn below, depicts the different possible cases. (a & b means a is compared with b. If a is smaller, the edge will be labeled a. The number within a circle, beside the leaf nodes, is the number of comparisons, needed to reach it.)

From the tree, we find there are 6 possible ways, total number of comparisons needed is 3+3+2+2+3+3=16. So, average number of comparisons is 16/6= 8/3.

 


37:  

Which of the following sorting methods will be the best if number of swappings done, is the only measure of efficienty?

A.

Bubble sort

B.

Selection sort

C.

Insertion sort

D.

Quick sort

 
 

Option: B

Explanation :

Because in selection sort algorithm we randomly access data rather than a list in which we can easily swap data which we want to swap and it takes less time. So, answer is 'B'


38:  

You are asked to sort 15 randomly generated numbers. You should prefer

A.

bubble sort

B.

Selection sort

C.

Insertion sort

D.

Quick sort

 
 

Option: A

Explanation :


39:  

As part of the maintenance work, you are entrusted with the work of rearranging the library books in a shelf in proper order, at the end of each day. The ideal choice will be

A.

bubble sort

B.

insertion sort

C.

selection sort

D.

heap sort

 
 

Option: B

Explanation :


40:  

The maximum number of comparisons needed to sort 7 items using radix sort is (assume each item is 4 digit decimal number)

A.

280

B.

40

C.

47

D.

38

 
 

Option: A

Explanation :

The maximum number of comparison is number of items ´ radix ´ number of digits i.e., 7´10´4 = 280.




Suggest an improvement