Heap Data Structure MCQ
This section focuses on the "Heap" in Data Structure. These Multiple Choice Questions (MCQ) should be practiced to improve the Data Structure skills required for various interviews (campus interviews, walk-in interviews, company interviews), placements, entrance exams and other competitive examinations.
1. A ________ is a special Tree-based data structure in which the tree is a complete binary tree.?
A. Graph
B. Heap
C. List
D. Stack
View Answer
Ans : B
Explanation: A Heap is a special Tree-based data structure in which the tree is a complete binary tree.
2. How many type of heap are there?
A. 2
B. 3
C. 4
D. 5
View Answer
Ans : A
Explanation: There are 2 types of heap : max-heap and min-heap.
3.In which heap the root node must be greatest among the keys present at all of it’s children?
A. min-heap
B. max-heap
C. Both A and B
D. None of the above
View Answer
Ans : B
Explanation : Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children
4.What is the complexity of adding an element to the heap?
A. O(log n)
B. O(log h)
C. O(h)
D. Both A and C
View Answer
Ans : D
Explanation : The total possible operation in re locating the new location to a new element will be equal to height of the heap.
5. Heap can be used as ________________
A. Priority queue
B. Stack
C. A decreasing order array
D. Normal Array
View Answer
Ans : A
Explanation : The property of heap that the value of root must be either greater or less than both of its children makes it work like a priority queue.
6. An array consists of n elements. We want to create a heap using the elements. The time complexity of building a heap will be in order of
A. O(n*n*logn)
B. O(n*logn)
C. O(n*n)
D. O(n *logn *logn)
View Answer
Ans : B
Explanation: The total time taken will be N times the complexity of adding a single element to the heap. And adding a single element takes logN time, so That is equal to N*logN.
7. Min heap can be used to implement selection sort.
A. True
B. False
View Answer
Ans : B
Explanation:In min heap, the insertion and deletion operation takes O(logn) time. Therefore, a selection sort with n insertions and n deletions can be implemented using a min heap in O(nlogn) operations.
8. Which one of the following array elements represents a binary min heap?
A. 12 10 8 25 14 17
B. 8 10 12 25 14 17
C. 25 17 14 12 10 8
D. 14 17 25 10 12 8
View Answer
Ans : B
Explanation : A tree is min heap when data at every node in the tree is smaller than or equal to it’s children’ s data. So, only 8 10 12 25 14 17 generates required tree.
9. Given an array of element 5, 7, 9, 1, 3, 10, 8, 4. Which of the following is the correct sequences of elements after inserting all the elements in a min-heap?
A. 1,3,4,5,7,8,9,10
B. 1,4,3,9,8,5,7,10
C. 1,3,4,5,8,7,9,10
D. 1,3,7,4,8,5,9,10
View Answer
Ans : A
Explanation : Building a min-heap the result will a sorted array so the 1, 3, 4, 5, 7, 8, 9, 10 is correct. If we change the implementation strategy 1, 4, 3, 8, 9, 5, 7, 10 is also correct. (First filling the right child rather than left child first).
10. What is the amortized cost per operation of a skew heap?
A. O(N)
B. O(N log N)
C. O(N2)
D. O(log N)
View Answer
Ans : D
Explanation : The amortized cost per operation of a skew heap is O(log N) since the worst case analysis of skew heap is O(N) and splay tree is O(M log N).
Discussion