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

Uncategorized

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

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

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. A hash table may become full in the case when we use open addressing.
A) true

B) false

Explanation: In the case of open addressing, a hash table can become complete. When we use different chaining, however, this does not occur.

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

Explanation: As compared to a doubly linked list, a singly linked list takes up less room. However, the singly linked list has a higher time complexity than a doubly linked list.

4. 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)
Explanation: When the list head is used for chaining, the worst case time complexity of the insert function in the hash table is O. (n). It occurs when there are a large number of collisions.

5. Which of the following technique is used for handling collisions in a hash table?
A) Open addressing

B) Hashing
C) Searching
D) Hash function

Explanation: In a hash table, open addressing is the technique for handling collisions. Separate chaining is another method for achieving the same goal.

6. By implementing separate chaining using list head we can reduce the number of collisions drastically.
A) True
B) False

Explanation: When a hash function returns repeated values, collision occurs. As a result, creating a better hash function will help minimise collisions. Separate chaining with a list head, on the other hand, is a collision handling strategy that has little to do with the amount of collisions that occur.

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

Explanation: In a hash table, open addressing is the technique for handling collisions. Since everything is stored in the same table, it has better cache capacity.

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

Explanation: A hash table is a type of data structure that is designed to allow for quick access to elements. In a hash table, hash functions are used to find the index of any input record.

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

Explanation: Hash tables are a type of data structure that allows for quick access to elements. However, compared to the hash table, the linked list is simpler to enforce.

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

Explanation: The index for corresponding data is calculated and returned by the hash function. As a result, the most important characteristic of a hash function is that it should cause the fewest possible collisions.

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

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

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

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 hash table (also known as a hash map) is a data structure that implements an associative array abstract data form, which can map keys to values. A hash table employs a hash function to generate an index, also referred to as a hash code, into an array of buckets or slots from which the desired value can be retrieved. The key is hashed during lookup, and the hash indicates where the corresponding value is located. The hash function can allocate each key to a specific bucket in theory, but most hash table designs use an incomplete hash function, which could result in hash collisions if the hash function produces the same index for multiple keys.

Leave a Reply

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