题目

CMPSC 132 Spring 2025 Module 6.2 Checkpoint

多重下拉选择题

Assume you have a hash table of size 11. What is the final status of the hash table after inserting 10, 22, 31, 4, 15, 28, 17, 88, 59 (in that order) using the open addressing techniques linear probing with probe +1, quadratic probing, and double hashing to resolve collision? For double hashing, H2(x) = 7- (x % 7). If the bucket remains empty after all insertions, select None Linear Probing +1 0 [ Select ] 22 None 88 17 15 4 28 31 10 59 1 [ Select ] 59 15 22 28 88 17 10 4 31 None 2 [ Select ] 59 17 31 4 10 15 None 28 88 22 3 [ Select ] 17 31 59 None 22 28 10 4 15 88 4 [ Select ] 31 59 22 10 4 15 None 28 17 88 5 [ Select ] 88 10 None 22 4 28 15 17 31 59 6 [ Select ] 88 22 10 59 4 31 28 None 15 17 7 [ Select ] 4 59 15 31 28 22 None 10 88 17 8 [ Select ] 15 10 28 59 88 None 4 17 31 22 9 [ Select ] 22 None 59 28 17 4 15 31 88 10 10 [ Select ] 15 88 59 31 10 22 4 17 None 28 Quadratic Probing 0 [ Select ] 17 31 15 22 10 4 None 88 28 1 [ Select ] 59 22 31 15 17 28 10 None 88 4 2 [ Select ] 88 28 22 31 15 4 10 None 59 17 3 [ Select ] 10 4 None 28 59 88 17 22 31 15 4 [ Select ] 59 22 17 31 4 88 10 28 None 15 5 [ Select ] 15 4 28 31 17 10 None 22 59 88 6 [ Select ] 31 15 10 None 28 17 4 88 59 22 7 [ Select ] 22 28 31 None 15 4 59 10 88 17 8 [ Select ] 22 17 4 59 31 None 10 88 15 9 [ Select ] 17 4 28 88 10 15 22 59 31 None 10 [ Select ] 17 31 28 None 4 15 10 22 88 59 Double Hashing 0 [ Select ] 31 22 59 15 None 28 4 10 17 88 1 [ Select ] 59 31 4 15 None 28 17 88 22 10 2 [ Select ] 10 22 4 28 31 88 17 59 15 None 3 [ Select ] 59 31 88 17 28 22 None 15 4 10 4 [ Select ] 88 31 28 10 59 4 17 15 22 None 5 [ Select ] 22 31 28 88 59 4 10 None 15 17 6 [ Select ] 59 22 4 31 10 17 28 None 15 88 7 [ Select ] 4 17 28 31 59 15 88 None 22 10 8 [ Select ] 4 15 None 22 88 28 31 59 17 10 9 [ Select ] 4 59 17 28 88 31 22 15 None 10 10 [ Select ] 4 10 88 17 28 None 31 59 15 22

查看解析

标准答案

Please login to view

思路分析

Question restatement: - We have a hash table of size 11. We insert the keys in this order: 10, 22, 31, 4, 15, 28, 17, 88, 59. We are asked for the final status (i.e., the contents of the 11 buckets) after performing the insertions using three different open addressing collision resolution techniques: linear probing with probe +1, quadratic probing, and double hashing (with H2(x) = 7 - (x % 7)). If a bucket remains empty after all insertions, it should be shown as None. - The provided interface shows, for Linear Probing +1, a list of 11 possible final values for each bucket (labeled 0 through 10); similarly for Quadratic Probing and for Double Hashing. The final answer field in the prompt gives a long sequence of candidates for each probe index across the three methods. - Our task is to reason about each option, explaining why a given final arrangement could be correct or incorrect, for each of the three probing methods. We will not simply state which option is correct; instead, we will evaluate the viability of each listed option, explain the reasoning behind why a specific arrangement could be correct or incorrect, and point out potential inconsistencies or common pitfalls for each approach. General approach to evaluating each option: - Step 1: Understand the required final state format. The table has 11 buckets (indices 0–10). After inserting 9 keys, up to 2 buckets could remain empty if there were collisions forcing some to occupy later slots; in practice, there will be exactly 2 empty buckets if every insertion found an open slot or collided and rehashed to an empty slot, but depending on the probing scheme, the exact number of empty slots can vary. We should look for exactly the appearance of the inserted keys (10, 22, 31, 4, 15, 28, 17, 88, 59) and None in buckets that could not be filled due to, for example, a full table (not the case here, since we have 9 inserts and 11 slots). - Step 2: For each probing method, recall the ......Login to view full explanation