NAT1 mark
The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node.
Suppose a Min-Heap stores 32 keys. The height of is _____________. (Answer in integer)
Numerical answer
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
NAT1 mark
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index __________
Numerical answer
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
NAT2 marks
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 __________.
Numerical answer
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
NAT2 marks
The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is _____.
Numerical answer
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
NAT2 marks
A complete binary min-heap is made by including each integer in 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 ________.
Numerical answer
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