Q.1 What is the main purpose of a hash function in a hash table?
To sort the data
To map keys to indices
To search sequentially
To compress data
Explanation - A hash function converts a key into an index where the corresponding value is stored in a hash table.
Correct answer is: To map keys to indices
Q.2 Which of the following is a common collision resolution technique in hashing?
Binary search
Chaining
Merge sort
Dynamic programming
Explanation - Chaining resolves collisions by storing multiple elements at the same index using a linked list or another structure.
Correct answer is: Chaining
Q.3 In open addressing, if a collision occurs, what happens next?
The hash table resizes
Another location is probed
The key is deleted
The table is sorted
Explanation - Open addressing resolves collisions by probing for the next available slot in the table.
Correct answer is: Another location is probed
Q.4 Which hash function is suitable for string keys?
Division method
Multiplication method
Folding method
All of the above
Explanation - Various methods like division, multiplication, and folding can be used to convert string keys into table indices.
Correct answer is: All of the above
Q.5 What is a primary drawback of using a poor hash function?
Faster searching
More collisions
Smaller table size
Reduced memory usage
Explanation - A poor hash function distributes keys unevenly, leading to more collisions and reduced performance.
Correct answer is: More collisions
Q.6 Which of the following is an example of a universal hashing method?
Separate chaining
Linear probing
Cuckoo hashing
Double hashing
Explanation - Double hashing uses a secondary hash function to resolve collisions, making it an example of universal hashing.
Correct answer is: Double hashing
Q.7 In a hash table with chaining, what is the average search time if there are n elements and m slots?
O(1)
O(n/m)
O(n^2)
O(log n)
Explanation - The average search time is proportional to the load factor, which is n/m, the average number of elements per slot.
Correct answer is: O(n/m)
Q.8 What does the load factor in a hash table represent?
Number of empty slots
Ratio of keys to table size
Size of the table
Number of collisions
Explanation - Load factor is defined as the ratio of the number of keys to the total number of slots in the hash table.
Correct answer is: Ratio of keys to table size
Q.9 Which of the following is true about separate chaining?
It requires additional memory for pointers
It eliminates collisions completely
It sorts elements automatically
It uses open addressing
Explanation - Separate chaining stores multiple elements at the same index using linked lists, requiring extra memory for pointers.
Correct answer is: It requires additional memory for pointers
Q.10 In linear probing, what is a major problem that can occur?
Hash function failure
Primary clustering
Memory overflow
Division by zero
Explanation - Linear probing can cause primary clustering, where consecutive slots get filled, degrading performance.
Correct answer is: Primary clustering
Q.11 Which hashing technique uses two hash functions to reduce collisions?
Separate chaining
Double hashing
Linear probing
Quadratic probing
Explanation - Double hashing uses a second hash function to calculate the next probe location, reducing clustering.
Correct answer is: Double hashing
Q.12 What is the worst-case search time in a hash table with chaining?
O(1)
O(n)
O(log n)
O(n^2)
Explanation - In the worst case, all elements may be in the same chain, leading to a linear search of O(n).
Correct answer is: O(n)
Q.13 Which of the following is NOT a property of a good hash function?
Deterministic
Uniform distribution
Minimizes collisions
Always returns zero
Explanation - A good hash function should distribute keys uniformly, not always return the same value.
Correct answer is: Always returns zero
Q.14 Which probing technique avoids primary clustering but may suffer secondary clustering?
Linear probing
Quadratic probing
Separate chaining
Direct addressing
Explanation - Quadratic probing spreads out the probe sequence to reduce primary clustering but may still have secondary clustering.
Correct answer is: Quadratic probing
Q.15 In a hash table of size 10, what is the index for key 37 using division method?
7
3
0
5
Explanation - Using division method, index = key % table_size = 37 % 10 = 7.
Correct answer is: 7
Q.16 What is cuckoo hashing?
A method using multiple hash tables
A linked list based method
A sorting algorithm
A dynamic array technique
Explanation - Cuckoo hashing uses two hash tables and two hash functions to resolve collisions efficiently.
Correct answer is: A method using multiple hash tables
Q.17 Which of the following is true about perfect hashing?
There are no collisions
It always uses open addressing
Load factor > 1
Requires dynamic resizing
Explanation - Perfect hashing ensures that each key maps to a unique slot, eliminating collisions.
Correct answer is: There are no collisions
Q.18 What is the primary advantage of hash tables over arrays for searching?
Faster average search
Lower memory usage
Easier sorting
Supports recursion
Explanation - Hash tables provide near O(1) average search time compared to O(n) in unsorted arrays.
Correct answer is: Faster average search
Q.19 In double hashing, if h1(key) = 5 and h2(key) = 3, what is the second probe index?
8
1
0
5
Explanation - The second probe index = (h1(key) + 1 * h2(key)) % table_size. Assuming table_size > 8, index = 5 + 3 = 8.
Correct answer is: 8
Q.20 Which type of data is unsuitable for direct addressing?
Small integer keys
Large integer keys
Sequential keys
Boolean keys
Explanation - Direct addressing requires a table size equal to the universe of keys, which is impractical for large keys.
Correct answer is: Large integer keys
Q.21 What happens to a hash table when load factor exceeds a threshold?
Table is resized or rehashed
All keys are deleted
Keys are sorted
Nothing
Explanation - When load factor exceeds a threshold, the table is typically resized and keys are rehashed to maintain efficiency.
Correct answer is: Table is resized or rehashed
Q.22 Which of these is a characteristic of a static hash table?
Size is fixed
Size changes dynamically
Uses linked lists only
Always sorted
Explanation - A static hash table has a fixed size, whereas a dynamic hash table can grow or shrink.
Correct answer is: Size is fixed
Q.23 Which operation is generally the slowest in a hash table using separate chaining?
Insertion
Deletion
Search
All are same
Explanation - Search may require traversing the linked list in a slot, which could take O(n) in the worst case.
Correct answer is: Search
Q.24 What is secondary clustering in hashing?
Keys with same initial hash follow same probe sequence
All keys collide at index 0
Keys are sorted in chains
Keys are deleted randomly
Explanation - Secondary clustering occurs when keys with the same initial hash value follow identical probe sequences, even in quadratic probing.
Correct answer is: Keys with same initial hash follow same probe sequence
Q.25 Which of the following ensures O(1) worst-case search time?
Perfect hashing
Separate chaining
Linear probing
Quadratic probing
Explanation - Perfect hashing guarantees no collisions, providing constant-time worst-case search.
Correct answer is: Perfect hashing