Question 1 |
Let A be a priority queue for maintaining a set of elements. Suppose A is
implemented using a max-heap data structure. The operation Extract-Max(A)
extracts and deletes the maximum element from A. The operation Insert(A,key)
inserts a new element key in A. The properties of a max-heap are preserved at the
end of each of these operations.
When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?
When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?
Both Extract-Max(A) and Insert(A,key) run in O(1). | |
Both Extract-Max(A) and Insert(A,key) run in O(log(n)). | |
Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(n). | |
Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(log(n)). |
Question 1 Explanation:
Question 2 |
Which one of the following sequences when stored in an array at locations
A[1], . . . , A[10] forms a max-heap?
23, 17, 10, 6, 13, 14, 1, 5, 7, 12 | |
23, 17, 14, 7, 13, 10, 1, 5, 6, 12 | |
23, 17, 14, 6, 13, 10, 1, 5, 7, 15 | |
23, 14, 17, 1, 10, 13, 16, 12, 7, 5 |
Question 2 Explanation:
Question 3 |
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 3 Explanation:
Question 4 |
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 4 Explanation:
Question 5 |
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 5 Explanation:
There are 5 questions to complete.
Please give question no 20 first then 19.
It will be in sequence