首页 > 试题广场 >

现有长度为11且初始为空的散列表HT，散列函数是H(key)

[单选题]

现有长度为 11 且初始为空的散列表 HT，散列函数是 H(key) = key % 7，采用线性探查（线性探测再散列）法解决冲突。将关键字序列 87, 40, 30, 6, 11, 22, 98, 20 依次插入 HT 后，HT 查找失败的平均查找长度是

查看正确选项

Mapple

1. 构造散列表
根据散列函数 H(key) = key %7 以及线性再探测，我们可以构造出散列表，如下图在这里插入图片描述

2. 计算失败的平均查找长度

计算失败，可以转换理解，就是在已经构造好的散列表上，我们再去插入一个新的值需要比较多少次。

比如，现在我再插入一个数 21，那么理论上应该存放在地址 0 的位置，但是地址 0 有 98 了，则我们线性再探测（就是依次增加一个地址，看是否为空，空则可以插入），同理地址 1 也存在元素。以此类推，我们一共要比较地址 0~7，发现都有值，直到比较地址 8 才为空。所以一共比较了 9 次。

对其他地址（0~6）用同样的方式去理解，则一共比较的次数是 9+8+7+6+5+4+3 = 42

这里要注意，因为我们的模是 7，所以计算的地址只可能在（0~6）这个范围，所以最后的结果是 42/7 =6

3.计算成功的平均查找长度
计算成功的长度，就是记录下每个数值比较了几次找到可存储的空间。
比如，本题每个数值比较（并存入）对应地址的次数如下图。
在这里插入图片描述

所以其 ASL = 1+1+1+1+1+1+1+1/8=1

note
1.注意失败与成功的查找长度的分母意义是不同的，失败时，分母是模的值；成功时，分母是元素个数。

发表于 2020-12-02 15:25:33 回复(5)

suhan_

通过取余的方式把关键字填入HT之后得到：

散列地址	0	1	2	3	4	5	6	7	8	9	10
关键字	98	22	30	87	11	40	6	20

分母：因为取余的模是 7，所以分母是 7。
分子：因为是查找失败的次数，所以第一个0号地址，（包括它自己）要向后走9次才能到达空的关键字。其他的关键字同理，数出到达空的关键字的次数。

所以是 9+8+7+6+5+4+3 = 42

ASL失败 = 42 / 7 = 6。

发表于 2024-11-21 00:15:43 回复(0)

阿达1248

老哥，看完你第一句就懂了！棒棒哒！！！

发表于 2022-04-12 16:38:06 回复(0)

提交观点

问题信息

2019 Java工程师

上传者：小小

难度：

3条回答 44收藏 11449浏览