Engineering Questions with Answers - Multiple Choice Questions
Hash Tables Chaining using Linked Lists MCQ’s
1 - Question
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.
2 - Question
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 - Question
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.
4 - Question
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 - Question
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.
6 - Question
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 - Question
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.
8 - Question
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 - Question
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
10 - Question
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 - Question
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 - Question
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 - Question
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 - Question
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 - Question
From the given table, find ‘?’.
Given: hash(x)= x mod 10
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.