设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为:H(key)=key % 17,采用线性测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表,并计算成功查找的平均查找度。手写过程
时间: 2023-08-31 18:20:11 浏览: 202
### 回答1:
首先构造一个长度为18的散列表,初始时所有位置均为空。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
接下来对每个关键字进行散列,计算其散列地址。由于散列函数为 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
然后按照线性探测法的规则,将每个关键字插入到其散列地址处,如果该位置已经被占用,则依次往后探测,直到找到一个空闲位置为止。具体过程如下:
- 29 -> 12
- 01 -> 1
- 13 -> 13
- 15 -> 15
- 56 -> 5
- 20 -> 3
- 87 -> 4
- 27 -> 10
- 69 -> 4 (冲突,线性探测)
- 9 -> 9
- 10 -> 10
- 74 -> 8
最终得到的散列表如下所示:
| 9 | 1 | 20 | 87 | 69 | 56 | 13 | 74 | 15 | 29 | 10 | 27 | 12 | | | 3 | | 4 |
其中,每个位置上的数字表示该位置存放的关键字,空位置用竖线“|”表示。
计算平均查找度的公式为:ASL = (成功查找时的平均查找长度 + 不成功查找时的平均查找长度) / 总记录数。
假设我们要查找关键字 20,由于 H(20) = 3,因此首先查找散列表中下标为 3 的位置。发现该位置存放的是关键字 20,因此查找成功,平均查找长度为 1。
对于不成功查找,可以假设要查找的关键字在散列表中不存在,此时需要从散列表中的每个位置依次开始搜索,直到找到一个空位置或搜索完整个散列表。由于这里的散列表长度比较小,我们可以手动模拟出所有可能的情况,并计算平均查找长度。不妨假设要查找的关键字为 99,那么所有可能的情况如下所示:
1. 0 -> 99 (ASL = 1)
2. 1 -> 99 (ASL = 2)
3. 2 -> 99 (ASL = 3)
4. 3 -> 空 (ASL = 4)
5. 4 -> 99 (ASL = 5)
6. 5 -> 99 (ASL = 6)
7. 6 -> 99 (ASL = 7)
8. 7 -> 99 (ASL = 8)
9. 8 -> 99 (ASL = 9)
10. 9 -> 空 (ASL = 10)
11. 10 -> 99 (ASL = 11)
12. 11 -> 99 (ASL = 12)
13. 12 -> 99 (ASL = 13)
14. 13 -> 99 (ASL = 14)
15. 14 -> 99 (ASL = 15)
16. 15 -> 99 (ASL = 16)
17. 16 -> 空 (ASL = 17)
根据公式,成功查找时的平均查找长度为 1,不成功查找时的平均查找长度为 (1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17) / 18 = 9。
因此,平均查找度为 (1+9) / 12 ≈ 0.83,即成功查找一次需要搜索 0.83 个位置。
### 回答2:
根据散列函数H(key) = key % 17,我们需要将关键字序列{29,01,13,15,56,20,87,27,69,9,10,74}映射到0到18的散列地址空间中。
首先,我们创建一个长度为19的散列表,初始化所有的位置为空。
然后,根据散列函数计算每个关键字的散列地址并插入到散列表中:
散列地址 = 关键字 % 17
29的散列地址 = 29 % 17 = 12,插入到地址为12的位置
01的散列地址 = 01 % 17 = 1,插入到地址为1的位置
13的散列地址 = 13 % 17 = 13,插入到地址为13的位置
15的散列地址 = 15 % 17 = 15,插入到地址为15的位置
...
依次类推
如果某个位置已经被占用,采用线性探测方法解决冲突,即往后寻找下一个空闲位置。
最终,散列表中的关键字分布如下:
0:空
1:01
2:15
3:15
4:空
5:56
6:20
7:空
8:空
9:69
10:10
11:空
12:29
13:13
14:空
15:27
16:74
17:87
18:空
计算成功查找的平均查找度,需要统计每个关键字在查找时的查找次数,并求平均值。
关键字29的查找次数为1
关键字01的查找次数为1
关键字13的查找次数为1
关键字15的查找次数为1
关键字56的查找次数为1
关键字20的查找次数为1
关键字87的查找次数为1
关键字27的查找次数为1
关键字69的查找次数为1
关键字9的查找次数为1
关键字10的查找次数为1
关键字74的查找次数为1
因此,成功查找的平均查找度为1。
需要注意的是,由于散列函数和冲突解决方法的选择,该散列表具有较低的冲突率。若冲突较多,则平均查找度可能会有所提高。
### 回答3:
首先,我们需要创建一个大小为19的散列表(0到18的散列地址空间)。然后,按照散列函数H(key)=key % 17,将关键字序列依次插入到散列表中。
插入第一个关键字29:
H(29) = 29 % 17 = 12
散列表:[ , , , , , , , , , , , , 29, , , , , , ]
插入第二个关键字01:
H(01) = 01 % 17 = 1
散列表:[ , 01, , , , , , , , , , , 29, , , , , , ]
插入第三个关键字13:
H(13) = 13 % 17 = 13
散列表:[ , 01, , , , , , , , , , , 29, 13, , , , , ]
插入第四个关键字15:
H(15) = 15 % 17 = 15
散列表:[ , 01, , , , , , , , , , , 29, 13, 15, , , , ]
插入第五个关键字56:
H(56) = 56 % 17 = 5
散列表:[ , 01, , , , 56, , , , , , , 29, 13, 15, , , , ]
插入第六个关键字20:
H(20) = 20 % 17 = 3
散列表:[ , 01, , 20, , 56, , , , , , , 29, 13, 15, , , , ]
插入第七个关键字87:
H(87) = 87 % 17 = 9
散列表:[ , 01, , 20, , 56, , , , 87, , , 29, 13, 15, , , , ]
插入第八个关键字27:
H(27) = 27 % 17 = 10
散列表:[ , 01, , 20, , 56, , , , 87, 27, , 29, 13, 15, , , , ]
插入第九个关键字69:
H(69) = 69 % 17 = 4
散列表:[ , 01, , 20, 69, 56, , , , 87, 27, , 29, 13, 15, , , , ]
插入第十个关键字9:
H(9) = 9 % 17 = 9 (发生冲突)
线性探测法解决冲突,尝试下一个位置:
H(9) + 1 = 10
散列表:[ , 01, , 20, 69, 56, , , , 87, 27, 9, 29, 13, 15, , , , ]
插入第十一个关键字10:
H(10) = 10 % 17 = 10 (发生冲突)
线性探测法解决冲突,尝试下一个位置:
H(10) + 1 = 11
散列表:[ , 01, , 20, 69, 56, , , , 87, 27, 9, 10, 29, 13, 15, , , , ]
插入第十二个关键字74:
H(74) = 74 % 17 = 8
散列表:[ , 01, , 20, 69, 56, , , 74, 87, 27, 9, 10, 29, 13, 15, , , , ]
最终得到的散列表为:
[ , 01, , 20, 69, 56, , , 74, 87, 27, 9, 10, 29, 13, 15, , , , ]
成功查找的平均查找度计算方法如下:
查找度 = (查找成功时的比较次数 + 1) / 2
总的查找度 = 所有关键字的查找度之和
计算关键字29的查找度:(1+1)/2 = 1
计算关键字01的查找度:(1+1)/2 = 1
计算关键字13的查找度:(1+1)/2 = 1
计算关键字15的查找度:(1+1)/2 = 1
计算关键字56的查找度:(1+1)/2 = 1
计算关键字20的查找度:(1+1)/2 = 1
计算关键字87的查找度:(1+1)/2 = 1
计算关键字27的查找度:(1+1)/2 = 1
计算关键字69的查找度:(1+1)/2 = 1
计算关键字9的查找度:(2+1)/2 = 1.5
计算关键字10的查找度:(2+1)/2 = 1.5
计算关键字74的查找度:(1+1)/2 = 1
总的查找度 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1.5 + 1.5 + 1 = 13
成功查找的平均查找度 = 总的查找度 / 插入关键字的数量 = 13 / 12 = 1.083
因此,成功查找的平均查找度为1.083。
阅读全文