1In a Max-Heap, what is the relationship between the value of a node and its children?
A.The node is greater than or equal to its children
B.There is no specific relationship
C.The node is equal to its children
D.The node is less than or equal to its children
Correct Answer: The node is greater than or equal to its children
Explanation:
In a Max-Heap, the key present at the root node must be greatest among the keys present at all of its children. The same property must be recursively true for all sub-trees.
Incorrect! Try again.
2Which data structure is commonly used to implement a Heap efficiently?
A.Stack
B.Linked List
C.Array
D.Queue
Correct Answer: Array
Explanation:
Heaps are usually implemented using arrays because they are complete binary trees. The parent-child relationship can be easily calculated using indices.
Incorrect! Try again.
3If a node is stored at index 'i' in an array representation of a binary heap (0-indexed), what is the index of its left child?
A.2i
B.2i + 1
C.i / 2
D.2i + 2
Correct Answer: 2i + 1
Explanation:
In a 0-indexed array representing a binary heap, the left child of a node at index 'i' is located at index '2i + 1'.
Incorrect! Try again.
4What is the time complexity to insert a new element into a binary heap of size N?
A.O(N)
B.O(log N)
C.O(N log N)
D.O(1)
Correct Answer: O(log N)
Explanation:
Insertion involves adding the element to the end and then 'bubbling up' (percolating) to restore the heap property, which takes time proportional to the height of the tree, O(log N).
Incorrect! Try again.
5What is the time complexity to find the maximum element in a Max-Heap?
A.O(N)
B.O(log N)
C.O(1)
D.O(N log N)
Correct Answer: O(1)
Explanation:
In a Max-Heap, the maximum element is always at the root, which can be accessed in constant time O(1).
Incorrect! Try again.
6Which operation is required to restore the heap property after extracting the root element?
A.Sorting
B.Linear Search
C.Bubble Up
D.Heapify (Percolate Down)
Correct Answer: Heapify (Percolate Down)
Explanation:
After removing the root, the last element is moved to the root, and the 'Heapify' or 'Percolate Down' process is used to move it down to its correct position.
Incorrect! Try again.
7A binary heap is strictly a __.
A.Complete Binary Tree
B.Binary Search Tree
C.AVL Tree
D.Full Binary Tree
Correct Answer: Complete Binary Tree
Explanation:
A binary heap must be a complete binary tree, meaning all levels are fully filled except possibly the last, which is filled from left to right.
Incorrect! Try again.
8What is the parent index of a node at index 'i' in a 0-indexed array heap?
A.(i + 1) / 2
B.i / 2
C.2i
D.(i - 1) / 2
Correct Answer: (i - 1) / 2
Explanation:
The parent of a node at index 'i' is located at floor((i - 1) / 2).
Incorrect! Try again.
9What is the worst-case time complexity of HeapSort?
A.O(log N)
B.O(N log N)
C.O(N^2)
D.O(N)
Correct Answer: O(N log N)
Explanation:
HeapSort involves building the heap (O(N)) and then extracting elements N times (each taking O(log N)), resulting in a total complexity of O(N log N).
Incorrect! Try again.
10HeapSort is generally considered stable. True or False?
A.True
B.Depends on implementation
C.Only for Min-Heap
D.False
Correct Answer: False
Explanation:
HeapSort is not a stable sort because the structure of the heap changes the relative order of equal elements during the heapify process.
Incorrect! Try again.
11Which of the following scenarios is the best use case for a Heap?
A.Finding the median in O(1)
B.Storing sorted data sequentially
C.Searching for an arbitrary element
D.Implementing a Priority Queue
Correct Answer: Implementing a Priority Queue
Explanation:
Heaps are ideal for Priority Queues because they efficiently support Insert and Extract-Min/Max operations.
Incorrect! Try again.
12What is the time complexity to build a heap from an unsorted array of N elements?
A.O(N log N)
B.O(N)
C.O(log N)
D.O(N^2)
Correct Answer: O(N)
Explanation:
While naive insertion takes O(N log N), the optimized 'build heap' algorithm (starting from the last non-leaf node) takes linear time O(N).
Incorrect! Try again.
13In HeapSort, where is the sorted array constructed?
A.In a new array
B.In-place within the same array
C.In a binary search tree
D.In a linked list
Correct Answer: In-place within the same array
Explanation:
HeapSort is an in-place algorithm. It swaps the root with the last element and reduces the heap size effectively building the sorted sequence at the end of the array.
Incorrect! Try again.
14What is the height of a binary heap with N nodes?
A.O(N)
B.O(N^2)
C.O(log N)
D.O(1)
Correct Answer: O(log N)
Explanation:
Since a binary heap is a complete binary tree, its height is bounded by log2(N).
Incorrect! Try again.
15Which hashing technique allows multiple keys to be stored in the same slot using a data structure like a linked list?
A.Linear Probing
B.Open Addressing
C.Separate Chaining
D.Double Hashing
Correct Answer: Separate Chaining
Explanation:
Separate Chaining uses a linked list (or another structure) at each bucket to store all keys that hash to the same index.
Incorrect! Try again.
16What is a 'Collision' in hashing?
A.When two different keys hash to the same index
B.When the hash table is full
C.When the load factor exceeds 1
D.When a key cannot be hashed
Correct Answer: When two different keys hash to the same index
Explanation:
A collision occurs when a hash function maps two distinct keys to the same location (index) in the hash table.
Incorrect! Try again.
17In the context of hash tables, what is the Load Factor (alpha)?
A.Time taken to hash
B.Number of buckets / Number of elements
C.Number of elements / Number of buckets
D.Size of the key
Correct Answer: Number of elements / Number of buckets
Explanation:
The load factor is the ratio of the number of elements stored (n) to the total number of buckets/slots (m) in the hash table.
Incorrect! Try again.
18Which simple hash function is defined as h(k) = k mod m?
A.Folding Method
B.Division Method
C.Multiplication Method
D.Mid-Square Method
Correct Answer: Division Method
Explanation:
The division method maps a key 'k' into one of 'm' slots by taking the remainder of k divided by m.
Incorrect! Try again.
19In Open Addressing, where are colliding elements stored?
A.In the same hash table at a different slot
B.In a separate linked list
C.In a secondary hash table
D.They are discarded
Correct Answer: In the same hash table at a different slot
Explanation:
Open addressing (Closed Hashing) stores all elements within the hash table array itself, searching for the next available slot upon collision.
Incorrect! Try again.
20What is the probe sequence for Linear Probing?
A.(h(k) + i * h2(k)) % m
B.(h(k) + i^2) % m
C.h(k) % m
D.(h(k) + i) % m
Correct Answer: (h(k) + i) % m
Explanation:
Linear probing looks for the next available slot sequentially: index, index+1, index+2, etc., wrapping around modulo m.
Incorrect! Try again.
21What is the main disadvantage of Linear Probing?
A.Complex implementation
B.Primary Clustering
C.Requires extra memory
D.Secondary Clustering
Correct Answer: Primary Clustering
Explanation:
Linear probing suffers from primary clustering, where long runs of occupied slots build up, increasing the average search time.
Incorrect! Try again.
22Quadratic Probing reduces primary clustering but suffers from which issue?
A.Secondary Clustering
B.Primary Clustering
C.Stack overflow
D.Infinite loops
Correct Answer: Secondary Clustering
Explanation:
Quadratic probing resolves primary clustering but causes secondary clustering, where keys hashing to the same initial position follow the exact same probe sequence.
Incorrect! Try again.
23Which collision resolution technique uses a second hash function?
A.Separate Chaining
B.Linear Probing
C.Quadratic Probing
D.Double Hashing
Correct Answer: Double Hashing
Explanation:
Double hashing uses a second hash function h2(k) to determine the step size when a collision occurs: (h1(k) + i * h2(k)) % m.
Incorrect! Try again.
24In Double Hashing, what property must the second hash function h2(k) have?
A.It must return a string
B.It should never evaluate to 0
C.It must result in 0
D.It must be equal to h1(k)
Correct Answer: It should never evaluate to 0
Explanation:
If h2(k) evaluates to 0, the probe sequence will not advance (step size 0), causing an infinite loop on the same index.
Incorrect! Try again.
25Which hashing method allows the load factor to exceed 1?
A.Separate Chaining
B.Linear Probing
C.Open Addressing
D.Quadratic Probing
Correct Answer: Separate Chaining
Explanation:
In Separate Chaining, because elements are stored in external lists, the number of elements can exceed the number of table slots.
Incorrect! Try again.
26What is the worst-case search time in a Hash Table using Separate Chaining?
A.O(N^2)
B.O(log N)
C.O(N)
D.O(1)
Correct Answer: O(N)
Explanation:
In the worst case, all keys hash to the same slot, creating a linked list of length N. Searching becomes O(N).
Incorrect! Try again.
27What is the average-case search time for a well-implemented hash table?
A.O(N log N)
B.O(N)
C.O(log N)
D.O(1)
Correct Answer: O(1)
Explanation:
With a good hash function and reasonable load factor, the average search time is constant, O(1).
Incorrect! Try again.
28What technique is used to handle deletions in Open Addressing tables?
A.Physical deletion
B.Lazy deletion (Tombstones)
C.Rehashing immediately
D.Shifting elements
Correct Answer: Lazy deletion (Tombstones)
Explanation:
Simply removing an element breaks the probe chain. Usually, deleted slots are marked with a specific flag (Tombstone) to allow searches to continue past them.
Incorrect! Try again.
29When choosing a table size 'm' for the Division Method (h(k) = k % m), 'm' should preferably be:
A.A multiple of 10
B.An even number
C.A prime number
D.A power of 2
Correct Answer: A prime number
Explanation:
Using a prime number helps distribute keys more uniformly and reduces clustering, especially if keys have patterns (like arithmetic progressions).
Incorrect! Try again.
30In the Mid-Square method of hashing, which part of the squared key is usually taken as the hash?
A.The first digits
B.The last digits
C.The sum of all digits
D.The middle digits
Correct Answer: The middle digits
Explanation:
The middle digits of the squared value depend on all bits of the original key, providing a good distribution.
Incorrect! Try again.
31What happens when the load factor of a hash table becomes too high?
A.Nothing changes
B.Collisions increase and performance degrades
C.Performance improves
D.The table automatically deletes elements
Correct Answer: Collisions increase and performance degrades
Explanation:
A high load factor means the table is filling up, leading to more collisions and longer probe sequences or longer chains, slowing down operations.
Incorrect! Try again.
32The process of increasing the size of a hash table and re-inserting all existing elements is called:
A.Rehashing
B.Resizing
C.Refactoring
D.Restructuring
Correct Answer: Rehashing
Explanation:
Rehashing involves creating a larger table and calculating new hash positions for all existing elements to maintain the load factor.
Incorrect! Try again.
33Which probing method uses the formula H(k, i) = (h(k) + c1i + c2i^2) % m?
A.Quadratic Probing
B.Double Hashing
C.Random Probing
D.Linear Probing
Correct Answer: Quadratic Probing
Explanation:
This formula represents Quadratic Probing, where the step size increases quadratically.
Incorrect! Try again.
34What is 'Perfect Hashing'?
A.A technique with no collisions
B.A technique for dynamic datasets
C.A hashing technique with O(N) access
D.A technique that uses minimal memory
Correct Answer: A technique with no collisions
Explanation:
Perfect hashing maps a static set of keys to a hash table with no collisions.
Incorrect! Try again.
35If we have a Max-Heap array: [100, 80, 90, 40, 50, 70], what is the left child of 80?
A.40
B.70
C.50
D.90
Correct Answer: 40
Explanation:
80 is at index 1. Left child is at 2(1)+1 = 3. The element at index 3 is 40.
Incorrect! Try again.
36In a Min-Heap, the root node always contains:
A.The median value
B.A random value
C.The minimum value
D.The maximum value
Correct Answer: The minimum value
Explanation:
By definition of a Min-Heap, the root is the smallest element.
Incorrect! Try again.
37Which of the following is NOT a requirement for a good hash function?
A.It should minimize collisions
B.It must be cryptographically secure
C.It should distribute keys uniformly
D.It should be easy to compute
Correct Answer: It must be cryptographically secure
Explanation:
For standard data structures, cryptographic security is not required; speed and uniform distribution are the primary concerns.
Incorrect! Try again.
38In Open Hashing (Separate Chaining), if the table size is 10 and we insert 20 elements, the load factor is:
A.10
B.2.0
C.0.5
D.20
Correct Answer: 2.0
Explanation:
Load Factor = Elements / Slots = 20 / 10 = 2.0.
Incorrect! Try again.
39What is the relationship between Open Hashing and Closed Addressing?
A.Open Hashing is Separate Chaining; Closed Addressing is Open Addressing
B.They are synonyms
C.They are unrelated
D.Open Hashing is Open Addressing; Closed Addressing is Separate Chaining
Correct Answer: Open Hashing is Separate Chaining; Closed Addressing is Open Addressing
Explanation:
Open Hashing refers to chaining (elements stored outside the table slots). Closed Hashing refers to Open Addressing (elements stored inside table slots).
Incorrect! Try again.
40In Linear Probing, search for a key stops when:
A.We have searched the entire table
B.We encounter an empty slot
C.All of the above
D.We find the key
Correct Answer: All of the above
Explanation:
Search stops on finding the key, hitting an empty slot (implying key not found), or traversing the whole table.
Incorrect! Try again.
41Which operation is typically faster in a Hash Table compared to a Binary Search Tree (BST)?
A.Finding the minimum element
B.Finding the maximum element
C.In-order traversal
D.Exact match search
Correct Answer: Exact match search
Explanation:
Exact match search is O(1) on average in a Hash Table, while it is O(log N) in a balanced BST.
Incorrect! Try again.
42When performing HeapSort on an array in ascending order, which type of heap is typically used?
A.Min-Heap
B.Fibonacci Heap
C.Binomial Heap
D.Max-Heap
Correct Answer: Max-Heap
Explanation:
A Max-Heap is used. The largest element (root) is swapped to the end of the array, and the heap size is reduced.
Incorrect! Try again.
43In the folding method of hashing, the key is:
A.Partitioned into parts and added together
B.Divided by a prime
C.Squared
D.Multiplied by a constant
Correct Answer: Partitioned into parts and added together
Explanation:
The folding method involves splitting the key into parts and adding them (sometimes with shifting) to generate the hash.
Incorrect! Try again.
44What is the primary benefit of Double Hashing over Quadratic Probing?
A.Simpler implementation
B.Guaranteed to find an empty slot in 1 step
C.No secondary clustering
D.Requires less memory
Correct Answer: No secondary clustering
Explanation:
Double hashing uses a second hash function dependent on the key, so keys mapping to the same initial slot have different probe sequences, eliminating secondary clustering.
Incorrect! Try again.
45If a hash table using Open Addressing is full, what is the time complexity to insert a new item?
A.Infinite loop (until resized or error)
B.O(log N)
C.O(1)
D.O(N)
Correct Answer: Infinite loop (until resized or error)
Explanation:
If the table is completely full in open addressing, the probe sequence will cycle indefinitely (or stop after checking N slots), requiring a resize or error handling.
Incorrect! Try again.
46For string keys, a common hashing approach involves:
A.Adding ASCII values
B.Taking the first character only
C.Using a polynomial rolling hash
D.Multiplying the length by the first character
Correct Answer: Using a polynomial rolling hash
Explanation:
Simple addition causes many collisions (anagrams). A polynomial rolling hash (using a multiplier like 31 or 33) preserves order information.
Incorrect! Try again.
47Which heap operation decreases the value of a key and restores the heap property?
A.Increase-Key
B.Decrease-Key
C.Delete
D.Extract-Min
Correct Answer: Decrease-Key
Explanation:
Decrease-Key updates a value to be smaller. In a Min-Heap, this might require bubbling up; in a Max-Heap, it might require percolating down.
Incorrect! Try again.
48In a hash table with size m = 10 and hash function h(k) = k % 10, where does key 23 go?
A.5
B.0
C.2
D.3
Correct Answer: 3
Explanation:
23 % 10 = 3.
Incorrect! Try again.
49Using Linear Probing with h(k) = k % 10, if slots 2 and 3 are occupied, where does key 12 go?
A.2
B.4
C.5
D.3
Correct Answer: 4
Explanation:
12 % 10 = 2. Slot 2 is full -> try 3. Slot 3 is full -> try 4. 4 is the insertion point.
Incorrect! Try again.
50What is the space complexity of a binary heap?
A.O(N)
B.O(N log N)
C.O(1)
D.O(N^2)
Correct Answer: O(N)
Explanation:
A binary heap stores N elements typically in an array, requiring linear space O(N).