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
Explanation: When some other value is placed at a specified location other than the desired key, it is said to be a collision.
2. What data organization method is used in hash tables?
a) Stack
b) Array
c) Linked list
d) Queue
View Answer
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
Explanation: Collision handling involves the process of formulating alternative indices for a key.
4. Which of the following is not a collision resolution technique?
a) Separate chaining
b) Linear probing
c) Quadratic probing
d) Hashing
View Answer
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
Explanation: Hashing is a data structure which is used to locate data in a table based on a key value.
6. In a hash table of size 10, where is element 7 placed?
a) 6
b) 7
c) 17
d) 16
View Answer
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
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.
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
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
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.
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
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
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
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
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
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
a) 13
b) 16
c) 12
d) 14
View Answer
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.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Programming MCQs
- Apply for Computer Science Internship
- Check Programming Books
- Check Computer Science Books
- Practice Design & Analysis of Algorithms MCQ
