2026-05-18 练习题答案与解析

单项选择题

1. 若二叉树的前序遍历序列与中序遍历序列相同，则该二叉树是？

答案：D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树

解析： 前序遍历顺序为"根 → 左 → 右"，中序遍历顺序为"左 → 根 → 右"。两者相等的充要条件是每一棵子树（包括整棵树）的"左子树"部分为空——否则前序会先出现"根"，而中序会先出现左子树的某个结点，二者必然不同。

因此结论是：要么是空树/只有根的二叉树，要么每个非叶结点都只有右子树而没有左子树（整棵树退化为一条向右延伸的链）。

2. 权值 {3, 4, 5, 6, 8, 9, 11, 12} 的哈夫曼树的带权外部路径长度（WPL）为？

答案：B. 169

解析： 哈夫曼树的 WPL 等于所有非叶（内部）结点的权值之和。反复合并当前最小的两个权值：

步骤	合并	新结点权值	剩余集合
1	3 + 4	7	{5, 6, 7, 8, 9, 11, 12}
2	5 + 6	11	{7, 8, 9, 11, 11, 12}
3	7 + 8	15	{9, 11, 11, 12, 15}
4	9 + 11	20	{11, 12, 15, 20}
5	11 + 12	23	{15, 20, 23}
6	15 + 20	35	{23, 35}
7	23 + 35	58	{58}

WPL = 7 + 11 + 15 + 20 + 23 + 35 + 58 = 169。

3. 若 X 在先序中位于 Y 之前，在后序中位于 Y 之后，则 X 与 Y 的关系是？

答案：C. X 是 Y 的祖先

解析： 分析两种遍历对四种位置关系的表现：

关系	先序中 X 与 Y	后序中 X 与 Y
X 是 Y 的祖先	X 在前（根先于子树）	X 在后（根后于子树）
X 是 Y 的后裔	X 在后	X 在前
X 是 Y 的左兄弟（X 在 Y 左侧）	X 在前	X 在前
X 是 Y 的右兄弟（X 在 Y 右侧）	X 在后	X 在后

只有"X 是 Y 的祖先"满足"先序 X 在前、后序 X 在后"，故选 C。

4. 森林中每个结点最多 2 个孩子，叶子数为 L，度为 2 的结点数为 N，求树的棵数 T？

答案：C. L − N

解析： 设度为 1 的结点数为 n₁。

总结点数：n = L + n₁ + N
总边数（每个度为 k 的结点贡献 k 条出边）：E = 0·L + 1·n₁ + 2·N = n₁ + 2N
森林性质：n 个结点的森林若由 T 棵树组成，则 E = n − T

代入：

n_1 + 2N = (L + n_1 + N) - T

化简得 T = L − N。

注意：该结论与单棵二叉树中"n₀ = n₂ + 1"是一致的——单棵树时 T = 1，即 L − N = 1。

5. 关于回溯法，下列叙述不正确的是？

答案：C. 回溯算法需要借助队列数据结构来保存从根结点到当前扩展结点的路径

解析： 回溯法本质是对解空间树的深度优先搜索（DFS），沿一条路径深入到底再回退，因此使用的是栈（显式栈或递归调用栈），用以保存"从根到当前扩展结点"的路径。一旦判定当前子树不可能包含有效解就剪枝并回溯到上一层。

A 正确：回溯既能枚举所有解，也能找到任意可行解后立即返回。
B 正确：系统性指它按解空间树有序枚举不会遗漏；跳跃性指通过剪枝跳过不可能产生有效解的子树。
C 错误：应为栈而非队列。队列对应的是广度优先搜索 / 分支限界法。
D 正确：这正是回溯法的剪枝判定流程。

6. 前序序列与后序序列正好相反的二叉树一定是？

答案：B. 高度等于其结点数

解析： 前序为"根 → 左 → 右"，后序为"左 → 右 → 根"。若它们正好互为逆序，则对任一子树，其根在前序的第一个、在后序的最后一个，自然满足；关键约束在子树本身：

若某结点同时拥有左、右子树，则前序中"左子树整体"在"右子树整体"之前，后序中也是"左子树整体在右子树整体之前"（仅根的位置变到了最后）。而要前后序互为逆序，要求左子树整体在后序中处于右子树之后——矛盾。

所以每个结点至多只有一个孩子，整棵树退化为一条单链（可能左、可能右、也可能左右混合）。

此时层数 0, 1, 2, …, n−1，最大层数 = n−1，高度 = (n−1) + 1 = n，恰等于结点数。

A 只覆盖 n ≤ 1 的特例，不够一般；
C、D 把"单链"误限定为"只有右孩子链"或"只有左孩子链"，但左右混合的单链同样满足条件（例如根-左-右-左的链）。

故选 B。

7. 二叉树中叶结点在前序、中序、后序中的相对次序如何变化？

答案：B. 不发生改变

解析： 前序（根-左-右）、中序（左-根-右）、后序（左-右-根）三种遍历差别仅在"根"的访问时机——但都遵循"先递归左子树，再递归右子树"的顺序。

对任意两个叶结点 X、Y：

若它们位于同一子树，则递归同样规则进入该子树后顺序一致；
若它们分属不同子树，则左子树的所有结点（含叶子）整体先于右子树的所有结点出现。

因此所有叶结点在三种遍历中始终按"从左到右"的相对位置出现，相对次序不变。

8. 度为 3 的树中 n₃=2，n₂=1，求叶子数 n₀。

答案：C. 6

解析： 设度为 0、1、2、3 的结点数分别为 n₀、n₁、n₂=1、n₃=2。

总结点数：n = n₀ + n₁ + 1 + 2 = n₀ + n₁ + 3
总边数（每个度为 k 的结点贡献 k 条出边）：E = n₁ + 2·1 + 3·2 = n₁ + 8
单棵树边数性质：E = n − 1

代入：

n_1 + 8 = (n_0 + n_1 + 3) - 1

化简得 n₀ = 6。注意 n₁ 的具体取值不影响结论（在等式两边被抵消）。

9. 由同一组关键字集合构造的各棵二叉排序树（BST）？

答案：B. 其形态不一定相同，平均查找长度也不一定相同

解析： BST 的形态完全由关键字的插入顺序决定，关键字集合相同但插入顺序不同会得到不同形态的 BST。

例：关键字集合 {1, 2, 3}

按 2, 1, 3 顺序插入 → 形态平衡，ASL = (1 + 2 + 2)/3 = 5/3
按 1, 2, 3 顺序插入 → 退化为右斜链，ASL = (1 + 2 + 3)/3 = 2

形态不同 ⇒ 各结点到根的路径长度不同 ⇒ ASL 通常也不同。故选 B。

10. 适合对动态查找表进行高效率查找的组织结构是？

答案：C. 二叉排序树

解析： "动态查找表"要求高效支持查找、插入、删除三种操作。

A 有序表：可用二分查找做到 O(log n) 检索，但插入/删除要移动 O(n) 个元素，只适合静态查找表；
B 堆排序 / D 快速排序：是排序算法，不是查找用的组织结构，与 ADT Map 的实现无关；
C 二叉排序树（BST）：平均情况下查找、插入、删除均为 O(log n)，且无需移动大量元素，是动态查找表的经典实现。

故选 C。

判断题

11. 若某叶子是子树前序序列的最后一个结点，则它一定是中序序列的最后一个结点。

答案：错误

解析： 前序的最后一个结点和中序的最后一个结点未必相同。

反例：根 A 只有一个左孩子 B（B 是叶子，无右子树）。

前序：A, B —— 最后是叶子 B ✓ 满足前提
中序：B, A —— 最后是 A，不是 B

实际上中序的最后一个结点是"沿右孩子方向一路向下"到达的结点；而前序的最后一个结点要在该子树的最右一支底部才必然等于中序最后一个。当根没有右子树时两者完全不同，故命题错误。

12. 若某非空二叉树的先序序列和后序序列正好相同，则该二叉树只有一个根结点。

答案：正确

解析： 先序首字符是根；后序首字符是先序意义下的"最左下叶"。

当 n = 1 时，先序 = 后序 = [根]，相同 ✓
当 n ≥ 2 时，根至少有一个孩子，后序的第一个结点必为某个叶子 ≠ 根，因此先序首 ≠ 后序首，两序列必不同。

故两序列相同 ⇒ 该二叉树只有根结点。

13. n 个结点的 BST 中树高最小者搜索效率最好。

答案：正确

解析： BST 的查找路径长度受树高约束。树高 h 越小，最坏查找次数（h 次）越少；平均查找长度 ASL 也大致随树高减小而减小。当 BST 趋于平衡（高度约为 ⌈log₂(n+1)⌉）时达到下界，此时无论最坏还是平均检索效率都是最优的。故"树高最小 ⇒ 搜索效率最好"成立。

14. 前序 HGEDBFCA，中序 EGBDHFAC，后序为 EBDGACFH，是否正确？

答案：正确

解析： 由前序首字符 H 是根；中序中 H 左侧 EGBD 为左子树，右侧 FAC 为右子树。

左子树（前序 GEDB，中序 EGBD）：根 G；G 的左为 E（叶），G 的右子树（前序 DB，中序 BD）：根 D，D 的左为 B。
右子树（前序 FCA，中序 FAC）：根 F；F 无左子树，F 的右子树（前序 CA，中序 AC）：根 C，C 的左为 A。

二叉树结构：

后序（左→右→根）：

左子树 G 的后序：E（G.left）→ B（D.left）→ D → G ⇒ E B D G
右子树 F 的后序：A（C.left）→ C → F ⇒ A C F
根 H

合起来：E B D G A C F H ✓ 与题给后序一致。

15. 查找 363 时三个序列皆可能是 BST 查找路径，是否正确？

答案：错误

解析： BST 查找路径上每访问一个结点 v，都会确定向左或向右走，因此后续访问的所有结点都必须落在 v 与目标共同决定的区间内。逐项验证：

A) 2, 252, 401, 398, 330, 344, 397, 363 —— 区间变化：

当前	与 363 比较	走向	后续允许区间
2	<	右	(2, +∞)
252	<	右	(252, +∞)
401	>	左	(252, 401)
398	>	左	(252, 398)
330	<	右	(330, 398)
344	<	右	(344, 398)
397	>	左	(344, 397)
363	=	—	—

每一项都落在前一步给出的区间内 ✓ 可能。

B) 925, 202, 911, 240, 912, ... —— 925 > 363 向左；202 < 363 向右（区间变 (202, 925)）；911 > 363 向左（区间 (202, 911)）；240 < 363 向右（区间 (240, 911)）。下一项 912 > 911 越界 ✗ 不可能。

C) 935, 278, 347, 621, 299, ... —— 935 → 左（区间 (−∞, 935)）；278 → 右（(278, 935)）；347 → 右（(347, 935)）；621 → 左（(347, 621)）。下一项 299 < 347 越界 ✗ 不可能。

只有 A 合法，故"三个皆有可能"是错误的。

16. 构建 N 个结点的二叉最小堆的时间复杂度是 O(N log₂N) ?

答案：错误

解析： 建堆有两种常见方式：

逐个插入 + siftup：每次插入 O(log N)，共 N 次，总复杂度 O(N log N)。
Floyd 自底向上 + siftdown：从最后一个非叶结点向根遍历，每个结点的下沉成本与其在树中的高度成正比。总成本为 $\sum_{h=0}^{\log N} \lceil N/2^{h+1}\rceil \cdot h = O(N)$ ，是线性的。

通常说的"建堆复杂度"指 Floyd 方法，即 O(N) 而非 O(N log₂N)。故命题错误。

填空题

17. 含 n 个结点的树，只有度为 k 的分支结点和度为 0 的叶子，叶子数为？

答案：n₀ = ((k − 1)·n + 1) / k（等价写法：n − (n − 1)/k）

解析： 设分支结点数为 n_k，叶子数为 n₀。

结点总数：n = n_k + n₀
总边数：每个分支结点产生 k 条出边 ⇒ E = k·n_k
树的边数性质：E = n − 1

由 k·n_k = n − 1 得 n_k = (n − 1)/k，代入第一式：

n_0 = n - n_k = n - \frac{n-1}{k} = \frac{kn - (n-1)}{k} = \frac{(k-1)n + 1}{k}

（注：该公式成立的前提是 (n−1) 能被 k 整除，即结点构成确实可行。）

18. 小根堆 [8, 15, 10, 21, 34, 16, 12] 删除 8 后重建堆的比较次数？

答案：3 次

解析： 删除堆顶（最小值 8）的标准做法：把堆末尾元素 12 移到根，再将其向下调整（siftdown）。删除后堆数组为 [12, 15, 10, 21, 34, 16]（0 号下标存 12，5 号下标存 16，size = 6）。

下滤过程（自顶向下）：

当前位置	操作	比较
索引 0（值 12）	左孩子 15、右孩子 10：比较 15 与 10，取较小者 10	1 次
	比较 12 与较小孩子 10：12 > 10，交换；12 下到索引 2	1 次
索引 2（值 12）	只剩左孩子 16（索引 5），无右孩子	—
	比较 12 与 16：12 < 16，停止	1 次

合计 3 次关键字比较，最终堆为 [10, 15, 12, 21, 34, 16]。

19. 二叉树共 101 个结点，叶子 36 个，求度为 2 与度为 1 的结点数。

答案：n₂ = 35；n₁ = 30

解析： 设度为 0、1、2 的结点数分别为 n₀、n₁、n₂。

由"叶子数 = 度 2 结点数 + 1"的恒等式（推导见第 1 题）：n₀ = n₂ + 1 ⇒ n₂ = 36 − 1 = 35。
由结点总数：n = n₀ + n₁ + n₂ ⇒ n₁ = 101 − 36 − 35 = 30。

20. 前序为 ADC 的二叉树树型数？

答案：5 种

解析： n 个结点的二叉树形态数为卡特兰数 $C_n = \binom{2n}{n}/(n+1)$ 。当 n = 3 时 $C_3 = 5$ 。

具体地，前序首字符 A 必为根；剩余 DC 可按"左子树前序 + 右子树前序"拆分：左子树取前 0、1、2 个结点，分别得到 3 种顶层结构，再对每个非空子树递归同理。穷举 5 种形态（前序均为 ADC）：

①        ②        ③          ④         ⑤
  A        A         A           A          A
 /        /           \           \          \
D        D            D            D          D
/         \          / \          /            \
C          C        D? (略)      C              C

按"D 在左 / D 在右"，"C 在 D 的左 / 右 / 或为 A 的另一边孩子"组合可得：

编号	结构（用括号表示）
1	A(D(C, _), _) — D 是 A 的左孩子，C 是 D 的左孩子
2	A(D(_, C), _) — D 是 A 的左孩子，C 是 D 的右孩子
3	A(D, C) — D 是 A 的左孩子，C 是 A 的右孩子
4	A(_, D(C, _)) — D 是 A 的右孩子，C 是 D 的左孩子
5	A(, D(, C)) — D 是 A 的右孩子，C 是 D 的右孩子

共 5 种。

21. 中序 DGBAECF、后序 GDBEFCA，求前序。

答案：ABDGCEF

解析： 后序最后字符 A 为整棵树的根。在中序 DGBAECF 中 A 左侧 DGB 为左子树、右侧 ECF 为右子树。

左子树（中序 DGB，后序 GDB）：后序最后 B 为根。中序中 B 左侧 DG 为左子树、右侧为空。
- 子子树（中序 DG，后序 GD）：根 D，D 的左为空，右子树中序仅 G → G 是 D 的右孩子。
右子树（中序 ECF，后序 EFC）：后序最后 C 为根。中序中 C 左侧 E，右侧 F。
- E 是 C 的左孩子，F 是 C 的右孩子。

整棵树结构：

前序（根→左→右）：A，左子树前序 B D G，右子树前序 C E F，合起来 A B D G C E F。

22. 57 个结点的完全二叉树（编号从 0 起），编号 18 的父、编号 19 的右孩子？

答案：父结点编号 = 8；右子女编号 = 40

解析： 当层次编号从 0 开始时，完全二叉树的标准公式为：

父结点：⌊(i − 1) / 2⌋
左孩子：2i + 1
右孩子：2i + 2

代入：

编号 18 的父：⌊(18 − 1) / 2⌋ = ⌊17/2⌋ = 8
编号 19 的右孩子：2 × 19 + 2 = 40

验证存在性：总结点 57，编号范围 0..56，40 ≤ 56 ✓。

（提示：若题目改成"从 1 起编号"，则父为 ⌊i/2⌋、左孩子 2i、右孩子 2i + 1，结果会不同，注意区分。）

综合题

23. 满二叉树前序转后序的递归函数填空。

答案与完整代码：

def pre2post(preorder, start, length):
    if length == 1:
        return preorder[start]                              # (1)
    else:
        length = (length - 1) // 2                          # (2)
        left  = pre2post(preorder, start + 1, length)       # (3)
        right = pre2post(preorder, start + 1 + length, length)  # (4)
        root  = preorder[start]                             # (5)
        return left + right + root

解析： 满二叉树每个非叶结点都恰有两个孩子，所以子树规模总满足"左 = 右 = (length − 1) / 2"。

(1) 长度为 1 时序列就是单个叶子，前序 = 后序 = preorder[start]。
(2) 除去根后剩余 length − 1 个结点平分给左右子树，每边 (length − 1) // 2 个；用它更新 length，便于后面递归调用复用这个变量名。
(3) 左子树前序从 start + 1 开始，长度为更新后的 length。
(4) 右子树紧挨左子树之后，起点是 start + 1 + length，长度同样为 length。
(5) 当前子树的根就是其前序第一个字符 preorder[start]。

后序遍历的顺序是"左 → 右 → 根"，所以最后拼接 left + right + root。

手验：

pre2post("ABC", 0, 3)：根 A，length = 1，左 = "B"，右 = "C"，返回 "B" + "C" + "A" = "BCA" ✓
pre2post("ABDECFG", 0, 7)：根 A，length = 3；
- 左 = pre2post("ABDECFG", 1, 3)：根 B，length = 1，左 "D"、右 "E" → "DEB"
- 右 = pre2post("ABDECFG", 4, 3)：根 C，length = 1，左 "F"、右 "G" → "FGC"
- 合："DEBFGCA" ✓

24. 用扩充二叉树前序序列构建二叉树并中序输出 —— 填空。

答案与完整代码：

s = input()
ptr = 0

class BinaryTree:
    def __init__(self, data, left=None, right=None):
        self.data, self.left, self.right = data, left, right
    def addLeft(self, tree):
        self.left = tree
    def addRight(self, tree):
        self.right = tree
    def inorderTraversal(self):
        if self.left:
            self.left.inorderTraversal()      # ①
        print(self.data, end="")
        if self.right:
            self.right.inorderTraversal()     # ②

def buildTree():
    global ptr
    if s[ptr] == "@":
        ptr += 1
        return None                            # ③
    tree = BinaryTree(s[ptr])                  # ④
    ptr += 1
    tree.addLeft(buildTree())                  # ⑤
    tree.addRight(buildTree())                 # ⑥
    return tree

tree = buildTree()                             # ⑦
tree.inorderTraversal()

解析：

① / ②：中序为"左 → 根 → 右"，对左右非空子树递归调用 inorderTraversal()。
③：扩充二叉树中 @ 代表空引用。遇到 @ 时已"消耗"当前位置，让 ptr 后移一位并返回 None，告诉上层"这里没有子树"。
④：当前字符非 @，先用它创建结点 BinaryTree(s[ptr])。
⑤ / ⑥：随后按"前序 = 根 → 左 → 右"递归建立左右子树并挂载。注意此时 ptr 已在第 ④ 步之后递增过。
⑦：在外层调用 buildTree() 触发递归，从前序序列首字符开始构建整棵树。

手工验证（输入 ABD@G@@@CE@@F@@）：

ptr=0  A → 建根 A
ptr=1  B → 建 A.left = B
ptr=2  D → 建 B.left = D
ptr=3  @ → D.left = None
ptr=4  G → 建 D.right = G
ptr=5  @ → G.left = None
ptr=6  @ → G.right = None
ptr=7  @ → B.right = None
ptr=8  C → 建 A.right = C
ptr=9  E → 建 C.left = E (左右皆 @)
ptr=12 F → 建 C.right = F (左右皆 @)

得到二叉树：

中序遍历输出 DGBAECF ✓。

2026-05-18 练习题答案与解析

On this page