# Coalesced Hashing Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Coalesced Hashing”.

1. Which of the following hashing technique is a combination of both separate chaining and open addressing techniques?
a) Linear probing
c) Coalesced hashing
d) Double hashing

Explanation: Hashing is a searching technique, which takes constant time for operations like search, insert and delete. Coalesced hashing is one of the hashing techniques, which is a combination of both separate chaining and open addressing.

2. By using which of the following data structure, the hash sequence is implemented within the hash table in coalesced hashing?
b) Stack
c) Tree
d) Queue

Explanation: In the hash table of coalesced hashing, the hash sequence is implemented as a linked list within the hash table. The next hash position is the next available position in the linked list. It takes extra space for the list.

3. Which of the following fields are included in the hash table of coalesced hashing?
a) h(key), data
b) h(key), data, next
c) data, next
d) h(key), next

Explanation: The hash table of the coalesced hashing consists of three fields h(key), data and next. The h(key) stores all the values for a key of any particular hash function. Data field stores all the keys that need to be stored. Next points to the colliding elements.

4. In the coalesced hashing, the collided element is placed in the first empty place of the hash table.
a) True
b) False

Explanation: Coalesced hashing is a combination of both separate chaining and open addressing. If a collision occurs, then just like linear probing, it tries to find the first empty place, but from the bottom of the hash table.

5. Coalesced hashing is better than separate chaining.
a) True
b) False

Explanation: Coalesced hashing has the advantages of both separate chaining and linear probing. In coalesced hashing, the colliding elements are inserted in the hash table itself instead of creating a separate chain. Hence, it is better than separate chaining.

6. A hash table contains 10 slots and uses coalesced hashing to resolve collisions. The hash function used is key % 10. If the values 67, 23, 45, 11, 95 are inserted in the table, in what location would the key value 95 be inserted?
a) 7
b) 8
c) 9
d) 10

Explanation: In the coalescing hashing, if a collision occurs then the element is added in the empty place from the bottom of the hash table. (67 % 10) = 7, 67 will be placed at slot 7. (23 % 10) = 3, 23 will be placed at slot 3. (45 % 10) = 5, 45 will be placed at slot 5. (11 % 10) = 1, 11 will be placed at slot 1. (95 % 10) = 5, slot 5 is already full, hence 95 will be inserted in the empty place from the bottom of the hash table that is 9.

7. Which of the following best represents the time complexity for inserting an element in coalesced hashing?
a) O(n)
b) O(1)
c) O(n2)
d) O(n log n)

Explanation: The best case for inserting an element in hashing occurs when we want to insert an element at a particular position, after calculating the hash value and that position is available. Hence, inserting an element takes constant time in the best case.

8. Which among the following is the worst case time complexity for deleting an element in coalesced hashing?
a) O(n)
b) O(1)
c) O(n2)
d) O(n log n)

Explanation: In coalesced hashing, if there occurs a collision in any slot, the element is added in the empty place from the bottom and it is mapped with the previous colliding element. When we want to delete an element, the worst case occurs when we have to scan the whole table for that element. Hence, in worst case it will take O(n) time.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.