🏷️ 知识点：平均查找长度
在关键字随机分布的情况下，用二分查找树的方法进行查找，其平均查找长度与（ ）量级相当。
A. 顺序查找 B. 折半查找 C. 分块查找 D. 散列查找
[tag_link]
正确答案：B
在关键字随机分布的情况下，构建的二分查找树（BST）通常趋于平衡，树的高度平均为 O(log n)，其中 n 是关键字的数量。 因此，使用二分查找树进行查找的平均查找长度（ASL）量级为 O(log n)。 折半查找（即二分查找）在有序数组上进行，每次比较后将搜索范围减半，其平均查找长度也是 O(log n) 量级。 顺序查找的 ASL 为 O(n)，分块查找的 ASL 介于顺序查找和折半查找之间，通常优于 O(n) 但不如 O(log n)，而散列查找在理想情况下 ASL 为 O(1)。 因此，二分查找树在随机分布下的平均查找长度与折半查找同属于对数量级。
现有长度为 11 且初始为空的散列表 HT，散列函数是 H(key)=key%7，采用线性探查（线性探测再散列）法解决冲突将关键字序列 87，40，30，6，11，22，98，20 依次插入到 HT 后，HT 查找失败的平均查找长度是（ ）。
A. 4 B. 5.25 C. 6 D. 6.29
[tag_link]
正确答案：C
构造
散列表
只有当遇到关键字为空的地址时才会查找失败，key%7 之后，初始地址只可能在 06，所以即 06 到空地址的距离求平均，即为查找失败的平均查找长度初始地址是 0 的失败查找长度为 9，同理得初始地址为 1，2，3，4，5，6 的失败查找长度为 8，7，6，5，4，3，(9+8+7+6+5+4+3)/7 = 6 答案是 C。
具有 12 个关键字的有序表中，对每个关键字的查找概率相同，折半查找查找成功和查找失败的平均查找长度依次为（ ）。
A. 37/12,49/13 B. 35/12,39/13 C. 37/13,49/13 D. 37/12,49/12
[tag_link]
正确答案：A
对于有序表折半查找，平均查找长度（ASL）需通过二叉判定树计算。 成功查找的 ASL 是找到每个关键字所需比较次数的平均值，失败查找的 ASL 是查找失败时比较次数的平均值。
首先构建 12 个关键字的判定树。 根节点为关键字 6（深度 1），左子树包含关键字 1~5，右子树包含关键字 7~12。 递归划分得到各关键字深度（即比较次数）：关键字 1、4、7、11 深度 3； 关键字 2、5、8、10、12 深度 4； 关键字 3、9 深度 2； 关键字 6 深度 1。 比较次数总和为 37，成功 ASL = 37/12。
失败查找对应判定树的外部节点，共 13 个。 外部节点的比较次数等于其父节点的深度：深度为 3 的父节点（关键字 1、4、7）对应 3 个外部节点，各比较 3 次； 深度为 4 的父节点（关键字 2、5、8、10、12）对应 10 个外部节点，各比较 4 次。 比较次数总和为 3×3 + 4×10 = 49，失败 ASL = 49/13。
因此，成功和失败的平均查找长度依次为 37/12 和 49/13，对应选项 A。
现有长度为 7、初始为空的散列表 HT，散列函数 H(k) = k % 7，用线性探测再散列法解决冲突。将关键字 22, 43, 15 依次插人到 HT 后，查找成功的平均查找长度是（ ）
A. 1.5 B. 1.6 C. 2 D. 3
[tag_link]
正确答案：C
可以构造得到如下的 HT：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 关键词 | 22 | 43 | 15 |
成功时的平均查找长度 = (1+2+3)/3 = 2。
现有长度为 5，初始为空的散列表 HT，散列表函数 H(k) = (k+4) % 5 用线性探查再散列法解决冲突。若将关键字序列 2022,12,25 依次插入 HT 中，然后删除关键字 25，则 HT 中查找失败的平均查找长度（ ）。
A. 1 B. 1.6 C. 1.8 D. 2.2
[tag_link]
正确答案：C
线性探测再散列法中删除一个关键字会导致后面的关键字无法通过线性探测找到正确的位置。当删除一个关键字时，为了保持散列表的连续性，通常会将后续的关键字向前移动填充空缺，这样后续的查找操作才能继续正确地找到它们。然而，如果删除的是一个位于中间位置的关键字，后面的关键字需要依次向前移动，这会导致删除操作的时间复杂度较高，因为需要移动大量的关键字。为了解决删除操作中的位置依赖性问题，可以使用删除标记来表示一个位置上的关键字已被删除。如下表所示，查找失败的平均查找长度为 (1+3+2+1+2)/5=1.8。本题答案选 C。
| 地址 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Key | 2022 | 12 | 25 (delete) | ||
| 查找失败次数 | 1 | 3 | 2 | 1 | 2 |
将关键字序列 ⟨7,8,30,11,18,9,14⟩ 散列存储到散列表中。散列表的存储空间是一个下标从 0 开始的一维数组，散列函数为 H(key)=(key×3)mod7 ，处理冲突采用线性探测再散列法，要求装填（载）因子为 0.7 。
(1) 请画出所构造的散列表。
(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。
[tag_link]
1）由装载因子为 0.7, 数据总数为 7, 得一维数组大小为 7/0.7= 10, 数组下标为 0~9。所构造的散列函数值见下表。
| key | 7 | 8 | 30 | 11 | 18 | 9 | 14 |
|---|---|---|---|---|---|---|---|
| H(key) | 0 | 3 | 6 | 5 | 5 | 6 | 0 |
采用线性探测再散列法处理冲突，所构造的散列表见下表。
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 关键词 | 7 | 14 | 8 | 11 | 30 | 18 | 9 |
2）查找成功时，是根据每个元素查找次数来计算平均长度的，在等概率的情况下，各关键字的查找次数见下表。
| key | 7 | 8 | 30 | 11 | 18 | 9 | 14 |
|---|---|---|---|---|---|---|---|
| 次数 | 1 | 1 | 1 | 1 | 3 | 3 | 2 |
ASL成功 = 查找次数/元素个数 = (1 + 2 + 1 + 1 + 1 + 3 + 3)/7 = 12/7。
这里要特别防止惯性思维。查找失败时，是根据查找失败位置计算平均次数，根据散列函数 mod7，初始只可能在 06 的位置。等概率情况下，查找 06 位置查找失败的查找次数见下表。
| H(key) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 次数 | 3 | 2 | 1 | 2 | 1 | 5 | 4 |
ASL不成功 = 查找次数/散列后地址个数 = (3 + 2 + 1 + 2 + 1 + 5 + 4)/7 = 18/7。
设包含 4 个数据元素的集合 S = { “do”, “for”, “repeat”, “while” }，各元素的查找概率依次为：p1=0.35，p2=0.15，p3=0.15，p4=0.35。将 S 保存在一个长度为 4 的顺序表中，采用折半查找法，查找成功时的平均查找长度为 2.2 。请回答：
(1) 若采用顺序存储结构保存 S ，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
(2) 若采用链式存储结构保存 S ，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
1）折半查找要求元素有序顺序存储，若各个元素的查找概率不同，则折半查找的性能不一定优于顺序查找。采用顺序查找时，元素按其查找概率的降序排列时查找长度最小。采用顺序存储结构，数据元素按其查找概率降序排列。采用顺序查找方法。查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。此时，显然查找长度比折半查找的更短。
2）答案一：采用链式存储结构时，只能采用顺序查找，其性能和顺序表一样，类似于上题。数据元素按其查找概率降序排列，构成单链表。采用顺序查找方法。查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。答案二：还可以构造成二叉排序树的形式。采用二叉链表的存储结构，构造二叉排序树，元素的存储方式见下图。采用二叉排序树的查找方法。
查找成功时的平均查找长度=0.15×1+0.35×2+0.35×2+0.15×3=2.0。【评分说明】①若考生以实际元素表示“降序排列”，同样给分。②若考生正确求出与其查找方法对应的查找成功时的平均查找长度，给 2 分；若计算过程正确，但结果错误，给 1 分。③考生给出其他更高效的查找方法且正确，可参照评分标准给分。