Hash Tables Chaining using Linked Lists Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Hash Tables Chaining using Linked Lists”.

1. The case in which a key other than the desired one is kept at the identified location is called?
a) Hashing
b) Collision
c) Chaining
d) Open addressing
View Answer

Answer: b
Explanation: When some other value is placed at a specified location other than the desired key, it is said to be a collision.
advertisement

2. What data organization method is used in hash tables?
a) Stack
b) Array
c) Linked list
d) Queue
View Answer

Answer: c
Explanation: The data structure used to organize data for hash tables is linked list. It contains a data field and a pointer field.

3. The task of generating alternative indices for a node is called?
a) Collision handling
b) Collision detection
c) Collision recovery
d) Closed hashing
View Answer

Answer: a
Explanation: Collision handling involves the process of formulating alternative indices for a key.
advertisement
advertisement

4. Which of the following is not a collision resolution technique?
a) Separate chaining
b) Linear probing
c) Quadratic probing
d) Hashing
View Answer

Answer: d
Explanation: Hashing is a technique of placing data items in specific locations. Collision may occur in hashing but hashing is not a collision resolution technique.

5. Hashing is the problem of finding an appropriate mapping of keys into addresses.
a) True
b) False
View Answer

Answer: a
Explanation: Hashing is a data structure which is used to locate data in a table based on a key value.
advertisement

6. In a hash table of size 10, where is element 7 placed?
a) 6
b) 7
c) 17
d) 16
View Answer

Answer: b
Explanation: The hash location is defined as hash(f)= key mod table_size.
7 mod 10 gives 7. It is placed in 7th position.

7. What should be the load factor for separate chaining hashing?
a) 0.5
b) 1
c) 1.5
d) 2
View Answer

Answer: b
Explanation: For hashing using separate chaining method, the load factor should be maintained as 1. For open addressing method, it should not exceed 0.5.
advertisement

8. Which of the following operations are done in a hash table?
a) Insert only
b) Search only
c) Insert and search
d) Replace
View Answer

Answer: c
Explanation: Hash tables are used to implement Insert and Find operations in constant average time. This is the prime purpose of hashing.

9. Which of the following is identical to that of a separate chaining hash node?
a) Linked list
b) Array
c) Stack
d) Queue
View Answer

Answer: a
Explanation: The hash node in separate chaining is similar to that of a linked list. The separate chaining hash table is an array of linked lists.
advertisement

10. Which of the following is the hashing function for separate chaining?
a) H(x)=(hash(x)+f(i)) mod table size
b) H(x)=hash(x)+i2 mod table size
c) H(x)=x mod table size
d) H(x)=x mod (table size * 2)
View Answer

Answer: c
Explanation: The hashing function for separate chaining is given by H(x)= key mod table size. H(x)=hash(x)+i2 mod table size defines quadratic probing.

11. What is the correct notation for a load factor?
a) Ω
b) ∞
c) ∑
d) ⅄
View Answer

Answer: d
Explanation: In general, load factor is denoted as ⅄. In separate chaining method, load factor is maintained as 1.0.

12. In hash tables, how many traversal of links does a successful search require?
a) 1+⅄
b) 1+⅄2
c) 1+ (⅄/2)
d) ⅄3
View Answer

Answer: c
Explanation: A successful search requires about 1+ (⅄/2) links to be traversed. There is a guarantee that at least one link must be traversed.

13. Which of the following is a disadvantage of using separate chaining using linked lists?
a) It requires many pointers
b) It requires linked lists
c) It uses array
d) It does not resolve collision
View Answer

Answer: a
Explanation: One of the major disadvantages of using separate chaining is the requirement of pointers. If the number of elements are more, it requires more pointers.

14. What is the worst case search time of a hashing using separate chaining algorithm?
a) O(N log N)
b) O(N)
c) O(N2)
d) O(N3)
View Answer

Answer: b
Explanation: The worst case search time of separate chaining algorithm using linked lists is mathematically found to be O(N).

15. From the given table, find ‘?’.
Given: hash(x)= x mod 10
hash-tables-chaining-linked-lists-questions-answers-q15
a) 13
b) 16
c) 12
d) 14
View Answer

Answer: c
Explanation: From the given options, 12 mod 10 hashes to 2 and hence ‘?’ = 12.

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.

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!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter