This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Heap Sort”.
1. On which algorithm is heap sort based on?
a) Fibonacci heap
b) Binary tree
c) Priority queue
d) FIFO
View Answer
Explanation: Heap sort is based on the algorithm of priority queue and it gives the best sorting time.
2. In what time can a binary heap be built?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
View Answer
Explanation: The basic strategy is to build a binary heap of N elements which takes O(N) time.
3. Heap sort is faster than Shell sort.
a) true
b) false
View Answer
Explanation: Heap sort is slower than Shell sort because Shell sort uses Sedgewick’s increment sequence.
4. Consider the following heap after buildheap phase. What will be its corresponding array?
a) 26,53,41,97,58,59,31
b) 26,31,41,53,58,59,97
c) 26,41,53,97,31,58,59
d) 97,53,59,26,41,58,31
View Answer
Explanation: Constructing a max heap using the elements 97,53,59,26,41,58,31 will cause the heap to look like that.
5. In what position does the array for heap sort contains data?
a) 0
b) 1
c) -1
d) anywhere in the array
View Answer
Explanation: The array for heap sort contains data at position 0 whereas for a binary heap, array begins at 1. This is the reason for its complexity.
6. In heap sort, after deleting the last minimum element, the array will contain elements in?
a) increasing sorting order
b) decreasing sorting order
c) tree inorder
d) tree preorder
View Answer
Explanation: By logic, after deleting minimum element, the heap will contain elements in decreasing sorting order. We can change this by altering the ordering property.
7. What is the typical running time of a heap sort algorithm?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
View Answer
Explanation: The total running time of a heap sort algorithm is mathematically found to be O(N log N).
8. How many arrays are required to perform deletion operation in a heap?
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: To perform deletion operation in a heap, we require 2 arrays and that occupies extra memory space and hence increase in running time.
9. What is the time taken to perform a delete min operation?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
View Answer
Explanation: The time taken to perform a deletion of a minimum element is mathematically found to be O( log N).
10. Heap sort is an extremely stable algorithm.
a) true
b) false
View Answer
Explanation: Heap sort uses fewer comparisons than other sorting algorithms and hence it is an extremely stable algorithm.
11. What is the average number of comparisons used in a heap sort algorithm?
a) N log N-O(N)
b) O(N log N)-O(N)
c) O(N log N)-1
d) 2N log N + O(N)
View Answer
Explanation: The average number of comparisons in a heapsort algorithm is mathematically found to be 2N log N + O(N).
12. What is the time taken to copy elements to and from two arrays created for deletion?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
View Answer
Explanation: The time taken to copy elements to and from the main array and extra array is found to be O(N).
13. What is the average number of comparisons used to heap sort a random permutation of N distinct items?
a) 2N log N-O(N)
b) 2N log N-O(N log N)
c) 2N log N-O(N log log N)
d) 2N log N-O(log N)
View Answer
Explanation: According to a theorem, the average number of comparisons used to heap sort a random permutation of N distinct items is found to be 2N log N-O(N log log N).
More MCQs on Heap Sort:
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Check Design and Analysis of Algorithms Books
- Practice Data Structure MCQ
- Practice Computer Science MCQs
- Check Computer Science Books
- Practice Programming MCQs