Hash Tables Chaining with Binary Trees Multiple Choice Questions and Answers (MCQs)

Uncategorized

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

1. 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)

Explanation: The delete function in a hash table has an O time complexity (1). The hash function must be designed in such a way that the number of collisions is minimal.

2. 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

Explanation: Both a hash table and a binary search tree (BST) are examples of data structures. The benefit of a hash table is that it has a lower time complexity for insert, delete, and search operations.

3. 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

Explanation: BST has the benefits of being easier to implement, having the ability to sort keys using only in-order traversal, and having the ability to perform range queries. Insert, erase, and search operations on a hash table are less time consuming.

4. 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

Explanation: In the event of a collision, open addressing is used to store data in the table itself. Chaining, on the other hand, stores data in a different body.

5. Separate chaining is easier to implement as compared to open addressing.
A) true

B) false

Explanation: In a hash table, there are two ways to handle collisions: open addressing and separate chaining. When compared to separate chaining, open addressing necessitates further computation.

6. In open addressing the hash table can never become full.
A) True
B) False

Explanation: In a hash table, there are two ways to handle collisions: open addressing and separate chaining. The hash table may become complete in open addressing.

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

Explanation: As compared to separate chaining, the hash table implementation using open addressing has a better cache efficiency. It’s because open addressing keeps all of the data in the same table, saving space.

8. 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

Explanation: Separate chaining hashing has the benefit of being less responsive to a hash feature. It’s also easy to put into practise.

9. 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

Explanation: Separate chaining has the downside of taking up more room while hashing. In the event of a collision, this space is used to store elements.

10. 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)

Explanation: On average, the time complexity of the insert function in a hash table is O(1). The condition is that the number of collisions be kept to a minimum.

11. 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)

Explanation: The search function in a hash table has an O time complexity (1). The condition is that the number of collisions be kept to a minimum.

A binary tree is a tree data structure in which each node has no more than two members, known as the left and right children. A (non-empty) binary tree is a triangle (L, S, R), where L and R are binary trees or the empty set, and S is a singleton set containing the root, according to a relational description using only set theory notions. The binary tree may also be the empty set, according to some writers. Binary (and K-ary) trees, as described here, are arborescences from the standpoint of graph theory.

Leave a Reply

Your email address will not be published. Required fields are marked *