Hash Tables Chaining with List Heads Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Hash Tables Chaining with List Heads”.

1. Which of the following helps keys to be mapped into addresses?
a) hash function
b) separate chaining
c) open addressing
d) chaining using a linked list
View Answer

Answer: a
Explanation: Hash table is an example of a data structure that is built for fast access of elements. Hash functions are used to determine the index of any input record in a hash table.
advertisement

2. What is the advantage of the hash table over a linked list?
a) faster access of data
b) easy to implement
c) very efficient for less number of entries
d) exhibit good locality of reference
View Answer

Answer: a
Explanation: Hash table is a data structure that has an advantage that it allows fast access of elements. But linked list is easier to implement as compared to the hash table.

3. Which of the following trait of a hash function is most desirable?
a) it should cause less collisions
b) it should cause more collisions
c) it should occupy less space
d) it should be easy to implement
View Answer

Answer: a
Explanation: Hash function calculates and returns the index for corresponding data. So the most important trait of a hash function is that it should cause a minimum number of collisions.
advertisement
advertisement

4. What is the time complexity of insert function in a hash table using list head?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer

Answer: a
Explanation: Time complexity of insert function in a hash table is O(1). Condition is that the number of collisions should be low.

5. What is the time complexity of search function in a hash table using list head?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer

Answer: a
Explanation: Time complexity of search function in a hash table is O(1). Condition is that the number of collisions should be low.
advertisement

6. What is the time complexity of delete function in the hash table using list head?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer

Answer: a
Explanation: Time complexity of delete function in a hash table is O(1). Condition is that the hash function should be such that the number of collisions should be low.

7. A hash table may become full in the case when we use open addressing.
a) true
b) false
View Answer

Answer: a
Explanation: A hash table may become full in the case when we use open addressing. But when we use separate chaining it does not happen.
advertisement

8. What is the advantage of using linked list over the doubly linked list for chaining?
a) it takes less memory
b) it causes more collisions
c) it makes the process of insertion and deletion faster
d) it causes less collisions
View Answer

Answer: a
Explanation: Singly linked list takes lesser space as compared to doubly linked list. But the time complexity of the singly linked list is more than a doubly linked list.

9. What is the worst case time complexity of insert function in the hash table when the list head is used for chaining?
a) O(1)
b) O(n log n)
c) O(log n)
d) O(n)
View Answer

Answer: d
Explanation: Worst case time complexity of insert function in the hash table when the list head is used for chaining is O(n). It is caused when a number of collisions are very high.
advertisement

10. Which of the following technique is used for handling collisions in a hash table?
a) Open addressing
b) Hashing
c) Searching
d) Hash function
View Answer

Answer: a
Explanation: Open addressing is the technique which is used for handling collisions in a hash table. Separate chaining is another technique which is used for the same purpose.

11. By implementing separate chaining using list head we can reduce the number of collisions drastically.
a) True
b) False
View Answer

Answer: b
Explanation: Collision is caused when a hash function returns repeated values. So collisions can be reduced by developing a better hash function. Whereas separate chaining using list head is a collision handling technique so it has no relation with a number of collisions taking place.

12. Which of the following is an advantage of open addressing over separate chaining?
a) it is simpler to implement
b) table never gets full
c) it is less sensitive to hash function
d) it has better cache performance
View Answer

Answer: a
Explanation: Open addressing is the technique which is used for handling collisions in a hash table. It has a better cache performance as everything is stored in the same table.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter