设有一组关键字 { 29,01, 13,15,56,20,87,27,69,9,10,74 },散列函数为 H(key)=key%17,采用平方探测方法解决冲突。试在 0 到 18 的散列地址空间中对该关键字序列构造散列表,则成功查找的平均查找长度为 __
时间: 2024-02-29 18:56:57 浏览: 138
详解Java 10 var关键字和示例教程
5星 · 资源好评率100%
根据题意,我们可以按照以下步骤构造散列表:
1. 创建一个大小为 19 的散列表,其中下标为 0 到 18。
2. 对于每个关键字 key,计算其散列地址 h = key % 17,如果该地址已经被占用,则使用平方探测方法探测下一个地址,直到找到一个空闲位置为止。
3. 将该关键字存储在散列表中对应的位置。
按照上述方法,我们可以得到以下散列表:
```
0: 01
1: 27
2: 15
3: 74
4: 56
5: 20
6: 87
7: 29
8:
9: 9
10: 10
11: 69
12: 13
13:
14:
15:
16:
17:
18:
```
其中,关键字 29、27、13、15、56、20、87、01、9、10、74 分别被散列到了下标为 7、1、12、3、4、5、6、0、9、10、3 的位置。注意,有些地址上出现了冲突,需要使用平方探测方法找到下一个空闲位置。
成功查找的平均查找长度是指在散列表中查找一个已知的关键字时,平均需要比较的次数。它可以通过以下公式计算:
```
平均查找长度 = 所有关键字的查找长度之和 / 关键字总数
```
在本例中,共有 12 个关键字需要查找。我们可以分别计算出这些关键字在散列表中的查找长度,然后求和并除以 12,即可得到平均查找长度。
关键字 29 在下标为 7 处,查找长度为 1。
关键字 01 在下标为 0 处,查找长度为 1。
关键字 13 在下标为 12 处,查找长度为 1。
关键字 15 在下标为 3 处,查找长度为 1。
关键字 56 在下标为 4 处,查找长度为 1。
关键字 20 在下标为 5 处,查找长度为 1。
关键字 87 在下标为 6 处,查找长度为 1。
关键字 27 在下标为 1 处,查找长度为 1。
关键字 69 在下标为 11 处,查找长度为 1。
关键字 9 在下标为 9 处,查找长度为 1。
关键字 10 在下标为 10 处,查找长度为 1。
关键字 74 在下标为 3 处,经过 1 次平方探测后查找到,查找长度为 2。
将所有关键字的查找长度之和除以 12,得到:
```
(1+1+1+1+1+1+1+1+1+1+1+2) / 12 = 11 / 12 ≈ 0.917
```
因此,成功查找的平均查找长度为约为 0.917。
阅读全文