对于输入30,20,56,75,31,19和散列函数h(K)=Kmd11,做以 a.构造它们的闭散列表。" b.求在本表中成功查找的最大键值比较次数。 c.求本表中成功查找的平均键值比较次数。
时间: 2024-01-24 17:19:48 浏览: 33
a. 构造闭散列表
首先需要确定散列表的大小,由于输入的数据数量为7个,可以选择散列表大小为10。接下来,我们需要将每个关键字进行散列计算,并进行插入操作。
计算过程如下:
- h(30) = 30 * 3 mod 11 = 9
- h(20) = 20 * 3 mod 11 = 8
- h(56) = 56 * 3 mod 11 = 8
- h(75) = 75 * 3 mod 11 = 5
- h(31) = 31 * 3 mod 11 = 8
- h(19) = 19 * 3 mod 11 = 8
由于有三个关键字(20、56、31)散列后的结果相同,因此需要使用开放地址法进行处理。一种简单的开放地址法是线性探测,在这里我们使用线性探测法解决冲突。
插入过程如下:
- 30 -> 9
- 20 -> 8
- 56 -> 8 (冲突,线性探测到下一个位置)
- 56 -> 9 (冲突,线性探测到下一个位置)
- 56 -> 10 (冲突,线性探测到下一个位置)
- 56 -> 0 (冲突,线性探测到下一个位置)
- 56 -> 1 (冲突,线性探测到下一个位置)
- 56 -> 2 (冲突,线性探测到下一个位置)
- 56 -> 3 (冲突,线性探测到下一个位置)
- 56 -> 4 (冲突,线性探测到下一个位置)
- 75 -> 5
- 31 -> 8 (冲突,线性探测到下一个位置)
- 31 -> 9 (冲突,线性探测到下一个位置)
- 31 -> 10 (冲突,线性探测到下一个位置)
- 31 -> 0 (冲突,线性探测到下一个位置)
- 31 -> 1 (冲突,线性探测到下一个位置)
- 31 -> 2 (冲突,线性探测到下一个位置)
- 31 -> 3 (冲突,线性探测到下一个位置)
- 31 -> 4 (冲突,线性探测到下一个位置)
- 19 -> 8 (冲突,线性探测到下一个位置)
- 19 -> 9 (冲突,线性探测到下一个位置)
- 19 -> 10 (冲突,线性探测到下一个位置)
- 19 -> 0 (冲突,线性探测到下一个位置)
- 19 -> 1 (冲突,线性探测到下一个位置)
- 19 -> 2 (冲突,线性探测到下一个位置)
- 19 -> 3 (冲突,线性探测到下一个位置)
- 19 -> 4 (冲突,线性探测到下一个位置)
最终得到的闭散列表为:
|位置|0|1|2|3|4|5|6|7|8|9|
|---|---|---|---|---|---|---|---|---|---|---|
|关键字|56|75|31|19|20|30|||||
b. 求在本表中成功查找的最大键值比较次数。
在本表中,最大的键值为75。假设要查找这个键值,它散列后的位置为5。查找过程如下:
- 比较位置5的关键字,发现不是要查找的75。
- 线性探测到位置6,比较关键字,不是75。
- 线性探测到位置7,比较关键字,不是75。
- 线性探测到位置8,比较关键字,是75。
因此,在本表中成功查找的最大键值比较次数为4。
c. 求本表中成功查找的平均键值比较次数。
假设成功查找的次数为k,散列表大小为m,则平均键值比较次数为k/m。在本表中,成功查找的键值有6个,散列表大小为10,因此平均键值比较次数为6/10=0.6。