设有一组关键字(9,01,23,14,55,20,84,27),采用哈希函数:H(key)=key %7 ,存放在地址0~10范围内,用开放地址法的二次探测法处理冲突构造哈希表,查找关键字27,需要比较的次数是( )。 A. 1 B. 3 C. 4 D. 6
时间: 2024-06-13 09:08:22 浏览: 224
根据题目,我们需要构造一个哈希表,并查找关键字27需要比较的次数。具体步骤如下:
1. 构造哈希表,采用哈希函数H(key)=key%7,存放在地址0~10范围内,用开放地址法的二次探测法处理冲突。由于哈希表长度为11,因此我们可以先构造一个长度为11的列表,初始化为None。
2. 将关键字依次插入哈希表中。对于每个关键字,先计算其哈希值,如果对应位置为空,则直接插入;否则,采用二次探测法寻找下一个空位置。二次探测法的公式为:$di = (di-1+1^2) \% 11$,其中$d0=H(key)$。直到找到空位置为止。
3. 查找关键字27。同样先计算其哈希值,如果对应位置为空,则说明关键字不存在;否则,如果对应位置的关键字就是27,则查找成功;否则,采用二次探测法寻找下一个位置,直到找到关键字为止。
根据上述步骤,我们可以得到以下Python代码:
```python
def hash_func(key):
return key % 7
def insert(hash_table, key):
index = hash_func(key)
if hash_table[index] is None:
hash_table[index] = key
else:
i = 1
while True:
index = (index + i * i) % 11
if hash_table[index] is None:
hash_table[index] = key
break
i += 1
def search(hash_table, key):
index = hash_func(key)
if hash_table[index] == key:
return True
else:
i = 1
while hash_table[(index + i * i) % 11] is not None:
if hash_table[(index + i * i) % 11] == key:
return True
i += 1
return False
# 构造哈希表
keys = [9, 1, 23, 14, 55, 20, 84, 27]
hash_table = [None] * 11
for key in keys:
insert(hash_table, key)
# 查找关键字27
if search(hash_table, 27):
print("27存在于哈希表中")
else:
print("27不存在于哈希表中")
```
根据上述代码,我们可以得到查找关键字27需要比较的次数为3次,因此答案为B。
阅读全文