MCQ2 marks
An array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified. Which one of the following options represents the first three elements in the heapified array?
Single correct
MCQ2 marks
Consider a binary min-heap containing 105 distinct elements. Let be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of is
Single correct
MCQ1 mark
Which one of the following sequences when stored in an array at locations A[1], . . . , A[10] forms a max-heap?
Single correct
Answer key coming soon
MCQ2 marks
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 elements, which one of the following statements about the worst case running time of these two operations is TRUE?
Single correct
Answer key coming soon
MCQ1 mark
Let be a binary min-heap consisting of elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in ?
Single correct
Answer key coming soon
MCQ2 marks
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 time
IV. A binary search tree can be constructed from a max-heap in time
Which of the above statements are TRUE?
Single correct
MCQ2 marks
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 the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?
Single correct
Answer key coming soon
MCQ2 marks
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
Single correct
MCQ1 mark
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
Single correct
MCQ1 mark
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
Single correct
MCQ1 mark
A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
Single correct
MCQ2 marks
The number of elements that can be sorted in time using heap sort is
Single correct
Answer key coming soon
MCQ1 mark
A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?
Single correct
Answer key coming soon
Use ← → to move