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
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
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
Explanation: The probe sequence depends in upon the key k since the initial probe position, the offset or both may vary.
4. The value of h2(k) can be composite relatively to the hash table size m.
a) True
b) False
View Answer
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)
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 AnswerExplanation: 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
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
Explanation: Double hashing has the greatest number of probe sequences thereby efficiently resolves hash collision problems.
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
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
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
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.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Check Data Structure Books
- Practice Computer Science MCQs
- Check Computer Science Books
- Check Programming Books
- Practice Design & Analysis of Algorithms MCQ
