Double Hashing Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Double Hashing”.

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

4. 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. 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)
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

b)

h1(k) = 1 + (m mod k)
    h2(k) =  m’ mod k

c)

h1(k) = 1+ (k mod m)
    h2(k) =  k mod m
advertisement

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

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

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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.