设关键字序列为{15,7,22,18,3,11,26,16,24,29},哈希表表长为13,哈希函数为 H(key)=keymod13,用线性探测法处理冲突,请回答以下问题:(1)按照关键字的给定次序,构造哈希表;(2)计算查找关键字22,26,29时的比较次数;(3)计算查找成功情况下,哈希表的平均查找长度(ASL)。
时间: 2024-04-28 13:23:21 浏览: 11
(1) 按照关键字的给定次序,构造哈希表:
关键字 | 哈希地址
-------|--------
15 | 2
7 | 7
22 | 9
18 | 8
3 | 3
11 | 11
26 | 0
16 | 3(冲突,线性探测1步)
24 | 11(冲突,线性探测1步)
29 | 3(冲突,线性探测2步)
哈希表:[26, 7, 18, 15, -1, -1, -1, -1, -1, 22, 24, 11, 29]
(2) 计算查找关键字22,26,29时的比较次数:
查找22:H(22)=9,比较1次,找到;
查找26:H(26)=0,比较1次,冲突,线性探测1步,比较2次,找到;
查找29:H(29)=3,比较1次,冲突,线性探测2步,比较3次,找到。
(3) 计算查找成功情况下,哈希表的平均查找长度(ASL):
ASL = (1*1 + 1*2 + 1*3) / 3 = 2
注:ASL指的是平均查找长度,即查找成功时需要查找的次数的平均值。在这个例子中,共进行了3次查找成功,需要查找的次数分别是1, 1, 3,所以ASL = (1*1 + 1*2 + 1*3) / 3 = 2。
相关问题
设有一组初始关键字序列为 (24,35,12,27,18,26),则第3趟直接插入排序结束后的结果的是
在第3趟直接插入排序中,前三个关键字已经有序,第四个关键字27需要插入到前面有序子序列中。
(24,35,12,27,18,26) -> (12,24,35,27,18,26)
然后,前四个关键字已经有序,第五个关键字18需要插入到前面有序子序列中。
(12,24,35,27,18,26) -> (12,18,24,35,27,26)
最后,前五个关键字已经有序,第六个关键字26需要插入到前面有序子序列中。
(12,18,24,35,27,26) -> (12,18,24,27,35,26)
经过3趟直接插入排序后,得到的有序序列为(12,18,24,27,35,26),其中,26需要再次插入到前面有序子序列中,最终得到完全有序序列为(12,18,24,26,27,35)。
设有一组初始关键字序列为(24,35,12,27,18,26),则第3趟直接插入排序结束后的结果的是
在第3趟直接插入排序结束后,前三个关键字已经有序,因此只需要将第4个关键字27插入到前面的有序序列中即可。插入过程如下:
1. 从序列中取出第4个关键字27。
2. 将27依次与前面的有序序列中的关键字进行比较,找到27插入的位置。
3. 在比较过程中,发现27大于12,因此将12向后移动一位,得到序列(24,35,12,27,18,26)。
4. 继续比较,发现27大于24,因此将27插入到24和35之间,得到序列(24,27,35,12,18,26)。
5. 第3趟直接插入排序结束后的结果为(24,27,35,12,18,26)。
因此,第3趟直接插入排序结束后的结果为(24,27,35,12,18,26)。
相关推荐
![](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)
![](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)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)