第 7 章 查找（B 树、散列）
本章地位：查找是 408 数据结构「选择题 + 大题」的双料高产户：散列表的 ASL 计算几乎隔年就考一次大题，B 树的插入删除、折半查找的判定树与比较次数是常青选择题。本章主线是「查找效率的阶梯」——顺序查找 \(O(n)\) → 折半 / 树型查找 \(O(\log_2 n)\) → 散列查找 \(O(1)\)。所有 ASL 结论都配「逐关键字列表格、逐项打 ✓」的完整计算，照着推一遍，大题分就稳了。
7.1 查找基本概念
7.1.1 查找表：静态与动态
- 静态查找表：只做查询 / 检索操作（查找「有没有」），不改动表内容——如顺序表上的顺序查找、折半查找；
- 动态查找表：查找的同时可能插入 / 删除元素（查找「没有就插入」）——如二叉排序树、B 树、散列表上的操作。
7.1.2 平均查找长度 ASL
① 成功 ASL：对表中 n 个已有关键字各查找一次，总比较次数 ÷ \(n\)；
② 失败 ASL：对「不在表中」的关键字各查找一次，总比较次数 ÷ 失败情况的个数（散列表中即散列函数能映到的地址个数，如 \(H(\mathrm{key})=\mathrm{key}\bmod 13\) 就是 13 种失败起点，除以 13，不是除以表长）。分母取错是散列大题最冤的失分点。
判断正误：(1) 折半查找可以在有序单链表上进行；(2) 二叉排序树是一种动态查找表；(3) 查找不成功时的比较次数也应计入失败 ASL。
查看答案
(1) 错：折半查找需要随机存取中间元素，链表不支持随机存取，只能用于有序顺序表。
(2) 对：二叉排序树查找失败时可继续插入新结点，表结构在查找过程中可变，属动态查找表。
(3) 对：失败 ASL 正是由「确定不存在」所经过的比较次数平均出来的。
7.2 顺序、折半与分块查找
7.2.1 顺序查找与哨兵技巧
// 顺序查找（a[0] 作哨兵，关键字存于 a[1..n]）
int seq_search(int a[], int n, int key) {
int i;
a[0] = key; // 哨兵：保证循环必然终止
for (i = n; a[i] != key; i--) // 无需判断 i >= 1
;
return i; // 返回 0 即失败（只碰过哨兵）
}n=5 的表 {10, 20, 30, 40, 50}，从后往前顺序查找，求成功 ASL。
查看解答
逐项数：查 50 比较 1 次、查 40 比较 2 次、查 30 比较 3 次、查 20 比较 4 次、查 10 比较 5 次。
\[ \mathrm{ASL}=\frac{1+2+3+4+5}{5}=\frac{15}{5}=3=\frac{5+1}{2}\ ✓ \]
失败：扫完 5 个元素再碰哨兵，共 \(5+1=6=n+1\) 次 ✓。
7.2.2 折半查找与判定树 高频考点
// 折半查找（升序表 a[0..n-1]，返回下标，失败返回 -1）
int bin_search(int a[], int n, int key) {
int low = 0, high = n - 1, mid;
while (low <= high) {
mid = (low + high) / 2; // 即 mid = ⌊(low+high)/2⌋
if (a[mid] == key)
return mid; // 成功
else if (a[mid] > key)
high = mid - 1; // 抛弃右半
else
low = mid + 1; // 抛弃左半
}
return -1; // low > high：失败
}有序表 {7, 14, 18, 21, 23, 29, 31, 35, 38, 42, 46, 49, 52}（n=13，存于 a[1..13]），分别查找 7 与 39，写出每轮的 low、high、mid 与比较结果。
查看解答
查 7：
| 轮次 | low | high | mid=⌊(low+high)/2⌋ | a[mid] | 比较与动作 |
|---|---|---|---|---|---|
| 1 | 1 | 13 | 7 | 29 | 7 < 29 → high=6 |
| 2 | 1 | 6 | 3 | 18 | 7 < 18 → high=2 |
| 3 | 1 | 2 | 1 | 7 | 相等，成功（3 次比较）✓ |
查 39：
| 轮次 | low | high | mid | a[mid] | 比较与动作 |
|---|---|---|---|---|---|
| 1 | 1 | 13 | 7 | 29 | 39 > 29 → low=8 |
| 2 | 8 | 13 | 10 | 46 | 39 < 46 → high=9 |
| 3 | 8 | 9 | 8 | 35 | 39 > 35 → low=9 |
| 4 | 9 | 9 | 9 | 38 | 39 > 38 → low=10 > high=9，失败（4 次比较）✓ |
失败时 low 越过 high，区间为空即终止。注意 13 个元素的表，任何查找最多 \(\lceil\log_2 14\rceil=4\) 次比较——本题 4 次已到上限。
11 个元素的有序表，按图 7-1 的判定树求折半查找的成功 ASL，并验证最大比较次数。
查看解答
逐层数结点个数与比较次数：
第 1 层：1 个结点 × 1 次 = 1；第 2 层：2 个 × 2 次 = 4；第 3 层：4 个 × 3 次 = 12；第 4 层：4 个 × 4 次 = 16。
\[ \mathrm{ASL}_{成功}=\frac{1\times1+2\times2+4\times3+4\times4}{11}=\frac{1+4+12+16}{11}=\frac{33}{11}=3\ ✓ \]
结点总数 \(1+2+4+4=11\) ✓（不重不漏，每个元素恰在一个结点上）。最大比较次数 = 树高 = 4，而 \(\lceil\log_2(n+1)\rceil=\lceil\log_2 12\rceil=4\) ✓。
套路总结：判定树层计数法——「第 k 层贡献（第 k 层结点数 × k）」，分母永远是 n；先数每层结点数，再核对总数 = n。
7.2.3 分块查找（索引顺序查找）
含 10000 个元素的表分 100 块、每块 100 个元素，分别求索引表用顺序查找与折半查找时的 ASL。
查看解答
顺序查索引：\(\mathrm{ASL}=\dfrac{b+1}{2}+\dfrac{s+1}{2}=\dfrac{101}{2}+\dfrac{101}{2}=50.5+50.5=101=\sqrt{10000}+1\) ✓（b=s=100 恰是最优分块）。
折半查索引：\(\mathrm{ASL}\approx\log_2(b+1)+\dfrac{s+1}{2}=\log_2 101+50.5\approx6.66+50.5\approx57.2\)。
块内永远是顺序查找（块内无序，不能折半）。两者都远小于整表顺序查找的 \(\frac{10000+1}{2}\approx5000\)，但都大于整表折半的 \(\log_2 10001\approx13.3\)——分块是「无序表用不上折半」时的折中方案。
n=100 的有序表折半查找：失败结点有多少个？任何一次查找最多比较多少次？
查看答案
失败结点 \(n+1=101\) 个。最多比较次数 = 判定树高 \(\lceil\log_2(n+1)\rceil=\lceil\log_2 101\rceil=7\)（\(2^6=64\lt101\le128=2^7\)）✓。
易错点：失败结点数是 n+1 不是 n；比较次数上界写 \(\lfloor\log_2 n\rfloor+1=7\) 数值相同，但标准表述是 \(\lceil\log_2(n+1)\rceil\)。
表长 2500 的表分块查找，索引表顺序查找，要使 ASL 最小应每块多少个元素？此时 ASL 为多少？
查看答案
取 \(s=\sqrt n=50\)（此时 \(b=50=s\)），\(\mathrm{ASL}=\sqrt{2500}+1=51\)。
核对：\(\dfrac{b+1}{2}+\dfrac{s+1}{2}=\dfrac{51}{2}+\dfrac{51}{2}=51\) ✓。若取 s=25（b=100）：\(\dfrac{101}{2}+\dfrac{26}{2}=63.5\gt51\)，确实更差 ✓。
7.3 B 树与 B+ 树 高频考点
7.3.1 m 阶 B 树的定义与高度
- 每个结点至多有 m 棵子树（即至多 m−1 个关键字）；
- 若根结点不是终端结点，则至少 2 棵子树（至少 1 个关键字）；
- 除根外的所有非终端（非叶）结点至少 \(\lceil m/2\rceil\) 棵子树，即至少 \(\lceil m/2\rceil-1\) 个关键字；
- 结点内关键字自左向右有序，第 \(i\) 棵子树的所有关键字严格介于第 \(i\) 个与第 \(i+1\) 个关键字之间；
- 所有终端结点（叶结点）位于同一层，故内部结点平衡（这是「分块 + 多路折半」的结构保障）。
(1) 5 阶 B 树中非根结点最少、最多各有多少个关键字？(2) 含 100 个关键字的 5 阶 B 树，高度 \(h\) 的取值范围是多少？
查看解答
(1) 最少 \(\lceil5/2\rceil-1=3-1=2\) 个，最多 \(m-1=4\) 个 ✓（2 ≤ 关键字数 ≤ 4）。
(2) 下界：\(h\ge\log_5(100+1)=\log_5 101\)。验证：\(5^2=25\lt101\le125=5^3\)，故 \(\log_5 101\approx2.87\)，\(h\ge3\)。
上界：\(h\le\log_3\!\left(\dfrac{101}{2}\right)+1=\log_3 50.5+1\approx3.57+1=4.57\)，故 \(h\le4\)。
核对（数结点）：\(h=2\) 至多装 \(5^2-1=24\) 个 < 100，装不下 ✓；\(h=3\) 至多装 \(5^3-1=124\ge100\) ✓；\(h=4\) 最少装 \(2\times3^{3}-1=53\le100\)，\(h=5\) 最少装 \(2\times3^{4}-1=161\gt100\) 装不下 ✓。综上 3 ≤ h ≤ 4。
3 阶 B 树（2-3 树）含 7 个关键字，用高度公式求 \(h\) 的范围，并各画一棵达到上下界的树（只需说明关键字数分布）。
查看答案
下界 \(h\ge\log_3 8\approx1.89\Rightarrow h\ge2\)；上界 \(h\le\log_2 4+1=3\)。故 \(2\le h\le3\)。
达到下界 h=2：根 2 个关键字 + 3 个孩子各 2 个关键字，共 \(2+6=8\ge7\) ✓（7 个可按 2+2+2+1 分布，其中一叶 1 个也合法——叶最少 1 个？不，非根最少 \(\lceil3/2\rceil-1=1\) 个，合法 ✓）。
达到上界 h=3：每个结点 1 个关键字（非根最少 1 个），共 \(1+2+4=7\) 个关键字，恰是满二叉树形状 ✓。
7.3.2 插入：溢出分裂、中位上移
将关键字序列 {4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54} 依次插入初始为空的 5 阶 B 树，写出每次分裂的细节并画出最终形态。
查看解答
按图 7-2 逐步执行（m=5，结点关键字上限 4，溢出取第 \(\lceil5/2\rceil=3\) 个上移）：
① 4、9、14、19 依次进入根（终端）结点，共 4 个，未超限；
② 插 24 → [4,9,14,19,24] 上溢 → 中位 14 上移建根，左右分裂为 [4,9] 与 [19,24]（各 2 个 ✓）；
③ 插 29、34 → 落入右结点成 [19,24,29,34]；插 39 → 上溢 → 中位 29 上移，右结点分裂为 [19,24] 与 [34,39]，根变 [14,29]；
④ 插 44、49 → [34,39,44,49]；插 54 → 上溢 → 中位 44 上移，分裂为 [34,39] 与 [49,54]，根变 [14,29,44]。
最终：根 3 个关键字（≤4 ✓），四个终端结点各 2 个（≥2 ✓），全部同层 ✓。11 个关键字 = 3+2×4 ✓。
套路总结：B 树插入题「一路向下找叶 → 直接插入 → 超限就取中位上移」；检查答案的三个动作——根关键字数、每叶关键字数 ≥ ⌈m/2⌉−1、所有叶同层。
7.3.3 删除：借兄弟与合并
- 够删：删除后仍 ≥ t 个 → 直接删；
- 兄弟够借：删除后不足 t 个，且相邻兄弟 > t 个 → 从兄弟借一个，双亲中相应关键字下来中转（再补一个兄弟关键字上移），保持大小关系；
- 兄弟也最少：删除后不足，相邻兄弟也恰为 t 个 → 本结点 + 双亲中分隔关键字 + 兄弟三者合并为一个结点（t+t+1 ≤ m−1 个，必不超限）。双亲少一个关键字可能连锁下溢，合并继续向上；若根的两个孩子合并，根被架空，树高减 1。
在图 7-2 最终得到的 5 阶 B 树（根 [14, 29, 44]，终端结点 [4,9]、[19,24]、[34,39]、[49,54]）上依次删除 9、19、29，说明每步用了哪种处理并给出结果。
查看解答
删 9（终端结点 [4,9]）：删后只剩 1 个 < 下限 2，右兄弟 [19,24] 恰好 2 个也最少，借不动 → 情景③合并：[4] + 双亲 14 + [19,24] → [4,14,19,24]（4 个 ≤4 ✓），根变 [29,44]。此时四个终端结点变为三个：[4,14,19,24]、[34,39]、[49,54]，仍同层 ✓。
删 19（终端结点 [4,14,19,24]）：删后剩 3 个 ≥ 2 → 情景①直接删，得 [4,14,24] ✓。
删 29（非终端，在根 [29,44] 中）：取 29 的直接前驱 = 左子树 [4,14,24] 的最大关键字 24 → 根变 [24,44]，再在终端结点中删 24 → [4,14]（2 个 ✓，够删）。最终：根 [24,44]，终端结点 [4,14]、[34,39]、[49,54]。
核对：各结点关键字数 2~4 ✓，全部终端结点同层 ✓，总数 \(2+3\times2=8=11-3\) ✓。
7.3.4 B+ 树与 B 树的区别
| 对比项 | B 树 | B+ 树 |
|---|---|---|
| 关键字与子树 | n 个关键字对应 n+1 棵子树 | n 个关键字对应 n 棵子树 |
| 非根结点关键字数 | \(\lceil m/2\rceil-1\) ~ \(m-1\) | \(\lceil m/2\rceil\) ~ \(m\) |
| 终端 / 叶结点 | 含部分关键字，其下还有空失败结点 | 含全部关键字与记录，叶间有链指针 |
| 非终端结点作用 | 关键字本身即是查找目标（命中即返回） | 仅作索引，不存记录，命中不停 |
| 查找终点 | 可在任意层命中结束 | 必须走到终端结点 |
| 典型应用 | 文件系统（如索引结点） | 数据库索引（MySQL InnoDB 等） |
下列关于 m 阶 B+ 树的叙述中，错误的是（ ）
A. 结点中 n 个关键字对应 n 棵子树
B. 非终端结点中存放的关键字是其各子树中最大关键字的副本
C. 查找某个关键字时可能在非终端结点处就成功终止
D. 终端结点包含全部关键字，且相互链接成有序链表
查看解答
C。B+ 树的非终端结点只起「路标」作用，即使中途结点里出现相同值也不停，必须查到终端结点才能确认成败——这与 B 树「任意结点命中即返回」相反。A、B、D 均为 B+ 树定义 ✓。
下列叙述中正确的是（ ）
A. B+ 树的非终端结点中包含了全部关键字
B. B 树中 n 个关键字对应 n 棵子树
C. B+ 树中查找任何关键字都必须查到终端结点
D. B 树的终端结点之间用指针链接以便顺序遍历
查看解答
C。逐项：
A 错：包含全部关键字的是 B+ 树的终端结点，非终端结点只作索引；
B 错：B 树是 n 个关键字对应 n+1 棵子树，n 对 n 是 B+ 树；
C 对：B+ 树非终端结点仅是副本索引，成败须在终端结点判定；
D 错：终端结点链接是 B+ 树的特征，B 树没有。
套路总结：B/B+ 对比选择题就抓三处——「n 对 n 还是 n+1」「数据在叶还是各层都有」「叶链有没有」，逐一对照排除。
7.4 散列表 高频考点
7.4.1 散列函数的构造
- 直接定址法：\(H(\mathrm{key})=a\times\mathrm{key}+b\)，地址与关键字线性对应——不会冲突，但关键字稀疏时浪费空间（适合连续编号，如年龄）；
- 除留余数法（最常用、408 主考）：\(H(\mathrm{key})=\mathrm{key}\bmod p\)，\(p\) 取不大于表长 m 的素数；
- 数字分析法、平方取中法、折叠法等：了解思想即可，考频低。
7.4.2 冲突处理：开放定址与链地址
- 线性探测法：\(d_i=1,2,\dots,m-1\)。一找邻位就顺手，但会把非同义词也堆到一起，产生堆积（聚集）；
- 平方探测法：\(d_i=1^2,-1^2,2^2,-2^2,\dots,k^2,-k^2\)（\(k\le\lfloor m/2\rfloor\)）。跳跃分散、不易堆积；只要表中有空位，在前 \(\lfloor m/2\rfloor\) 次探测内必能探到；当表长 \(m\) 是形如 \(4k+3\) 的素数时可探测到全表每个位置；
- 双散列法：\(d_i=i\times H_2(\mathrm{key})\)（\(H_2\) 是另一个散列函数）。探测序列依赖关键字，聚集最小。
表长 m=11，\(H(\mathrm{key})=\mathrm{key}\bmod 11\)。插入 key=22 时发现 H(22)=0 的单元已被占用，分别写出线性探测法与平方探测法接下来依次探测的 4 个地址。
查看答案
线性探测（\(d_i=1,2,3,4\)）：\(0{\to}1{\to}2{\to}3{\to}4\)（含已占用的 0 共探测 5 个地址）。
平方探测（\(d_i=1,-1,4,-4\)）：\(0{\to}0{+}1=1{\to}0{-}1=10{\to}0{+}4=4{\to}0{-}4=7\)。注意负向探测要 mod m：\(0-1=-1\bmod11=10\) ✓。
若 \(H_2(\mathrm{key})=7\)（双散列）：\(0{\to}7{\to}14\bmod11=3{\to}21\bmod11=10{\to}28\bmod11=6\)。
7.4.3 ASL 计算大题（核心）高频考点
关键字序列 {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，散列函数 \(H(\mathrm{key})=\mathrm{key}\bmod 13\)，表长 m=16，用线性探测法处理冲突。画出散列表，求成功与失败的 ASL。
查看解答
第一步：逐个插入（探测次数 = 比较过的单元数，含最终落位那次）：
| 关键字 | H(key) | 探测过程 | 落位 | 次数 |
|---|---|---|---|---|
| 19 | 6 | 6 空 | 6 | 1 |
| 14 | 1 | 1 空 | 1 | 1 |
| 23 | 10 | 10 空 | 10 | 1 |
| 1 | 1 | 1 占 → 2 空 | 2 | 2 |
| 68 | 3 | 3 空 | 3 | 1 |
| 20 | 7 | 7 空 | 7 | 1 |
| 84 | 6 | 6、7 占 → 8 空 | 8 | 3 |
| 27 | 1 | 1、2、3 占 → 4 空 | 4 | 4 |
| 55 | 3 | 3、4 占 → 5 空 | 5 | 3 |
| 11 | 11 | 11 空 | 11 | 1 |
| 10 | 10 | 10、11 占 → 12 空 | 12 | 3 |
| 79 | 1 | 1～8 占 → 9 空 | 9 | 9 |
得散列表（下标 0～15）：
0:空 1:14 2:1 3:68 4:27 5:55 6:19 7:20 8:84 9:79 10:23 11:11 12:10 13～15:空
第二步：成功 ASL（分母 = n = 12）：
\[ \mathrm{ASL}_{成功}=\frac{1+1+1+2+1+1+3+4+3+1+3+9}{12}=\frac{30}{12}=2.5\ ✓ \]第三步：失败 ASL（分母 = p = 13，即从地址 0～12 各失败查一次，数到首个空单元为止）：
| 起始地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 探测次数 | 1 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 |
（例：从 1 出发要一路数过 1～12 共 12 个占用单元，到 13 空，共 13 次；从 12 出发数 12 后到 13 空，2 次。）
\[ \mathrm{ASL}_{失败}=\frac{1+13+12+11+10+9+8+7+6+5+4+3+2}{13}=\frac{91}{13}=7\ ✓ \]易错：失败 ASL 分母是 13（mod 13 的地址个数）不是表长 16；地址 13～15 不是合法散列起点，绝不参与失败统计。
对例 10 的同一组关键字与散列函数，改用链地址法处理冲突，求成功与失败的 ASL，并与线性探测法对比。
查看解答
成功 ASL：每个关键字的比较次数 = 它在链上的位置（按图 7-3）：
链 1：14 第 1、1 第 2、27 第 3、79 第 4 → \(1+2+3+4=10\)；链 3：68 第 1、55 第 2 → 3；链 6：19 第 1、84 第 2 → 3；链 7：20 → 1；链 10：23 第 1、10 第 2 → 3；链 11：11 → 1。
\[ \mathrm{ASL}_{成功}=\frac{10+3+3+1+3+1}{12}=\frac{21}{12}=1.75\ ✓ \]失败 ASL（分母 = 13）：从地址 0～12 出发，失败的比较次数 = 该链结点数（空链为 0）：
\[ 0,4,0,2,0,0,2,1,0,0,2,1,0\ \Rightarrow\ \mathrm{ASL}_{失败}=\frac{4+2+2+1+2+1}{13}=\frac{12}{13}\approx0.92\ ✓ \]
（若按「与空指针的比较也计一次」的口径，则为 \(\frac{12+13}{13}=\frac{25}{13}\)；408 王道口径取结点数本身，答题以参考答案口径为准。）
对比：线性探测 2.5 / 7，链地址 1.75 / 0.92——链地址法不产生堆积，且删除方便；代价是指针空间与 Cache 局部性差。
7.4.4 装填因子与删除标记
② 开放定址法的散列表删除只能打删除标记（墓碑），不能物理清空——清空会截断后续同义词的探测链，使本可查到的元素「查不到」。例：例 10 中若物理删除 27（槽 4），再查 55（H=3→4 空）会误判「不存在」✗。链地址法无此限制，直接摘链即可。
判断：(1) 表长 16、已存 8 个元素，装填因子为 0.5；(2) 散列表的 ASL 只与装填因子有关，与表长无直接关系；(3) 链地址法删除结点需要打删除标记；(4) 线性探测法比平方探测法更容易产生堆积。
查看答案
(1) 对：\(\alpha=8/16=0.5\) ✓。
(2) 对：在散列函数与冲突处理给定后，ASL 由 α 决定（这是散列区别于顺序 / 折半查找的根本点）。
(3) 错：链地址法直接从链上摘除结点即可，无需标记；要打标记的是开放定址法。
(4) 对：线性探测「挨个往后挪」使非同义词连成一片（堆积）；平方探测正负跳跃，分散得多。
7.5 章末自测 真题风格
限时 50 分钟，先做后看答案。难度：★★ 基础 / ★★★ 强化 / ★★★★ 冲刺。散列 ASL 大题务必动笔列表格，别跳步。
下列存储结构中，适合进行折半查找的是（ ）
A. 有序单链表 B. 有序顺序表 C. 分块有序的单链表 D. 二叉链表存储的二叉排序树
查看答案
B。折半查找要求有序 + 顺序存储（可随机存取）；链表无法 O(1) 定位中点，A、C 错；D 是树形查找，不叫折半查找。
长度为 12 的有序表，等概率下折半查找成功的最多比较次数与失败结点数分别为（ ）
A. 4、12 B. 4、13 C. 3、12 D. 3、13
查看答案
B。最多比较次数 = 判定树高 = \(\lceil\log_2(12+1)\rceil=\lceil\log_2 13\rceil=4\)（\(2^3=8\lt13\le16\)）✓；失败结点 \(n+1=13\) 个 ✓。
含 20 个关键字的 5 阶 B 树，其高度 \(h\) 的可能范围是（ ）
A. \(2\le h\le3\) B. \(3\le h\le4\) C. \(2\le h\le4\) D. \(3\le h\le5\)
查看答案
A。下界 \(h\ge\log_5 21\approx1.89\Rightarrow h\ge2\)；上界 \(h\le\log_3\!\big(\frac{21}{2}\big)+1=\log_3 10.5+1\approx2.18+1=3.18\Rightarrow h\le3\)。核对：\(h=2\) 最多装 \(5^2-1=24\ge20\) ✓，\(h=3\) 最少装 \(2\times3^2-1=17\le20\) ✓，\(h=4\) 最少装 \(2\times3^3-1=53\gt20\) 不可能 ✓。
下列关于 m 阶 B+ 树的叙述中，正确的是（ ）
A. 结点中 n 个关键字对应 n+1 棵子树
B. 查找任一关键字都可能在非终端结点处成功终止
C. 终端结点包含全部关键字，且相互链接成有序链表
D. 非终端结点中存放数据记录本身
查看答案
C。A 错：B+ 树是 n 对 n（n+1 是 B 树）；B 错：必须查到终端结点；D 错：非终端结点只作索引不存记录。数据库索引正是用 B+ 树，范围查询沿叶链顺序扫描。
除留余数法 \(H(\mathrm{key})=\mathrm{key}\bmod p\) 中，p 取不大于表长的最大素数，主要目的是（ ）
A. 节省存储空间 B. 使散列地址分布更均匀、减少冲突 C. 加快取余计算 D. 防止同义词产生
查看答案
B。素数模能把「含公共质因子」的一批关键字打散（见 7.4.1 例）。D 错：同义词（同余）永远可能产生，散列函数只能减少冲突，不能消灭冲突。
表长 100 的顺序表，等概率下顺序查找的成功 ASL 为 \(\underline{\hspace{1cm}}\)，失败时（含哨兵）需比较 \(\underline{\hspace{1cm}}\) 次。
查看答案
成功 \(\frac{100+1}{2}=50.5\)；失败 \(n+1=101\) 次（扫完 100 个元素再比较一次哨兵）。
表长 13 的散列表已存入 6 个元素，装填因子 \(\alpha=\)\(\underline{\hspace{1cm}}\)；若把表长与元素个数同时加倍，ASL 将 \(\underline{\hspace{1cm}}\)（变大 / 变小 / 基本不变）。
查看答案
\(\alpha=6/13\approx0.46\)；基本不变——散列表的 ASL 取决于装填因子 α，而不是表长或元素个数本身。
用线性探测法解决冲突的散列表中删除一个元素，正确的做法是（ ）
A. 将其单元直接置空 B. 仅做逻辑删除标记 C. 把其后所有元素前移一格 D. 重建整张散列表
查看答案
B。物理置空会截断探测链：设 \(H(a)=H(b)\) 且 b 存在 a 后面，删 a 置空后再查 b，探测到 a 的空位即误判失败。删除标记让探测「路过但不停」，插入时可复用。链地址法则可直接摘链删除。
关键字序列 {10, 22, 31, 4, 15, 28, 17, 88, 59}，\(H(\mathrm{key})=\mathrm{key}\bmod 11\)，表长 11，线性探测法处理冲突。画出散列表，计算成功与失败的 ASL。
查看解答
建表（逐项验证）：10→10 空（1 次）；22→0 空（1）；31→9 空（1）；4→4 空（1）；15：4 占→5（2）；28→6 空（1）；17：6 占→7（2）；88：0 占→1（2）；59：4、5、6、7 占→8（5）。
散列表（0～10）：0:22 1:88 2:空 3:空 4:4 5:15 6:28 7:17 8:59 9:31 10:10
\[ \mathrm{ASL}_{成功}=\frac{1+1+1+1+2+1+2+2+5}{9}=\frac{16}{9}\approx1.78\ ✓ \]
失败（分母 11，从 0～10 数到首个空单元）：起点 0 → 3 次；1 → 2；2 → 1；3 → 1；4 → 4～10、0、1 占到 2 空 → 10；5 → 9；6 → 8；7 → 7；8 → 6；9 → 5；10 → 4。
\[ \mathrm{ASL}_{失败}=\frac{3+2+1+1+10+9+8+7+6+5+4}{11}=\frac{56}{11}\approx5.09\ ✓ \]易错：失败从地址 4 出发要越过 4～10 共 7 个占用位再绕回 0、1，最后在 2 停下——「绕回」别忘 mod 表长。
将关键字 {30, 60, 90, 20, 15} 依次插入初始为空的 3 阶 B 树，写出每次分裂过程并画出最终树，最后检查合法性。
查看解答
m=3：结点关键字上限 2，下限（非根）\(\lceil3/2\rceil-1=1\)；上溢取第 \(\lceil3/2\rceil=2\) 个（中位）上移。
① 30、60 → 根 [30,60]；② 插 90 → [30,60,90] 上溢 → 中位 60 上移建根，分裂为 [30] 与 [90]（树高 +1）；③ 插 20 → 落左结点 [20,30]；④ 插 15 → [15,20,30] 上溢 → 中位 20 上移，左结点分裂为 [15] 与 [30]，根变 [20,60]。
最终：根 [20,60]（2 个 ≤2 ✓），终端结点 [15]、[30]、[90]（各 1 个 ≥1 ✓，同层 ✓）。关键字总数 \(2+3=5\) ✓。
套路总结：3 阶 B 树每个结点最多 2 个关键字，「第三个必分裂」；分裂时中间的上移、两边各留一个。
7.6 本章考点总结
| 考点 | 常考题型 | 热度 | 核心方法 |
|---|---|---|---|
| 折半查找过程与判定树 | 选择 / 解答 | ★★★★★ 每年必考 | mid=⌊(low+high)/2⌋ 逐步列表；判定树逐层计数；比较次数 ≤ ⌈log₂(n+1)⌉，失败结点 n+1 个；只适用于有序顺序表 |
| 顺序 / 分块查找 ASL | 选择 / 填空 | ★★★ | 顺序成功 (n+1)/2、失败 n+1；分块 ASL=L索引+L块内，最优 s=√n 时 ≈ √n+1 |
| m 阶 B 树定义与高度 | 选择 | ★★★★ | 关键字数 ⌈m/2⌉−1 ~ m−1、根至少 1、叶同层；高度 log_m(n+1) ≤ h ≤ log_⌈m/2⌉((n+1)/2)+1，代小值核对 |
| B 树插入 / 删除 | 选择 / 解答 | ★★★★ 高频 | 插入：到终端结点，上溢取中位上移可连锁分裂（树高向上长）；删除：够删直接删、缺则借兄弟、都缺则与双亲中分隔关键字合并；非终端删用前驱 / 后继替换 |
| B+ 树辨析 | 选择 | ★★★ | n 关键字 n 子树；叶含全部关键字且串链；非叶仅索引；查找必到叶；数据库索引用 B+ 树 |
| 散列函数与冲突处理 | 选择 / 大题第一步 | ★★★★ | 除留余数 p 取素数；线性探测易堆积、平方探测 ⌊m/2⌋ 内必中、双散列最散；链地址无堆积、删除方便 |
| 散列表 ASL 计算 | 综合大题 | ★★★★★ 高频大题 | 逐关键字列探测次数表；成功 ÷ n，失败 ÷ p（mod 的模数，不是表长）；绕回 mod 表长别漏 |
| 装填因子与删除标记 | 选择 / 判断 | ★★★ | α=n/m 决定 ASL，与表长无直接关系；开放定址删除只能打标记（保探测链），链地址直接摘链 |