Heap operations (insertion, deletion, heapify) MCQs

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

Question: Which data structure is typically used to implement a heap?

A) Array
B) Linked List
C) Stack
D) Queue
Answer: A) Array
Question: What is the time complexity of inserting an element into 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: In a max-heap, which element is at the root?

A) Largest element
B) Smallest element
C) Median element
D) None of the above
Answer: A) Largest element
Question: Which operation is used to maintain the heap property after an element is deleted from the heap?

A) Heapify
B) Merge
C) Sort
D) Search
Answer: A) Heapify
Question: Which of the following is true about a min-heap?

A) The smallest element is at the root.
B) The largest element is at the root.
C) It is not possible to have duplicate elements.
D) Elements are not stored in any specific order.
Answer: A) The smallest element is at the root.
Question: When inserting an element into a heap, which operation ensures that the heap property is maintained?

A) Bubble up
B) Bubble down
C) Swap with parent
D) Swap with child
Answer: A) Bubble up
Question: What is the worst-case time complexity of deleting the root element from 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 type of heap is more commonly used in priority queue implementations?

A) Max-heap
B) Min-heap
C) Binary search heap
D) Fibonacci heap
Answer: B) Min-heap
Question: In a max-heap, which child of a node at index
𝑖
i is the larger one?

A) Left child (2*i)
B) Right child (2*i + 1)
C) Either child, as both are equal
D) Neither child, as both are smaller
Answer: A) Left child (2*i)
Question: What is the primary advantage of using a heap over a sorted array for implementing priority queues?

A) Faster search operations
B) Guaranteed constant-time insertion
C) Efficient removal of the maximum element
D) Ability to store duplicate elements
Answer: C) Efficient removal of the maximum element
Question: Which operation is used to convert an unordered array into a heap?

A) Insertion
B) Deletion
C) Heapify
D) Merge
Answer: C) Heapify
Question: What happens to the heap structure if an element is inserted into an already max-heap?

A) It remains unchanged.
B) It becomes a min-heap.
C) It gets sorted.
D) It might violate the heap property.
Answer: D) It might violate the heap property.
Question: Which condition is necessary to maintain during the heapify process?

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: What is the time complexity of building a heap from an array of
𝑛
n elements?

A) O(n)
B) O(log n)
C) O(n log n)
D) O(n^2)
Answer: A) O(n)
Question: Which operation is used to remove an arbitrary element from a heap?

A) Bubble up
B) Bubble down
C) Heapify
D) Extract min/max
Answer: C) Heapify
Question: In a max-heap, what does the delete operation typically involve?

A) Deleting the root and replacing it with the smallest element
B) Deleting the root and replacing it with the largest element
C) Deleting the smallest element in the heap
D) Deleting the largest element in the heap
Answer: B) Deleting the root and replacing it with the largest element
Question: Which data structure can efficiently implement both insertion and deletion operations in a heap?

A) Queue
B) Stack
C) Binary Tree
D) Priority Queue
Answer: D) Priority Queue
Question: What is the index of the parent node of any node
𝑖
i in a heap?

A)
𝑖
/
2
i/2
B)
2
∗
𝑖
2∗i
C)
𝑖
−
1
i−1
D)
𝑖
+
1
i+1
Answer: A)
𝑖
/
2
i/2
Question: Which property ensures that a heap is a complete binary tree?

A) All levels are completely filled except possibly the last level, which is filled from left to right.
B) All levels are completely filled, regardless of the order.
C) All nodes have exactly two children.
D) All nodes are connected directly to the root.
Answer: A) All levels are completely filled except possibly the last level, which is filled from left to right.
Question: When deleting an element from a heap, what is the process used to maintain the heap property?

A) Bubble up
B) Bubble down
C) Swap with parent
D) Swap with child
Answer: B) Bubble down

 

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