Q1. What is the complexity of inserting an element into the heap?
a. O(log n) & O(h)
b. O(log n)
c. O(log h)
d. O(h)
Ans: a
Explanation: Total operation in relocating to a new location will be equal to the height of the heap.
Q2. An element with the most significant key is always in which node?
a. Leaf node
b. The first node of the left subtree
c. Root node
d. The first node of the right subtree
Ans: c
Explanation: The maximum heap root node is always the most significant value in the heap data structure.
Q3. Consider a binary tree max-heap implemented using an array; which one of the following arrays represents a binary max-heap?
a. 25,12,16,13,10,8,14
b. 25,14,13,16,10,8,12
c. 25,14,16,13,10,8,12
d. 25,14,12,13,10,8,16
Ans: c
Explanation: The parent node should be greater than the children node in max-heap.
Q4.What is the context of the array after 2 delete operations? The correct option for the above operation is:
a. 14,13,12,10,8
b. 14,12,13,8,10
c. 14,13,8,12,10
d. 14,13,12,8,10
Ans: d
Explanation: In a heap tree, deletion of a node includes two operations:
- Replace the root with the last element on the previous level.
- Starting from the root, heapify the complete tree from top to bottom.
Q5. What is the complexity of finding the smallest element in a binary max-heap containing n number is :
a. O(n)
b. O(log n)
c. O(log logn)
d. O(1)
Ans: a
Explanation: The smallest element is always present at a leaf node in a max-heap. So we need to check the minimum value for all leaf nodes. The worst-case complexity will be O(n).
Q6. In a min-heap with n elements with the smallest element at the root, the 7th smallest element can be found in time. Assume that there are no duplicates in min-heap and accessing heap elements below the root is allowed.
a. (nlogn)
b. (n)
c. (log n)
d. (1).
Ans: d
Explanation: Total number of nodes in any Binary heap in the first 7 levels is at most 1+2+4+8+16+32+64, which is a constant. Therefore, we can always find the 7th smallest element in θ(1). And if Min-heap is allowed to have duplicates, then time complexity becomes θ(Log n).
Q7. Which of the following arrays represents a binary min-heap?
a. 13 10 8 25 15 17
b. 8 10 13 25 15 17
c. 25 17 15 13 10 8
d. 15 17 25 10 13 8
Ans: b
Explanation: The parent node should always be smaller than the children node in the min-heap.
Q8. Given an array of elements 5 7 9 1 3 10 8 4 . After inserting all the elements in the min-heap, which of the following is the correct sequence of elements?
a. 1 3 4 5 6 8 9 15
b. 1 4 3 9 8 5 6 15
c. 1 3 4 5 8 6 9 15
d. 1 3 6 4 8 5 9 15
Ans: a
Explanation: For min-heap sorted array will be correct. so , the answer is 1,3,4,5,6,8,9,15.
Q9. Let H be the primary min-heap consisting of n elements implemented as an array. What is the worst-case complexity of an algorithm to find the maximum element in H?
a. θ(log n)
b. θ(n)
c. θ(1)
d. θ( n log n)
Ans: b
Explanation: For finding worst-case complexity, if we use the brute force technique, it means if we traverse the tree from root to node for finding the maximum element, it will take θ(n).
Q10. Which of the following represents a binary search heap?
a. 27,13,17,14,11,9,16
b. 27,16,13,14,11,9,17
c. 27,16,14,17,11,9,13
d. 27,16,17,14,11,9,13
Ans: d
Explanation: For finding max heap, compare parent node(i) with left child node(2 * i) and right child node(2*i + 1):
In the first option, node(14) is greater than node(13), which violates the property of the max heap
In the second option, element 17 is greater than node(13), which is not satisfying the max-heap property.
In the third option, node(16), which is the parent node, is smaller than node(17), which is the child node.
Therefore, Option d is correct.
Key Takeaways
In this article, we have discussed different important MCQs on the heap and also some previously asked questions. If this helped you share it with your friends. If you want to learn more on such topics, visit coding ninjas and heap.
Check out this problem - Largest BST In Binary Tree
968+ registered