第7章 查找

7.1 查找的基本概念

1. 【竟成·模拟二-10】 在下列各种数据结构中，一般而言查找操作效率较低的是（）。

A. 二叉堆    B. 二叉排序树    C. B树    D. 红黑树

查看答案与解析

答案： A

解析： 二叉堆只保证父结点与孩子结点之间满足堆序关系，并不保证左、右子树内部按关键字有序。因此，除查找堆顶最大值或最小值外，查找任意指定关键字通常需要遍历大量结点，最坏时间复杂度为 $O(n)$。

• 二叉排序树在树形较平衡时，查找时间复杂度约为 $O(\log n)$，最坏退化为 $O(n)$。
• B 树是一种多路平衡查找树，查找复杂度为 $O(\log n)$，特别适用于外存查找。
• 红黑树能够保证树高为 $O(\log n)$，查找复杂度稳定为 $O(\log n)$。

因此一般而言，二叉堆对任意关键字的查找效率最低，选择 A。

---

7.2 顺序查找和折半查找

7.2.2 折半查找

2. 【王道·卷三-Q08】 在一个长度为12的有序顺序表中，每个元素的查找概率相等，则对其进行折半查找时，查找成功的平均查找长度是（ ）。

A. 35/12    B. 31/12    C. 37/12    D. 39/12

查看答案与解析

答案： C

解析： 采用折半查找并按中点向下取整构造判定树。长度为 $12$ 的表中，各层内部结点数依次为：

$$1,2,4,5$$

对应比较次数分别为 $1,2,3,4$。由于各元素查找概率相等，查找成功的平均查找长度为：

$$\begin{array}{rl}AS{L}_{\text{成功}}& =\frac{1\times 1+2\times 2+4\times 3+5\times 4}{12}\\ & =\frac{1+4+12+20}{12}\\ & =\frac{37}{12}.\end{array}$$

故选 C。

---

3. 【王道·卷四-Q08】 折半查找有序表{2,10,25,35,40,65,70,75,81,82,88,100}。若查找元素75，则可能的查找次序是（ ）。

A. 65,82,75    B. 70,82,75    C. 65,81,75    D. 65,81,70,75

查看答案与解析

答案： D

解析： 有序表共有 $12$ 个元素，采用中点向下取整。

1. 初始区间为第 $1$～$12$ 个元素，中点为：

$$\lfloor \frac{1+12}{2}\rfloor =6$$

比较第 6 个元素 $65$。因为 $75>65$，转到右半区间第 $7$～$12$ 个元素。

2. 新中点为：

$$\lfloor \frac{7+12}{2}\rfloor =9$$

比较第 9 个元素 $81$。因为 $75<81$，转到区间第 $7$～$8$ 个元素。

3. 新中点为第 7 个元素 $70$。因为 $75>70$，继续查找第 8 个元素。

4. 比较第 8 个元素 $75$，查找成功。

因此查找次序为：

$$65,81,70,75$$

选择 D。

---

4. 【竟成·模拟一-10】 对有序序列{1,2,3,4,5,6,7,8,9,10}，使用折半查找（判定树采用向下取整）。假设各元素的查找概率相等，则下列描述错误的是（）。

A. 该折半查找判定树是AVL树    B. 查找成功的平均查找长度为29/10

C. 查找失败的平均查找长度为39/11    D. 该折半查找判定树的后序遍历序列为{1,4,3,2,7,6,10,9,8,5}

查看答案与解析

答案： 题目有误（A、B、C、D 均正确，无错误选项）

解析： 采用中点向下取整构造折半查找判定树，根结点为关键字 5，结构可表示为：

Text

5
/   \
2     8
/ \   / \
1   3 6   9
\  \   \
4  7   10

逐项验证如下。

• A 正确。任一结点左右子树高度差的绝对值均不超过 1，因此该树是 AVL 树。
• B 正确。各层结点数依次为 $1,2,4,3$，所以：

$$AS{L}_{\text{成功}}=\frac{1\times 1+2\times 2+4\times 3+3\times 4}{10}=\frac{29}{10}.$$

• C 正确。共有 $11$ 个查找失败区间，各区间所需比较次数之和为：

$$3+3+3+4+4+3+4+4+3+4+4=39$$

因此：

$$AS{L}_{\text{失败}}=\frac{39}{11}.$$

• D 正确。该树的后序遍历为：

$$1,4,3,2,7,6,10,9,8,5$$

因此四个选项均正确，题目不存在“错误”的选项，应为原题或选项设置有误。

---

5. 【竟成·模拟二-08】 若某折半查找判定树包含20个结点，则其查找失败的查找长度最小是（）。

A. 1    B. 2    C. 3    D. 4

查看答案与解析

答案： D

解析： 折半查找判定树是根据每次取中点递归构造的近似完全二叉树。

对于 $20$ 个内部结点：

$$2^4-1=15<20<2^5-1=31$$

因此判定树有 5 层。前 4 层必须全部含有内部结点，第 5 层只含部分内部结点。查找失败时，需要沿查找路径到达一个空指针位置；最浅的失败位置出现在第 4 层内部结点的空孩子处，因此至少要比较 4 次。

所以查找失败的最小查找长度为 $4$，选择 D。

---

7.2.3 分块查找

6. 【竟成·模拟六-10】 当采用分块查找时，数据的组织方式为（）。

A. 数据分成若干块，每块内数据有序

B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D. 数据分成若干块，每块（除最后一块外）中数据个数需要相同

查看答案与解析

答案： B

解析： 分块查找又称索引顺序查找，其基本组织原则是“块间有序、块内无序”。

• 块间有序：前一块中所有关键字均小于后一块中的所有关键字，或满足相应的统一有序关系。
• 块内无序：同一块内的元素不要求按关键字排序，定位到目标块后可采用顺序查找。
• 索引表通常保存每块的最大关键字或最小关键字，以及该块的起始地址。

因而 B 正确。A、C 错在要求块内有序；D 错在各块元素个数不必完全相同。

---

7.3 树形查找

7.3.1 二叉排序树 BST

7. 【王道·卷一-Q08】 在下列选项中，（ ）不可能构成任何二叉排序树的前序遍历序列。

A. 4,2,3,5,6,7    B. 4,3,2,7,6,5    C. 6,5,4,2,3,7    D. 6,5,3,4,2,7

查看答案与解析

答案： D

解析： 二叉排序树的前序序列满足：根结点之后先出现所有小于根的左子树结点，再出现所有大于根的右子树结点；这一规则对子树递归成立。

• A：根为 4，左子树序列为 $2,3$，右子树序列为 $5,6,7$，可以构成二叉排序树。
• B：根为 4，左子树序列为 $3,2$，右子树序列为 $7,6,5$，可以构成二叉排序树。
• C：根为 6，左子树序列为 $5,4,2,3$，右子树为 7。左子树内部也满足前序序列约束，可以构成二叉排序树。
• D：根为 6，左子树序列为 $5,3,4,2$。在以 3 为根的子树中，4 大于 3，说明已经进入 3 的右子树；此后又出现小于 3 的结点 2，不可能再回到 3 的左子树，因此该序列不可能是任何二叉排序树的前序遍历序列。

故选 D。

---

8. 【王道·卷五-Q08】 假设要在二叉排序树中查找关键码为52的结点，则在如下序列中，不可能是在二叉排序树中的查找顺序的是（ ）。

A. 80,22,76,25,37,52    B. 95,59,84,25,70,52    C. 1,58,54,20,43,52    D. 90,22,82,63,52

查看答案与解析

答案： B

解析： 在二叉排序树中查找关键字 52 时，每比较一个结点，都会进一步缩小后续结点允许出现的取值范围。

• A：依次得到约束

$$22<52<76<80$$

后续的 25、37、52 均处于当前允许区间内，可能出现。

• B：比较 95 后进入其左子树；比较 59 后还应继续进入 59 的左子树，因此后续结点必须小于 59。但下一结点为 84，违反约束，所以不可能出现。
• C：查找区间依次收缩为

$$43<52<54$$

整个序列符合二叉排序树的查找规律。

• D：查找区间依次收缩为

$$22<52<63$$

整个序列也可能出现。

因此，不可能的查找序列是 B。

---

9. 【竟成·模拟五-08】 若在一棵二叉排序树中查找关键字363，下列序列中，不可能是查找过的序列的是（）。

A. 5,256,441,368,340,354,367,363    B. 936,240,911,248,896,259,361,363

C. 985,200,911,240,912,258,363    D. 8,402,387,229,266,382,381,278,363

查看答案与解析

答案： C

解析： 查找关键字 363 时，可用上下界检查每一步是否可能出现。

• A：比较过程中的区间依次缩小，最终有

$$354<363<367$$

序列合法。

• B：各结点始终位于当前查找区间内，最终由 361 进入其右子树找到 363，序列合法。
• C：比较 911 时，因为

$$363<911$$

所以后续查找必须位于 911 的左子树，即后续关键字必须小于 911。然而下一结点是 912，不满足要求，因此该序列不可能出现。

• D：上下界不断更新，所有结点均落在当前允许区间内，序列合法。

故选 C。

---

10. 【竟成·模拟七-06】 下列说法错误的是（）。

A. 若一棵二叉排序树中一个结点有两个孩子，则它的中序后继结点没有左孩子，它的中序前驱结点没有右孩子

B. 若二叉排序树中一个结点x的右子树为空，且x有一个中序后继y，则y一定是x的祖先，且y的左孩子也是x的祖先（结点本身也视为自己的一个祖先）

C. 中序线索树中，从最左边的结点开始不断的访问右孩子或者线索结点，一定能遍历树内所有的结点

D. 若x是二叉排序树的叶结点，y是其父结点，那么y的数值要么是树中大于x的数值的最小关键字，要么是树中小于x的数值的最大关键字

查看答案与解析

答案： C

解析： 逐项分析如下。

• A 正确。若结点有右子树，则其中序后继是右子树中最左边的结点，因此该后继不可能有左孩子；同理，其中序前驱是左子树中最右边的结点，不可能有右孩子。
• B 正确。当结点 $x$ 的右子树为空时，其中序后继是从 $x$ 向上回溯时遇到的第一个“其左子树包含 $x$”的祖先 $y$。从 $y$ 的左孩子到 $x$ 存在一条向下路径，因此 $y$ 的左孩子也是 $x$ 的祖先，允许该左孩子就是 $x$ 本身。
• C 错误。在中序线索二叉树中，若当前结点的右指针为线索，可直接沿线索找到后继；但若右指针指向右孩子，则中序后继并不一定就是该右孩子，而应是该右子树中最左边的结点。因此不能仅通过“访问右孩子或线索”完成遍历。
• D 正确。若 $x$ 是 $y$ 的左孩子，则 $y$ 是 $x$ 的中序后继；若 $x$ 是 $y$ 的右孩子，则 $y$ 是 $x$ 的中序前驱。由于 $x$ 是叶结点，不存在更近的子树结点改变这一关系。

因此错误的是 C。

---

7.3.2 平衡二叉树

11. 【王道·卷一-Q09】 在一棵有232个结点的AVL树中，每个非叶结点的平衡因子不是1就是-1，那么离根最远的叶结点所处的层次为（ ）。假设根结点所处的层次为1。

A. 6    B. 8    C. 11    D. 13

查看答案与解析

答案： C

解析： 设满足题意且高度为 $h$ 的 AVL 树的最少结点数为 $N_h$。由于每个非叶结点的平衡因子只能是 $1$ 或 $-1$，其左右子树高度必须恰好相差 1。为使结点数最少，根的两棵子树应分别取高度 $h-1$ 和 $h-2$，因此：

$$N_h=N_{h-1}+N_{h-2}+1$$

初值为：

$$N_1=1,N_2=2$$

依次计算：

$$\begin{array}{rl}{N}_3& =4,N_4=7,N_5=12,N_6=20,\\ N_7& =33,N_8=54,N_9=88,N_{10}=143,\\ N_{11}& =232.\end{array}$$

题目给出的结点数恰好为 $232=N_{11}$，因此树的高度为 11，离根最远的叶结点位于第 11 层。故选 C。

---

12. 【王道·卷六-Q08】 由元素序列(27,16,75,38,51)构造平衡二叉树时，首次出现的最小不平衡子树的根（离插入结点最近且平衡因子的绝对值为2的结点）是（ ）。

A. 27    B. 38    C. 51    D. 75

查看答案与解析

答案： D

解析： 按顺序插入各关键字：

1. 插入 27，作为根结点。
2. 插入 16，成为 27 的左孩子。
3. 插入 75，成为 27 的右孩子，此时仍平衡。
4. 插入 38，成为 75 的左孩子，此时各结点仍平衡。
5. 插入 51，其查找路径为

$$27\to 75\to 38$$

因为 $38<51<75$，所以 51 成为 38 的右孩子。

插入后，结点 38 的平衡因子绝对值为 1；结点 75 的左子树高度为 2，右子树高度为 0，因此其平衡因子绝对值为 2。沿插入结点向根回溯，首次遇到的不平衡结点是 75。

故选 D。

---

13. 【王道·卷七-Q07】 右图所示为一棵平衡二叉树（字母不是关键字），在结点 $D$ 的右子树上插入结点 $F$ 后，会导致该平衡二叉树失去平衡，则调整后的平衡二叉树中平衡因子的绝对值为1的分支结点数为（ ）。

A. 0    B. 1    C. 2    D. 3

查看答案与解析

答案： B

解析： 原树结构为：根结点 A 的左孩子为 B、右孩子为 C；C 的左孩子为 E、右孩子为 D。将 F 插入 D 的右子树后，结构为：

Text

A
/ \
B   C
/ \
E   D
\
F

此时 A 的右子树高度比左子树高 2，且新增结点位于 A 的右孩子 C 的右子树中，属于 RR 型失衡，因此对 A 做一次左旋。调整后为：

Text

C
/ \
A   D
/ \   \
B   E   F

各分支结点的平衡因子为：

• C 的左右子树等高，平衡因子为 0；
• A 的左右子树等高，平衡因子为 0；
• D 只有右孩子 F，平衡因子的绝对值为 1。

因此平衡因子绝对值为 1 的分支结点只有 1 个，选择 B。

---

14. 【王道·卷七-Q08】 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 $a$，且已知插入前的左孩子的平衡因子为 $-1$，右孩子的平衡因子为0，则做（ ）调整有可能使其平衡。 I. 左旋 II. 先左旋后右旋 III. 先右旋后左旋 IV. 右旋

A. I和III    B. II和IV    C. I和II    D. III和IV

查看答案与解析

答案： A

解析： 设平衡因子定义为“左子树高度减右子树高度”。结点 $a$ 是插入后最低的不平衡结点，因此从插入位置到 $a$ 之间的孩子结点在插入后仍应保持平衡。

插入前，$a$ 的左孩子平衡因子为 $-1$，说明其右子树比左子树高 1。若在该左孩子的子树内插入并使其高度增加：

• 插入左子树时，左右子树会变得等高，整个左孩子的高度不增加；
• 插入右子树时，该左孩子会先失衡，与“$a$ 是最低不平衡结点”矛盾。

因此，$a$ 不可能因左子树增高而成为最低不平衡结点，只可能因右子树增高而出现右侧失衡。

$a$ 的右孩子原平衡因子为 0，插入后可能出现两种情况：

• 插入右孩子的右子树，形成 RR 型，需对 $a$ 左旋，即 I；
• 插入右孩子的左子树，形成 RL 型，需先右旋后左旋，即 III。

所以可能的调整为 I 和 III，选择 A。

---

15. 【王道·卷八-Q08】 在有15个结点的平衡二叉树上，查找关键字为28（存在该结点）的结点，则依次比较的关键字有可能是（ ）。

A. 30,36    B. 38,48,28    C. 48,18,38,28    D. 60,20,50,40,38,28

查看答案与解析

答案： C

解析： 首先检查二叉排序树查找过程的大小关系，再结合 AVL 树的高度限制判断。

• A：比较 30 后，因为 $28<30$，下一结点必须位于 30 的左子树，关键字应小于 30；但下一关键字为 36，不可能。
• B：比较 38 后，因为 $28<38$，下一关键字应小于 38；但下一关键字为 48，不可能。
• C：查找过程为

$$48\to 18\to 38\to 28$$

各步满足：

$$18<28<38<48$$

可以构造出满足该查找路径的 AVL 树。

• D：该序列需要比较 6 次，即目标结点位于第 6 层。AVL 树高度为 6 时最少需要的结点数满足：

$$N_1=1,N_2=2,N_h=N_{h-1}+N_{h-2}+1$$

从而：

$$N_6=20$$

但题中只有 15 个结点，因此不可能具有 6 层查找路径。

故选 C。

---

16. 【竟成·模拟一-04】 对于关键字集合{1,4,5,10,16,17,21}，能够构成不同的平衡二叉树的数量是（）。

A. 7    B. 10    C. 13    D. 17

查看答案与解析

答案： D

解析： 对一个给定的互异关键字集合，每一种满足 AVL 条件的二叉树形态都唯一对应一棵二叉排序树，因此只需统计含 7 个结点的不同 AVL 树形态。

设 $F(n,h)$ 表示含 $n$ 个结点、高度为 $h$ 的 AVL 树数量。根的左、右子树结点数之和为 $n-1$，且两棵子树高度差不超过 1。

含 7 个结点的 AVL 树分为两类：

1. 高度为 3。此时只能是满二叉树，形态数为 1。
2. 高度为 4。高度为 4 的最少结点数为 7，因此根的两棵子树高度必须分别为 3 和 2。高度为 3、含 4 个结点的最小 AVL 子树共有 4 种形态；高度为 2、含 2 个结点的 AVL 子树共有 2 种形态。高、低子树还可左右互换，因此形态数为：

$$2\times 4\times 2=16$$

总数为：

$$1+16=17$$

因此选择 D。

---

17. 【竟成·模拟二-07】 关于平衡二叉树，下述说法正确的是（）。 I. 在AVL树中，若某个结点的左右孩子的平衡因子均为0，则该结点的平衡因子也是0 II. 同时满足完全二叉树和二叉搜索树定义的二叉树也是AVL树 III. 一棵AVL树的任意两个叶结点的层次差的绝对值不大于1

A. II    B. I、II、III    C. II、III    D. I、III

查看答案与解析

答案： A

解析： 逐项判断如下。

• I 错误。左右孩子各自的平衡因子为 0，只能说明每个孩子内部的左右子树等高，并不能说明这两个孩子本身的高度相等。例如，左孩子可以是一棵高度为 2 的满二叉树，右孩子可以是一个叶结点，两者平衡因子都为 0，但其双亲的平衡因子为 1。
• II 正确。完全二叉树中，任一结点的左右子树高度差都不超过 1，因此完全二叉树本身满足 AVL 树的平衡条件；若它同时又满足二叉搜索树的有序条件，则必然是一棵 AVL 树。
• III 错误。AVL 树只要求每个结点的左右子树高度差不超过 1，并不要求整棵树中任意两个叶结点的层次差不超过 1。不同分支上的叶结点层次可能相差 2 或更多。

因此只有 II 正确，选择 A。

---

7.3.3 红黑树

18. 【王道·卷二-Q08】 下列关于红黑树的说法中，正确的是（ ）。

A. 任意一棵红黑树中红结点的数量和黑结点的数量一定相等

B. 红黑树的黑高可能正好是整棵红黑树高度的一半

C. 红黑树的查找效率要优于平衡二叉树

D. 一棵合法的红黑树应该也是一棵平衡二叉树

查看答案与解析

答案： B

解析： 红黑树通过“任一结点到其所有后代空结点的路径上黑结点数相同”和“红结点不能有红孩子”等性质，将最长路径限制为最短路径的至多 2 倍。

• A 错误。红黑树只约束路径上的黑结点数量，并不要求整棵树中红、黑结点总数相等。
• B 正确。若一条最长路径上的结点颜色呈黑、红交替排列，则树高可以达到黑高的 2 倍，因此黑高可能恰好为整棵树高度的一半。
• C 错误。AVL 树的平衡条件更严格，通常树高更低，单纯从查找路径长度看，AVL 树一般不劣于红黑树。红黑树的优势主要在于插入、删除时调整代价较小。
• D 错误。红黑树只保证近似平衡，某些结点左右子树高度差可以大于 1，因此不一定满足 AVL 树的定义。

故选 B。

---

19. 【王道·卷八-Q09】 在关于红黑树和AVL树的如下说法中，正确的是（ ）。

A. 红黑树查找比AVL树快

B. 红黑树插入和删除时旋转次数比AVL树多

C. 红黑树的结构比AVL树更加平衡

D. 红黑树和AVL树的插入、删除操作的时间复杂度都是 $O({\log }_{2}n)$

查看答案与解析

答案： D

解析： 红黑树和 AVL 树都属于自平衡二叉搜索树，其高度均为 $O(\log n)$，因此查找、插入和删除的最坏时间复杂度均为 $O(\log n)$。

• A 错误。AVL 树平衡得更严格，通常查找路径更短，不能说红黑树查找一定更快。
• B 错误。红黑树插入、删除时通常通过少量旋转配合变色完成调整，旋转次数一般少于 AVL 树。
• C 错误。AVL 树要求任一结点左右子树高度差不超过 1，结构比红黑树更加平衡。
• D 正确。两者的树高都为对数级，所以插入、删除操作的最坏时间复杂度均为 $O({\log }_{2}n)$。

故选 D。

---

20. 【竟成·模拟四-08】 将关键字{41,38,31,12,19,8}依次插入空的红黑树后，关于得到的结果树，下列说法错误的是（）。

A. 有2个红色结点，4个黑色结点    B. 12和41在同一层

C. 8是12的孩子    D. 有相邻黑色内部结点

查看答案与解析

答案： B

解析： 按红黑树插入规则依次插入关键字，最终得到：

Text

38(B)
/     \
19(R)    41(B)
/   \
12(B) 31(B)
/
8(R)

其中，括号内的 B、R 分别表示黑色和红色。

• 红结点为 19、8，共 2 个；黑结点为 38、12、31、41，共 4 个，A 正确。
• 41 位于第 2 层，12 位于第 3 层，二者不在同一层，B 错误。
• 8 是 12 的左孩子，C 正确。
• 38 与 41 是相邻的两个黑色内部结点，D 正确。

因此错误的是 B。

---

21. 【竟成·模拟五-09】 下列选项中，错误的是（）。

A. 若向一棵红黑树连续插入n(n>1)个结点，则该树至少有1个红结点

B. 在一棵红黑树中，如果一个结点是黑的，那么它的孩子结点（若存在）一定是红的

C. 在一棵红黑树中，如果所有结点都是黑的，那么它的形态一定是满二叉树

D. 红黑树的查找路径上不允许出现两个连续的红结点

查看答案与解析

答案： B

解析： - A 正确。红黑树插入的新结点初始为红色，插入调整可能变色或旋转，但从空树连续插入两个以上结点后，树中至少会保留一个红色内部结点。

• B 错误。红黑树只规定红结点的孩子必须是黑色，并未规定黑结点的孩子必须是红色。黑结点的孩子既可以是红色，也可以是黑色。
• C 正确。若所有内部结点均为黑色，则由任一结点到所有空结点的黑高相同可知，各叶层必须等深；同时任一内部结点不能只存在一侧非空子树，否则左右路径黑高不同。因此其形态必为满二叉树。
• D 正确。红黑树明确禁止红结点拥有红孩子，因此任一查找路径上不能出现两个连续的红结点。

故选 B。

---

22. 【竟成·模拟七-05】 将关键字41，38，31，12，19，8依次插入空的红黑树后，下列对结果的树说法错误的是（）。

A. 有2个红色结点，4个黑色结点    B. 12和41的黑高相同

C. 8是31的孩子    D. 树中存在相邻的黑色内部结点

查看答案与解析

答案： C

解析： 插入完成后的红黑树为：

Text

38(B)
/     \
19(R)    41(B)
/   \
12(B) 31(B)
/
8(R)

• 红结点为 19、8，黑结点为 38、12、31、41，A 正确。
• 从 12 到其后代空结点的路径与从 41 到其后代空结点的路径所含黑结点数相同，因此二者黑高相同，B 正确。
• 8 是 12 的左孩子，而不是 31 的孩子，C 错误。
• 38 与 41 是相邻黑色内部结点，D 正确。

因此错误的是 C。

---

7.4 B树和B+树

7.4.1 B树及其基本操作

23. 【王道·卷二-Q09】 对于如下这棵3阶 $B$ 树，完成“删除71”操作后应该是（ ）。

A. 见图中 A    B. 见图中 B    C. 见图中 C    D. 见图中 D

查看答案与解析

答案： C

解析： 3 阶 B 树中，每个结点至多有 3 棵子树、至多有 2 个关键字；除根结点外，每个结点至少有 1 个关键字。

1. 删除叶结点中的关键字 71 后，该叶结点变为空结点，发生下溢。
2. 它的兄弟结点只含关键字 55，已经达到最少关键字数，不能借关键字，因此将 55、双亲中的关键字 60 与空结点合并，形成叶结点 $[55,60]$。
3. 原内部结点 60 因失去唯一关键字而继续下溢。其兄弟内部结点 20 也只有最少关键字，不能借，因此再将左子树、根关键字 47 和右子树合并。
4. 原根结点变空，树高降低 1，新根为 $[20,47]$，三个孩子依次为 $[18]$、$[23]$、$[55,60]$。

该结构对应图中 C，故选 C。

---

24. 【王道·卷六-Q09】 往高度为 $h$ 的 $B$ 树中插入一个关键字时，若该关键字所在的结点已满，且其兄弟结点未满，则需要进行调整，调整后该结点与其兄弟结点各含有一半的关键字，其双亲结点也增加一个关键字；若该结点及其兄弟结点都已满，则需要分裂该结点，调整后树的高度可能会增加1。假设内存足够大，在插入过程中为查找插入位置读入的结点一直在内存中，则最坏情况下可能需要读/写磁盘次数为（ ）。（假设根结点的高度为1，且根结点初始未读入内存。）

A. $h+1$    B. $2h+1$    C. $3h+1$    D. $4h+2$

查看答案与解析

答案： C

解析： 最坏情况是从叶结点开始，分裂一直向上传播到根结点。

1. 查找插入位置需要从根到叶访问 $h$ 个结点，因此需要读磁盘 $h$ 次。
2. 对于除根以外的每一层，满结点分裂后要把分裂所得的两个结点写回磁盘，共有 $h-1$ 层，因此需要：

$$2(h-1)$$

次写磁盘。 3. 根结点最终也分裂时，需要写回分裂所得的两个子结点，并写入新根，共 3 次。

因而最坏情况下总的磁盘读写次数为：

$$h+2(h-1)+3=3h+1$$

故选 C。

---

25. 【王道·卷七-Q09】 在一棵含有 $n$ 个关键字的 $m$ 阶 $B$ 树中进行查找，至多需要读磁盘（ ）次。

A. ${\log }_{2}n$    B. $1+{\log }_{2}n$

C. ${\log }_{[m/2]}((n+1)/2)+1$    D. ${\log }_{[n/2]}((m+1)/2)+1$

查看答案与解析

答案： C

解析： 查找时，每访问一层通常需要读取一个磁盘块，因此最多读磁盘次数等于 B 树的最大高度。

设非根结点的最少分支数为：

$$t=\lceil \frac{m}{2}\rceil$$

高度为 $h$ 的 B 树，为使高度最大，应让各结点尽量少含关键字。此时根至少有 2 个孩子，其余内部结点至少有 $t$ 个孩子，可得最少关键字数为：

$$n_{\min }=2t^{h-1}-1$$

因此：

$$h⩽{\log }_t\frac{n+1}{2}+1$$

选项中以 $[m/2]$ 表示最小分支数，故至多读磁盘次数为：

$${\log }_{[m/2]}\left(\frac{n+1}{2}\right)+1$$

故选 C。

---

26. 【竟成·模拟二-09】 高度为h的B树插入一个新关键字后最多可能生成（）个新结点（提示：本题的新结点指的是与原来B树内容不相同的结点）。

A. h+1    B. 2h    C. 3h    D. 2h+1

查看答案与解析

答案： D

解析： 最坏情况下，插入导致从叶结点到根结点的每一层都发生分裂。

• 对于原树中除根以外的 $h-1$ 个路径结点，每个结点分裂后形成两个内容与原结点不同的结点，共产生：

$$2(h-1)$$

个“新结点”。

• 原根结点分裂时，会形成两个内容改变的子结点，并额外生成一个新根，共计 3 个“新结点”。

因而最多生成：

$$2(h-1)+3=2h+1$$

个新结点，故选 D。

---

27. 【竟成·模拟三-08】 下列关于B树的说法错误的是（）。 I. 查找B树的一个结点的前驱结点就是查找其左孩子的最右结点 II. B树支持顺序查找 III. B树每次都需查询到叶结点，查询性能稳定 IV. 使用B树进行范围查找时，需要依赖中序遍历

A. I、II、III    B. III    C. III、IV    D. II、IV

查看答案与解析

答案： B

解析： 逐项判断如下。

• I 正确。对于位于内部结点中的某个关键字，其直接前驱是该关键字左侧子树中的最大关键字，即沿对应左孩子不断向最右侧查找所得的关键字。
• II 正确。B 树中的关键字具有全序关系，通过中序遍历可以按关键字递增次序访问，因此支持顺序查找。
• III 错误。B 树的关键字既可存放在内部结点，也可存放在叶结点。查找成功时可能在某个内部结点就结束，并非每次都必须查询到叶结点，所以成功查找的磁盘访问次数不完全固定。
• IV 正确。B 树的所有层次都可能存放记录，且叶结点之间没有顺序链指针。进行范围查找时，通常需要从起始关键字位置出发，按照中序次序继续遍历。

因此只有 III 错误，选择 B。

---

28. 【竟成·模拟四-07】 有n个关键字的m阶B树的高度最大是（）。

A. $1+{\log }_{2}n$    B. $1+{\log }_{2}m$

C. $1+{\log }_{\lceil m/2\rfloor }\left(\frac{n+1}{2}\right)$    D. $1+{\log }_{\lceil n/2\rfloor }\left(\frac{m+1}{2}\right)$

查看答案与解析

答案： C

解析： 设这棵 B 树的高度为 $h$，为使高度达到最大，应让每个结点所含关键字数和分支数尽可能少。

对于一棵 $m$ 阶 B 树，除根结点外的非叶结点至少有：

$$t=\lceil \frac{m}{2}\rceil$$

个分支，因此至少有 $t-1$ 个关键字。根结点若不是叶结点，则至少有 2 个分支、1 个关键字。

高度为 $h$ 时，关键字总数的最小值为：

$$n_{\min }=2t^{h-1}-1$$

由 $n⩾n_{\min }$，得：

$$\begin{array}{rl}n+1& ⩾2t^{h-1}\\ h& ⩽1+{\log }_t\frac{n+1}{2}\end{array}$$

因此最大高度为：

$$1+{\log }_{\lceil m/2\rceil }\left(\frac{n+1}{2}\right)$$

故选 C。

---

29. 【竟成·模拟六-07】 下列关于B树的说法错误的是（）。

A. 高度为h的m阶B树最多存储mʰ-1个关键字

B. 所有叶结点都在同一层次上

C. 含n个结点（不含失败结点）的m阶（m>2）B树至少包含(n-1)×(⌈m/2⌉-1)+1个关键字

D. 和二叉搜索树相同，B树高度的增加也是发生在底部

查看答案与解析

答案： D

解析： 逐项判断如下。

• A 正确。高度为 $h$ 的 $m$ 阶 B 树，每个结点最多有 $m-1$ 个关键字，满树共有：

$$1+m+m^2+\cdots +m^{h-1}=\frac{m^h-1}{m-1}$$

个结点，因此最多包含：

$$(m-1)\cdot \frac{m^h-1}{m-1}=m^h-1$$

个关键字。

• B 正确。B 树是一棵多路平衡查找树，所有叶结点都处于同一层次。
• C 正确。根结点至少有 1 个关键字，其余 $n-1$ 个结点至少各有 $\lceil m/2\rceil -1$ 个关键字，因此至少有：

$$1+(n-1)\left(\lceil \frac{m}{2}\rceil -1\right)$$

个关键字。

• D 错误。B 树插入时，结点分裂可能逐层向上传播；当根结点分裂并产生新根时，树高增加。因此 B 树高度的增加发生在根部，而不是底部。二叉搜索树通常通过在叶结点下方插入新结点而增加高度。

故选 D。

---

7.4.2 B+树的基本概念

30. 【王道·卷一-Q10】 下列关于 $B$ 树和 $B+$ 树的描述中，正确的是（ ）。 I. $B$ 树的结点可以同时存储关键字和数据，而 $B+$ 树的非叶结点仅可以存储关键字 II. $B+$ 树的叶结点之间存在指针链接，这有利于进行范围查询 III. 在相同的磁盘 $I/O$ 条件下，$B+$ 树通常比 $B$ 树更适用于数据库索引 IV. $B$ 树在进行插入和删除操作时，可能需要合并或分裂结点以保持其平衡性

A. 仅I和IV    B. 仅I、II和IV    C. 仅I、III和IV    D. I、II、III和IV

查看答案与解析

答案： D

解析： 四个说法均正确。

• I 正确。B 树的内部结点可以直接保存关键字及其对应记录；B+ 树的非叶结点只保存索引关键字和子树指针，所有记录均存放在叶结点中。
• II 正确。B+ 树的叶结点通常按关键字顺序通过链指针连接，定位范围起点后可沿链表顺序扫描，因此范围查询效率较高。
• III 正确。B+ 树非叶结点不保存完整记录，在相同磁盘块大小下可容纳更多关键字和分支，树通常更矮；同时叶结点有序链接，适合数据库中的等值查询和范围查询。
• IV 正确。B 树插入时结点可能溢出并发生分裂，删除时结点可能下溢，需要借关键字或合并结点，以维持各结点关键字数约束及所有叶结点等高。

因此 I、II、III、IV 均正确，选择 D。

---

7.5 散列 Hash 表

7.5.3 处理冲突的方法

31. 【王道·卷三-Q09】 散列表的表长为 $m=14$，散列函数为 $Hash(key)=key\%11$。表中已有4个结点，地址分别为 $addr(15)=4$、$addr(38)=5$、$addr(61)=6$ 和 $addr(84)=7$，其余地址均为空。若采用二次探测法解决冲突，则关键码值为49的散列地址是（ ）。

A. 8    B. 3    C. 5    D. 9

查看答案与解析

答案： D

解析： 首先计算关键字 49 的初始散列地址：

$$H(49)=49\mathrm{mod}11=5$$

地址 5 已被占用。二次探测法的探测增量通常依次为：

$$1^2,-1^2,2^2,-2^2,\dots$$

因而探测过程为：

$$\begin{array}{rlrl}5+1^2& \equiv 6(\mathrm{mod}14)& & \text{已占用}\\ 5-1^2& \equiv 4(\mathrm{mod}14)& & \text{已占用}\\ 5+2^2& \equiv 9(\mathrm{mod}14)& & \text{为空}\end{array}$$

所以关键字 49 应存放在地址 9，故选 D。

---

32. 【王道·卷四-Q09】 在下列关于散列表的说法中，正确的个数是（ ）。 I. 散列表的平均查找长度与处理冲突方法无关 II. 在散列表中，“比较”操作一般是不可避免的 III. 散列表查找成功时的平均查找长度只与表长有关 IV. 若在散列表中删除一个元素，则只需简单地将该元素删除即可

A. 1    B. 2    C. 3    D. 4

查看答案与解析

答案： A

解析： 逐项判断如下。

• I 错误。不同的冲突处理方法会形成不同的探测序列或链表结构，直接影响平均查找长度。
• II 正确。散列函数只能确定候选地址；由于可能发生冲突，通常仍需比较关键字，才能判断查找成功或失败。
• III 错误。查找成功的平均查找长度与散列函数、装填因子、关键字分布及冲突处理方法等均有关，并非只由表长决定。
• IV 错误。采用开放定址法时，若直接把被删位置置为空，可能截断其他同义词的探测序列，因此通常要设置“已删除”标记；只有链地址法等结构中才能直接从链中删除结点。

因此只有 II 正确，正确个数为 1，选择 A。

---

33. 【王道·卷五-Q09】 散列表的装填因子 $a$ 可以大于或等于1的情况仅发生在使用（ ）法处理冲突时。

A. 线性探测    B. 二次探测    C. 双散列    D. 链地址

查看答案与解析

答案： D

解析： 装填因子定义为：

$$\alpha =\frac{\text{表中已存关键字数}}{\text{散列表地址空间长度}}$$

线性探测、二次探测和双散列都属于开放定址法，每个表地址至多存放一个关键字，因此关键字数不能超过表长，必须满足：

$$\alpha ⩽1$$

链地址法允许多个同义关键字链接在同一个散列地址对应的链表中，所以关键字总数可以等于或超过表长，即 $\alpha ⩾1$ 是可能的。

故选 D。

---

34. 【王道·卷八-Q10】 散列表的地址范围为 $0\sim 17$，散列函数为 $H(k)=k\mathrm{mod}17$。采用线性探测法处理冲突，将关键字序列26,25,72,38,8,18,59依次存储到散列表中。元素59存放在散列表中的地址是（ ）。

A. 8    B. 9    C. 10    D. 11

查看答案与解析

答案： D

解析： 依次插入各关键字：

• $26\mathrm{mod}17=9$，存入地址 9。
• $25\mathrm{mod}17=8$，存入地址 8。
• $72\mathrm{mod}17=4$，存入地址 4。
• $38\mathrm{mod}17=4$，地址 4 冲突，线性探测到地址 5。
• $8\mathrm{mod}17=8$，地址 8、9 均被占用，存入地址 10。
• $18\mathrm{mod}17=1$，存入地址 1。

对关键字 59：

$$H(59)=59\mathrm{mod}17=8$$

地址 8、9、10 均已占用，继续线性探测到地址 11，该地址为空，因此 59 存入地址 11。

故选 D。

---

35. 【竟成·模拟六-09】 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入足够长的散列表中，至少要进行（）次探测。

A. k-1次    B. k次    C. k+1次    D. k(k+1)/2次

查看答案与解析

答案： D

解析： 这 $k$ 个关键字互为同义词，说明它们的初始散列地址相同。采用线性探测法时：

• 第 1 个关键字探测 1 次即可插入；
• 第 2 个关键字需探测 2 次；
• 第 3 个关键字需探测 3 次；
• ……
• 第 $k$ 个关键字需探测 $k$ 次。

因此总探测次数至少为：

$$1+2+\cdots +k=\frac{k(k+1)}{2}$$

故选 D。

---

7.5.4 散列查找及性能分析的应用

36. 【竟成·模拟一-09】 散列表HT长度为7、初始为空，散列函数H(k)=k%7。在HT中依次插入关键字11,21,39,46,55，然后再删除键值21。若分别采用拉链法（尾插法）和线性探测再散列法处理冲突，则下列描述错误的是（）。

A. 采用拉链法时，查找成功的平均查找长度为7/4，查找失败的平均查找长度为4/7

B. 采用线性探测再散列法时，查找成功的平均查找长度为9/4，查找失败的平均查找长度为22/7

C. 采用拉链法时，HT的装填因子为2/7，采用线性探测再散列法时，HT的装填因子为4/7

D. 采用线性探测再散列法时，在HT中查找关键字14，确认查找失败时的散列地址为2

查看答案与解析

答案： C

解析： 先计算各关键字的散列地址：

$$\begin{array}{rlrlrl}H(11)& =4,& H(21)& =0,& H(39)& =4,\\ H(46)& =4,& H(55)& =6& & \end{array}$$

删除 21 后，表中保留 11、39、46、55，共 4 个关键字。

拉链法：

• 地址 4 的链表为 $11\to 39\to 46$；
• 地址 6 的链表为 $55$；
• 地址 0 的链表因删除 21 而为空。

查找成功的比较次数分别为 1、2、3、1，因此：

$$AS{L}_{成功}=\frac{1+2+3+1}{4}=\frac{7}{4}$$

查找失败时，各地址需要遍历的链长之和为 $3+1=4$，故：

$$AS{L}_{失败}=\frac{4}{7}$$

线性探测法： 插入后各关键字位置为：

$$11\to 4,21\to 0,39\to 5,46\to 6,55\to 1$$

删除 21 后，地址 0 应保留“已删除”标记，不能直接置为空。四个关键字成功查找的探测次数分别为 1、2、3、3，因此：

$$AS{L}_{成功}=\frac{1+2+3+3}{4}=\frac{9}{4}$$

从地址 0～6 开始查找失败所需的探测次数依次为：

$$3,2,1,1,6,5,4$$

所以：

$$AS{L}_{失败}=\frac{3+2+1+1+6+5+4}{7}=\frac{22}{7}$$

查找关键字 14 时，$H(14)=0$，依次探测地址 0、1、2，在地址 2 遇到真正的空单元后确认失败，因此 D 正确。

删除后两种方法中均有 4 个有效关键字，装填因子都为：

$$\alpha =\frac{4}{7}$$

因而 C 中“拉链法装填因子为 $2/7$”错误，故选 C。