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)?

Question

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)?

BlackTom AI · Accepted Answer

h(3) = 3, so the probe sequence begins at index 3 and proceeds by linear probing (i+1 mod 11) until an empty slot is encountered or the key is found.

Relevant concepts:
- Hash index = k mod 11, so 3 maps to index 3.
- Linear probing: on collision or mismatch, examine the next index (wrapping around modulo table size).
- A "defunct" (deleted) slot must be treated as occupied for searching (you must continue probing), whereas a truly empty slot (never occupied) terminates the search with “not found.”

Step-by-step reasoning and intermediate steps:
1. Compute h(3) = 3 mod 11 = 3. Start at index 3.
2. Index 3 contains key 14. Compare 14 to 3 → not equal. Continue to next index.
3. Index 4 is marked defunct (a deleted entry). A defunct slot cannot stop the search because items inserted after the deleted item may have been displaced past it; therefore continue probing.
4. Index 5 contains key 25. Compare 25 to 3 → not equal. Continue.
5. Index 6 contains key 4. Compare 4 to 3 → not equal. Continue.
6. Index 7 is an empty slot (no entry ever inserted). An empty slot indicates that no further keys that hashed to earlier positions could have been displaced past this point, so the search terminates: key 3 is not present.

Thus the indices examined in order are 3, 4, 5, 6, 7.

Why other choices are incorrect:
- "3" or "3,4": stopping at 3 or 4 would be wrong because neither contains key 3 and index 4 is defunct (search must continue).
- "3,4,5,6": stopping at 6 would be wrong because index 6 is occupied (with 4); the correct stopping condition is the first truly empty slot at index 7.

Final confirmation: The probe sequence examined is 3,4,5,6,7, which matches the provided answer.

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)? 单项选择题

类似问题

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

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搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单