设哈希表的地址范围为0~17,哈希函数为:H(key)=key%16。用线性探测法处理冲突,输入关键字序列:(10,24,32,17,31,30,46,47,40,63,49),构造哈希表,试回答下列问题: ① 画出哈希表的示意图; ② 若查找关键字63,需要依次与哪些关键字进行比较? ③ 若查找关键字60,需要依次与哪些关键字比较? ④ 假定每个关键字的查找概率相等,求查找成功时的平均查找长度。
时间: 2023-11-28 15:03:57 浏览: 892
好的,我来回答你的问题。
首先,我们按照哈希函数 H(key)=key%16 将关键字序列映射到哈希表中,并使用线性探测法处理冲突,得到哈希表如下:
| 索引 | 哈希值 | 关键字 |
| ---- | ------ | ------ |
| 0 | 0 | |
| 1 | 1 | |
| 2 | 2 | 32 |
| 3 | 3 | 17 |
| 4 | 4 | |
| 5 | 5 | 30 |
| 6 | 6 | 46 |
| 7 | 7 | 47 |
| 8 | 8 | 24 |
| 9 | 9 | 40 |
| 10 | 10 | 10 |
| 11 | 11 | 31 |
| 12 | 12 | |
| 13 | 13 | |
| 14 | 14 | 49 |
| 15 | 15 | 63 |
| 16 | 0 | |
| 17 | 1 | |
其中,哈希表的地址范围为 0~17,共 18 个地址,但是只存储了 11 个关键字,因此有些位置为空。
接下来回答你的问题:
① 哈希表的示意图如下:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| - | - | - | - | - | - | - | - | - | - | -- | -- | -- | -- | -- | -- | -- | -- |
| | | 32| 17| | 30| 46| 47| 24| 40| 10 | 31 | | | 49| 63| | |
② 如果要查找关键字 63,它的哈希值为 15,按照线性探测法的规则,我们需要依次查找哈希表中索引位置 15、16、0、1,最终找到了关键字 63。
因此,查找关键字 63 需要依次与关键字 15、17、0、1 进行比较。
③ 如果要查找关键字 60,它的哈希值为 12,按照线性探测法的规则,我们需要依次查找哈希表中索引位置 12、13、14、15、16、0、1、2、3、4、5,直到找到一个空闲位置或者查找到关键字 60。
因此,查找关键字 60 需要依次与关键字 12、13、14、15、0、1、2、3、4、5 进行比较。
④ 假设每个关键字的查找概率相等,那么查找成功时的平均查找长度为:
ASL = (1 * P1 + 2 * P2 + 3 * P3 + ... + k * Pk) / n
其中,P1、P2、P3 等是查找关键字时经过 1、2、3 次探测的概率,k 是查找关键字时最终经过的探测次数,n 是表中关键字的总数。
根据题目中给出的哈希函数和关键字序列构造哈希表后的结果,我们可以得到以下概率:
P1 = 11/18 = 0.6111
P2 = 6/18 = 0.3333
P3 = 1/18 = 0.0556
如果查找关键字 63,它的平均查找长度为:
ASL = (1 * 0.6111 + 2 * 0.3333 + 3 * 0.0556) / 11 = 0.9722 / 11 = 0.0884
因此,查找成功时的平均查找长度为 0.0884。