Engineering Questions with Answers - Multiple Choice Questions

Hash Tables Chaining with Binary Trees Multiple Choice MCQ

1 - Question

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

Answer: c
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 - Question

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

Answer: c
Explanation: Hashing with separate chaining has an advantage that it is less sensitive to a hash function. It is also easy to implement.




3 - Question

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

Answer: b
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 - Question

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

Answer: a
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 - Question

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

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.




6 - Question

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

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 - Question

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

Answer: a
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 - Question

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

Answer: d
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 - Question

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

Answer: d
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 - Question

Separate chaining is easier to implement as compared to open addressing.
a) true
b) false

View Answer

Answer: a
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 - Question

In open addressing the hash table can never become full.
a) True
b) False

View Answer

Answer: b
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.

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners