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

**1. Which of the following is the correct function definition for linear probing?**

A) F(i)= 1**B) F(i)=i**

C) F(i)=i^{2}

D) F(i)=i+1

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

**2. ___________ is not a theoretical problem but actually occurs in real implementations of probing.**

A) Hashing**B) Clustering**

C) Rehashing

D) Collision

Explanation: Clustering is not a theoretical problem, but it does occur in hashing implementations. A form of hashing is rehashing.

**3. What is the hash function used in linear probing?**

A) H(x)= key mod table size

B) H(x)= (key+ F(i^{2})) mod table size**C) H(x)= (key+ F(i)) mod table size**

D) H(x)= X mod 17

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.

**4. Hashing can be used in online spelling checkers.****A) True**

B) False

Explanation: If misspelling detection is critical, an entire dictionary can be pre-hash and words tested in real time.

**5. 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**

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.

**6. What is the formula to find the expected number of probes for an unsuccessful search in linear probing?**

A) 121+1(1−⅄)**B) 121+1(1−⅄)2**

C) 121+1(1+⅄)

D) 121+1(1+⅄)(1−⅄)

Explanation: The mathematical formula for calculating the number of probes for an unsuccessful search is 121+1(1−⅄)2. For insertion, it is 121+1(1−⅄).

**7. Which of the following problems occur due to linear probing?****A) Primary collision**

B) Secondary collision

C) Separate chaining

D) Extendible hashing

Explanation: The linear probing technique causes the primary collision. A quadratic probing technique is used to solve it.

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

Explanation: The average number of probes needed for insertion is 2.5, and the average number of probes required for a successful search is 1.5, according to the formula.

**9. What is the load factor for an open addressing technique?**

A) 1**B) 0.5**

C) 1.5

D) 0

Explanation: An open addressing technique should have a load factor of 0.5. The load factor for the separate chaining technique is 1.

**10. Which of the following is not a collision resolution strategy for open addressing?**

A) Linear probing

B) Quadratic probing

C) Double hashing**D) Rehashing**

Explanation: Collision resolution techniques for open addressing include linear probing, quadratic probing, and double hashing, while rehashing is a different technique.

**11. 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

Explanation: The cost of an unsuccessful search can be used to calculate the average cost of a successful search using the random collision resolution algorithm.

Linear probing is a method of resolving collisions in hash tables, which are data structures for storing a list of key–value pairs and retrieving the value associated with a given key. Other hash functions, such as MurmurHash, may also produce good results in practise. Hash tables are a type of data structure that can be implemented in two ways: linear and non-linear. They’re frequently implemented using a linear data structure. As the hash table fills up, double hashing, like all other types of open addressing, becomes linear.