目标

通过 7 道 408 历年真题与 5 道王道习题，检查自己能否准确处理二叉排序树的定义、构造与查找路径。

完成后应能：

• 用中序有序性解释 BST 的排序能力，并推断最大/最小关键字结点的指针特征；
• 由插入序列构造 BST，并判断哪些序列能（或不能）生成给定树形；
• 用"上下界持续收紧"判别一条序列能否构成查找路径；
• 说明删除再插入对树形的影响，区分叶结点与非叶结点两种情形。

前置知识

建议先阅读 8.2 节 二叉排序树，掌握插入构造、三类删除与"查找路径 = 根到结点路径"的对应关系。

环境、输入与预期输出

• 环境：任意现代浏览器；图形题建议先在纸上重画树形再作答。
• 输入：本页 12 道单项选择题，题面中的树形用 1(2(_,3),4) 式记法表示（括号内依次为左、右子树，_ 表示空指针）。
• 预期输出：一份独立作答记录，以及每道错题的错误原因和正确推理。

作答方法

1. 阅读题面后点击一个选项，先写下选择依据；
2. 点击"提交答案"，再核对对错、正确答案和题解；
3. 做错的题点击"重新作答"后再次推导，直到能说明其余选项为什么不成立；
4. 完成全部题目后再使用页面末尾的答案总览复核，避免只记答案字母。

选择题

答题进度已答 0/12正确 0

第 1 题

难度基础考点二叉排序树、中序遍历标识search-wd73-q02

按（ ）遍历二叉排序树得到的序列是一个有序序列。

请选择一个答案

A先序

B中序

C后序

D层次

第 2 题

难度基础考点二叉排序树、存储结构标识search-wd73-q04

在常用的描述二叉排序树的存储结构中，关键字值最大的结点（ ）。

请选择一个答案

A左指针一定为空

B右指针一定为空

C左右指针均为空

D左右指针均不为空

第 3 题

难度进阶考点二叉排序树、插入构造标识search-wd73-q06

分别以下列序列构造二叉排序树，与其他 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)

第 4 题

难度基础考点二叉排序树、查找路径、比较次数标识search-wd73-q07

从空树开始，依次插入元素 52, 26, 14, 32, 71, 60, 93, 58, 24, 41 后构成了一棵二叉排序树。在该树中查找 60 需要进行的比较次数为（ ）。

请选择一个答案

A3

B4

C5

D6

第 5 题

难度进阶考点二叉排序树、形态计数标识search-wd73-q09

五个不同结点构成的二叉查找树的形态共有（ ）种。

请选择一个答案

A20

B30

C32

D42

第 6 题

难度基础考点二叉排序树、树高标识search-wd73-q10

构造一棵具有 n 个结点的二叉排序树时，最理想情况下的深度为（ ）。

请选择一个答案

An/2

Bn

C$\lfloor {\log }_2(n+1)\rfloor$

D$\lceil {\log }_2(n+1)\rceil$

第 7 题

难度基础考点二叉搜索树、关键字取值范围标识search-408-2024-q07

一棵二叉搜索树如题 7 图所示，k1、k2、k3 分别是对应结点中保存的关键字。子树 T 的任一结点中保存的关键字 x 满足的是（ ）。

k1(_, k2(k3(_, T), _))

结构（文字版）：根为 k1（左子树省略），右孩子为 k2；k2 的左孩子为 k3、右子树省略；k3 的左子树省略，右子树即 T。

请选择一个答案

Ax < k1

Bx > k2

Ck1 < x < k3

Dk3 < x < k2

第 8 题

难度基础考点二叉排序树、插入序列标识search-408-2020-q05

下列给定的关键字输入序列中，不能生成如下二叉排序树的是（ ）。

4(2(1, 3), 5)

结构（文字版）：根 4，左孩子 2（其左右孩子分别为 1、3），右孩子 5。

请选择一个答案

A4, 5, 2, 1, 3

B4, 5, 1, 2, 3

C4, 2, 5, 3, 1

D4, 2, 1, 3, 5

第 9 题

难度基础考点二叉排序树、关键字大小关系标识search-408-2018-q06

已知二叉排序树如下图所示，元素之间应满足的大小关系是（ ）。

x1(_, x2(x3(_, x4(x5, _)), _))

结构（文字版）：根 x1 只有右孩子 x2；x2 只有左孩子 x3；x3 只有右孩子 x4；x4 只有左孩子 x5。

请选择一个答案

Ax1 < x2 < x5

Bx1 < x4 < x5

Cx3 < x5 < x4

Dx4 < x3 < x5

第 10 题

难度进阶考点二叉排序树、查找路径标识search-wd73-q05

设二叉排序树中关键字由 1 到 1000 的整数构成，现要查找关键字为 363 的结点。下述关键字序列中，不可能是二叉排序树上查找序列的是（ ）。

请选择一个答案

A2, 252, 401, 398, 330, 344, 397, 363

B924, 220, 911, 244, 898, 258, 362, 363

C925, 202, 911, 240, 912, 245, 363

D2, 399, 387, 219, 266, 382, 381, 278, 363

第 11 题

难度基础考点二叉排序树、查找路径标识search-408-2011-q07

对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ）。

请选择一个答案

A95, 22, 91, 24, 94, 71

B92, 20, 91, 34, 88, 35

C21, 89, 77, 29, 36, 38

D12, 25, 71, 68, 33, 34

第 12 题

难度进阶考点二叉排序树、删除与插入标识search-408-2013-q06

在任意一棵非空二叉排序树 T1 中，删除某结点 v 之后形成二叉排序树 T2，再将 v 插入 T2 形成二叉排序树 T3。下列关于 T1 与 T3 的叙述中，正确的是（ ）。

I. 若 v 是 T1 的叶结点，则 T1 与 T3 不同

II. 若 v 是 T1 的叶结点，则 T1 与 T3 相同

III. 若 v 不是 T1 的叶结点，则 T1 与 T3 不同

IV. 若 v 不是 T1 的叶结点，则 T1 与 T3 相同

请选择一个答案

A仅 I、III

B仅 I、IV

C仅 II、III

D仅 II、IV

答案总览（建议完成全部题目后查看）

1. 第 1 题：B
2. 第 2 题：B
3. 第 3 题：C
4. 第 4 题：A
5. 第 5 题：D
6. 第 6 题：D
7. 第 7 题：D
8. 第 8 题：B
9. 第 9 题：C
10. 第 10 题：C
11. 第 11 题：A
12. 第 12 题：C

完成清单

• 12 道题均在提交答案前独立作答；
• 能独立推导"不可能构成查找路径"类题目中被违反的上下界；
• 能逐项模拟插入序列并核对最终树形；
• 能解释"删除再插入"对叶结点与非叶结点结论的差异。

思考题

1. 为什么 BST 的中序遍历恰好得到升序序列？把"左 < 根 < 右"改成"左 > 根 > 右"会得到什么？
2. 查找路径判别题中，"上下界收紧"和 BST 插入时的路径有什么对应关系？
3. 删除双孩子结点时用中序后继填补，为什么重新插入后 v 必然变成叶结点？

复盘

• 我是否把"查找路径"当成任意合法的根到结点路径，而忽略了比较次序的约束？
• 图形题里我是否先重画树形、列出每条路径的不等式，再对照选项？
• 哪道题我靠"感觉像"作答，而没有落到上下界或逐项模拟？