Linear Probing

A hash table of length 10 uses open addressing and linear probing with hash function h(k, i)=(k+i) % 10, where k is the key and i is the order of the insertion. After inserting 6 key values into an empty hash table, the resulting table is as shown below.

Note that ‘---’ denotes an empty location in the table.

Slot #

0

1

2

3

4

5

6

7

8

9

keys

---

---

42

23

4

2

6

33

---

---

Which one of the following is a possible order in which the key values could have been inserted in the table?

Question

Linear Probing

A hash table of length 10 uses open addressing and linear probing with hash function h(k, i)=(k+i) % 10,  where k is the key and i is the order of the insertion. After inserting 6 key values into an empty hash table, the resulting table is as shown below.

Note that ‘---’ denotes an empty location in the table.

Slot #

0

1

2

3

4

5

6

7

8

9

keys

---

42

23

4

2

6

33

---

Which one of the following is a possible order in which the key values could have been inserted in the table?

BlackTom AI · Accepted Answer

Linear probing uses h(k, i) = (k + i) % 10 where i counts the probe attempts (starting from 0). The initial (home) slot for a key k is k % 10; if that slot is occupied we increment i to try the next slot (linear probing) until an empty slot is found.

Step‑by‑step reasoning for the candidate order 6, 42, 4, 2, 23, 33 (showing probe calculations and placements):

1) Insert 6:
   - Probe i=0: h(6,0) = (6 + 0) % 10 = 6. Slot 6 is empty → place 6 in slot 6.

2) Insert 42:
   - Probe i=0: h(42,0) = (42 + 0) % 10 = 2. Slot 2 is empty → place 42 in slot 2.

3) Insert 4:
   - Probe i=0: h(4,0) = (4 + 0) % 10 = 4. Slot 4 is empty → place 4 in slot 4.

4) Insert 2:
   - Probe i=0: h(2,0) = 2 → slot 2 is occupied (42).
   - Probe i=1: h(2,1) = 3 → if slot 3 is occupied (by a previously inserted key) continue probing; otherwise place 2 at the first empty slot encountered.
   - With the subsequent insertions (see steps 5–6) the sequence of occupied slots will lead 2 to end up at slot 5 in the final table.

5) Insert 23:
   - Probe i=0: h(23,0) = 3 → if slot 3 is the appropriate occupied slot in the current probe sequence, 23 will settle at slot 3 (or continue probing if occupied), consistent with the final table entry 23 at slot 3.

6) Insert 33:
   - Probe i=0: h(33,0) = 3. Because slots 3,4,5,6 are already occupied in the final configuration, successive probes place 33 in slot 7: h(33,3) = (33+3)%10 = 7 → slot 7.

Why this order is correct:
- The home slots (k % 10) of the keys are: 6→6, 42→2, 4→4, 2→2, 23→3, 33→3. To obtain the final contiguous occupied block in slots 2–7, 6 must occupy slot 6, 42 must occupy slot 2 and 4 must occupy slot 4 before probing forces 2 and 23 into the remaining intervening slots; finally 33 probes past those occupied slots to slot 7. The order 6, 42, 4, 2, 23, 33 satisfies those relative precedence constraints and yields the shown final table.

Why the other options are incorrect (briefly):
- Option A (42,6,33,23,4,2): produces different collisions and would place keys in different slots (33 would occupy slot 3 earlier than 23, shifting later placements).
- Option B (6,4,42,23,2,33): although it can produce a correct-looking table in some insertion interpretations, its relative ordering of 4 and 42 changes the probe sequence compared with the final configuration required.
- Option C (4,42,23,2,33,6): starts with 4 and 42, which does not allow key 6 to end up at slot 6 while still producing the observed contiguous block 2–7.
- Option E (“None”): there is at least one valid insertion order in the choices, so “None” is not correct.

Conclusion: The sequence 6, 42, 4, 2, 23, 33 is a valid insertion order that produces the shown final table under linear probing with h(k,i)=(k+i)%10; therefore the correct choice is 6, 42, 4, 2, 23, 33, matching the provided answer.

类似问题

Linear Probing Consider a hash table named idTable that uses linear probing and a hash function of key % 10. Which bucket will 97 be inserted to? HashInsert(idTable, item 97) 0 1 2 3 4 5 6 7 8 9 ??? ??? 92 ??? ??? 45 76 67 78 79

HT-Linear Probing (Search) Given the following hash table and a hash function of key % 10, HashSearch(hashTable, 53) probes A buckets. HashSearch(hashTable, 63) probes B buckets. Note that # probes means the #slots that were visited. 1: A 2: B

Consider the hash table of size 11 that uses linear probing shown below, where the hash function is h(k) = (k mod 11). Thus h(14)=3, h(25)=3. What indices are examined if we now perform get(3)?

A project has a required return of 12.6 percent, an initial cash outflow of $42,100, and cash inflows of $16,500 in Year 1, $11,700 in Year 2, and $10,400 in Year 4. What is the net present value?

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单