Q.1 What is the main purpose of a hash function in hashing?
To encrypt data
To compress data
To map keys to table indices
To sort data
Explanation - A hash function transforms a given key into a table index where the data is stored, allowing efficient access.
Correct answer is: To map keys to table indices
Q.2 Which of the following is a common collision resolution technique?
Merging
Rehashing
Chaining
Sorting
Explanation - Chaining handles collisions by storing multiple elements in a linked list at the same hash index.
Correct answer is: Chaining
Q.3 In open addressing, if the desired slot is already occupied, what is done?
The table is discarded
A new hash function is created
Another slot is probed
The element is dropped
Explanation - Open addressing resolves collisions by probing other slots until an empty one is found.
Correct answer is: Another slot is probed
Q.4 Which of the following is NOT an open addressing method?
Linear probing
Quadratic probing
Double hashing
Chaining
Explanation - Chaining is a separate collision resolution technique, not a type of open addressing.
Correct answer is: Chaining
Q.5 What is the load factor in hashing?
Number of keys / Size of table
Size of table / Number of keys
Hash function efficiency
Number of collisions
Explanation - Load factor measures how full a hash table is, calculated as the ratio of number of keys to table size.
Correct answer is: Number of keys / Size of table
Q.6 Which hash function is most commonly used for integers?
Division method
Multiplication method
Mid-square method
All of the above
Explanation - All listed methods are common hash functions for integers, each with pros and cons.
Correct answer is: All of the above
Q.7 In linear probing, clustering occurs because:
Slots are chosen randomly
Empty slots are scattered
Consecutive slots fill up
Keys are deleted
Explanation - Linear probing causes primary clustering since occupied slots tend to form long consecutive runs.
Correct answer is: Consecutive slots fill up
Q.8 Which method reduces primary clustering?
Linear probing
Quadratic probing
Separate chaining
Sorting
Explanation - Quadratic probing reduces clustering by probing slots at increasing intervals rather than consecutive slots.
Correct answer is: Quadratic probing
Q.9 What is double hashing?
Using two hash tables
Applying two different hash functions
Doubling table size
Hashing twice with same function
Explanation - Double hashing uses two distinct hash functions to reduce collisions and clustering.
Correct answer is: Applying two different hash functions
Q.10 The worst-case time complexity of search in hashing is:
O(1)
O(log n)
O(n)
O(n log n)
Explanation - In worst-case scenarios (many collisions), searching may require traversing all keys, leading to O(n).
Correct answer is: O(n)
Q.11 The expected time complexity of a successful search in a hash table is:
O(1)
O(log n)
O(n)
O(n log n)
Explanation - On average, a well-designed hash function provides O(1) search time.
Correct answer is: O(1)
Q.12 What happens when the load factor exceeds 1 in open addressing?
Hash table becomes empty
No slot is available
Rehashing is done
Collisions are avoided
Explanation - In open addressing, load factor must be <1, otherwise no free slot exists for new keys.
Correct answer is: No slot is available
Q.13 Which technique uses linked lists for handling collisions?
Linear probing
Quadratic probing
Separate chaining
Double hashing
Explanation - Separate chaining uses linked lists at each index to store multiple keys that hash to the same slot.
Correct answer is: Separate chaining
Q.14 The multiplication method of hashing requires:
Prime table size
A constant between 0 and 1
Division by table size
A random generator
Explanation - Multiplication method multiplies the key by a constant A (0 < A < 1) and extracts fractional part.
Correct answer is: A constant between 0 and 1
Q.15 What is rehashing?
Reapplying the same hash function
Increasing table size and re-inserting elements
Deleting all keys
Using two hash tables
Explanation - Rehashing resizes the table and reinserts existing elements to reduce load factor.
Correct answer is: Increasing table size and re-inserting elements
Q.16 Which of the following applications commonly use hashing?
Databases
Compilers
Caching
All of the above
Explanation - Hashing is widely used in databases, compilers, and caching systems for fast lookups.
Correct answer is: All of the above
Q.17 Which of the following is a disadvantage of chaining?
Slower average search
Memory overhead of linked lists
Clustering
Hash function complexity
Explanation - Chaining requires extra memory for pointers in linked lists, leading to memory overhead.
Correct answer is: Memory overhead of linked lists
Q.18 If all keys hash to the same slot, chaining results in:
O(1) search time
O(n) search time
O(log n) search time
Table overflow
Explanation - If all keys collide in one slot, chaining degenerates into a linked list with O(n) search.
Correct answer is: O(n) search time
Q.19 Which method suffers from primary clustering?
Linear probing
Quadratic probing
Double hashing
Chaining
Explanation - Linear probing suffers from primary clustering since consecutive filled slots increase collisions.
Correct answer is: Linear probing
Q.20 Which method suffers from secondary clustering?
Linear probing
Quadratic probing
Double hashing
Chaining
Explanation - Quadratic probing reduces primary clustering but still suffers from secondary clustering.
Correct answer is: Quadratic probing
Q.21 Which of the following is TRUE about perfect hashing?
No collisions occur
Every slot is filled
Keys are lost
Load factor is always >1
Explanation - Perfect hashing guarantees no collisions, usually with special construction of hash functions.
Correct answer is: No collisions occur
Q.22 What is cuckoo hashing?
Using multiple hash tables
Using linked lists
Using random numbers
Sorting keys before hashing
Explanation - Cuckoo hashing uses two or more tables and moves keys between them to resolve collisions.
Correct answer is: Using multiple hash tables
Q.23 In which case will double hashing work best?
When clustering is high
When load factor = 1
When both hash functions are poor
When keys are deleted
Explanation - Double hashing works well in reducing clustering by spreading keys more uniformly.
Correct answer is: When clustering is high
Q.24 What is the main drawback of open addressing?
Memory overhead
Pointer usage
Performance degrades at high load factor
Hash function limitation
Explanation - Open addressing performs poorly when load factor approaches 1, as probing becomes costly.
Correct answer is: Performance degrades at high load factor
Q.25 What is the advantage of chaining over open addressing?
Simpler hash function
Handles load factor >1
Avoids collisions
Faster searches always
Explanation - Chaining can handle more keys than slots since linked lists can grow, unlike open addressing.
Correct answer is: Handles load factor >1