This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Hash Tables Chaining with Binary Trees”.
1. Which of the following variant of a hash table has the best cache performance?
a) hash table using a linked list for separate chaining
b) hash table using binary search tree for separate chaining
c) hash table using open addressing
d) hash table using a doubly linked list for separate chaining
View Answer
Explanation: Implementation of the hash table using open addressing has a better cache performance as compared to separate chaining. It is because open addressing stores data in the same table without using any extra space.
2. What is the advantage of hashing with chaining?
a) cache performance is good
b) uses less space
c) less sensitive to hash function
d) has a time complexity of O(n) in the worst case
View Answer
Explanation: Hashing with separate chaining has an advantage that it is less sensitive to a hash function. It is also easy to implement.
3. What is the disadvantage of hashing with chaining?
a) not easy to implement
b) takes more space
c) quite sensitive to hash function
d) table gets filled up easily
View Answer
Explanation: Hashing with separate chaining has a disadvantage that it takes more space. This space is used for storing elements in case of a collision.
4. What is the time complexity of insert function in a hash table using a binary tree?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer
Explanation: Time complexity of insert function in a hash table is O(1) on an average. Condition is that the number of collisions should be low.
5. What is the time complexity of the search function in a hash table using a binary tree?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer
Explanation: Time complexity of search function in a hash table is O(1). Condition is that the number of collisions should be low.
6. What is the time complexity of the delete function in the hash table using a binary tree?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer
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. What is the advantage of a hash table over BST?
a) hash table has a better average time complexity for performing insert, delete and search operations
b) hash table requires less space
c) range query is easy with hash table
d) easier to implement
View Answer
Explanation: Hash table and BST both are examples of data structures. Hash table has an advantage that it has a better time complexity for performing insert, delete and search operations.
8. What is the disadvantage of BST over the hash table?
a) BST is easier to implement
b) BST can get the keys sorted by just performing inorder traversal
c) BST can perform range query easily
d) Time complexity of hash table in inserting, searching and deleting is less than that of BST
View Answer
Explanation: BST has an advantage that it is easier to implement, can get the keys sorted by just performing in-order traversal and can perform range query easily. Hash table has lesser time complexity for performing insert, delete and search operations.
9. Which of the following technique stores data separately in case of a collision?
a) Open addressing
b) Double hashing
c) Quadratic probing
d) Chaining using a binary tree
View Answer
Explanation: Open addressing is used to store data in the table itself in case of a collision. Whereas chaining stores data in a separate entity.
10. Separate chaining is easier to implement as compared to open addressing.
a) true
b) false
View Answer
Explanation: There are two methods of handling collisions in a hash table:- open addressing and separate chaining. Open addressing requires more computation as compared to separate chaining.
11. In open addressing the hash table can never become full.
a) True
b) False
View Answer
Explanation: There are two methods of handling collisions in a hash table:- open addressing and separate chaining. In open addressing the hash table can become full.
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]
- Check Data Structure Books
- Practice Programming MCQs
- Apply for Computer Science Internship
- Practice Design & Analysis of Algorithms MCQ
- Check Programming Books
