题21

题21

题目

Q:【2019 统考真题】现有长度为 11 且初始为空的散列表 HT，散列函数是 key%7, 采用线性探查（线性探测再散列）法解决冲突.
将关键字序列 87,40,30,6,11,22,98,20依次插入 HT 后，HT 查找失败的平均查找长度是( )
A. 4
B. 5.25
C. 6
D. 6.29

分析

A:和题20对比起来看散列表的ASL成功还有ASL失败是怎么计算的

我这里是算错了

解

C
采用线性探查法计算每个关键字的存放情况如下表所示。

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

由于 $\mathrm{H}( \mathrm{{key}}) = 0 \sim 6$ ,查找失败时可能对应的地址有 7 个,对于计算出地址为 0 的关键字 key 0,只有比较完 $0 \sim 8$ 号地址后才能确定该关键字不在表中,比较次数为 9 ; 对于计算出地址为 1 的关键字 key 1,只有比较完 $1 \sim 8$ 号地址后才能确定该关键字不在表中,比较次数为 8 ; 以此类推。 需要特别注意的是, 散列函数不可能计算出地址 7 , 因此有 $$ {\mathrm{{ASL}}}_{\text{失败 }} = ( {9 + 8 + 7 + 6 + 5 + 4 + 3}) /7 = 6 $$