Applications of heaps (priority queues, heap sort) MCQs

By: Prof. Dr. Fazal Rehman | Last updated: September 20, 2024

Question: Which data structure is primarily used to implement a priority queue?

A) Array
B) Linked List
C) Stack
D) Heap
Answer: D) Heap
Question: What is the time complexity of inserting an element into a priority queue implemented using a heap of size
𝑛
n?

A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: B) O(log n)
Question: Which sorting algorithm uses a heap as its data structure?

A) Merge sort
B) Quick sort
C) Bubble sort
D) Heap sort
Answer: D) Heap sort
Question: What is the worst-case time complexity of heap sort for sorting
𝑛
n elements?

A) O(n)
B) O(log n)
C) O(n log n)
D) O(n^2)
Answer: C) O(n log n)
Question: In heap sort, what is the process used to build a max-heap from an array?

A) Bubble up
B) Bubble down
C) Heapify
D) Merge
Answer: C) Heapify
Question: Which of the following is a primary advantage of using a priority queue?

A) Faster deletion operations
B) Guaranteed constant-time access
C) Efficient retrieval of the maximum element
D) Ability to store elements in any order
Answer: C) Efficient retrieval of the maximum element
Question: Which operation is typically used to remove the maximum element from a max-heap in a priority queue?

A) Extract min
B) Extract max
C) Delete
D) Remove
Answer: B) Extract max
Question: In a min-heap-based priority queue, what operation retrieves the minimum element without removing it?

A) Peek
B) Poll
C) Pop
D) Remove
Answer: A) Peek
Question: Which sorting algorithm exhibits a stable behavior (preserves the relative order of equal elements)?

A) Quick sort
B) Heap sort
C) Merge sort
D) Bubble sort
Answer: C) Merge sort
Question: Which property of heap sort makes it suitable for applications requiring in-place sorting?

A) Stable sorting
B) Adaptive sorting
C) Recursive sorting
D) In-place sorting
Answer: D) In-place sorting
Question: Which operation is used to convert an unordered array into a heap in heap sort?

A) Insertion
B) Deletion
C) Heapify
D) Merge
Answer: C) Heapify
Question: What is the main disadvantage of using a heap-based priority queue compared to other data structures?

A) Slower insertion operations
B) Limited to fixed-size elements
C) Unstable retrieval of maximum element
D) Higher memory usage
Answer: D) Higher memory usage
Question: Which application often requires efficient priority queue operations?

A) Sorting names alphabetically
B) Implementing a scheduler for tasks
C) Counting occurrences of elements
D) Finding shortest paths in a graph
Answer: B) Implementing a scheduler for tasks
Question: In a priority queue implemented using a min-heap, what is the root element?

A) Smallest element
B) Largest element
C) Median element
D) Arbitrary element
Answer: A) Smallest element
Question: Which data structure does not use a heap for its implementation?

A) Binary Search Tree
B) AVL Tree
C) Red-Black Tree
D) Heap Tree
Answer: A) Binary Search Tree
Question: What is the primary benefit of using heap sort over other sorting algorithms?

A) Stable sorting
B) Adaptive sorting
C) Worst-case time complexity
D) Ease of implementation
Answer: C) Worst-case time complexity
Question: Which operation in a priority queue is similar to removing the root in a heap?

A) Peek
B) Poll
C) Push
D) Pop
Answer: B) Poll
Question: Which property must be maintained during the heapify process in heap sort?

A) Parent node should be greater than both child nodes.
B) Parent node should be less than both child nodes.
C) Parent node should be equal to both child nodes.
D) Parent node should be greater than or equal to both child nodes.
Answer: A) Parent node should be greater than both child nodes.
Question: Which operation is not typically supported directly by a heap-based priority queue?

A) Insertion
B) Deletion of arbitrary elements
C) Merge of two priority queues
D) Extracting the minimum element
Answer: B) Deletion of arbitrary elements
Question: Which sorting algorithm is generally preferred when stable sorting is not a requirement?

A) Merge sort
B) Heap sort
C) Bubble sort
D) Insertion sort
Answer: B) Heap sort

 

Data Structures MCQs

Basic Concepts

1. Introduction to Data Structures
   • Abstract Data Types (ADT) MCQs
2. Complexity Analysis MCQs
   • Time complexity MCQs
   • Space complexity MCQs
   • Big O, Big Ω, Big Θ notations MCQs

Linear Data Structures MCQs

1. Arrays MCQs
   • One-dimensional arrays MCQs
   • Multi-dimensional arrays MCQs
   • Operations: traversal, insertion, deletion MCQs
2. Linked Lists MCQs
   • Singly linked list MCQs
   • Doubly linked list MCQs
   • Circular linked list MCQs
3. Stacks MCQs
   • Stack operations (push, pop, peek) MCQs
   • Applications of stacks (expression evaluation, recursion) MCQs
4. Queues MCQs
   • Queue operations (enqueue, dequeue, front, rear) MCQs
   • Types: Simple queue, circular queue, priority queue, deque MCQs

Non-Linear Data Structures MCQs

1. Trees MCQs
   • Binary trees MCQs
   • Binary Search Trees (BST) MCQs
   • AVL Trees MCQs
   • B-trees and B+ trees MCQs
   • Tree traversal methods (in-order, pre-order, post-order) MCQs
2. Heaps MCQs
   • Min-heap MCQs
   • Max-heap MCQs
   • Heap operations (insertion, deletion, heapify) MCQs
   • Applications of heaps (priority queues, heap sort) MCQs
3. Graphs MCQs
   • Graph representation (adjacency matrix, adjacency list) MCQs
   • Graph traversal algorithms (DFS, BFS) MCQs
   • Shortest path algorithms (Dijkstra’s, Bellman-Ford) MCQs
   • Minimum Spanning Tree (Kruskal’s, Prim’s) MCQs

Hashing MCQs MCQs

1. Hash Tables
   • Hash functions MCQs
   • Collision resolution techniques (chaining, open addressing) MCQs
   • Applications of hashing MCQs

Sorting and Searching Algorithms MCQs 

1. Sorting Algorithms MCQs
   • Bubble sort MCQs
   • Selection sort MCQs
   • Insertion sort MCQs
   • Merge sort MCQs
   • Quick sort MCQs
   • Heap sort MCQs
2. Searching Algorithms MCQs
   • Linear search MCQs
   • Binary search MCQs
   • Interpolation search MCQs

Miscellaneous

1. Memory Management in data structures MCQs
   • Dynamic memory allocation MCQs
   • Garbage collection MCQs
2. String Manipulation Algorithms MCQs
   • Pattern matching (KMP, Rabin-Karp) MCQs
   • String hashing MCQs

1. Data Structures MCQs 1
2. Data Structures MCQs 2
3. Data Structures MCQs 3
4. Data Structures MCQs 4
5. Data Structures MCQs 5
6. Stacks Solved MCQs
7. Queues MCQs
8. pointer mcqs
9. Array MCQs