设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为:H(key)=key % 17,采用线性测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表,并计算成功查找的平均查找度。手写过程
时间: 2023-06-23 19:10:15 浏览: 229
首先,根据散列函数 H(key) = key % 17,可以得到每个关键字的散列地址如下:
29 -> 12
01 -> 1
13 -> 13
15 -> 15
56 -> 5
20 -> 3
87 -> 4
27 -> 10
69 -> 4
9 -> 9
10 -> 10
74 -> 8
其中,有两个关键字 87 和 69 的散列地址相同,即都为 4,因此需要解决冲突。采用线性探测法,从 4 开始依次向后探测,直到找到一个空闲的散列地址。假设先找到的是 5,那么将 69 存储在地址为 5 的位置。接着,继续探测冲突的关键字 87,从 4 开始依次向后探测,发现地址为 6 和 7 都已经被占用,直到找到空闲的地址 8,将 87 存储在地址为 8 的位置。
经过冲突解决后,散列表中的关键字分布如下:
0:
1: 01
2:
3: 20
4: 74, 9
5: 56, 69
6: 27
7:
8: 87
9:
10: 29, 10
11:
12: 15
13: 13
14:
15:
16:
接下来,计算成功查找的平均查找度。对于每个关键字,查找的最大次数为散列表的长度,即 18 次。如果所有关键字都被查找到,则总的查找次数为:
18 * 12 = 216
其中,12 表示关键字的数量。因此,成功查找的平均查找度为:
216 / 12 = 18
即需要查找 18 个位置才能找到一个关键字。
相关问题
设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为:H(key)=key%11,采用线性探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表,并计算成功查找的平均查找长度。
根据散列函数H(key)=key%11,我们可以将关键字序列的散列地址计算出来:
```
key : 29 01 13 15 56 20 87 27 69 9 10 74
H(key) : 07 01 02 04 01 09 09 05 03 9 10 03
```
由于采用线性探测方法解决冲突,我们需要在散列表中寻找下一个可用的空位置。若当前位置已经被占用,则继续向后查找,直到找到一个空位置或者查找完整个散列表。
```
地址 : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
: [9] [1] [13] [56] [20] [69] [29] [87] [10] [27] [74] [3]
```
以上是构造出的散列表,用中括号括起来的数字表示该位置存储的关键字。例如,[9]表示散列地址为9的位置存储了关键字69。
接下来,我们可以计算成功查找的平均查找长度(ASL)。
对于每个关键字,它的查找长度是它在散列表中的位置与它原本的散列地址之差。例如,关键字10的查找长度为11-10=1。
成功查找的平均查找长度是所有关键字的查找长度之和除以关键字个数。在本例中,计算公式如下:
ASL = (1+1+1+1+2+1+1+1+1+1+1+1)/12 = 12/12 = 1
因此,成功查找的平均查找长度为1。
设有一组关键字 { 29,01, 13,15,56,20,87,27,69,9,10,74 },散列函数为 H(key)=key%17,采用平方探测方法解决冲突。试在 0 到 18 的散列地址空间中对该关键字序列构造散列表,则成功查找的平均查找长度为
首先,我们需要计算每个关键字在散列表中的地址:
H(29)=12
H(01)=1
H(13)=13
H(15)=15
H(56)=4
H(20)=3
H(87)=4
H(27)=10
H(69)=4
H(9)=9
H(10)=10
H(74)=8
可以看出,有多组关键字映射到了同一个散列地址,因此需要采用平方探测方法解决冲突。
接下来,我们按照平方探测方法将关键字插入散列表中。具体过程如下:
1. 将 29 插入散列表,位置为 12。
2. 将 01 插入散列表,位置为 1。
3. 将 13 插入散列表,位置为 13。
4. 将 15 插入散列表,位置为 15。
5. 将 56 插入散列表,位置为 4。
6. 将 20 插入散列表,位置为 3。
7. 将 87 插入散列表,发现位置 4 已经被占用,因此进行平方探测,插入位置为 2。
8. 将 27 插入散列表,位置为 10。
9. 将 69 插入散列表,发现位置 4 和位置 2 都已经被占用,因此进行平方探测,插入位置为 5。
10.将 9 插入散列表,位置为 9。
11.将 10 插入散列表,发现位置 10 已经被占用,因此进行平方探测,插入位置为 11。
12.将 74 插入散列表,发现位置 8 已经被占用,因此进行平方探测,插入位置为 0。
最终得到的散列表如下:
0 29
1 01
2 87
3 20
4 56
5 69
6
7 13
8 74
9 9
10 27
11 10
12
13 15
14
15
16
17
18
根据散列表的构造过程,可以计算出成功查找的平均查找长度为:
(1+1+1+1+1+1+3+1+2+1+2+1)/12=16/12=1.33
因此,成功查找的平均查找长度为 1.33。
相关推荐
![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)
![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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)