Sorting Interview Questions Part 7

11. In bubble sort algorithm the number of comparison is irrespective of data set i.e., input whether best or worst.(T/F)
Ans:True
12. The basic procedures related to heap are
a.Heapify, which runs in O(lg n) time.
b.Build-Heap, which runs in linear time.
c.Heap Sort, which runs in O(n lg n) time.
d.Extract-Max, which runs in O(lg n) time.
Ans:a,b,c,d
13. Heapify runs in O(lg n) time while build-heap runs in _____time.
Ans: linear
14. A process picks the largest child key and compares it to the parent key and if parent key is larger then the process quits, otherwise it swaps the parent key with the largest child key, so that the parent now becomes larger than its children.Such a process is called
a.Heap sort
b.Heapify
c.Build heap
d.none
Ans:b
15. Process (A, i)
1. l ← left [i]
2. r ← right [i]
3. if l ≤ Process-size [A] and A[l] > A[i]
4. then largest ← l
5. else largest ← i
6. if r ≤ Process -size [A] and A[i] > A[largest]
7. then largest ← r
8. if largest ≠ i
9. then exchange A[i] ↔ A[largest]
10. Process (A, largest)
The above process indicates
a.Heap sort
b.Heapify
c.Build heap
d.none
Ans:b

16.The output of heapify of the following tree is




a. 15 8 4 7 5 3 1 2 6 b. 8 15 4 7 5 3 1 2 6 c. 15 8 4 7 5 3 1 6 2 d. 15 8 4 5 7 3 1 2 6
Ans:a
17. Process (A)
1. BUILD_HEAP (A)
2. for i ← length (A) down to 2 do
exchange A[1] ↔ A[i]
heap-size [A] ← heap-size [A] - 1
Heapify (A, 1)
The process here denotes
a.Selection sort b.Heap sort c.Bubble sort d.none
Ans:b

18. The time taken for build heap is
a.O(n)
b.O(log n)
c.O(nlogn)
d.none
Ans:a
The HEAPSORT procedure takes time O(n lg n), since the call to BUILD_HEAP takes time O(n) and each of the n -1 calls to Heapify takes time O(lg n).
19. Process (A1, A2, A)
i.← j 1
A1[m+1], A2[n+1] ← INT_MAX
For k ←1 to m + n do
if A1[i] < A2[j]
then A[k] ← A1[i]
i ← i +1
else
A[k] ← A2[j]
j ← j + 1
SORT (A)
A1[1 . . n/2 ] ← A[1 . . n/2 ]
A2[1 . . n/2 ] ← A[1 + n/2 . . n]
Process (A1)
Process (A1)
Process (A1, A2, A)
Which sorting algorithm does SORT represent
a.Selection sort b.Heap sort c.Bubble sort d.Merge sort
Ans:d
20.Quick sort is recursive.(T/F)
Ans:True