Engineering Questions with Answers - Multiple Choice Questions
Double Hashing MCQ’s
1 - Question
Double hashing is one of the best methods available for open addressing.
a) True
b) False
View Answer
Answer: a
Explanation: Double hashing is one of the best methods for open addressing because the permutations produced have many characteristics of randomly chosen permutations.
2 - Question
What is the hash function used in Double Hashing?
a) (h1(k) – i*h2(k))mod m
b) h1(k) + h2(k)
c) (h1(k) + i*h2(k))mod m
d) (h1(k) + h2(k))mod m
View Answer
Answer: c
Explanation: Double hashing uses a hash function of the form (h1(k) + i*h2(k))mod m where h1 and h2 are auxiliary hash functions and m is the size of the hash table.
3 - Question
On what value does the probe sequence depend on?
a) c1
b) k
c) c2
d) m
View Answer
Answer: b
Explanation: The probe sequence depends in upon the key k since the initial probe position, the offset or both may vary.
4 - Question
The value of h2(k) can be composite relatively to the hash table size m.
a) True
b) False
View Answer
Answer: b
Explanation: The value h2(k) must be relatively prime to the hash table size m for the entire hash table to be searched. It can be ensured by having m in powers of 2 and designing h2 so that it produces an odd number.
5 - Question
What are the values of h1(k) and h2(k) in the hash function?
a)
h1(k) = m mod k
h2(k) = 1+ (m’ mod k)
b)
h1(k) = 1 + (m mod k)
h2(k) = m’ mod k
c)
h1(k) = 1+ (k mod m)
h2(k) = k mod m
d)
h1(k) = k mod m
h2(k) = 1+ (k mod m’)
View Answer
Answer: d
Explanation: The values h1(k) and h2(k) are k mod m and 1+(k mod m’) respectively where m is a prime number and m’ is chosen slightly less than m. (m’=m-1).
6 - Question
What is the running time of double hashing?
a) Theta(m)
b) Theta(m2)
c) Theta(m log k)
d) Theta(m3)
View Answer
Answer: a
Explanation: The running time of double hashing is Theta(m) since each possible (h1(k), h2(k)) pair yields a distinct probe sequence. Hence the performance of double hashing is better.
7 - Question
Which technique has the greatest number of probe sequences?
a) Linear probing
b) Quadratic probing
c) Double hashing
d) Closed hashing
View Answer
Answer: c
Explanation: Double hashing has the greatest number of probe sequences thereby efficiently resolves hash collision problems.
8 - Question
At what position the number 72 gets inserted in the following table?
| Index | Key |
| 0 | 22 |
| 1 | 34 |
| 2 | |
| 3 | |
| 4 | |
| 5 | 56 |
| 6 | |
| 7 | 18 |
| 8 | 41 |
| 9 | |
| 10 |
a) 3
b) 10
c) 4
d) 6
View Answer
Answer: d
Explanation: The number 72 must be inserted at index 6.
H(k)=k mod m
H(72)= 72 mod 11
H(72)= 6.
9 - Question
Where does the number 14 get inserted in the following table?
| Index | Key |
| 0 | |
| 1 | 79 |
| 2 | |
| 3 | |
| 4 | 69 |
| 5 | 98 |
| 6 | |
| 7 | 72 |
| 8 | |
| 9 | |
| 10 | |
| 11 | 50 |
| 12 |
a) 2
b) 9
c) 4
d) 8
View Answer
Answer: b
Explanation: Here the hash table is of size 13 with h1(k) = k mod 13 and h2(k) = 1 + k mod 11. Since 14 = 1 (mod 13) and 14 = 3 (mod 11), the key 14 is inserted into empty slot 9.
10 - Question
What is the value of m’ if the value of m is 19?
a) 11
b) 18
c) 17
d) 15
View Answer
Answer: c
Explanation: The value of m’ is chosen as a prime number slightly less than the value of m. Here the value of m is 19, hence the value of m’ can be chosen as 17.