Question 1 |
Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?
\Theta (1) | |
\Theta (\log n) | |
\Theta ( n) | |
\Theta (n \log n) |
Question 1 Explanation:
Question 2 |
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is ___________.
512 | |
511 | |
1022 | |
10 |
Question 2 Explanation:
Question 3 |
Consider the following statements:
I. The smallest element in a max-heap is always at a leaf node.
II. The second largest element in a max-heap is always a child of the root node.
III. A max-heap can be constructed from a binary search tree in \Theta (n) time.
IV. A binary search tree can be constructed from a max-heap in \Theta (n) time.
Which of the above statements is/are TRUE?
I. The smallest element in a max-heap is always at a leaf node.
II. The second largest element in a max-heap is always a child of the root node.
III. A max-heap can be constructed from a binary search tree in \Theta (n) time.
IV. A binary search tree can be constructed from a max-heap in \Theta (n) time.
Which of the above statements is/are TRUE?
I, II and III | |
I, II and IV | |
I, III and IV | |
II, III and IV |
Question 3 Explanation:
Question 4 |
Given a binary-max heap. The elements are stored in an arrays as 25,14,16,13,10,8,12. What is the content of the array after two delete operations?
14,13,8,12,10 | |
14,12,13,10,8 | |
14,13,12,8,10 | |
14,13,12,10,8 |
Question 4 Explanation:
Question 5 |
The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is _____.
7 | |
16 | |
240 | |
80 |
Question 5 Explanation:
Question 6 |
A complete binary min-heap is made by including each integer in [1,1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is_____.
.
9 | |
8 | |
1022 | |
1021 |
Question 6 Explanation:
Question 7 |
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node.Assume that the heap is implemented in an array and i refers to the i-th index of thearray.If the heap tree has depth d (number of edges on the path from the root to the farthest leaf),the n what is the time complexity to re-fix the heap efficiently after the removal of the element?
O(1) | |
O(d) but not O(1) | |
O(2^{d}) but not O(d) | |
O(d 2^{d}) but not O(2^{d}) |
Question 7 Explanation:
Question 8 |
Consider the following array of elements.
(89,19,50,17,12,15,2,5,7,11,6,9,100)
The minimum number of interchanges needed to convert it into a max-heap is
(89,19,50,17,12,15,2,5,7,11,6,9,100)
The minimum number of interchanges needed to convert it into a max-heap is
4 | |
5 | |
2 | |
3 |
Question 8 Explanation:
Question 9 |
Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is
\Omega (log n) | |
(n) | |
\Omega (n \; log n) | |
\Omega (n^{2}) |
Question 9 Explanation:
Question 10 |
Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.

Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

Now consider that a value 35 is inserted into this heap. After insertion, the new heap is
40, 30, 20, 10, 15, 16, 17, 8, 4, 35 | |
40, 35, 20, 10, 30, 16, 17, 8, 4, 15 | |
40, 30, 20, 10, 35, 16, 17, 8, 4, 15 | |
40, 35, 20, 10, 15, 16, 17, 8, 4, 30 |
Question 10 Explanation:
There are 10 questions to complete.
Please give question no 20 first then 19.
It will be in sequence