12. D
## 12. D 依次探测图的各条边，用并查集检查该边依附的两个顶点是否已属于同一集合（两个顶点的根结点是否相同）。若是，则说明图中存在环路，选项 A 错误。经过路径优化后，并查集在最坏情况下的高度远小于 $O(n)$，选项 B 错误。Find 操作总返回当前根结点作为集合的标志，选项 C 错误。 ## 13. D 在用并查集实现 Kruskal 算法求图的最小生成树时：判断是否加入一条边之前，先查找这条边关联的两个顶点是否属于同一个集合（判断加入这条边之后是否形成回路），若形成回路，则继续判断下一条边；若不形成回路，则将该边和边对应的顶点加入最小生成树 $T$，并继续判断下一条边，直到所有顶点都已加入最小生成树 $T$。选项 B 正确。用并查集判断无向图连通性的方法：遍历无向图的边，每遍历到一条边，就把这条边连接的两个顶点合并到同一个集合中，处理完所有边后，只要是相互连通的顶点都会被合并到同一个子集合中，相互不连通的顶点一定在不同的子集合中。选项 C 正确。未做路径优化的并查集在最坏情况下的高度为 $n$，此时查找操作的时间复杂度为 $O(n)$，时间复杂度通常指最坏情况下的时间复杂度。选项 D 错误。 ## 14. A 哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为 1 的结点，选项 B 正确。构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，选项 C 正确。哈夫曼树中任意一个非叶结点的权值为其左右子树根结点的权值之和，可知，哈夫曼树中任意一个非叶结点的权值一定不小于下一层任意一个结点的权值。 ## 15. D 前缀编码的定义是在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。选项 D 中的编码 110 是编码 1100 的前缀，违反了前缀编码的规则，所以选项 D 不是前缀编码。 ## 16. D 在哈夫曼树中，左右孩子权值之和为父结点权值。仅以分析选项 A 为例：若两个 10 分别属于两棵不同的子树，则根的权值不等于其孩子的权值和，不符；若两个 10 属同棵子树，则其权值不等于其两个孩子（叶结点）的权值和，不符。选项 B、C 选项的排除方法相同。 ## 17. D 哈夫曼编码是前缀编码，各个编码的前缀不同，因此直接拿编码序列与哈夫曼编码一一比对即可。序列可分割为 0100 011 001 001 011 11 0101，译码结果是 afeefgd。选项 D 正确。 ## 18. A 根据各字符出现的次数构造的哈夫曼树如右图所示。由图可知，a、c 和 e 的编码长度应该相同；a 和 c 的第 1 个编码应该相同，且与 e 的第 1 个编码不同；b 和 d 的前 3 个编码应该相同。 ## 19. C $n$ 个符号构造成哈夫曼树的过程中，共新建了 $n - 1$ 个结点（双分支结点），因此哈夫曼树的结点总数为 $2n - 1 = 115$，$n$ 的值为 58。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 202 -->
2027年数据结构考研复习指导
## 20. B
对于带权值的结点，构造出哈夫曼树的带权路径长度（WPL）最小，哈夫曼树的构造过程如下图所示。求得其 $\mathrm{WPL} = (10 + 12)\times 3 + (30 + 16 + 21)\times 2 = 200$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 21. D
可以画一个简单的特例来证明。图1是满足条件的二叉树 $T_{1}$，图2是满足条件的二叉树 $T_{2}$，结点中有值表示这个结点是编码字符。$T_{1}$和 $T_{2}$的结点数不同，选项A错误。$T_{1}$的高度等于 $T_{2}$的高度，选项B错误。出现频次不同的字符在 $T_{1}$中也可能处于相同的层，选项C错误。对于定长编码集，所有字符一定都在 $T_{2}$ 中处于相同的层，而且都是叶结点。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图1
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2 ## 22. B 构建哈夫曼树的过程如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
对叶结点的哈夫曼编码，共有4个长度为3的叶结点、2个长度为2的叶结点，编码的加权平均长度为 $[(3 + 4 + 5 + 6)\times 3 + (8 + 10)\times 2] / (3 + 4 + 5 + 6 + 8 + 10) = 2.5$。 ## 23. D 哈夫曼编码的编码长度等于该字符在哈夫曼树中的路径深度（从根到该叶结点的边数）。一个字符所在子树参与后续合并的轮数越多，其深度越大。合并过程如下：①合并2和 $3\rightarrow$ 新结点5；②合并4和 $5\rightarrow$ 新结点9；③合并6和 $8\rightarrow$ 新结点14；④合并9和 $10\rightarrow$ 新结点19；⑤合并11和 $14\rightarrow$ 新结点25；⑥合并19和 $25\rightarrow$ 根结点44。最终构建的哈夫曼树如右图所示。因此，编码长度不小于3的字符为4、2、3、6、8，共5个。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 203 --> 第5章 树与二叉树 191 ## 二、综合应用题 ### 01. 【解答】 根据哈夫曼树的构造方法，每次从森林中选取两个根结点值最小的树合并成一棵树，将原先的两棵树作为左右子树，且新根结点的值为左右孩子关键字之和。构造过程如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
由构造出的哈夫曼树可得 $\mathrm{WPL} = (2 + 3)\times 4 + (5 + 6 + 7)\times 3 + (8 + 9)\times 2 = 108$。
## 注意
哈夫曼树并不唯一，但带权路径长度一定是相同的。
### 02. 【解答】
1）最先合并的表中的元素在后续的每次合并中都会再次参与比较，因此求最小合并次数类似于求最小带权路径长度，此时可立即想到哈夫曼树。根据哈夫曼树的构造过程，每次选择表集合中长度最小的两个表进行合并。6个表的合并顺序如右图所示。
根据图中的哈夫曼树，6个序列的合并过程如下：
① 在表集合 $\{10,35,40,50,60,200\}$ 中，选择表 A 与表 B 合并，生成含 45 个元素的表 AB。
② 在表集合 $\{40,45,50,60,200\}$ 中，将表 AB 与表 C 合并，生成含 85 个元素的表 ABC。
③ 在表集合 $\{50,60,85,200\}$ 中，表 D 与表 E 合并，生成含 110 个元素的表 DE。
④ 在表集合 $\{85,110,200\}$ 中，表 ABC 与表 DE 合并，生成含 195 个元素的表 ABCDE。
⑤ 当前表集合为 $\{195, 200\}$，表 ABCDE 与表 F 合并，生成含 395 个元素的表 ABCDEF。因为合并两个长度分别为 $m$ 和 $n$ 的有序表，最坏情况下需要比较 $m + n - 1$ 次，所以最坏情况下比较的总次数计算如下：
第 1 次合并：最多比较次数 $= 10 + 35 - 1 = 44$。
<!-- page: 204 -->
2027年数据结构考研复习指导
第2次合并：最多比较次数 = 40 + 45 - 1 = 84。
第3次合并：最多比较次数 = 50 + 60 - 1 = 109。
第4次合并：最多比较次数 = 85 + 110 - 1 = 194。
第5次合并：最多比较次数 = 195 + 200 - 1 = 394。
比较的总次数最多为 44 + 84 + 109 + 194 + 394 = 825。
2）各表的合并策略是：对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借助哈夫曼树的构造思想，依次选择最短的两个表进行合并，此时可以获得最坏情况下的最佳合并效率。
## 03. 【解答】
1）使用一棵二叉树保存字符集中各字符的编码，每个编码对应于从根开始到达某叶结点的一条路径，路径长度等于编码位数，路径到达的叶结点中保存该编码对应的字符。
2）从左至右依次扫描 0/1 串中的各位。从根开始，根据串中当前位沿当前结点的左子指针或右子指针下移，直到移动到叶结点时为止。输出叶结点中保存的字符。然后从根开始重复这个过程，直到扫描到 0/1 串结束，译码完成。
3）二叉树既可用于保存各字符的编码，又可用于检测编码是否具有前缀特性。判定编码是否具有前缀特性的过程，也是构建二叉树的过程。初始时，二叉树中仅含有根结点，其左子指针和右子指针均为空。
依次读入每个编码 C，建立/寻找从根开始对应于该编码的一条路径，过程如下：
对每个编码，从左至右扫描C的各位，根据C的当前位（0或1）沿结点的指针（左子指针或右子指针）向下移动。当遇到空指针时，创建新结点，让空指针指向该新结点并继续移动。沿指针移动的过程中，可能遇到三种情况：
① 若遇到了叶结点（非根），则表明不具有前缀特性，返回。
② 若在处理C的所有位的过程中，均没有创建新结点，则表明不具有前缀特性，返回。
③ 若在处理C的最后一个编码位时创建了新结点，则继续验证下一个编码。
若所有编码均通过验证，则编码具有前缀特性。
## 归纳总结
本章内容较为丰富，其中二叉树是极其重要的考查重点。在历年统考真题中，已多次出现基于二叉树的算法设计题，考生需特别关注。
遍历是二叉树各类操作的基础，统考常结合遍历过程考查对结点的各种附加操作。建议读者重点掌握各种遍历方法的代码实现，并在此基础上灵活完成相关操作。其中，递归算法结构简洁、逻辑清晰，在考试中出现的概率较高，切勿掉以轻心。应熟练掌握先序、中序、后序遍历的程序模板，并通过足量习题训练，方能在考试中快速写出规范、高效的代码。
二叉树遍历的通用递归框架如下：
将访问操作 visit() 放在位置(1)、(2)或(3)，分别对应先序遍历、中序遍历和后序遍历。但在具体题目中，需根据问题要求灵活调整和扩展该模板。
例如，设二叉树采用二叉链表存储结构，请编写有关二叉树的递归算法。
1）统计二叉树中度为1的结点数。
2）统计二叉树中度为2的结点数。
3）统计二叉树中度为0的结点（叶结点）个数。
4）求二叉树的高度。
5）求二叉树的宽度（各层中结点数的最大值）。
6）删除二叉树中的所有叶结点。
7）计算指定结点 *p 所在的层次。
8）求二叉树中所有结点数据值的最大值。
9）交换二叉树中每个结点的左右孩子。
10）以先序次序输出二叉树中每个结点的数据值及其所在层次。
## 思维拓展
输入一个整数 data 和一棵二元树。从树的根结点开始往下访问一直到叶结点，所经过的所有结点形成一条路径。打印出路径及与 data 相等的所有路径。例如，输入整数 22 和右图所示的二元树，则打印出两条路径 10, 12 和 10, 5, 7。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
### 注意 使用数组或线保存访问的路径，并记录当前路径上所有元素的和 sum。若当前结点为叶结点，且当前结点值与 sum 的和等于 data，则满足条件，打印当前路径。然后递归返回到父结点，注意在递归返回之前要先减去当前结点元素的值。使用先序遍历操作的递归算法模板可以简化程序。 ## 购买王道书，就上 **王道官方考研书店** wangdao.taobao.com
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 206 --> 第6章 # 图 ## 【考纲内容】 （一）图的基本概念 （二）图的存储及基本操作 邻接矩阵；邻接表；邻接多重表；十字链表 （三）图的遍历 深度优先搜索；广度优先搜索 （四）图的基本应用 最小（代价）生成树；最短路径；拓扑排序；关键路径 ## 【知识框架】
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
视频讲解
图
图的定义
图结构的存储
邻接矩阵法、邻接表法
邻接多重表、十字链表
深度优先遍历
广度优先遍历
图的相关应用
最小生成树：Prim算法、Kruskal算法
最短路径：Dijkstra算法、Floyd算法
拓扑排序：AOV网
关键路径：AOE网
## 【复习提示】
图算法整体难度较大，应重点掌握深度优先搜索与广度优先搜索。理解图的基本概念与性质，掌握邻接矩阵、邻接表、邻接多重表和十字链表等存储结构及其特点，并能进行结构间的转换。掌握基于这些结构的遍历操作及典型应用，如拓扑排序、最小生成树、最短路径和关键路径等。图算法较多，通常只需掌握其核心思想与实现步骤，代码实现并非重点。
# 6.1 图的基本概念
## 6.1.1 图的定义
图 $G$ 由顶点集 $V$ 和边集 $E$ 组成，记为 $G = (V, E)$。其中，$V(G)$ 表示图 $G$ 中顶点的有限非空集；$E(G)$ 表示图 $G$ 中顶点之间的关系（边）集合。若 $V = \{\nu_{1}, \nu_{2}, \dots, \nu_{n}\}$，则用 $|V|$ 表示图 $G$ 中顶点的数量，$E = \{(u, v) \mid u \in V, v \in V\}$，用 $|E|$ 表示图 $G$ 中边的数量。
<!-- page: 207 -->
第6章图
195
# 注意
线性表可以是空表，树可以是空树，但图不可以是空图。也就是说，图中不能一个顶点也没有，图的顶点集 $V$ 必须是非空的，但边集 $E$ 可以为空，此时图中只有顶点而无边。
下面是图的一些基本概念及术语。
## 1. 有向图
若 $E$ 是有向边（也称弧）的有限集合，则图 $G$ 称为有向图。弧是顶点的有序对，记为 $\langle v, w \rangle$，其中，$v$ 称为弧尾，$w$ 称为弧头，表示从 $v$ 到 $w$ 的有向边，也称 $v$ 邻接到 $w$。
图 6.1(a) 所示的有向图 $G_{1}$ 可表示为
$$
\begin{array}{l}
G_{1} = (V_{1}, E_{1}) \\
V_{1} = \{1, 2, 3\} \\
E_{1} = \{\langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 2, 3 \rangle\}
\end{array}
$$
## 2. 无向图
若 $E$ 是无向边（简称边）的有限集合，则图 $G$ 称为无向图。边是顶点的无序对，记为 $(v, w)$ 或 $(w, v)$。可以说 $w$ 和 $v$ 互为邻接点，或称边 $(v, w)$ 和 $v, w$ 相关联。
图 6.1(b) 所示的无向图 $G_{2}$ 可表示为
$$
\begin{array}{l}
G_{2} = (V_{2}, E_{2}) \\
V_{2} = \{1, 2, 3, 4\} \\
E_{2} = \{(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)\}
\end{array}
$$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 有向图 $G_{1}$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 无向图 $G_{2}$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) 有向完全图 $G_{3}$
图 6.1 图的示例
## 3. 简单图、多重图
若图 $G$ 满足条件：① 不存在重复边；② 不存在顶点到自身的边，则称图 $G$ 为简单图。图 6.1 中 $G_{1}$ 和 $G_{2}$ 均为简单图。若图 $G$ 中某两个顶点之间的边数超过 1 条，并且允许顶点通过一条边与自身关联，则称图 $G$ 为多重图。多重图和简单图的定义是相对的。本书仅讨论简单图。
## 4. 顶点的度、入度和出度
**特点击右**
$\triangleright$ 无向图中顶点和边的关系（2009，2017）
在无向图中，顶点 $v$ 的度是指依附于顶点 $v$ 的边的数量，记为 $\mathrm{TD}(v)$。图 6.1(b) 中，每个顶点的度均为 3。无向图的全部顶点的度之和等于边数的 2 倍，因为每条边与两个顶点相关联。
在有向图中，顶点 $v$ 的度分为入度和出度，入度是以顶点 $v$ 为终点的有向边的数量，记为 $\mathrm{ID}(v)$；而出度是以顶点 $v$ 为起点的有向边的数量，记为 $\mathrm{OD}(v)$。图 6.1(a) 中，顶点 2 的出度为 2、入度为 1。顶点 $v$ 的度等于其入度与出度之和，即 $\mathrm{TD}(v) = \mathrm{ID}(v) + \mathrm{OD}(v)$。有向图的全部顶点的入度之和与出度之和相等，并且等于边数，这是因为每条有向边都有一个起点和终点。
<!-- page: 208 -->
2027年数据结构考研复习指导
# 5. 路径、路径长度和回路
顶点 $v_{p}$ 到 $v_{q}$ 之间的一条路径是指顶点序列 $v_{p}, v_{t_{1}}, v_{t_{2}}, \dots, v_{t_{m}}, v_{q}$。路径所含边的数量称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有 $n$ 个顶点，且有大于 $n - 1$ 条边，则此图一定有环。
# 6. 简单路径、简单回路
考点追查 路径、回路、简单路径、简单回路的定义（2011）
路径序列中顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复的回路称为简单回路。
# 7. 距离
从顶点 $u$ 到 $v$ 的最短路径的长度称为从 $u$ 到 $v$ 的距离。若不存在路径，则距离为无穷大。
# 8. 子图
设有两个图 $G = (V, E)$ 和 $G' = (V', E')$，若 $V'$ 是 $V$ 的子集，且 $E'$ 是 $E$ 的子集，则称 $G'$ 是 $G$ 的子图。若有满足 $V(G') = V(G)$ 的子图 $G'$，则称其为 $G$ 的生成子图。图6.1中 $G_3$ 为 $G_1$ 的子图。
# 注意
并非 $V$ 和 $E$ 的任何子集都能构成 $G$ 的子图，因为这样的子集可能不是图，即 $E$ 的子集中的某些边关联的顶点可能不在这个 $V$ 的子集中。
# 9. 连通、连通图和连通分量
考点追查 图的连通性与边和顶点的关系（2010、2022）
在无向图中，若从顶点 $v$ 到 $w$ 存在路径，则称 $v$ 和 $w$ 是连通的。若图 $G$ 中任意两个顶点都是连通的，则称图 $G$ 为连通图；否则为非连通图。无向图中的极大连通子图称为连通分量，在图6.2(a)中，图 $G_4$ 的3个连通分量如图6.2(b)所示。假设一个图有 $n$ 个顶点，若边数少于 $n - 1$，则此图必然是非连通的。思考：在一个非连通图中，最多可能有多少条边？
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 无向图 $G_{4}$
图6.2 无向图及其连通分量
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) $G_{4}$ 的3个连通分量
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图6.2 无向图及其连通分量
# 10. 强连通图、强连通分量
在有向图中，如果一对顶点 $v$ 和 $w$，从 $v$ 到 $w$ 和从 $w$ 到 $v$ 之间都有路径，则称这两个顶点是强连通的。如果图中任意一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强
① 非连通情况下边最多的情况：由 $n - 1$ 个顶点构成一个完全图，此时再加入一个顶点则变成非连通图。
<!-- page: 209 -->
第6章 图
197
连通子图称为强连通分量，图 $G_{1}$ 的强连通分量如图 6.3 所示。思考，假设有向图拥有 $n$ 个顶点，且该图是强连通的，则最少需要多少条边？①
**注意**
在无向图中讨论连通性，在有向图中讨论强连通性。
## 11. 生成树、生成森林
连通图的生成树是一个包含所有顶点的极小连通子图。若图中有 $n$ 个顶点，则其生成树恰好包含 $n - 1$ 条边。这样的子图仅通过最少数量的边保持连通。对生成树而言，若移除任意一条边，都会变成非连通图；添加任何一条边则会形成一个回路。在非连通图中，每个连通分量的生成树共同构成了该图的生成森林。图 $G_{2}$ 的一个生成树如图 6.4 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 6.3 图 $G_{1}$ 的强连通分量
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 6.4 图 $G_{2}$ 的一个生成树
**注意**
区分极大连通子图和极小连通子图。极大连通子图要求子图必须连通，而且包含尽可能多的顶点和边；极小连通子图是既要保持子图连通又要使得边数最少的子图。