Classical

Data Structures - Sorting & Searching

26:  

The number of swappings needed to sort the numbers 8, 22, 7, 9, 31, 19, 5, 13 in ascending order, using bubble sort is

A.

11

B.

12

C.

13

D.

14

 
 

Option: D

Explanation :


27:  

The average successful search time taken by binary search on a sorted array of 10 items is

A.

2.6

B.

2.7

C.

2.8

D.

2.9

 
 

Option: D

Explanation :

The 10 items i1, i2, ..., i10 may be arranged in a binary search trees as in Fig   To get i5, the number of comparision needed is 1; for i2, it is 2; for i8 it is 2; for i1 it is 3, and so on. The average is (1+(2+2) +(3+3+3+3)+(4+4+4))/10, i.e., 2.9.

sorting tree


28:  

The average successful search time for sequential search on 'n' items is

A.

n/2

B.

(n-1)/2

C.

(n+1)/2

D.

log (n)+1

 
 

Option: C

Explanation :

If the search key matches the very first item, with one ocmparision we can terminate. If it is second, two comparisons , etc. So, average is (1+2+...+n)/n .i.e. (n+1)/2


29:  

The running time of an algorithm T(n), where 'n' is the input size, is given by

T(n) = 8T(n/2) + qn, if n>1

Where p,q are constants. The order of this algorithm is

A.

n2

B.

nn

C.

n3

D.

n

 
 

Option: C

Explanation :


30:  

L:et m, n be positive integers. Define Q (m, n) as

Q (m, n) = 0, if m>n

Then Q (m, 3) is (a div b, gives the quotient when a is divided by b)

 

A.

a constant

B.

p x (m mod 3)

C.

p x (m div 3)

D.

3 x p

 
 

Option: C

Explanation :

Let m>n. Let m/n yield a quotient x and remainder y. So, m= n*x+y and y<m div 3 is the quotient when m is divided by 3. So, that many times p is added, before we terminate recursion by satisfying the end condition Q (m,n) = 0 if m<n. Hence the result.




Suggest an improvement