Data Structure Questions and Answers – Hash Tables

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Hash Tables”.

1. What is a hash table?
a) A structure that maps values to keys
b) A structure that maps keys to values
c) A structure used for storage
d) A structure used to implement stack and queue
View Answer

Answer: b
Explanation: A hash table is used to implement associative arrays which has a key-value pair, so the has table maps keys to values.

2. If several elements are competing for the same bucket in the hash table, what is it called?
a) Diffusion
b) Replication
c) Collision
d) Duplication
View Answer

Answer: c
Explanation: In a hash table, if sevaral elements are computing for the same bucket then there will be a clash among elements. This condition is called Collision. The Collision is reduced by adding elements to a linked list and head address of linked list is placed in hash table.

3. What is direct addressing?
a) Distinct array position for every possible key
b) Fewer array positions than keys
c) Fewer keys than array positions
d) Same array position for all keys
View Answer

Answer: a
Explanation: Direct addressing is possible only when we can afford to allocate an array that has one position for every possible key.
advertisement
advertisement

4. What is the search complexity in direct addressing?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)
View Answer

Answer: d
Explanation: Since every key has a unique array position, searching takes a constant time.

5. What is a hash function?
a) A function has allocated memory to keys
b) A function that computes the location of the key in the array
c) A function that creates an array
d) A function that computes the location of the values in the array
View Answer

Answer: b
Explanation: In a hash table, there are fewer array positions than the keys, so the position of the key in the array has to be computed, this is done using the hash function.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. Which of the following is not a technique to avoid a collision?
a) Make the hash function appear random
b) Use the chaining method
c) Use uniform hashing
d) Increasing hash table size
View Answer

Answer: d
Explanation: On increasing hash table size, space complexity will increase as we need to reallocate the memory size of hash table for every collision. It is not the best technique to avoid a collision. We can avoid collision by making hash function random, chaining method and uniform hashing.

7. What is the load factor?
a) Average array size
b) Average key size
c) Average chain length
d) Average hash table length
View Answer

Answer: c
Explanation: In simple chaining, load factor is the average number of elements stored in a chain, and is given by the ratio of number of elements stored to the number of slots in the array.
advertisement

8. What is simple uniform hashing?
a) Every element has equal probability of hashing into any of the slots
b) A weighted probabilistic method is used to hash elements into the slots
c) Elements has Random probability of hashing into array slots
d) Elements are hashed based on priority
View Answer

Answer: a
Explanation: In simple uniform hashing, any given element is equally likely to hash into any of the slots available in the array.

9. In simple uniform hashing, what is the search complexity?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)
View Answer

Answer: d
Explanation: There are two cases, once when the search is successful and when it is unsuccessful, but in both the cases, the complexity is O(1+alpha) where 1 is to compute the hash function and alpha is the load factor.
advertisement

10. In simple chaining, what data structure is appropriate?
a) Singly linked list
b) Doubly linked list
c) Circular linked list
d) Binary trees
View Answer

Answer: b
Explanation: Deletion becomes easier with doubly linked list, hence it is appropriate.

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.