设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为:H(key)=key 00000000% 17,采用线性测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表,并计算成功查找的平均查找度。手写过程在0到18的散列地址空间中
时间: 2023-06-23 21:09:41 浏览: 44
首先,我们需要构造一个长度为 19 的散列表,因为散列地址空间是从 0 到 18。
然后,根据散列函数 H(key) = key % 17,我们可以得到每个关键字的散列地址:
29 % 17 = 12
01 % 17 = 1
13 % 17 = 13
15 % 17 = 15
56 % 17 = 5
20 % 17 = 3
87 % 17 = 4
27 % 17 = 10
69 % 17 = 4
9 % 17 = 9
10 % 17 = 10
74 % 17 = 8
其中,关键字 87 和 69 发生了冲突,因为它们的散列地址都是 4。根据线性探测法,我们需要依次向后查找空闲的散列地址,直到找到一个空闲的地址为止。在这种情况下,我们可以将关键字 69 存储在散列地址 5 上,因为散列地址 5 是 4 后面的第一个空闲地址。
最终的散列表如下:
0:
1: 01
2:
3: 20
4: 87
5: 69
6: 10
7: 74
8: 56
9: 9
10: 27
11:
12: 29
13: 13
14:
15: 15
16:
接下来,我们可以计算成功查找的平均查找度。假设我们要查找关键字 27。根据散列函数,它的散列地址是 10。因此,我们首先在散列地址 10 上查找,发现关键字并不在那里。然后,我们依次向后查找,直到找到关键字或者遇到一个空闲地址。在这种情况下,我们需要查找散列地址 11、12、13、14、15、16、0、1、2、3、4、5 共 12 次,才能找到关键字 27。
同样地,我们可以对每个关键字进行查找,然后计算它们的平均查找度。最终的平均查找度是:
(1 + 1 + 1 + 1 + 1 + 1 + 2 + 1 + 1 + 2 + 1 + 12) / 12 = 1.75
因此,成功查找的平均查找度为 1.75。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)