注意
# 注意
由以上题目可知B树和 $\mathrm{B + }$ 树的定义与性质尤为重要，需要熟练掌握。
08. C、B
5阶B树中共有53个关键字，由最大高度公式 $H\leqslant \log (m / 2)((n + 1) / 2) + 1$ 得最大高度 $H\leqslant$
<!-- page: 325 -->
第7章 查找
313
$\log_2[(53 + 1) / 2] + 1 = 4$，即最大高度为 4；由最小高度公式 $h \geqslant \log_m(n + 1)$ 得最小高度 $h \geqslant \log_5 54 \approx 2.5$，从而最小高度为 3。
## 09. A、D
利用前面的公式即最小高度 $h \geqslant \log_m(n + 1)$ 和最大高度 $H \leqslant \log_{\lceil m / 2 \rceil}[(n + 1) / 2] + 1$，易算出最大高度 $H \leqslant \log_2[(2047 + 1) / 2] + 1 = 11$，最小高度 $h \geqslant \log_3 2048 = 6.9$，从而最小高度取 7（注意，有些辅导书针对本题算出的高度要比这里给出的答案多 1，因为它们在对 B 树的高度定义中，把最底层不包含任何关键字的叶结点也算进去了）。
## 10. B
本题要计算的是最坏情况下第 2016 个关键字在 7 阶 B 树中的最大深度，即考查 B 树结点中关键字数最少的情况。按照 B 树的定义，根结点至少有 1 个关键字，第二层至少有 2 个结点，即 $2 \times 3$ 个关键字；第三层至少有 $2 \times 4$ 个结点，即 $2 \times 4 \times 3$ 个关键字；第四层至少有 $2 \times 4^2$ 个结点，即 $2 \times 4^2 \times 3$ 个关键字；以此类推，第 $h$ 层至少有 $2 \times 4^{h+2}$ 个结点，即 $2 \times 4^{h+2} \times 3$ 个关键字，故前 $h$ 层的关键字总数 $n = 1 + 2 \times 3 \times (1 + 4 + \dots + 4^{h+2}) = 1 + 2 \times (4^{h+1} - 1)$。故当 $h = 5$ 时，$n = 511$；当 $h = 6$ 时，$n = 2047$，说明 5 层高的 7 阶 B 树最少有 511 个关键字，而 6 层高的 7 阶 B 树最少有 2047 个关键字，故最坏情况下第 2016 个关键字在 7 阶 B 树的第 6 层，需启动 5 次 I/O 操作。
## 11. B
考虑最坏情况，在待插入结点中插入一个关键码后，导致结点分裂，在该层分裂成 2 个结点，因此需要 2 次写磁盘操作；分裂操作逐层向上传导，导致每层都有结点分裂，因为结点分裂而导致的写磁盘操作共有 $2h$ 次，加上最后一次结点分裂形成新根结点也需要 1 次写磁盘操作，写磁盘的总次数为 $2h + 1$，即由于本次插入而产生的新结点个数为 $h + 1$，加上寻找插入位置而引起的 $h$ 次的读磁盘操作，整个过程中读/写磁盘的总次数为 $3h + 1$ 次，选项 C、D 正确。若插入操作导致了 B 树的高度增加，则分裂操作一定是从最底层传导至根结点的，即前面分析的最坏情况，选项 A 正确。若分裂操作没有传导至根结点，则 B 树的高度不变，选项 B 错误。
## 12. A
B 树和 B+树的差异主要体现在：① 结点关键字和子树的个数；② B+树非叶结点仅起索引作用；③ B 树叶结点关键字和其他结点包含的关键字是不重复的；④ B+树支持顺序查找和随机查找，而 B 树仅支持随机查找。B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，因此可以进行顺序查找，而 B 树不支持顺序查找。B 树和 B+树都可用于文件索引结构，但 B+树更适合做数据库索引和文件索引，因为它的磁盘读/写代价更低。
## 13. C
在 B 树的查找操作中，若目标元素在某个内部结点中，则查找结束，不需要进入叶结点；查找失败时，叶结点是所有路径的终点，选项 A、B 正确。B+树中仅叶结点包含信息，非叶结点仅起到索引作用，查找成功时一定会找到相应的叶结点，所经过的路径长度都相等，选项 C 错误，选项 D 正确。
## 14. D
$m$ 阶 B 树不要求将各叶结点之间用指针链接。选项 D 描述的实际上是 B+树。
## 15. D
对于图中所示的 3 阶 B 树，被删关键字 78 所在的结点在删除前的关键字个数 $= 1 = \lceil 3 / 2 \rceil - 1$，且其左兄弟结点的关键字个数 $= 2 \geqslant \lceil 3 / 2 \rceil$，属于“兄弟够借”的情况，因此要把该结点的左兄弟结点中的最大关键字上移到父结点中，同时把父结点中大于上移关键字的关键字下移到要删除关键字的结点中，这样就达到了新的平衡，如下图所示。
<!-- page: 326 -->
2027年数据结构考研复习指导
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
16. A 对于5阶B树，根结点的分支数最少为2（关键字数最少为1），其他非叶结点的分支数最少为 $\lceil n / 2\rceil = 3$ （关键字数最少为2），因此关键字个数最少的情况如右图所示（叶结点不计入高度）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
注意
一般来说，对于某个具体的B树图形，并不能确定是几阶B树。对于本题所述的5阶B树，不要误认为：“存在至少有一个含关键字结点中的关键字达到4”才符合5阶B树的要求，因为5阶B树中各个结点包含的关键字个数最少为2（$\lceil 5 / 2\rceil -1 = 2$），最多为4（$5 - 1 = 4$）。当5阶B树中各个结点包含的关键字个数为2时，也满足5阶B树的要求。
17. D
关键字数量不变，要求结点数量最多，即要求每个结点中含关键字的数量最少。根据4阶B树的定义，根结点最少含1个关键字，非根结点中最少含 $[4 / 2] - 1 = 1$ 个关键字，所以每个结点中关键字数量最少都为1个，即每个结点都有2个分支，类似于排序二叉树，而15个结点正好可以构造一个4层的4阶B树，使得终端结点全在第四层，符合B树的定义。
18. A
$\mathbf{B}+$ 树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，因此可以进行顺序查找，而B树不支持顺序查找（只支持多路查找）。
19. B
$\mathbf{B}+$ 树是应文件系统所需而产生的 $\mathbf{B}$ 树的变形，前者比后者更加适用于实际应用中的操作系统的文件索引和数据库索引，因为前者的磁盘读/写代价更低，查询效率更加稳定。编译器中的词法分析使用有穷自动机和语法树。网络中的路由表快速查找主要靠高速缓存、路由表压缩技术和快速查找算法。系统一般使用空闲空间链表管理磁盘空闲块。
20. B
$m$ 阶B树的基本性质：除根结点外的非叶结点最少含有 $\lceil m / 2\rceil -1$ 个关键字，代入 $m = 3$ 得到每个非叶结点中最少包含1个关键字，而根结点含有1个关键字，因此所有非叶结点都有两个孩子。此时其树形与 $h = 5$ 的满二叉树相同，可求得关键字最少为31个。
21. B
一个4阶B树的任意非叶结点至多含有 $m - 1 = 3$ 个关键字，在关键字依次插入的过程中，会导致结点的不断分裂，插入过程如下图所示。得到根结点包含的关键字为6,9。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 327 --> 第7章 查找 315 22. A 在阶为3的B树中，每个结点至多含有2个关键字（至少1个），至多有3棵子树。本题规定第二层有4个关键字，欲使B树的结点数达到最多，则这4个关键字包含在3个结点中，B树树形如下图所示，其中A, B, C, …, M表示关键字，最多有11个结点。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
23. D
在5阶B树中，除根结点外的非叶结点的关键字数 $k$ 需要满足 $2 \leqslant k \leqslant 4$ 。当被删关键字x不在终端结点（最底层非叶结点）时，可以用x的前驱（或后继）关键字y来替代x，然后在相应结点中删除y。情况①：删除260，将其前驱110放入260处，删除110后的结点<100>不满足5阶B树定义，从左兄弟中借85，将85放入根中，将根中的90移入结点<100>变为<90,100>。情况②：删除260，将其后继280放入260处，结点<300>不满足5阶B树定义且左右兄弟都不够借，结点<300>可以和左兄弟<100,110>以及关键字280合并成一个新的结点<100,110,280,300>。情况③：在情况②中，结点<300>也可以和右兄弟<400,500>以及关键字350合并成一个新的结点<300,350,400,500>。综上， $T_{1}$ 根结点中的关键字序列可能是<60,85,110,350>或<60,90,350>或<60,90,280>，仅选项D不可能。
快速解法：假如选项D的60,90,110,350作为根结点，则在90和110之间只有100这一个数据，显然不符合5阶B树的定义，因此选项D不可能。
24. B
B 树的插入操作可能导致叶结点分裂，叶结点分裂可能导致父结点分裂，甚至会传导到根结点，从而导致 B 树高度增 1，说法 I 正确。若被删结点是叶结点，则显然会导致叶结点变化；若被删结点不是叶结点，则要先将被删结点和它的前驱或后继交换，最终转换为删除叶结点，还是导致叶结点变化，说法 II 正确。若在非叶结点中查找到了给定的关键字，则不用向下继续查找，说法 III 错误。插入关键字的初始位置是最底层叶结点，但可能因结点分裂而被转移到父结点中，说法 IV 错误。
注意
由本题可知，与大多数教材不同，统考真题中称最底层终端结点为叶结点。
25. C
对于4阶B树，每个结点包含 $1\sim 3$ 个关键字（根结点可为 $1\sim 3$ 个，非根结点至少1个）。给定7个不同关键字，按树高分类讨论：①当树为2层时，若根含1个关键字，则其2个子结点需要分配6个关键字，唯一合法的分配为(3,3)，对应1种；若根含2个关键字，则3个子结点分配5个关键字，合法分配为(3,1,1)和(2,2,1)，考虑所有排列共6种；若根含3个关键字，则4个子结点各含1个关键字，对应1种；合计8种。②当树为3层时，仅当根及其两个子结点均含1个关键字时，剩余4个关键字恰好分配给4个叶子结点（各1个），满足最小关键字数要求，仅1种。综上，共可构造 $8 + 1 = 9$ 种不同的4阶B树。
二、综合应用题
01. 【解答】
$m = 3$ ，因此除根结点外，非叶结点关键字个数为 $1 \sim 2$ 。
<!-- page: 328 -->
2027年数据结构考研复习指导
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
如上图所示，首先插入20,30，结点内关键字个数不超过 $m - 1 = 2$，不会引起分裂；插入50，插入20,30所在的结点，引起分裂，结点内第 $\lceil m / 2\rceil$ 个关键字30上升为父结点。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
如上图所示，插入52，插入50所在的结点，不会引起分裂；继续插入60，插入50,52所在的结点，引起分裂，52上升到父结点中，不会引起父结点的分裂。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
如上图所示，插入68，插入60所在的结点，不会引起分裂；继续插入70，插入60,68所在的结点，引起分裂，68上升为新的父结点，68上升到30,52所在的结点后，会继续引起该结点的分裂，所以52上升为新的根结点。最后得到的B树如右图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 02. 【解答】 1）插入90：将90插入100所在的结点，插入90后该结点中的元素个数不超过 $\lceil 3 / 2\rceil = 2$，不会引起结点的分裂，插入后的B树如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
2）插入25：将25插入8, 20所在的结点，插入后结点内的元素个数为3，引起分裂。所以将结点内的中间元素20上升到父结点中，此时父结点中的元素个数为2（元素20和30），不会引起继续分裂，插入25后的B树如右图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
3）插入45：将45插入35,40所在的结点，引起分裂，中间元素40上升到父结点（20,30所在的结点）中，引起父结点分裂，中间元素30上升到父结点（50所在的结点）中，两次分裂后的B树如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 329 --> 第7章 查找 317 4）删除60：删除60后，其所在的结点元素为空，从而导致借用右兄弟结点的元素，调整后的B树如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
5）删除80：删除80后，导致80所在结点的父结点与其右兄弟结点合并，这时父结点元素个数为0，再次对父结点进行调整。将50与40合并成一个新结点，则90、100所在结点为这个结点的子结点。从而构造的B树如下图所示。注意，这次调整的过程实际上包含多次调整过程，希望读者对照考点讲解中的删除过程仔细思考。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 注意
B树中结点的插入、删除操作（特别是插入、删除后的结点分裂与合并）是本节的重点，也是难点，请读者务必熟练掌握。
## 03. 【解答】
根据B树的概念，一个索引结点应适应操作系统一次读/写的物理记录大小，其大小应取不超过但最接近一个磁盘页块的大小。假设B树为 $m$ 阶，一个B树结点最多存放 $m - 1$ 个关键字（5B）和对应的记录地址（5B）、$m$ 个子树指针（5B）和1个指示结点中的实际关键字个数的整数（2B），则有
$$
(2 \times (m - 1) + m) \times 5 + 2 \leqslant 4000
$$
计算结果为 $m \leqslant 267$ 。
一个索引结点最多可以存放 $m - 1 = 266$ 个索引项，最少可以存放 $\lceil m / 2 \rceil - 1 = 133$ 个索引项。全部有 $n = 20000000$ 个记录，每个记录占用空间200B，每个页块可以存放 $4000 / 200 = 20$ 个记录，则全部记录分布在 $20000000 / 20 = 1000000$ 个页块中，最多需要占用 $1000000 / 133 = 7519$ 个磁盘页块作为B树索引，最少需要占用 $1000000 / 266 = 3760$ 个磁盘页块作为B树索引（注意B树与B+树的不同，B树所有对数据记录的索引项分布在各个层次的结点中，B+树所有对数据记录的索引项都在叶结点中）。
## 7.5 散列（Hash）表
### 7.5.1 散列表的基本概念
在前面介绍的线性表和树表查找中，查找记录需要进行一系列关键字比较。由于记录在表中的位置与其关键字之间不存在映射关系，因此这些结构的查找效率取决于关键字比较的次数。
散列函数（也称哈希函数）是一种将关键字映射到其对应存储地址的函数，记为
$$
\operatorname {H a s h} (\text {k e y}) = \operatorname {A d d r} \quad \text {或} \quad H (\text {k e y}) = \operatorname {A d d r}
$$
其中，地址可以是数组下标、索引或内存地址等。
散列函数可能会将两个或两个以上不同的关键字映射到同一地址，这种现象称为冲突，这些发生冲突的不同关键字称为同义词。一方面，良好的散列函数应尽可能减少冲突的发生；另一方面
<!-- page: 330 -->
2027年数据结构考研复习指导
面，由于冲突总是不可避免的，因此还需设计有效的冲突处理方法。
散列表（也称哈希表）：一种根据关键字直接进行访问的数据结构。它建立了关键字到存储地址的直接映射。
在理想情况下，对散列表进行查找的时间复杂度为 $O(1)$，即与表中元素的个数无关。下面将分别介绍常用的散列函数和处理冲突的方法。
## 7.5.2 散列函数的构造方法
在构造散列函数时，必须注意以下几点：
1）散列函数的定义域必须包含全部关键字，而值域的范围则取决于散列表的大小。
2）散列函数计算出的地址应尽可能均匀地分布在整个地址空间，以有效减少冲突。
3）散列函数应尽量简单，能在较短时间内计算出任意关键字对应的散列地址。
下面介绍常用的散列函数。
### 1. 直接定址法
直接取关键字的某个线性函数值作为散列地址，其散列函数为
$$
H(\text{key}) = \text{key} \quad \text{或} \quad H(\text{key}) = a \cdot \text{key} + b
$$
其中，$a$ 和 $b$ 是常数。该方法计算最简单，且不会产生冲突，适用于关键字分布基本连续的情形。若关键字分布稀疏、空位较多，则会造成存储空间的浪费。
### 2. 除留余数法
这是最简单且最常用的散列函数构造方法。设散列表长度为 $m$，选取一个不超过 $m$ 且尽可能接近 $m$ 的质数 $p$，通过以下公式将关键字映射为散列地址：
$$
H(\text{key}) = \text{key} \% p
$$
除留余数法的关键在于合理选择 $p$，使得不同关键字经该函数映射后能近似等概率地落在散列空间的各个位置，从而尽可能减少冲突。
### 3. 数字分析法
设关键字是 $r$ 进制数，其各位上的数码（共 $r$ 种）出现的频率可能不同；某些数位上数码分布较为均匀，各种数码出现的机会接近均等；而另一些数位上分布不均，仅有少数几种数码频繁出现。此时应选取那些数码分布较为均匀的数位，以其组合构成散列地址。该方法适用于已知且固定的关键字集合，若关键字集合发生变化，则需重新构造新的散列函数。
### 4. 平方取中法
顾名思义，该方法取关键字平方值的中间几位作为散列地址。具体取多少位根据散列表大小和关键字范围确定。由于平方运算与关键字的每位都有关系，因此使得散列地址的分布较为均匀。该方法适用于关键字的各位取值分布不均或关键字本身位数较少的情形。
在不同应用场景下，各类散列函数的性能表现各异，因此不能笼统地说某种方法最优。实际选择时，应根据关键字集合的特性合理选用散列函数的构造方法。
## 7.5.3 处理冲突的方法
应当注意到，任何散列函数都无法绝对避免冲突。因此，必须设计有效的冲突处理机制，即为发生冲突的关键字寻找下一个可用的散列地址。设 $H_{i}$ 表示第 $i$ 次探测所得的散列地址。若初始地址 $H_{0} = H(\text{key})$ 发生冲突，则尝试 $H_{1}$；若 $H_{1}$ 仍冲突，则继续计算 $H_{2}$，以此类推，直到找到首个不发生冲突的地址 $H_{k}$，该地址即为关键字在散列表中的最终存储位置。
<!-- page: 331 -->
第7章 查找
319
## 导航图12
### 冲突处理方法的特点（2025）
#### 1. 开放定址法
开放定址法是指散列表中的所有空闲地址均可用于存放任意关键字（无论是否与其同义）。其地址探测序列由如下递推公式给出：
$$
H_i = (H(\text{key}) + d_i) \% m
$$
其中，$H(\text{key})$ 为散列函数；$d_i$ 为第 $i$ 次探测的增量，$i = 1, 2, \cdots, k$（$k \leqslant m - 1$）；$m$ 为散列表表长。一旦选定增量序列，对应的冲突处理方法即被确定。常见的增量序列取法有以下四种。
## 导航图13
### 堆积现象导致的结果（2014）
1）线性探测法，也称线性探测再散列法。增量序列 $d_i = 1, 2, \cdots, m - 1$。
其特点是：冲突发生时，顺序查看表中下一个单元；若探测到表尾地址 $m - 1$，则下一个探测地址回绕至表首地址 0，如此循环，直到找到一个空闲单元（只要表未满，必能找到）。然而，线性探测法容易引发“聚集（或称堆积）”现象：原本映射到地址 $i$ 的同义词被存入 $i + 1$，而本应存入 $i + 1$ 的元素则被迫占用 $i + 2$，以此类推。这会导致大量元素在相邻地址上堆积，显著降低查找效率。
2）平方探测法，也称二次探测法。增量序列 $d_i = 1^2, -1^2, 2^2, -2^2, \cdots, k^2, -k^2$（$k \leqslant m/2$）。其中，散列表长度 $m$ 必须是一个形如 $4k + 3$ 的素数。
平方探测法能有效避免“堆积”问题，是一种较好的冲突处理方法。其缺点是无法探测散列表中的所有位置，但至少可以覆盖一半的地址空间。
3）双散列法。增量序列 $d_i = iH_2(\text{key})$。
该方法需使用两个散列函数。当通过第一个散列函数 $H(\text{key})$ 得到的地址发生冲突时，利用第二个散列函数 $H_2(\text{key})$ 计算地址增量。其探测序列为：
$$
H_i = (H(\text{key}) + iH_2(\text{key})) \% m
$$
其中，初始探测位置 $H_0 = H(\text{key}) \% m$。$i = 0, 1, 2, \cdots$ 表示探测序号。
4）伪随机序列法。增量序列由一个伪随机数生成器产生，即 $d_i = \text{第 } i$ 个伪随机数。