Heap Sort Interview Question Part 2

17. The __________ data structure is a n array object that can be viewed as a nearly complete binary tree.
a. stack
b. queue
c. binary heap
d.linked list
Ans. c

18. The MAX-HEAPIFY procedure has running time
a. O(n)
b. O(n log n)
c. O(log n)
d. O(n²)
Ans. c

19. The worst case running time of MAX-HEAPIFY on a heap of size n is ______
a. O(lg n)
b. θ (lg n)
c. Ω (lg n)
d. O(n)
Ans. c

20. The worst case running time of heapsort is
a. O(n log n)
b. O(log n)
c. Θ(log n)
d. Ω(n log n)
Ans. d

21. Which of the following arrays represent descending (max) heaps?
a. [10,7,7,2,4,6]
b. [10,7,6,2,4,7]
c. [10]
d. [10,6,7,2,4,6]
Ans. c

22. Which of the following is/are incorrect?
a. The worst case complexity of Heap Sort is O(n2).
b. A heap can be easily constructed in an array so that the left and right children of a node at index k have indexes 2k and 2k+1 respectively.
c. The worst case complexity of Heap Sort is O(n log n).
d. A binary tree can be transformed into a heap by systematically moving items up in the binary tree, starting from the leaf nodes.
Ans. a

23. Consider the following statements:
(i) In a max heap, the value of each non-leaf node is strictly less than the values of its children.
(ii) A binary heap is a complete binary tree.
(iii) All complete binary trees are heaps.

Which of the above statement(s) is/are correct?
a. (i) only
b. (ii) only
c. (iii) only
d. (i) and (ii) only
Ans. b


24. Which of the following statement(s) describe properties of a Heap

(i) A heap is a special kind of binary tree, that does not leave any gap in the array implementation.
(ii) The value stored at any node is larger than the value stored in it’s children.
(iii) A heap may be easily constructed from an array. The left child of a node k has index 2k and right child has index 2k+1.
(iv) Level of all leaf nodes must be last level or last level-1.
a.(i), (ii), (iii) and (iv) only.
b.(i) and (ii) only.
c.(i) and (iii) only.
d.(i), (ii) and (iii) only.
Ans:d

25. {2,8,6,1,10,15,3,12,11} is a set of integers. If you create a maximum heap and store it in an array, what would be the final values in the array?

(a)1,2,3,6,8,10,11,12,15
(b)15,12,11,10,8,6,3,2,1
(c) 15,12,6,11,10,2,3,8,1
(d)15,12,10,11,2,6,3,1,8
Ans:d

26. Consider the following statements:
(i) In a max heap, root value is always higher than its children (if any).
(ii) A heap is fully filled from level 1 to level last –1.

Which of the above statements is/are correct?
a.only 1 b.only 2 c.both 1 and 2 d.none
Ans:c
27. The following sequence represents a max heap stored in an array: 60 40 50 35 32
30 20 34 10 25. What would be the content of the array after 3 removeMax (& reheap)
operations of a heap-sort algorithm implemented in place?
a). 35 34 30 10 32 25 20 40 50 60
b). 35 34 30 10 32 25 20 60 50 40
c). 60 50 40 35 32 30 20 34 10 25
d). 40 10 50 34 60 32 35 25 30 20
Ans:a

28. Inserting an item into a heap takes O(n2) time.(T/F)
false -- O(lg n)