Open Addressing Probing MCQs: 12 Solved Questions with Explanations

Open addressing questions demand more than naming linear probing, quadratic probing or double hashing. You must trace occupied slots, wrap around the table, distinguish a probe number from an address, and recover insertion constraints from a final table. Attempt each option on paper before reading its explanation because one skipped slot can change the answer. More than 50 Open Addressing (Probing) questions are available for continued practice through the Coding & DSA Courses for Placements collection.

1. The three probe rules to write before solving

In open addressing, every key stays in the table array, so a collision triggers a deterministic sequence of alternative slots.

• Linear probing: $(h(k) + i) \bmod m$

• Quadratic probing: $(h(k) + i^2) \bmod m$

• Double hashing: $(h_1(k) + i h_2(k)) \bmod m$

Here, $i=0$ is always the first probe. For a calibration case, take $m=7$, home slot $h(k)=3$, with slots 3 and 4 occupied. Linear probing visits 3, 4, 5. Quadratic probing visits 3, 4, 0 because $(3+2^2) \bmod 7=0$. With $h_2(k)=3$, double hashing visits 3, 6, 2 because each probe adds a step of 3 modulo 7. A usable double-hash step must eventually reach the table's slots. Choosing a step coprime to $m$ is a common way to ensure that. The earlier Hashing Basics and Functions MCQs: 12 Solved Questions with Explanations owns the hash-function, collision and load-factor definitions. The calculations here start where that foundation ends: probe arithmetic, wrap-around and final-table constraints.

2. Open addressing MCQs 1-3: double-hashing formula and probe arithmetic

Question 1

The hash function used in double hashing is of the form:

• (a) $h(k,i)=(h_1(k)+h_2(k)+i) \: mod \: m$

• (b) $h(k,i)=(h_1(k)+h_2(k)-i) \: mod \: m$

• (c) $h(k,i)=(h_1(k)+i \: h_2(k)) \: mod \: m$

• (d) $h(k,i)=(h_1(k)-i \: h_2(k)) \: mod \: m$

Answer: (c).

The hash, $h_1(k)$, gives starting slot, while $h_2(k)$ gives the step. Multiplication by $i$ generates $h_1(k)$, $h_1(k)+h_2(k)$, $h_1(k)+2h_2(k)$, all modulo $m$. The other formulas add the second hash once or use the wrong direction. Practice this question.

Question 2

Consider double hashing of the form$h(k,i)=(h_1(k)+ih_2(k)) \text{mod m}$ where $h_{1}(k) = \text{k mod m} \ , \ \ h_{2}(k)=1+(\text{k mod n})$ where $n=m-1$ and $m=701$ . For $𝑘=123456$, what is the difference between first and second probes in terms of slots?

• (a) 255

• (b) 256

• (c) 257

• (d) 258

Answer: (c) 257.

First, $n=700$. Then $123456 \bmod 700=256$, so $h_2(k)=1+256=257$. Probe 0 is $123456 \bmod 701=80$. Probe 1 is $(80+257) \bmod 701=337$. Their slot difference is $337-80=257$, exactly the secondary-hash step. This difference selects C. Practice this question.

Question 3

Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23, and the secondary hash function is h2(k) = 1+(k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________ .

• (a) 13

• (b) 15

• (c) 21

• (d) 23

Answer: (a) 13.

Calculate $h_1(90)=90 \bmod 23=21$ and $h_2(90)=1+(90 \bmod 19)=15$. Counting begins at 0, so probe 1 is $(21+15) \bmod 23=13$. Address 21 is probe 0. Practice this question.

3. Open addressing MCQs 4-5: methods and the clustering trap

Question 4

Which of the following is not a method of open addressing?

• (a) Linear Probing

• (b) Quadratic Probing

• (c) Double Hashing

• (d) All of the above are methods of open addressing

Answer: (d).

The negative wording matters. Linear probing, quadratic probing and double hashing are all open-addressing methods, so none of A, B or C satisfies "not." Option D is therefore correct. For the broader survey of hash functions, probing, chaining and load factor, use Hashing MCQs: 12 Solved on Hash Functions (GATE). Its two shared trace anchors reappear as Questions 8 and 10 here, while the remaining questions extend the method into double-hash arithmetic, wrap-around and insertion-order constraints. Practice this question.

Question 5

Which of the following is a major drawback of linear probing?

• (a) Secondary clustering

• (b) Primary clustering

• (c) Requires a second hash function

• (d) Uses extra memory for links

Answer: (b) Primary clustering.

Keys hashing to 4, 4 and 5 occupy 4, 5 and 6. Another key entering the run extends it, causing primary clustering, and future collisions join the same block. Quadratic sequences cause secondary clustering; a second hash means double hashing; links mean chaining. Practice this question.

4. Open addressing MCQs 6-8: linear probing, collisions and wrap-around

Question 6

A hash function h defined as h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?

• (a) 3

• (b) 4

• (c) 5

• (d) 6

Answer: (c) slot 5.

Insert in order: $44\to2$, $45\to3$, and 79 hashes to 2 but moves to 4. Next, $55\to6$ and $91\to0$. Since $18 \bmod 7=4$ and slot 4 holds 79, 18 enters empty slot 5. Key 63 arrives later. So C. Practice this question.

Question 7

Consider a 13 element hash table for which f(key)=key mod 13 is used with integer keys. Assuming linear probing is used for collision resolution, at which location would the key 103 be inserted, if the keys 661, 182, 24 and 103 are inserted in that order?

• (a) 0

• (b) 1

• (c) 11

• (d) 12

Answer: (b) slot 1.

Here, $661 \bmod 13=11$, $182 \bmod 13=0$, and $24 \bmod 13=11$, so 24 moves to 12. Next, $103 \bmod 13=12$. Slots 12 and 0 are occupied, so the probe wraps and stops at slot 1. Do not skip 0. Practice this question.

Question 8

A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in what location would the key value 142 be inserted?

• (a) 2

• (b) 3

• (c) 4

• (d) 6

Answer: (d) slot 6.

Before 142, slots 2 to 5 hold 62, 43, 123 and 165. $142 \bmod 10=2$, giving probes 2, 3, 4, 5, 6. All earlier probes are occupied; 142 enters slot 6. Practice this question.

5. Open addressing MCQs 9-10: building the table from an insertion order

Question 9

The following keys 22, 28, 23, 12 and 13 are inserted into initially empty hash table of length 9 using open addressing with hash function h(k)=k mod  9 and linear probing. At what index key 13 is inserted?

• (a) 4

• (b) 5

• (c) 6

• (d) 7

Answer: (c) index 6.

Insert in order: $22\to4$, $28\to1$, $23\to5$, and $12\to3$. Key 13 hashes to 4, but slots 4 and 5 hold 22 and 23. The first empty slot is 6. Linear probing follows physical slots, not key order. Therefore option C. Practice this question.

Question 10

Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.

• (a) 8, _, _, _, _, _, 10

• (b) 1, 8, 10, _, _, _, 3

• (c) 1, _, _, _, _, _,3

• (d) 1, 10, 8, _, _, _, 3

Answer: (b).

Homes are $h(1)=h(8)=0$ and $h(3)=h(10)=6$. Insert 1 at 0 and 3 at 6. Key 8 probes 0, 1; key 10 probes 6, 0, 1, 2. Thus the table is $[1,8,10,\_,\_,\_,3]$. Practice this question.

6. Open addressing MCQs 11-12: a complete trace and insertion-order constraints

Question 11

Consider a hash table with 10 slots. What is the sequence of the following elements in a hash table if the hash function is k mod 10 and the collision is resolved using linear probing? 44, 26, 12, 93, 80, 57, 56, 23, 46, 36

• (a) 80, 46, 12, 93, 44, 23, 26, 57, 56, 36

• (b) 80, 36, 12, 93, 44, 23, 26, 57, 56, 46

• (c) 80, 36, 12, 93, 44, 23, 26, 56, 46, 57

• (d) 12, 23, 26, 36, 44, 46, 56, 57, 80, 93

Answer: (b).

First six placements are $80@0$, $12@2$, $93@3$, $44@4$, $26@6$, and $57@7$. Then 56 probes 6, 7 and enters 8. Key 23 probes 3, 4 and enters 5. Key 46 probes 6, 7, 8 and enters 9. Finally, 36 probes 6, 7, 8, 9, 0, wraps, and enters 1. Reading slots 0 through 9 gives $[80,36,12,93,44,23,26,57,56,46]$, option B. This trace preserves collisions and wrap-around. Practice this question.

Question 12

A hash table of length 10 uses open addressing with hash function h(k) = k mod 10 and linear probing.

After inserting six values into an empty hash table, the final table is:

- 0: empty

- 1: empty

- 2: 42

- 3: 23

- 4: 34

- 5: 52

- 6: 46

- 7: 33

- 8: empty

- 9: empty

How many different insertion sequences of these key values can produce the table shown above?

• (a) 10

• (b) 20

• (c) 30

• (d) 40

Answer: (c) 30.

For 52, home slot 2, to finish at 5, keys 42, 23 and 34 must already fill slots 2 to 4. For 33, home slot 3, to finish at 7, keys 23, 34, 52 and 46 must fill slots 3 to 6. Thus 33 is last. Among 42, 23, 34 and 52, 52 follows the other three, which can appear in $3!=6$ orders. Key 46 can occupy any of five positions before 33. Hence $6\times5=30$. Practice this question.

7. Read the score, fix the probe error, and choose the next set

Misses in 1 to 3 show arithmetic errors; 4 to 5, definition gaps; 6 to 11, trace errors; 12, insertion-constraint errors.

Use Data Structures MCQs for broader gaps. Continue with the Zero to Hero Complete CS Course for a structured CS study path.

The short version

Hide the answers, redraw the indices, and re-solve missed groups until every numerical answer includes its probe sequence.