Sorting Interview Questions Part 9

36. According to the max-heap property, each node in a tree has a key which is _______ than or equal to the key of its parent.
Ans. less

37. A sort algorithm that repeatedly looks through remaining itemsto find the least one and moves it to its final location is
a. Quick sort
b. Insertion sort
c. Selection sort
d. Merge sort
Ans. c

38. __________ is a specialization of selection sort.
a. quick sort
b. selection sort
c. bingo sort
d. strand sort
Ans. c
Bingo sort is a variant of selection sort that orders items by repeatedly looking through remaining items to find the greatest value and moving all items with that value to their final location. This is more efficient if there are many duplicate values.

39. __________ can be seen as a variant of selection sort in which sorted items are arranged in a heap to quickly find the next item.
a. heap sort
b. bingo sort
c. shell sort
d.none of the above
Ans. a

40. ___________ is a kind of quicksort
a. balanced quicksort
b. multikey quicksort
c. retrospective sort
d. all the above
Ans. d

41. ___________ is a part of or used in quicksort.
a. divide and conquer
b. partition
c. recursion
d. all the above
Ans. d

42. Insertion sort is also known as __________.
Ans. Linear insertion sort




43. Given the following sequence of elements 11,2,9,13,57,25,17,1,90,3 what will be the output after MAX_HEAPIFY(A,2) where heap-size[A]=10.
a. 11,2,9,13,25,57,17,1,90,3
b. 11,2,9,90,57,25,17,1,13,3
c. 11,90,9,13,57,25,17,1,2,3
d. 90,57,25,13,11,9,17,1,2,3
ans. c

44. Given the following set of elements 16,4,10,14,7,9,3,2,8,1 what will be the output after MAX_HEAPIFY(A,2) where heap-size[A]=10.
a. 16,4,10,14,7,9,3,2,8,1
b. 16,14,10,4,7,9,3,2,8,1
c. 16,14,10,8,7,9,3,2,4,1
d. 16,14,10,8,7,3,9,2,4,1
Ans. c

45. Give the output of MAX_HEAPIFY(A,3) in the array A=( 27,17,3,16,13,10,1,5,7,12,4,8,9,0).
a. 27,17,3,16,13,10,1,5,7,12,4,8,9,0
b. 27,17,10,16,13,3,1,5,7,12,4,8,9,0
c. 27,17,10,16,13,9,1,5,7,12,4,8,3,0
d. 27,17,3,16,13,7,1,5,10,12,4,8,9,0
Ans. c





46. If the sequence: (2,2) (0,4) (1,4) (0,1) (1,2) (0,6) (2,1) (1,1) were sorted using a
stable sort by ascending order on the first key and then using the same method were
sorted again on the second key, the result would be:
8.a). (0,4) (0,1) (0,6) (1,4) (1,2) (1,1) (2,2) (2,1)
8.b). (0,1) (2,1) (1,1) (2,2) (1,2) (0,4) (1,4) (0,6)
8.c). (2,1) (1,1) (0,1) (2,2) (1,2) (1,4) (0,4) (0,6)
8.d). (0,1) (1,1) (2,1) (1,2) (2,2) (0,4) (1,4) (0,6) ***
8.e). (0,1) (0,4) (0,6) (1,1) (1,2) (1,4) (2,1) (2,2)


47. Mergesort always runs faster than bubblesort. (T/F)
false -- depends on the constants and the size of the input. Given a large enough input, mergesort will most likely run faster than bubblesort.
48. Selection sort and quicksort both fall into the same category of sorting algorithms. What is this category?
A. O(n log n) sorts
B. Divide-and-conquer sorts
C. Interchange sorts
D. Average time is quadratic
Ans:c