#树与图 章节测

范围：树与二叉树（性质、遍历、线索、树/森林转换、哈夫曼、并查集）与图（存储、遍历、最小生成树、最短路径、拓扑排序、关键路径）。说明：本卷共 25 题，全部单选，全部为模拟题（非真题），细节题为主，风格对齐 408 统考选择题。限时 50 分钟。答案与解析见文末，做完前不要下翻。

#第 1 题

某二叉树中度为 2 的结点有 9 个，度为 1 的结点有 4 个，则该二叉树的总结点数为（ ）

A. 22 B. 23 C. 24 D. 25

#第 2 题

一棵完全二叉树共有 1001 个结点，则叶结点个数为（ ）

A. 500 B. 501 C. 502 D. 无法确定

#第 3 题

100 个结点的完全二叉树，编号为 50 的结点（ ）

A. 有两个孩子 B. 只有左孩子 C. 只有右孩子 D. 是叶结点

#第 4 题

一棵完全二叉树第 6 层（根为第 1 层）有 8 个叶结点，则该完全二叉树的结点数最多为（ ）

A. 63 B. 79 C. 111 D. 119

#第 5 题

已知某二叉树的先序序列为 1 2 4 5 3、中序序列为 4 2 5 1 3，则其后序序列为（ ）

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

#第 6 题

下列序列组合中，不能唯一确定一棵二叉树的是（ ）

A. 先序序列与中序序列 B. 后序序列与中序序列 C. 先序序列与后序序列 D. 层序序列与中序序列

#第 7 题

$$ 个结点的二叉树按二叉链表存储并中序线索化后，线索（存前驱/后继的指针域）的总数为（ ）

A. $$ B. $$ C. $$ D. $$

#第 8 题

在中序线索二叉树中，结点 p 的 rtag 为 0，则 p 的中序后继是（ ）

A. p 的 rchild 所指结点 B. p 的右子树中最左下的结点 C. p 的双亲结点 D. p 的右子树中最右下的结点

#第 9 题

将一棵树转换为二叉树后，该二叉树根结点的特点是（ ）

A. 一定没有左子树 B. 一定没有右子树 C. 左右子树都可能有且非空 D. 左右子树一定都为空

#第 10 题

设森林 F 对应的二叉树为 B（由 F 转换而来），则下列对应关系正确的是（ ）

A. F 的先序遍历序列与 B 的先序遍历序列相同 B. F 的先序遍历序列与 B 的中序遍历序列相同 C. F 的中序遍历序列与 B 的后序遍历序列相同 D. F 的中序遍历序列与 B 的先序遍历序列相同

#第 11 题

由 5 个权值 {2, 3, 4, 5, 6} 构造哈夫曼树（每次合并权值最小的两棵树），所得树的结点总数为（ ）

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

#第 12 题

由权集 {2, 4, 5, 7} 构造哈夫曼树，其带权路径长度（WPL）为（ ）

A. 34 B. 35 C. 36 D. 46

#第 13 题

下列编码组中，不是前缀码的是（ ）

A. {0, 10, 110, 111} B. {00, 01, 10, 11} C. {0, 1, 10, 11} D. {1, 01, 001, 000}

#第 14 题

并查集在采用"按秩合并 + 路径压缩"优化后，其查找（Find）与合并（Union）操作的单次均摊时间复杂度为（ ）

A. $$ B. $$ C. $$（$$ 为反阿克曼函数，近似常数） D. $$ 严格常数

#第 15 题

设森林 F 由 3 棵树组成，结点数分别为 4、5、6，将 F 转换为二叉树 B 后，B 的根结点右子树中的结点数为（ ）

A. 10 B. 11 C. 14 D. 与树的形态有关

#第 16 题

对二叉树进行中序非递归遍历（借助栈）时，一个结点出栈并立即被访问，发生的时机是（ ）

A. 结点刚被压入栈之后 B. 该结点的左子树全部处理完之后 C. 该结点的右子树全部处理完之后 D. 该结点的左右子树都处理完之后

#第 17 题

关于二叉树的非递归后序遍历（使用一个栈和指针 r 记录最近访问的结点），指针 r 的作用是（ ）

A. 记录当前栈最深的位置，便于回退 B. 判断栈顶结点的右子树是否已经访问过，防止重复进入 C. 记录后序序列的最后一个结点 D. 用于区分先序与后序访问时机

#第 18 题

$$ 个结点的二叉树中，叶结点数最少为（ ）

A. 0 B. 1 C. $$ D. $$

#第 19 题

具有 $$ 个顶点、$$ 条边的无向图采用邻接表存储，其边结点（表结点）的总数为（ ）

A. $$ B. $$ C. $$ D. $$

#第 20 题

下列关于图存储结构的说法中，错误的是（ ）

A. 十字链表是有向图的存储结构，一条弧只对应一个边结点 B. 邻接多重表是无向图的存储结构，一条边只对应一个边结点 C. 有向图的邻接表中，求任一顶点的入度需要遍历整个邻接表 D. 无向图的邻接矩阵一定是对称矩阵，且对角线元素全为 1

#第 21 题

对具有 $$ 个顶点、$$ 条边的图采用邻接表存储进行深度优先遍历（DFS），其时间复杂度为（ ）

A. $$ B. $$ C. $$ D. $$

#第 22 题

关于 Dijkstra 算法，下列说法错误的是（ ）

A. 它按路径长度递增的次序产生最短路径 B. 它不能正确处理带负权边的图 C. 采用邻接矩阵存储时时间复杂度为 $$ D. 它一次运行可以求出图中每一对顶点间的最短路径

#第 23 题

对 AOE 网求关键路径，下列说法中正确的是（ ）

A. 关键路径是源点到汇点的最短路径 B. 关键活动是最早开始时间与最迟开始时间相等的活动 C. 缩短任何一个关键活动的持续时间，整个工程的工期一定缩短 D. AOE 网中关键路径只能有一条

#第 24 题

某 AOE 网（事件 1 为源点、事件 4 为汇点）：活动 $$: 1→2 时长 3，$$: 1→3 时长 4，$$: 2→4 时长 2，$$: 3→4 时长 5，则该工程的工期（关键路径长度）为（ ）

A. 5 B. 7 C. 9 D. 12

#第 25 题

下列关于最小生成树的说法中，正确的是（ ）

A. Prim 算法适合稀疏图，Kruskal 算法适合稠密图 B. 当图中所有边权互不相同时，最小生成树唯一 C. 最小生成树一定是唯一的 D. 图中权值最小的边一定不在最小生成树中

#答案与解析

#第 1 题：B

• 考点标签：二叉树度数关系 $$
• 难度：易
• 解析：$$，总数 $$。
• 错因提醒：漏加 $$ 本身得 13/14 类干扰需排除；本题给的是一般二叉树（$$ 任意），别套完全二叉树的 $$。

#第 2 题：B

• 考点标签：完全二叉树叶结点数
• 难度：易
• 解析：$$ 为奇数 → $$，$$（自检 $$，$$ 成立）。
• 错因提醒：套 $$ 时注意其前提是完全二叉树；一般二叉树仅由 $$ 无法确定叶子数。

#第 3 题：B

• 考点标签：完全二叉树编号性质
• 难度：中
• 解析：$$ 为偶数，最后一个分支结点编号 $$；其左孩子 $$ 存在，右孩子 101 超出总结点数，故只有左孩子。
• 错因提醒：$$ 奇偶决定最后一个分支结点有一个还是两个孩子；编号 $$ 的结点全是叶。

#第 4 题：C

• 考点标签：完全二叉树结点数最值
• 难度：难
• 解析：前 5 层全满 $$；第 6 层最多 32 个结点，其中 8 个叶结点必须靠右（双亲从左到右满配），靠左 24 个为分支结点、各带 2 个孩子 → 第 7 层 $$ 个叶。最多 $$。
• 错因提醒：63（漏第 7 层）、79（第 6 层只算 8 个结点等错误拼法）为典型干扰；牢记"最后一层的叶居最右、倒数第二层的叶居最左"。

#第 5 题：A

• 考点标签：先序 + 中序重建二叉树
• 难度：中
• 解析：先序首元素 1 为根；中序中 1 左侧 {4, 2, 5} 为左子树、{3} 为右子树。左子树先序 2 4 5、中序 4 2 5 → 2 为根、左 4 右 5。后序 = 左右根 = 4 5 2 3 1。
• 错因提醒：后序最后一个才是根，别把 3 当根（那是右子树的根）。

#第 6 题：C

• 考点标签：遍历序列互推可行性
• 难度：易
• 解析：先序 + 后序无法区分独子结点是左孩子还是右孩子（最小反例：先序 AB、后序 BA）。其余三项均可唯一确定。
• 错因提醒：补充特例——若所有结点度为 0 或 2，先序 + 后序也能唯一确定；选项常以此设置绝对化陷阱。

#第 7 题：C

• 考点标签：线索二叉树线索数
• 难度：易
• 解析：$$ 个指针域中 $$ 个指向孩子，空链域 $$ 个，全部改为线索。
• 错因提醒："线索数 = 空链域数 = $$"是恒等式；勿与"指针域总数 $$"混淆。

#第 8 题：B

• 考点标签：中序线索树找后继
• 难度：中
• 解析：rtag = 0 表示 rchild 是真孩子指针，p 有右子树；p 的中序后继 = 右子树中第一个被中序访问的结点，即右子树中最左下（一路向左到底）的结点。
• 错因提醒：rtag = 1 时后继才是 rchild 线索直接指的结点；选 D 混淆了"找中序首结点"（最左下）与"找子树中序末结点"（最右下）。

#第 9 题：B

• 考点标签：树转二叉树
• 难度：易
• 解析：转换规则：第一个孩子变左孩子、右兄弟变右孩子。树的根没有兄弟，故转换后二叉树的根没有右子树（左子树对应原根的子树们）。
• 错因提醒：这是判断"某二叉树能否由一棵树转换而来"的标志；森林转二叉树则根的右子树装其余所有树。

#第 10 题：A

• 考点标签：森林与二叉树遍历对应
• 难度：中
• 解析：对应关系：森林先序 ↔ 二叉树先序；森林中序（逐树后根）↔ 二叉树中序。二叉树后序在树/森林体系中无对应。
• 错因提醒：C 是最高频干扰项——"森林中序"对应的是二叉树"中序"而非"后序"。

#第 11 题：A

• 考点标签：哈夫曼树结点总数
• 难度：易
• 解析：$$ 个叶结点的哈夫曼树共 $$ 个结点（合并 $$ 次、每次新增 1 结点），且不存在度为 1 的结点。
• 错因提醒：权值集合具体数字是烟雾弹，结点总数只与叶结点个数有关。

#第 12 题：B

• 考点标签：哈夫曼树 WPL 计算
• 难度：中
• 解析：合并过程：2+4=6；5+6=11；7+11=18。WPL = 新建合并结点权值之和 $$。逐叶复核：叶 7 深 1、叶 5 深 2、叶 2 与 4 深 3：$$。
• 错因提醒：两条路（合并结点求和 / 逐叶 $$）必须互检；34/36 是把某叶放错层一档的典型错值。

#第 13 题：C

• 考点标签：前缀码判定
• 难度：中
• 解析：C 中 1 是 10 和 11 的前缀，不是前缀码。A 各码字互不为前缀；B 等长码必为前缀码；D 中 1/01/001/000 互不为前缀。
• 错因提醒：等长码必是前缀码（速判）；哈夫曼编码是前缀码，但前缀码不都是哈夫曼编码。

#第 14 题：C

• 考点标签：并查集复杂度
• 难度：中
• 解析：按秩合并 + 路径压缩下，$$ 次操作总代价 $$，单次均摊 $$，$$ 为反阿克曼函数，增长极慢、工程上视作常数。
• 错因提醒：D 错在"严格 $$"（理论上界是 $$）；仅按秩合并是 $$。

#第 15 题：B

• 考点标签：森林转二叉树的结构
• 难度：中
• 解析：森林转二叉树：第一棵树的全部结点构成根及其左子树方向结构，第 2、3 棵树（各自转换后）依次挂在根的右链上。根的右子树含第 2、3 棵树的全部结点 $$。
• 错因提醒：与树（单棵）转换对比——单棵树转换后根无右子树；14 是把第一棵树也算进去的错误。

#第 16 题：B

• 考点标签：中序非递归遍历
• 难度：中
• 解析：中序"左根右"：结点出栈时，其左子树（它一路向左压栈后再弹出的过程）已全部处理完，此时访问它，然后转向右子树。C/D 描述的是后序访问时机。
• 错因提醒：中序出栈序即中序序；同一模板下先序在入栈前访问、中序在出栈时访问、后序需 last 指针辅助。

#第 17 题：B

• 考点标签：后序非递归遍历
• 难度：难
• 解析：结点第一次回到栈顶时若右子树存在且未访问完，须先转右子树；r 记录最近访问的结点，用 p->rchild != r 判断右子树是否刚处理完，避免第二次回到同一栈顶时重复进入右子树（死循环）。
• 错因提醒：没有 r 指针的"出栈—转右"框架是历年改错题经典考点；r 比较的对象是栈顶结点的右孩子，不是栈顶结点本身。

#第 18 题：B

• 考点标签：二叉树叶子数最值
• 难度：易
• 解析：$$ 个结点的二叉树最少 1 个叶子：每内部结点只带一个孩子（单支/链形树），末端恰一个叶。
• 错因提醒：0 个叶子的树至少 1 个结点且非空树的根在无孩子时就是叶；$$ 是完全二叉树的叶子数，不是任意二叉树的最少值。

#第 19 题：B

• 考点标签：邻接表存储空间
• 难度：易
• 解析：无向图每条边 $$ 在 u 和 v 的边链表中各出现一次，边结点共 $$ 个；总空间 $$。
• 错因提醒：有向图出边表只有 $$ 个边结点；$$ 是总空间量级而非边结点数。

#第 20 题：D

• 考点标签：十字链表与邻接多重表辨析
• 难度：中
• 解析：无向图邻接矩阵对称、对角线为 0（无自环时 $$），"对角线全为 1"错误。A/B/C 均为正确表述（十字链表配有向图、邻接多重表配无向图，均一条边/弧一个结点）。
• 错因提醒：对角线元素表示自环，一般图默认无自环故为 0；"十字链表/邻接多重表"的适用图方向（有向/无向）是配对类选择题的高频考点。

#第 21 题：C

• 考点标签：DFS 复杂度
• 难度：易
• 解析：邻接表下每个顶点访问一次、每条边（的表结点）扫描一次，$$；邻接矩阵下为 $$。
• 错因提醒：两种存储的复杂度结论要成对记；D 是邻接矩阵下的结论，命题人最爱交叉设坑。

#第 22 题：D

• 考点标签：Dijkstra 算法性质
• 难度：中
• 解析：Dijkstra 是单源算法，求每对顶点间最短路需对每个顶点各跑一次（或用 Floyd）；A/B/C 均为正确性质。
• 错因提醒：B 的机理要会说：贪心假定每轮入集点的 dist 已最终，负权边可从已确定点的外部路径反超，前提崩溃。

#第 23 题：B

• 考点标签：关键路径概念
• 难度：中
• 解析：关键活动定义即最早开始时间与最迟开始时间相等（$$，$$）。关键路径是源到汇的最长路径（A 错）；缩短任一关键活动不一定缩短工期（关键路径可能多条，C 错）；关键路径也可能不止一条（D 错）。
• 错因提醒：A/C 是最典型错误选项；只有缩短所有关键路径共同经过的关键活动且不超过可压缩余量，工期才一定缩短。

#第 24 题：C

• 考点标签：关键路径计算
• 难度：中
• 解析：$$，$$，$$，$$，工期 $$。关键路径 1→3→4（$$）。复核：$$，$$，事件 3 关键 ✓。
• 错因提醒：5 是只看最短支路（1→2→4）的错误；求工期一律取最长路径，与最短路径考点方向相反。

#第 25 题：B

• 考点标签：最小生成树性质
• 难度：中
• 解析：边权互不相同时 MST 唯一（各候选集中最小边唯一确定）。A 说反（Prim 适合稠密、Kruskal 适合稀疏）；C 错（等权边可导致多棵 MST，但总权唯一）；D 错（权值最小的边必属于某个 MST，若唯一最小则必在每棵 MST 中）。
• 错因提醒："MST 树形可能不唯一但总权唯一"与"唯一最小横切边必选"两条性质常被打散混搭出题。