Q.1 What is a priority queue?
A queue where elements are dequeued in FIFO order
A queue where elements are dequeued based on priority
A queue implemented using arrays only
A queue where elements are enqueued based on priority
Explanation - A priority queue is an abstract data type where each element has a priority. Elements with higher priority are dequeued before elements with lower priority.
Correct answer is: A queue where elements are dequeued based on priority
Q.2 Which of the following data structures is commonly used to implement a priority queue efficiently?
Stack
Heap
Linked List
Queue
Explanation - Heaps, particularly binary heaps, are commonly used to implement priority queues because they allow insertion and extraction of the maximum or minimum element in O(log n) time.
Correct answer is: Heap
Q.3 In a max-heap, which property is maintained?
Parent node is smaller than children nodes
Parent node is larger than children nodes
All nodes have the same value
Leaf nodes are always greater than root
Explanation - A max-heap ensures that the value of each parent node is greater than or equal to the values of its children nodes.
Correct answer is: Parent node is larger than children nodes
Q.4 What is the time complexity of inserting an element into a binary heap of size n?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - Insertion in a binary heap requires adding the element at the end and then performing a 'heapify up' operation, which takes O(log n) time.
Correct answer is: O(log n)
Q.5 What is the time complexity of extracting the maximum element from a max-heap?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - Extracting the maximum element involves removing the root and then performing 'heapify down' to maintain the heap property, which takes O(log n) time.
Correct answer is: O(log n)
Q.6 Which of the following is TRUE about a min-heap?
The root contains the maximum element
All leaves have the same value
The root contains the minimum element
It cannot be represented as an array
Explanation - In a min-heap, the root node always contains the smallest element, and each parent is smaller than its children.
Correct answer is: The root contains the minimum element
Q.7 How is a binary heap typically represented in memory?
Linked List
Array
Graph
Stack
Explanation - A binary heap is usually represented as an array. For a node at index i, its left child is at 2i+1 and right child at 2i+2 (0-based indexing).
Correct answer is: Array
Q.8 In a priority queue implemented using a heap, how do you increase the priority of an element?
Decrease the key and heapify down
Increase the key and heapify up
Swap with root
Remove and reinsert the element
Explanation - To increase the priority, you increase the key value and perform 'heapify up' to maintain the heap property.
Correct answer is: Increase the key and heapify up
Q.9 What is the space complexity of a binary heap with n elements?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - A binary heap stores all n elements, typically in an array, so the space complexity is O(n).
Correct answer is: O(n)
Q.10 Which operation is used to restore the heap property after deletion in a max-heap?
Heapify up
Heapify down
Insertion
Merge
Explanation - After deleting the root from a max-heap, 'heapify down' is used to move the new root to its correct position to maintain the max-heap property.
Correct answer is: Heapify down
Q.11 Which of the following operations is NOT supported efficiently by a priority queue?
Insert an element
Extract the highest priority element
Search for an arbitrary element
Peek at the highest priority element
Explanation - Priority queues are optimized for inserting, extracting, and peeking at highest-priority elements. Searching an arbitrary element is O(n).
Correct answer is: Search for an arbitrary element
Q.12 A binary heap is a complete binary tree. What does 'complete' mean here?
All levels are fully filled
All levels except possibly the last are fully filled, and last level is filled left to right
All nodes have two children
The tree has equal height on all branches
Explanation - A complete binary tree is fully filled at all levels except possibly the last, which is filled from left to right.
Correct answer is: All levels except possibly the last are fully filled, and last level is filled left to right
Q.13 Which sorting algorithm uses a priority queue (heap) to sort elements?
Quick Sort
Merge Sort
Heap Sort
Insertion Sort
Explanation - Heap Sort builds a heap from the input data and then repeatedly extracts the maximum (or minimum) to get a sorted array.
Correct answer is: Heap Sort
Q.14 If you insert n elements one by one into a binary heap, what is the total time complexity?
O(n)
O(n log n)
O(n^2)
O(log n)
Explanation - Inserting each element takes O(log n), so inserting n elements one by one takes O(n log n).
Correct answer is: O(n log n)
Q.15 Which of the following is true about a d-ary heap compared to a binary heap?
It has more children per node, reducing the height
It requires more space
It has slower insertion time
It cannot implement priority queues
Explanation - A d-ary heap has d children per node, reducing the height and potentially making some operations faster compared to a binary heap.
Correct answer is: It has more children per node, reducing the height
Q.16 What is the worst-case time complexity of building a heap from an unsorted array of size n?
O(n log n)
O(n)
O(log n)
O(n^2)
Explanation - Using the 'heapify' method from the bottom-up, building a heap from an unsorted array can be done in O(n) time.
Correct answer is: O(n)
Q.17 In a min-priority queue, which operation would you perform to get the element with the lowest key?
Extract-Min
Extract-Max
Insert
Delete
Explanation - In a min-priority queue, 'Extract-Min' removes and returns the element with the minimum key.
Correct answer is: Extract-Min
Q.18 What is the root of a max-heap called?
Leaf node
Minimum element
Maximum element
Parent node
Explanation - In a max-heap, the root node always contains the maximum element of the heap.
Correct answer is: Maximum element
Q.19 Which of the following is an advantage of using a heap over a sorted array to implement a priority queue?
Faster insertion
Faster search
Uses less memory
Allows duplicate elements
Explanation - Heaps allow O(log n) insertion, whereas maintaining a sorted array requires O(n) time for insertion.
Correct answer is: Faster insertion
Q.20 Which operation is typically used in Dijkstra's algorithm that requires a priority queue?
Heapify
Extract-Min
Insert
Delete
Explanation - Dijkstra's algorithm repeatedly extracts the vertex with the minimum tentative distance using 'Extract-Min' from a min-priority queue.
Correct answer is: Extract-Min
Q.21 In an array representation of a binary heap, what is the index of the parent of a node at index i (0-based)?
(i-1)/2
2i+1
2i+2
i/2
Explanation - In a 0-based array, the parent of a node at index i is at index floor((i-1)/2).
Correct answer is: (i-1)/2
Q.22 Which of the following statements is FALSE about heaps?
Heaps are complete binary trees
Heaps can be used for sorting
In heaps, nodes are always arranged in sorted order
Heaps support priority queue operations efficiently
Explanation - Heaps maintain heap property but not overall sorted order. Only the root is guaranteed to have the max (or min) value.
Correct answer is: In heaps, nodes are always arranged in sorted order
Q.23 What is the complexity of finding the maximum element in a min-heap?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - In a min-heap, the maximum element could be any leaf, so finding it requires scanning all n elements.
Correct answer is: O(n)
Q.24 What is the main difference between a priority queue and a regular queue?
Priority queue supports dequeue based on priority, regular queue uses FIFO
Priority queue uses arrays, regular queue uses linked lists
Priority queue cannot store duplicates, regular queue can
Priority queue is always sorted, regular queue is not
Explanation - Priority queues dequeue elements based on priority, whereas regular queues dequeue elements in first-in-first-out order.
Correct answer is: Priority queue supports dequeue based on priority, regular queue uses FIFO