# Hash Tables with Linear Probing Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Hash Tables with Linear Probing”.

1. Which of the following problems occur due to linear probing?
a) Primary collision
b) Secondary collision
c) Separate chaining
d) Extendible hashing
View Answer

Answer: a
Explanation: Primary collision occurs due to linear probing technique. It is overcome using a quadratic probing technique.

2. How many probes are required on average for insertion and successful search?
a) 4 and 10
b) 2 and 6
c) 2.5 and 1.5
d) 3.5 and 1.5
View Answer

Answer: c
Explanation: Using formula, the average number of probes required for insertion is 2.5 and for a successful search, it is 1.5.

3. What is the load factor for an open addressing technique?
a) 1
b) 0.5
c) 1.5
d) 0
View Answer

Answer: b
Explanation: The load factor for an open addressing technique should be 0.5. For separate chaining technique, the load factor is 1.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

4. Which of the following is not a collision resolution strategy for open addressing?
a) Linear probing
b) Quadratic probing
c) Double hashing
d) Rehashing
View Answer

Answer: d
Explanation: Linear probing, quadratic probing and double hashing are all collision resolution strategies for open addressing whereas rehashing is a different technique.

5. In linear probing, the cost of an unsuccessful search can be used to compute the average cost of a successful search.
a) True
b) False
View Answer

Answer: a
Explanation: Using random collision resolution algorithm, the cost of an unsuccessful search can be used to compute the average cost of a successful search.

6. Which of the following is the correct function definition for linear probing?
a) F(i)= 1
b) F(i)=i
c) F(i)=i2
d) F(i)=i+1
View Answer

Answer: b
Explanation: The function used in linear probing is defined as, F(i)=I where i=0,1,2,3….,n.

7. ___________ is not a theoretical problem but actually occurs in real implementations of probing.
a) Hashing
b) Clustering
c) Rehashing
d) Collision
View Answer

Answer: b
Explanation: Clustering is not a theoretical problem but it occurs in implementations of hashing. Rehashing is a kind of hashing.
advertisement

8. What is the hash function used in linear probing?
a) H(x)= key mod table size
b) H(x)= (key+ F(i2)) mod table size
c) H(x)= (key+ F(i)) mod table size
d) H(x)= X mod 17
View Answer

Answer: c
Explanation: The hash function used in linear probing is defined to be H(x)= (key+ F(i)) mod table size where i=0,1,2,3,…,n.

9. Hashing can be used in online spelling checkers.
a) True
b) False
View Answer

Answer: a
Explanation: If misspelling detection is important, an entire dictionary can be pre-hashed and words can be checked in constant time.
advertisement

10. In the following given hash table, use linear probing to find the location of 49.

 0 1 2 3 4 5 6 7 8 18 9 89

a) 7
b) 6
c) 2
d) 0
View Answer

Answer: d
Explanation: Initially, collision occurs while hashing 49 for the first time.
Hence, after setting f(i)=1, the hashed location is found to be 0.

11. What is the formula to find the expected number of probes for an unsuccessful search in linear probing?
a) $$\frac{1}{2} \frac{1+1}{(1-⅄)}$$
b) $$\frac{1}{2}\frac{1+1}{(1-⅄)^2}$$
c) $$\frac{1}{2}\frac{1+1}{(1+⅄)}$$
d) $$\frac{1}{2}\frac{1+1}{(1+⅄)(1-⅄)}$$
View Answer

Answer: b
Explanation: The mathematical formula for calculating the number of probes for an unsuccessful search is $$\frac{1}{2}\frac{1+1}{(1-⅄)^2}$$. For insertion, it is $$\frac{1}{2} \frac{1+1}{(1-⅄)}$$.

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, 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 & technical discussions at Telegram SanfoundryClasses.