10.设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77},其哈希函数为h(key)=key % 13。采用开放地址法的线性探测法解决冲突,试在0~18的哈希表中对该关键字序列构造哈希表,并求在成功和不成功情况下的平均查找长度。 (1) 填空题 构建出哈希表如表1所示。 表中探测次数为相应关键字成功查找时所需比较关键字的次数。 请将上表中标序号的地方填写完整,左边一列在“key、下标”这两个词中选:(a)______;(b)______; 右边各列填数据,空缺的地方填小写的a: (0)~(9)依次为__________(请直接写出数据或字母a,中间以一个空格隔开,如1 2 a 3 4 a 5,不用加其他符号,下面的填写也用同样的规则); (20)~(38)依次为__________。 由上表可求出ASL成功=__________,求的过程中所用分母为____。 第1空: 下标 第2空: key 第3空: 第4空: 第5空: 第6空: (2) 填空题 查找不成功表示在表中未找到指定关键字的记录,可得到如表2所示结果。 表2 不成功查找的探测次数 表2除最后一行外,其他同表1,不用填;只在最后一行填数据。 (20)~(38)依次为__________。 由上表可求出ASL不成功=__________,求的过程中所用分母为____。 第1空: 第2空: 第3空:
时间: 2023-06-19 17:06:07 浏览: 284
(a) 下标;(b) key
(0) 55 1 14 27 68 11 77 a 19 20
(1) 1 84 a a a a a a a a
(2) 23 a a a a a a a a a
(3) 14 a a a a a a a a a
(4) a a a a a a a a a a
(5) 19 a a a a a a a a a
(6) a a a a a a a a a a
(7) a a a a a a a a a a
(8) a a a a a a a a a a
(9) 10 a a a a a a a a a
(10)~(18) a a a a a a a a a a
(20)~(38) 14 27 27 27 27 11 11 11 68 68 77 a a a a a a a a a a
ASL成功=3.1818,分母为11
(20) 14 27 27 27 27 11 11 11 68 68 77 a a a a a a a a a a
ASL不成功=2.8182,分母为11
相关问题
9.设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链接法构造散列表,散列函数为H(key)=key MOD 13,散列地址为1的链中有()个记录。
将关键字用散列函数H(key)=key MOD 13计算散列地址,得到的散列地址如下:
| key | H(key) |
| --- | --- |
| 19 | 6 |
| 14 | 1 |
| 23 | 10 |
| 1 | 1 |
| 68 | 5 |
| 20 | 7 |
| 84 | 4 |
| 27 | 1 |
| 55 | 3 |
| 11 | 11 |
| 10 | 10 |
| 79 | 12 |
其中,散列地址为1的链中有3个记录,即14、1、27。
设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用散列函数H(key)=key%13,采用开放地址法的二次探测再散列方法解决冲突,试在0~18的散列地址空间中对该关键字序列构造散列表。
好的,让我来回答你的问题。
根据题目中所给的关键字和散列函数,我们可以得到以下散列地址:
- 19 -> 6
- 01 -> 1
- 23 -> 10
- 14 -> 1
- 55 -> 3
- 20 -> 7
- 84 -> 11
- 27 -> 1
- 68 -> 4
- 11 -> 11
- 10 -> 10
- 77 -> 5
其中,关键字14和27的散列地址与关键字01相同,发生了冲突。我们可以采用开放地址法中的二次探测再散列方法解决冲突。具体地,如果第一次散列地址为h,冲突解决的第i步散列地址为:
$h_i = (h + c_1i + c_2i^2) \mod m$
其中,c1和c2是正整数,m是散列表的大小。
在本题中,我们可以取c1=1,c2=3,m=13。则,关键字14的散列地址为2,关键字27的散列地址为12。最终的散列表如下:
- 0:
- 1: 01
- 2: 14
- 3: 55
- 4: 68
- 5: 77
- 6: 19
- 7: 20
- 8:
- 9: 23
- 10: 10
- 11: 84, 11
- 12: 27
这样,我们就成功地构造出了一个散列表,其中每个关键字都被正确地插入到了对应的散列地址处。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![xlsx](https://img-home.csdnimg.cn/images/20210720083732.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)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)