题23

题23

题目

[!error]+
Q:【2023 统考真题】现有长度为 5 ，初始为空的散列表 HT，散列函数 ，用线性探查再散列法解决冲突。若将关键字序列 2022, 12, 25 依次插入 HT 中，然后删除关键字 25 ，则 HT 中查找失败的平均查找长度📍为（ ）。
A. 1
B. 1.6
C. 1.8
D. 2.2

分析

[!NOTE]+
A:在哈希表之ASL和不成功ASL的计算(平均查找长度)里面详细说明了这个计算
算ASL不成功是每一个有元素的位置，到第一个空位置的平均查找长度，但是这里是开放定址法里面的线性探测，他说删去25，不能真的删除，只会把这个散列表的操作置为D，我们找到4这个槽位的时候，当作是有数字，执行线性探测，查找下一个位置，到0槽位，然后为空位置，也就是查找失败，这和以前做的那种是不同

解

[!done]+
题09
C
当采用开放定址法时, 不能随便物理删除表中的已有元素, 因为若删除元素, 则可能截断其他具有相同散列地址的元素的查找地址。因此, 当要删除一个元素时, 可给它做一个删除标记。 依次将 插入散列表,然后删除 25,得到的散列表如下:

地址	0	1	2	3	4
关键字		2022	12		25（删除）
查找失败次数	1	3	2	1	2

当查找位置是删除标记时, 应继续往后查找。
查找失败的平均查找长度为 。