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
b) Quadratic probing
c) Coalesced hashing
d) Double hashing
View Answer
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?
a) Linked list
b) Stack
c) Tree
d) Queue
View Answer
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
View Answer
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
View Answer
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
View Answer
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
View Answer
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)
View Answer
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)
View Answer
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.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Check Design and Analysis of Algorithms Books
- Check Computer Science Books
- Practice Programming MCQs
- Practice Data Structure MCQ
- Apply for Computer Science Internship
