408模拟选择题 · 数据结构 · 第7章查找

7.1 查找的基本概念

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

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

查看答案与解析

答案： A

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

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

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

7.2 顺序查找和折半查找

7.2.2 折半查找

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

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

查看答案与解析

答案： C

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

\displaystyle 1,\quad 2,\quad 4,\quad 5

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

\displaystyle \begin{aligned} ASL_{\text{成功}} &=\dfrac{1\times1+2\times2+4\times3+5\times4}{12}\\ &=\dfrac{1+4+12+20}{12}\\ &=\dfrac{37}{12}. \end{aligned}

故选 C。

【王道·卷四-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

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

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

\displaystyle \left\lfloor\dfrac{1+12}{2}\right\rfloor=6

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

新中点为：

\displaystyle \left\lfloor\dfrac{7+12}{2}\right\rfloor=9

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

新中点为第 7 个元素 $\displaystyle 70$ 。因为 $\displaystyle 75>70$ ，继续查找第 8 个元素。
比较第 8 个元素 $\displaystyle 75$ ，查找成功。

因此查找次序为：

\displaystyle 65,81,70,75

选择 D。

【竟成·模拟一-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 正确。各层结点数依次为 $\displaystyle 1,2,4,3$ ，所以：

\displaystyle ASL_{\text{成功}} =\dfrac{1\times1+2\times2+4\times3+3\times4}{10} =\dfrac{29}{10}.

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

\displaystyle 3+3+3+4+4+3+4+4+3+4+4=39

因此：

\displaystyle ASL_{\text{失败}}=\dfrac{39}{11}.

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

\displaystyle 1,4,3,2,7,6,10,9,8,5

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

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

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

查看答案与解析

答案： D

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

对于 $\displaystyle 20$ 个内部结点：

\displaystyle 2^4-1=15<20<2^5-1=31

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

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

7.2.3 分块查找

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

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

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

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

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

查看答案与解析

答案： B

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

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

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

7.3 树形查找

7.3.1 二叉排序树 BST

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

故选 D。

【王道·卷五-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：依次得到约束

\displaystyle 22<52<76<80

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

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

\displaystyle 43<52<54

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

D：查找区间依次收缩为

\displaystyle 22<52<63

整个序列也可能出现。

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

【竟成·模拟五-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：比较过程中的区间依次缩小，最终有

\displaystyle 354<363<367

序列合法。

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

\displaystyle 363<911

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

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

故选 C。

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

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

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

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

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

查看答案与解析

答案： C

解析： 逐项分析如下。

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

因此错误的是 C。

7.3.2 平衡二叉树

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

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

查看答案与解析

答案： C

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

\displaystyle N_h=N_{h-1}+N_{h-2}+1

初值为：

\displaystyle N_1=1,\qquad N_2=2

依次计算：

\displaystyle \begin{aligned} N_3&=4,\quad N_4=7,\quad N_5=12,\quad N_6=20,\\ N_7&=33,\quad N_8=54,\quad N_9=88,\quad N_{10}=143,\\ N_{11}&=232. \end{aligned}

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

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

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

查看答案与解析

答案： D

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

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

\displaystyle 27\rightarrow75\rightarrow38

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

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

故选 D。

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

题图缺失： 卷七_Q07_平衡二叉树（原引用：images/卷七_Q07_平衡二叉树.png）

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。

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

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

查看答案与解析

答案： A

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

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

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

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

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

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

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

【王道·卷八-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 后，因为 $\displaystyle 28<30$ ，下一结点必须位于 30 的左子树，关键字应小于 30；但下一关键字为 36，不可能。
B：比较 38 后，因为 $\displaystyle 28<38$ ，下一关键字应小于 38；但下一关键字为 48，不可能。
C：查找过程为

\displaystyle 48\rightarrow18\rightarrow38\rightarrow28

各步满足：

\displaystyle 18<28<38<48

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

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

\displaystyle N_1=1,\quad N_2=2,\quad N_h=N_{h-1}+N_{h-2}+1

从而：

\displaystyle N_6=20

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

故选 C。

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

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

查看答案与解析

答案： D

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

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

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

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

\displaystyle 2\times4\times2=16

总数为：

\displaystyle 1+16=17

因此选择 D。

【竟成·模拟二-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 红黑树

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

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

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

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

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

查看答案与解析

答案： B

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

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

故选 B。

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

A. 红黑树查找比AVL树快

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

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

D. 红黑树和AVL树的插入、删除操作的时间复杂度都是

\displaystyle O(\log_{2}n)

查看答案与解析

答案： D

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

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

故选 D。

【竟成·模拟四-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。

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

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

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

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

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

查看答案与解析

答案： B

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

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

故选 B。

【竟成·模拟七-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树及其基本操作

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

题图缺失： 卷二_Q09_3阶B树删除71（原引用：images/卷二_Q09_3阶B树删除71.png）

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

查看答案与解析

答案： C

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

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

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

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

\displaystyle h + 1

\displaystyle 2h + 1

\displaystyle 3h + 1

\displaystyle 4h + 2

查看答案与解析

答案： C

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

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

\displaystyle 2(h-1)

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

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

\displaystyle h+2(h-1)+3=3h+1

故选 C。

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

\displaystyle \log_{2}n

\displaystyle 1 + \log_{2}n

\displaystyle \log_{[m/2]}((n + 1) / 2) + 1

\displaystyle \log_{[n/2]}((m + 1) / 2) + 1

查看答案与解析

答案： C

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

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

\displaystyle t=\left\lceil\dfrac{m}{2}\right\rceil

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

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

因此：

\displaystyle h\leqslant \log_t\dfrac{n+1}{2}+1

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

\displaystyle \log_{[m/2]}\left(\dfrac{n+1}{2}\right)+1

故选 C。

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

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

查看答案与解析

答案： D

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

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

\displaystyle 2(h-1)

个“新结点”。

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

因而最多生成：

\displaystyle 2(h-1)+3=2h+1

个新结点，故选 D。

【竟成·模拟三-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。

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

\displaystyle 1+\log_2 n

\displaystyle 1+\log_2 m

\displaystyle 1+\log_{\lceil m/2\rfloor}\left(\dfrac{n+1}{2}\right)

\displaystyle 1+\log_{\lceil n/2\rfloor}\left(\dfrac{m+1}{2}\right)

查看答案与解析

答案： C

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

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

\displaystyle t=\left\lceil\dfrac{m}{2}\right\rceil

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

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

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

由 $\displaystyle n\geqslant n_{\min}$ ，得：

\displaystyle \begin{aligned} n+1 &\geqslant 2t^{h-1} \\ h &\leqslant 1+\log_t\dfrac{n+1}{2} \end{aligned}

因此最大高度为：

\displaystyle 1+\log_{\lceil m/2\rceil}\left(\dfrac{n+1}{2}\right)

故选 C。

【竟成·模拟六-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 正确。高度为 $\displaystyle h$ 的 $\displaystyle m$ 阶 B 树，每个结点最多有 $\displaystyle m-1$ 个关键字，满树共有：

\displaystyle 1+m+m^2+\cdots+m^{h-1}=\dfrac{m^h-1}{m-1}

个结点，因此最多包含：

\displaystyle (m-1)\cdot\dfrac{m^h-1}{m-1}=m^h-1

个关键字。

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

\displaystyle 1+(n-1)\left(\left\lceil\dfrac{m}{2}\right\rceil-1\right)

个关键字。

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

故选 D。

7.4.2 B+树的基本概念

【王道·卷一-Q10】 下列关于 $\displaystyle B$ 树和 $\displaystyle B+$ 树的描述中，正确的是（）。 I. $\displaystyle B$ 树的结点可以同时存储关键字和数据，而 $\displaystyle B+$ 树的非叶结点仅可以存储关键字 II. $\displaystyle B+$ 树的叶结点之间存在指针链接，这有利于进行范围查询 III. 在相同的磁盘 $\displaystyle I/O$ 条件下， $\displaystyle B+$ 树通常比 $\displaystyle B$ 树更适用于数据库索引 IV. $\displaystyle 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 处理冲突的方法

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

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

查看答案与解析

答案： D

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

\displaystyle H(49)=49\bmod 11=5

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

\displaystyle 1^2,-1^2,2^2,-2^2,\ldots

因而探测过程为：

\displaystyle \begin{aligned} 5+1^2 &\equiv 6\pmod {14} &&\text{已占用}\\ 5-1^2 &\equiv 4\pmod {14} &&\text{已占用}\\ 5+2^2 &\equiv 9\pmod {14} &&\text{为空} \end{aligned}

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

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

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

查看答案与解析

答案： A

解析： 逐项判断如下。

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

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

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

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

查看答案与解析

答案： D

解析： 装填因子定义为：

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

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

\displaystyle \alpha\leqslant 1

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

故选 D。

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

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

查看答案与解析

答案： D

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

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

对关键字 59：

\displaystyle H(59)=59\bmod 17=8

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

故选 D。

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

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

查看答案与解析

答案： D

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

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

因此总探测次数至少为：

\displaystyle 1+2+\cdots+k=\dfrac{k(k+1)}{2}

故选 D。

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

【竟成·模拟一-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

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

\displaystyle \begin{aligned} H(11)&=4, & H(21)&=0, & H(39)&=4,\\ H(46)&=4, & H(55)&=6 \end{aligned}

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

拉链法：

地址 4 的链表为 $\displaystyle 11\to39\to46$ ；
地址 6 的链表为 $\displaystyle 55$ ；
地址 0 的链表因删除 21 而为空。

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

\displaystyle ASL_{成功}=\dfrac{1+2+3+1}{4}=\dfrac{7}{4}

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

\displaystyle ASL_{失败}=\dfrac{4}{7}

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

\displaystyle 11\to4,\quad21\to0,\quad39\to5,\quad46\to6,\quad55\to1

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

\displaystyle ASL_{成功}=\dfrac{1+2+3+3}{4}=\dfrac{9}{4}

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

\displaystyle 3,2,1,1,6,5,4

所以：

\displaystyle ASL_{失败}=\dfrac{3+2+1+1+6+5+4}{7}=\dfrac{22}{7}

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

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

\displaystyle \alpha=\dfrac{4}{7}

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

7.1 查找的基本概念​

7.2 顺序查找和折半查找​

7.2.2 折半查找​

7.2.3 分块查找​

7.3 树形查找​

7.3.1 二叉排序树 BST​

7.3.2 平衡二叉树​

7.3.3 红黑树​

7.4 B树和B+树​

7.4.1 B树及其基本操作​

7.4.2 B+树的基本概念​

7.5 散列 Hash 表​

7.5.3 处理冲突的方法​

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

7.1 查找的基本概念

7.2 顺序查找和折半查找

7.2.2 折半查找

7.2.3 分块查找

7.3 树形查找

7.3.1 二叉排序树 BST

7.3.2 平衡二叉树

7.3.3 红黑树

7.4 B树和B+树

7.4.1 B树及其基本操作

7.4.2 B+树的基本概念

7.5 散列 Hash 表

7.5.3 处理冲突的方法

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