7.3.4 本节试题精选
## 7.3.4 本节试题精选 ### 一、单项选择题 01. 对于二叉排序树，下面的说法中，（ ）是正确的。 A. 二叉排序树是动态树表，查找失败时插入新结点，会引起树的重新分裂和组合 B. 对二叉排序树进行层序遍历可得到有序序列 C. 用逐点插入法构造二叉排序树，若先后插入的关键字有序，二叉排序树的深度最大 D. 在二叉排序树中进行查找，关键字的比较次数不超过结点数的 1/2 02. 按（ ）遍历二叉排序树得到的序列是一个有序序列。 A. 先序 B. 中序 C. 后序 D. 层次 03. 在二叉排序树中进行查找的效率与（ ）有关。 A. 二叉排序树的深度 B. 二叉排序树的结点的个数 C. 被查找结点的度 D. 二叉排序树的存储结构 04. 在常用的描述二叉排序树的存储结构中，关键字值最大的结点（ ）。 A. 左指针一定为空 B. 右指针一定为空 C. 左右指针均为空 D. 左右指针均不为空 05. 设二叉排序树中关键字由 1 到 1000 的整数构成，现要查找关键字为 363 的结点，下述关键字序列中，不可能是在二叉排序树上查找的序列是（ ）。 A. 2,252,401,398,330,344,397,363 B. 924,220,911,244,898,258,362,363 C. 925,202,911,240,912,245,363 D. 2,399,387,219,266,382,381,278,363 06. 分别以下列序列构造二叉排序树，与用其他 3 个序列所构造的结果不同的是（ ）。 A. (100, 80, 90, 60, 120, 110, 130) B. (100, 120, 110, 130, 80, 60, 90) C. (100, 60, 80, 90, 120, 110, 130) D. (100, 80, 60, 90, 120, 130, 110) 07. 从空树开始，依次插入元素 52,26,14,32,71,60,93,58,24 和 41 后构成了一棵二叉排序树。在该树查找 60，要进行比较的次数为（ ）。 A. 3 B. 4 C. 5 D. 6 08. 在含有 $n$ 个结点的二叉排序树中查找某个关键字的结点时，最多进行（ ）次比较。 <!-- page: 304 --> 2027年数据结构考研复习指导 A. $n/2$ B. $\log_2 n$ C. $\log_2 n + 1$ D. $n$ 09. 五个不同结点构造的二又查找树的形态共有（ ）种。 A. 20 B. 30 C. 32 D. 42 10. 构造一棵具有 $n$ 个结点的二又排序树时，最理想情况下的深度为（ ）。 A. $n/2$ B. $n$ C. $\left\lfloor \log_2(n + 1)\right\rfloor$ D. $\left\lceil \log_2(n + 1)\right\rceil$ 11. 含有 20 个结点的平衡二又树的最大深度为（ ）。 A. 4 B. 5 C. 6 D. 7 12. 具有 5 层结点的平衡二又树至少有（ ）个结点。 A. 10 B. 12 C. 15 D. 17 13. 高度为 3 的平衡二又排序树的形态共有（ ）种。 A. 13 B. 14 C. 16 D. 15 14. 在平衡二又树的基本操作中，可能发生两次旋转的操作是（ ）。 A. 添加、删除结点 B. 仅删除结点 C. 仅添加结点 D. 都不会 15. 将关键字 1,2,3,…,1024 依次插入到初始为空的平衡二又树中，假设只有一个根结点的二又树的高度为 0，则插入结束后的平衡二又树的高度为（ ）。 A. 8 B. 9 C. 10 D. 11 16. 下列关于红黑树和 AVL 树的说法中，不正确的是（ ）。 I. 一棵含有 $n$ 个结点的红黑树的高度至多为 $2\log_2(n + 1)$ II. 若一个结点是红色的，则它的父结点和孩子结点都是黑色的 III. 红黑树的查询效率一般要优于含有相同结点数的 AVL 树 IV. 若 AVL 树的某结点的左右孩子的平衡因子都是零，则该结点的平衡因子也是零 A. I、III B. III C. II、IV D. III、IV 17. 下列关于红黑树和AVL树的描述中，不正确的是（ ）。 A. 两者都属于自平衡的二又树 B. 两者查找、插入、删除的时间复杂度都相同 C. 红黑树插入和删除过程至多有 2 次旋转操作 D. 红黑树的任意一个结点的左右子树高度（含叶结点）之比不超过 2 18. 下列关于红黑树的说法中，正确的是（ ）。 A. 红黑树的红结点的数目最多和黑结点的数目相同（不考虑虚构结点） B. 若红黑树的所有结点都是黑色的，则它一定是一棵满二又树 C. 红黑树的任何一个分支结点都有两个非空孩子结点 D. 红黑树的子树也一定是红黑树 19. 下列四个选项中，满足红黑树定义的是（ ）。 A.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
B.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
C.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
D.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
20. 将关键字 1,2,3,4,5,6,7 依次插入初始为空的红黑树 $T$ ，则 $T$ 中红结点的个数是（ ）。 A. 1 B. 2 C. 3 D. 4 <!-- page: 305 --> 第7章 查找 293 21. 将关键字 5,4,3,2,1 依次插入初始为空的红黑树 $T$，则 $T$ 的最终形态是（）。 A.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
B.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
C.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
D.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
22. 在下图所示的红黑树中插入结点 2 且染成红色后，则下一步应进行的操作是（）。 A. 左旋 B. 右旋 C. 变色 D. 无须调整 23. 【2009 统考真题】下列二叉排序树中，满足平衡二叉树定义的是（）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A. B. C. D. 24. 【2010 统考真题】在下图所示的平衡二叉树中插入关键字 48 后得到一棵新平衡二叉树，在新平衡二叉树中，关键字 37 所在结点的左右子结点中保存的关键字分别是（）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
B.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
C.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
D.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A. 13,48
B. 24,48
C. 24,53
D. 24,90
25. 【2011 统考真题】对下列关键字序列，不可能构成某二叉排序树中一条查找路径的是（）。
A. 95,22,91,24,94,71
B. 92, 20, 91, 34, 88, 35
C. 21,89,77,29,36,38
D. 12, 25, 71, 68, 33, 34
26. 【2012 统考真题】若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为（）。
A. 12
B. 20
C. 32
D. 33
27. 【2013 统考真题】在任意一棵非空二叉排序树 $T_{1}$ 中，删除某结点 $\nu$ 之后形成二叉排序树 $T_{2}$，再将 $\nu$ 插入 $T_{2}$ 形成二叉排序树 $T_{3}$。下列关于 $T_{1}$ 与 $T_{3}$ 的叙述中，正确的是（）。
I. 若 $\nu$ 是 $T_{1}$ 的叶结点，则 $T_{1}$ 与 $T_{3}$ 不同
<!-- page: 306 -->
2027年数据结构考研复习指导
II. 若 $v$ 是 $T_{1}$ 的叶结点，则 $T_{1}$ 与 $T_{3}$ 相同
III. 若 $v$ 不是 $T_{1}$ 的叶结点，则 $T_{1}$ 与 $T_{3}$ 不同
IV. 若 $v$ 不是 $T_{1}$ 的叶结点，则 $T_{1}$ 与 $T_{3}$ 相同
A. 仅 I、III
B. 仅 I、IV
C. 仅 II、III
D. 仅 II、IV
28. 【2013 统考真题】若将关键字 1, 2, 3, 4, 5, 6, 7 依次插入初始为空的平衡二叉树 $T$，则 $T$ 中平衡因子为 0 的分支结点的个数是（ ）。
A. 0
B. 1
C. 2
D. 3
29. 【2015 统考真题】现有一棵无重复关键字的平衡二叉树 (AVL)，对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。
A. 根结点的度一定为 2
B. 树中最小元素一定是叶结点
C. 最后插入的元素一定是叶结点
D. 树中最大元素一定是无左子树
30. 【2018 统考真题】已知二叉排序树如右图所示，元素之间应满足的大小关系是（ ）。
A. $x_{1} < x_{2} < x_{5}$
B. $x_{1} < x_{4} < x_{5}$
C. $x_{3} < x_{5} < x_{4}$
D. $x_{4} < x_{3} < x_{5}$
31. 【2019 统考真题】在任意一棵非空平衡二叉树（AVL 树） $T_{1}$ 中，删除某结点 $v$ 之后形成平衡二叉树 $T_{2}$，再将 $v$ 插入 $T_{2}$ 形成平衡二叉树 $T_{3}$。下列关于 $T_{1}$ 与 $T_{3}$ 的叙述中，正确的是（ ）。
I. 若 $v$ 是 $T_{1}$ 的叶结点，则 $T_{1}$ 与 $T_{3}$ 可能不相同
II. 若 $v$ 不是 $T_{1}$ 的叶结点，则 $T_{1}$ 与 $T_{3}$ 一定不相同
III. 若 $v$ 不是 $T_{1}$ 的叶结点，则 $T_{1}$ 与 $T_{3}$ 一定相同
A. 仅 I
B. 仅 II
C. 仅 I、II
D. 仅 I、III
32. 【2020 统考真题】下列给定的关键字输入序列中，不能生成右边二叉排序树的是（ ）。
A. 4, 5, 2, 1, 3
B. 4, 5, 1, 2, 3
C. 4, 2, 5, 3, 1
D. 4, 2, 1, 3, 5
33. 【2021 统考真题】给定平衡二叉树如右图所示，插入关键字 23 后，根中的关键字是（ ）。
A. 16
B. 20
C. 23
D. 25
34. 【2024 统考真题】一棵二叉搜索树如右图所示，$k_{1}$，$k_{2}$，$k_{3}$ 分别是对应结点中保存的关键字。子树 $T$ 的任一结点中保存的关键字 $x$ 满足的是（ ）。
A. $x < k_{1}$
B. $x > k_{2}$
C. $k_{1} < x < k_{3}$
D. $k_{3} < x < k_{2}$
## 二、综合应用题
01. 一棵二叉排序树按先序遍历得到的序列为(50, 38, 30, 45, 40, 48, 70, 60, 75, 80)，试画出该二叉排序树，并求出等概率下查找成功和查找失败的平均查找长度。
02. 按照序列(40, 72, 38, 35, 67, 51, 90, 8, 55, 21)建立一棵二叉排序树，画出该树，并求出在等概率的情况下，查找成功的平均查找长度。
<!-- page: 307 -->
第7章 查找
295
03. 依次把结点(34, 23, 15, 98, 115, 28, 107)插入初始状态为空的平衡二叉排序树，使得在每次插入后保持该树仍然是平衡二叉树。请依次画出每次插入后所形成的平衡二叉排序树。
04. 给定一个关键字集合{25, 18, 34, 9, 14, 27, 42, 51, 38}，假定查找各关键字的概率相同，请画出其最佳二叉排序树。
05. 试编写一个算法，判断给定的二叉树是否是二叉排序树。
06. 设计一个算法，求出指定结点在给定二叉排序树中的层次。
07. 利用二叉树遍历的思想编写一个判断二叉树是否是平衡二叉树的算法。
08. 设计一个算法，求出给定二叉排序树中最小和最大的关键字。
09. 设计一个算法，从大到小输出二叉排序树中所有值不小于 $k$ 的关键字。
10. 编写一个递归算法，在一棵有 $n$ 个结点的、随机建立的二叉排序树上查找第 $k（1 \leqslant k \leqslant n$ ）小的元素，并返回指向该结点的指针。要求算法的平均时间复杂度为 $O(\log_2 n)$。二叉排序树的每个结点中除 data, lchild, rchild 等数据成员外，增加一个 count 成员，保存以该结点为根的子树上的结点个数。
## 7.3.5 答案与解析
### 一、单项选择题
#### 01. C
二叉排序树插入新结点时不会引起树的分裂组合。对二叉排序树进行中序遍历可得到有序序列。当插入的关键字有序时，二叉排序树会形成一个长链，此时深度最大。在此种情况下进行查找，有可能需要比较每个结点的关键字，超过总结点数的 $1/2$。
#### 02. B
由二叉排序树的定义不难得出中序遍历二叉树得到的序列是一个有序序列。
#### 03. A
二叉排序树的查找路径是自顶向下的，其平均查找长度主要取决于树的高度。
#### 04. B
在二叉排序树的存储结构中，每个结点由三部分构成，其中左（或右）指针指向比该结点的关键字值小（或大）的结点。关键字值最大的结点位于二叉排序树的最右位置，因此它的右指针一定为空（有可能不是叶结点）。还可用反证法，若右指针不为空，则右指针上的关键字肯定比原关键字大，所以原关键字结点一定不是值最大的，与条件矛盾，所以右指针一定为空。
#### 05. C
在二叉排序树上查找时，先与根结点值进行比较，若相同，则查找结束，否则根据比较结果，沿着左子树或右子树向下继续查找。根据二叉排序树的定义，有左子树结点值 $\leqslant$ 根结点值 $\leqslant$ 右子树结点值。C序列中，比较911关键字后，应转向其左子树比较240，左子树中不应出现比911更大的数值，但240竟有一个右孩子结点值为912，所以不可能是正确的序列。
#### 06. C
按照二叉排序树的构造方法，不难得到A,B,D序列的构造结果相同。
#### 07. A
以第一个元素为根结点，依次将元素插入树，生成的二叉排序树如右图所示。进行查找时，先与根结点比较，然后根据比较结果，继续在左子树或右子树上进行查找。比较的结点依次为52,71,60。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 308 -->
2027年数据结构考研复习指导
08. D
当输入序列是一个有序序列时，构造的二叉排序树是一个单支树，当查找一个不存在的关键字值或最后一个结点的关键字值时，需要 $n$ 次比较。
09. D
五个不同结点构造的二叉查找树，中序序列是确定的。先序序列的个数为 $n = 5$ 的卡特兰数，加上中序序列和先序序列能唯一确定一棵二叉树，因此二叉排序树的形态共有 $\mathrm{Catalan}(5) = 42$ 种。
10. D
当二叉排序树的叶结点全部都在相邻的两层内时，深度最小。理想情况是从第一层到倒数第二层为满二叉树。类比完全二叉树，可得深度为 $\lceil \log_2(n + 1) \rceil$。
11. C
平衡二叉树结点数的递推公式为 $n_0 = 0$，$n_1 = 1$，$n_2 = 2$，$n_h = 1 + n_{h-1} + n_{h-2}$（$h$ 为平衡二叉树高度，$n_h$ 为构造此高度的平衡二叉树所需的最少结点数）。通过递推公式可得，构造5层平衡二叉树至少需12个结点，构造6层至少需要20个结点。
12. B
设 $n_h$ 表示高度为 $h$ 的平衡二叉树中含有的最少结点数，则有 $n_1 = 1, n_2 = 2, n_h = n_{h-1} + n_{h-2} + 1$，由此求出 $n_5 = 12$，对应的AVL如右图所示。
13. D
高度为3的平衡二叉树的左右子树的高度共有三种情况：① 左右子树都是高度为2的平衡二叉树；② 左子树是高度为1的平衡二叉树，右子树是高度为2的平衡二叉树；③ 左子树是高度为2的平衡二叉树，右子树是高度为1的平衡二叉树。高度为1的平衡二叉树只有1种形态，即单个结点，如图1所示；高度为2的平衡二叉树有3种形态，如图2所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图1 图2 因此，对于情况①，共有 $3 \times 3 = 9$ 种树形态；对于情况②，共有 $1 \times 3 = 3$ 种树形态；情况③和情况②类似，也有3种树形态，所以共有 $9 + 3 + 3 = 15$ 种树形态。 14. A 插入和删除结点都有可能引起LR平衡旋转或者RL平衡旋转，发生两次旋转操作。 15. C 当按关键字有序的顺序插入初始为空的平衡二叉树时，若关键字个数 $n = 2^k - 1$ 时，则该平衡二叉树一定是一棵满二叉树（可以用 $1 \sim 3$、$1 \sim 7$ 手工验证）。当插入关键字1023时，平衡二叉树正好是一棵满二叉树，高度为9。因此，插入关键字1024后，平衡二叉树的高度为10。 16. D 说法I和II都是红黑树的性质。AVL是高度平衡的二叉查找树，红黑树是适度平衡的二叉查找树，从这一点也可以看出AVL的查询效率往往更优，说法III错误。AVL的某结点的左右孩子的平衡因子都是零，并不能说明左右子树的高度相等，因此该结点的平衡因子不一定为零，说法IV错误。 17. C 自平衡的二叉排序树是指在插入和删除时能自动调整以保持其所定义的平衡性，两者都属于 <!-- page: 309 --> 第7章 查找 297 自平衡二叉树，选项 A 正确。两者的查找、插入、删除操作的时间复杂度都为 $O(\log_2 n)$，选项 B 正确。在红黑树中删除结点时，情况 1 可能变为情况 2、3 或 4，情况 2 会变为情况 3，可能会出现旋转次数超过 2 次的情况，选项 C 错误。从任一结点到每个叶结点的所有路径都包含相同数目的黑结点，没有两个连续的红结点，且叶结点是黑色的，这意味着在任一结点到其左右子树中最远和最近的叶结点之间，红结点的数目小于或等于黑结点的数目，路径长度之比不超过 2，选项 D 正确。 18. B 红黑树的红结点数目最大可以是黑结点数目的 2 倍（如一棵有 3 个结点的红黑树，第 1 层为黑色，第 2 层为红色），选项 A 错误。从根结点出发到所有叶结点的黑结点数是相同的，若所有结点都是黑色，则一定是满二叉树，选项 B 正确。考虑某个黑结点，它可以有一个空叶结点孩子和一个非空红结点孩子，选项 C 错误。红黑树中可能存在红结点，根结点为红色的子树不是红黑树，选项 D 错误。 19. A 红黑树是一种特殊的二叉排序树，选项 B 不满足二叉排序树的性质。选项 C 中，结点 2 的左右黑结点数不同。在选项 D 中，结点 3 的左右黑结点数不同。只有选项 A 满足红黑树的定义。 20. C 关键字 1,2,3,4,5,6,7 依次插入红黑树后的形态变化如下：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
21. D 关键字 5,4,3,2,1 依次插入红黑树后的形态变化如下：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
22. B 插入结点 2 且将其染成红色后违反不红红原则，并且拟结点是黑色，应进行 LL 旋转，将结 <!-- page: 310 --> 2027年数据结构考研复习指导 点3右旋旋转到结点5的位置，结点2和结点5分别成为结点3的左右孩子，然后将结点3染成黑色，结点2和结点5染成红色。因此，下一步应进行右旋操作。 ## 23. B 根据平衡二叉树的定义，任意结点的左右子树高度差的绝对值不超过1。而其余3个答案均可以找到不满足条件的结点。答题时可以把每个非叶结点的平衡因子都写出来。 ## 24. C 插入48以后，该二叉树根结点的平衡因子由-1变为-2，在最小不平衡子树根结点的右子树（R）的左子树（L）中插入新结点引起的不平衡属于RL型平衡旋转（先右旋后左旋）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
调整后，关键字37所在结点的左右子结点中保存的关键字分别是24、53。 ## 25. A 在二叉排序树中，左子树结点值小于根结点，右子树结点值大于根结点。在选项A中，当查找到91后再向24查找，说明这一条路径（左子树）之后查找的数都要比91小，而后面却查找到了94（解题过程中，建议配合画图），因此错误。 画图法：各选项对应的查找过如下图所示。选项B、C、D对应的查找树都是二叉排序树，选项A对应的查找树不是二叉排序树，因为在91为根的左子树中出现了比91大点的结点94。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 选项A的查找过程
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 选项B的查找过程
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) 选项C的查找过程
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(d) 选项D的查找过程