What is the primary purpose of Heap Sort?
A) To search for an element
B) To sort an array
C) To merge two arrays
D) To partition data
Answer: B) To sort an array
What is the time complexity of Heap Sort in the worst case?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
Answer: B) O(n log n)
Which data structure is used to implement Heap Sort?
A) Stack
B) Queue
C) Heap
D) Array
Answer: C) Heap
What is the space complexity of Heap Sort?
A) O(1)
B) O(n)
C) O(n log n)
D) O(log n)
Answer: A) O(1)
How does Heap Sort differ from other sorting algorithms?
A) It is not based on comparisons.
B) It uses a divide and conquer approach.
C) It builds a heap data structure.
D) It is a stable sorting algorithm.
Answer: C) It builds a heap data structure.
What type of heap is commonly used in Heap Sort?
A) Min-Heap
B) Max-Heap
C) Binary Tree
D) Fibonacci Heap
Answer: B) Max-Heap
What is the main advantage of Heap Sort over Quick Sort?
A) It is stable.
B) It does not require additional memory.
C) It has better worst-case performance.
D) It is faster on average.
Answer: C) It has better worst-case performance.
What is the first step in the Heap Sort algorithm?
A) Sorting the array
B) Building the heap
C) Performing the merge
D) Partitioning the array
Answer: B) Building the heap
In a Max-Heap, which of the following statements is true?
A) The parent node is less than or equal to its children.
B) The parent node is greater than or equal to its children.
C) All nodes have two children.
D) It is a complete binary tree.
Answer: B) The parent node is greater than or equal to its children.
What happens during the heapify process?
A) The heap is sorted.
B) The heap property is restored.
C) The array is merged.
D) Elements are randomly shuffled.
Answer: B) The heap property is restored.
What is the effect of using a Min-Heap in Heap Sort?
A) It results in sorting in ascending order.
B) It results in sorting in descending order.
C) It makes the algorithm unstable.
D) It has no effect on the sorting order.
Answer: B) It results in sorting in descending order.
What is the time complexity of building a heap?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(n^2)
Answer: A) O(n)
Which of the following best describes the overall process of Heap Sort?
A) Build a heap, extract elements, and then sort.
B) Build a tree, perform an in-order traversal.
C) Sort by repeatedly swapping adjacent elements.
D) Merge sorted arrays.
Answer: A) Build a heap, extract elements, and then sort.
What is the maximum height of a binary heap?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: B) O(log n)
Which of the following is not a property of a heap?
A) Complete binary tree
B) Parent is greater than children in Max-Heap
C) Parent is less than children in Min-Heap
D) The height can be less than log n
Answer: D) The height can be less than log n
What will be the output of Heap Sort on the array [4, 10, 3, 5, 1]?
A) [10, 5, 4, 3, 1]
B) [1, 3, 4, 5, 10]
C) [10, 4, 5, 3, 1]
D) [1, 4, 3, 5, 10]
Answer: B) [1, 3, 4, 5, 10]
In Heap Sort, what is done after the heap is built?
A) The elements are added to the heap.
B) The largest element is extracted and placed in sorted order.
C) The array is divided into subarrays.
D) The heap is merged with another heap.
Answer: B) The largest element is extracted and placed in sorted order.
What type of sorting algorithm is Heap Sort classified as?
A) Comparison-based sorting
B) Non-comparison based sorting
C) Adaptive sorting
D) Hybrid sorting
Answer: A) Comparison-based sorting
Which step is repeated until the heap is empty in Heap Sort?
A) Merging
B) Heapifying
C) Extracting the maximum
D) Building the heap
Answer: C) Extracting the maximum
What is the purpose of the “sift down” operation in Heap Sort?
A) To build the heap
B) To restore the heap property
C) To merge two heaps
D) To sort the array
Answer: B) To restore the heap property
Which of the following statements about Heap Sort is true?
A) It is a stable sorting algorithm.
B) It is an in-place sorting algorithm.
C) It is inefficient for large datasets.
D) It can sort linked lists efficiently.
Answer: B) It is an in-place sorting algorithm.
How is the time complexity of Heap Sort affected by the size of the input?
A) It increases linearly with the size.
B) It is constant regardless of input size.
C) It increases logarithmically with the size.
D) It increases proportionally to n log n.
Answer: D) It increases proportionally to n log n.
What is the primary disadvantage of Heap Sort compared to Quick Sort?
A) It requires more space.
B) It is always slower.
C) It is not stable.
D) It cannot handle large datasets.
Answer: C) It is not stable.
Which of the following operations is not performed in Heap Sort?
A) Building the heap
B) Extracting the maximum
C) Merging two heaps
D) Restoring heap property
Answer: C) Merging two heaps
What will be the output of applying Heap Sort on the array [8, 4, 7, 3, 2]?
A) [2, 3, 4, 7, 8]
B) [8, 7, 4, 3, 2]
C) [3, 4, 7, 8, 2]
D) [2, 4, 3, 7, 8]
Answer: A) [2, 3, 4, 7, 8]
What is the initial step in the Heap Sort algorithm?
A) Extracting elements
B) Heapifying the array
C) Merging two sorted arrays
D) Finding the median
Answer: B) Heapifying the array
In a Min-Heap, which statement is true?
A) The parent node is greater than its children.
B) The parent node is less than its children.
C) It is not a complete binary tree.
D) It can have missing nodes.
Answer: B) The parent node is less than its children.
How does the performance of Heap Sort compare to Merge Sort in practice?
A) Heap Sort is generally faster.
B) Merge Sort is generally faster.
C) They perform equally well in all scenarios.
D) It depends on the specific implementation.
Answer: B) Merge Sort is generally faster.
What is the effect of using a binary heap for sorting?
A) It allows for quicker search operations.
B) It provides a method for in-place sorting.
C) It guarantees a stable sort.
D) It allows for parallel processing.
Answer: B) It provides a method for in-place sorting.
What is the process of “sifting up” in a heap?
A) Adding a new element to the heap
B) Removing the maximum element
C) Adjusting the heap after insertion
D) Sorting the elements
Answer: C) Adjusting the heap after insertion
What happens to the structure of a heap during Heap Sort?
A) It becomes unbalanced.
B) It is preserved.
C) It is destroyed.
D) It is rebuilt from scratch.
Answer: C) It is destroyed.
Which of the following sorting algorithms is not comparison-based?
A) Heap Sort
B) Quick Sort
C) Counting Sort
D) Merge Sort
Answer: C) Counting Sort
What is a key factor in determining the efficiency of Heap Sort?
A) Choice of data structure
B) Input data size
C) Memory allocation
D) Pivot selection
Answer: A) Choice of data structure
Which operation is required to convert an array into a heap?
A) Heapify
B) Partition
C) Merge
D) Sort
Answer: A) Heapify
What kind of trees are heaps?
A) Full binary trees
B) Complete binary trees
C) Balanced binary trees
D) Degenerate trees
Answer: B) Complete binary trees
How is the root node in a Max-Heap related to its children?
A) It is less than both children.
B) It is equal to one child and greater than the other.
C) It is greater than or equal to both children.
D) It has no relation.
Answer: C) It is greater than or equal to both children.
What is the effect of reducing the size of the heap during Heap Sort?
A) It improves performance.
B) It has no effect.
C) It increases complexity.
D) It helps maintain the heap property.
Answer: D) It helps maintain the heap property.
In Heap Sort, what is done after the largest element is extracted from the heap?
A) The heap is rebuilt.
B) The remaining elements are sorted.
C) The heap property is restored.
D) The sorted array is finalized.
Answer: C) The heap property is restored.
Basic Concepts
Non-Linear Data Structures MCQs
Sorting and Searching Algorithms MCQs
- Data Structures MCQs 1
- Data Structures MCQs 2
- Data Structures MCQs 3
- Data Structures MCQs 4
- Data Structures MCQs 5
- Stacks Solved MCQs
- Queues MCQs
- pointer mcqs
- Array MCQs