Sorting Interview Questions Part 5

68. Which of these is the correct big-O expression for 1+2+3+...+n?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)
Ans:d


69. Consider the following polynomial

aknk+ak-1nk-1+………….a0 .

What is the Big –O representation of the above polynomial?
(a)O(n) (b) O(nk) (c) O(nk+1) (d) O(log k)
Ans:b
70. Consider the program segment given below:
Int i,j,sum;
for ( i=0 ; i < n; i++) {
for (j = 1,sum=a[0]; j < = i; j++)
Sum+=a[j];
printf(“ sum for sub-array through %d is %d”,i , sum);
}

The running time of the above algorithm is

(a) n. (b) n log n . (c) log n. (d) n2.
Ans:d


71. Consider the following algorithm:

Step 1 : If S has zero or one element, return S immediately; it is already sorted. Otherwise, split S into two parts S1 and S2, such that S1 contains the first [n/2] elements of S, and S2 contains the remaining elements of S.
Step 2: Recursively sort sequences S1 and S2
Step 3: put back the elements into S by merging the sorted sequences S1 and S2 into a sorted sequence.

Which of the following describe(s) the above algorithm?

(a) Sorting by insertion
(b) Sorting by selection
(c) Sorting by exchange
(d) Divide and conquer
Ans:d


72. Consider the following algorithm :
abc(data[])
Transform data into a heap
for ( i=data.length-1; i> 1 ; i--)
Swap the root with the element in position i;
Restore the heap property for the tree data[0],…….. data[i-1];
Which of the following are not the intermediate functions of the above algorithm?
(a) Transforming data into either an ascending order or descending order of a heap
(b) Transforming data into a maximum heap
(c) The 1st step of the sorting process is exchanging the last element and the first element, and decreasing the array size by one.
(d) Finally, get either the ascending order or the descending order of nodes
Ans: b