10. 【解答】
## 10. 【解答】 本题初看起来感觉难度较大，但仔细分析就可发现考查的其实是邻接表的数据结构。 1）图题中给出的是一个简单的网络拓扑图，可以抽象为无向图。 2）图的常用存储结构有邻接矩阵法和邻接表法，其中邻接表法属于链式存储结构，因此本题的基本思路就是写出邻接表的数据类型定义，并根据题意调整相应的边表结点和顶点表结点的成员变量。具体分析如下：邻接表由表头顶点和弧顶点组成。根据题目给出的图和表，可将顶点分为三类：路由器、网络和链路。路由器是连接网络和链路的载体，因此可将它作为表头顶点。网络和链路则是连接路由器的边，因此可将它们作为弧顶点。为了简化代码，可将网络和链路的结构合并为一个，用一个标志位来区分它们，这样就可用邻接表来实现图的存储。链式存储结构如下图所示。 弧结点的两种基本形态 | Flag=1 | Next | | --- | --- | | ID | | | IP | | | Metric | | | Flag=2 | Next | | --- | --- | | Prefix | | | Mask | | | Metric | | | 表头结点结构示意 | RouterID | | --- | --- | | | LN_link | | | Next | <!-- page: 271 --> 第6章图 259 其数据类型定义如下：对应表的链式存储结构示意图如下所示。typedef struct{ unsigned int ID, IP; }LinkNode; //Link 的结构 typedef struct{ unsigned int Prefix, Mask; }NetNode; //Net 的结构 typedef struct Node{ int Flag; //Flag=1 为 Link; Flag=2 为 Net union{ LinkNode Lnode; NetNode Nnode }LinkORNet; Unsigned int Metric; struct Node *next; }ArcNode; //弧结点 typedef struct hNode{ unsigned int RouterID; ArcNode *LN_link; Struct hNode *next; }HNODE; //表头结点
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
3）计算结果如下表所示。 | | 目的网络 | 路径 | 代价（费用） | | --- | --- | --- | --- | | 步骤 1 | 192.1.1.0/24 | 直接到达 | 1 | | 步骤 2 | 192.1.5.0/24 | R1→R3→192.1.5.0/24 | 3 | | 步骤 3 | 192.1.6.0/24 | R1→R2→192.1.6.0/24 | 4 | | 步骤 4 | 192.1.7.0/24 | R1→R2→R4→192.1.7.0/24 | 8 | 11. 【解答】 1）Prim 算法属于贪心策略。算法从一个任意的顶点开始，一直长大到覆盖图中的所有顶点 <!-- page: 272 --> 2027年数据结构考研复习指导 为止。算法的每一步在连接树集合 $S$ 的顶点和其他顶点的边中，选择一条使得树的总权重增加最小的边加入集合 $S$。当算法终止时，$S$ 就是最小生成树。 ① $S$ 中顶点为 $A$，候选边为 $(A, D), (A, B), (A, E)$，选择 $(A, D)$ 加入 $S$。 ② $S$ 中顶点为 $A, D$，候选边为 $(A, B), (A, E), (D, E), (C, D)$，选择 $(D, E)$，加入 $S$。 ③ $S$ 中顶点为 $A, D, E$，候选边为 $(A, B), (C, D), (C, E)$，选择 $(C, E)$ 加入 $S$。 ④ $S$ 中顶点为 $A, D, E, C$，候选边为 $(A, B), (B, C)$，选择 $(B, C)$ 加入 $S$。 ⑤ $S$ 就是最小生成树。 依次选出的边为 $$ (A, D), (D, E), (C, E), (B, C) $$ 2）图 $G$ 的 MST 是唯一的。第一小题的最小生成树包括了图中权值最小的 4 条边，其他边除 $(A, E)$ 外都比这 4 条边大，但若用 $(A, E)$ 替换同权值的 $(C, E)$，$A, D, E$ 三个顶点构成了回路，因此不能替换，所以此图的 MST 唯一。 3）当带权连通图的任意一个环中所包含的边的权值均不相同时，其 MST 是唯一的。此题不要求回答充分必要条件，所以回答一个限制边权值的充分条件即可。 ## 12. 【解答】 1）为了求解最经济的方案，可把问题抽象为求无向带权图的最小生成树。可以采用手动 Prim 算法或 Kruskal 算法作图。注意本题的最小生成树有两种构造，如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
方案的总费用为 16。
2）存储题中的图可采用邻接矩阵（或邻接表）。构造最小生成树采用 Prim 算法（或 Kruskal 算法）。
3）$\mathrm{TTL} = 5$，即 IP 分组的生存时间（最大传递距离）为 5，方案 1 中 TL 和 BJ 的距离过远，$\mathrm{TTL} = 5$ 不足以让 IP 分组从 H1 传送到 H2，因此 H2 不能收到 IP 分组。而方案 2 中 TL 和 BJ 邻近，H2 可以收到 IP 分组。
## 13. 【解答】
1）算法的基本设计思想：建立图 $G$ 各顶点的入度表 degree[]。选择入度为 0 的顶点 $\nu$，将 $\nu$ 的所有邻接点的入度减 1，重复执行这个过程。若每次选中的入度为 0 的顶点有且仅有一个，且共进行了 G.numVertices 次，则意味着存在唯一的拓扑序列，返回 1，否则不存在拓扑序列，或者存在多个拓扑序列，返回 0。
2）用 C 语言描述的算法如下：
int uniquely(MGraph G) { //判定有向图是否存在唯一的拓扑序列
int *degree,i,j,count=0,in0=-1,prev_in0;
degree=(int*)malloc(G.numVertices*sizeof(int));
for (j=0;j&lt;G.numVertices;j++) { //计算各顶点的入度
degree[j]=0;
for (i=0;i&lt;G.numVertices;i++)
degree[j]+=G.Edge[i][j];
if (degree[j]==0) {
<!-- page: 273 -->
第6章 图
261
```javascript
if (in0==-1) in0=j; //入度为 0 的顶点
else in0=-2; //有多个入度为 0 的顶点
}
while (in0&gt;=0) {
count++;
prev_in0=in0;
in0=-1;
for (j=0; j<g.numvertices;j++) #="" $="" $v_{i}(1)="0$" $v_{i}(3)="v_{r}(1)" $v_{r}(6)="v_{t}(3)" $v_{t}(6)$-="" $v_{t}(6)+g$="" $v_{t}(6)+g$)="\max\{0" $v_{t}(6)$-$v_{r}(3)+c="2" $v_{r}(6)$="" (事件="" +="" -="" 1)="" 1,="" 12="" 12.="" 14.="" 15.="" 16.="" 17.="" 2)="" 2,="" 2.="" 3="" 4)="9;$" 4)="" 5="" 5,="" 5+4)="9;$" 5+4)="9;$" 5+4)="9;$" 5+4)="" 7)="" \="" \="" \div="" \div,="" \div)="" \div)="" \div)2)="\max\{v_{r}(1)" \}="\max\{v_{r}(4)" \}="\max\{0" \}="" \}="\max\{0+3,2" \}="" \}="\max\{0+3,2+3,3+1\}="5;$" \}="\max\{v_{r}(1)+d,v_{r}(3)+e,v_{r}(6)+g\}="\max\{0+3,2+3,3+1\}="5;$" \}="\max\{v_{r}(1)+b,v_{r}(4)+f\}="\max\{0+5,5+4\}="9;$" \}="\max\{v_{r}(2)" \}="" \}="\max\{v_{r}(4)-e,v_{r}(6)-c\}="\min\{5-3,8-1\}="2;$" \}="\max\{v_{r}(2)-f,v_{r}(5)-j,v_{r}(7)-m\}="\min\{10-4,12-1,9-4\}="5;$" \}="\max\{v_{r}(4)-e,v_{r}(6)-c\}="\min\{5-3,8-1\}="2;$" \}="\max\{v_{r}(1)="\min\{v_{t}(3)-a,v_{t}(2)-b,v_{t}(4)-d\}="\min\{2-2,10-5,5-3\}="0.$" 12.="" 12.2.="" 12.5="" 12.5,="" 14.="" 15="" 16="" 17="" 18="" 2)="" 2.="" 2.5="" 3)="" 4)="" 5)="" 5,="" 5,5)="" 5,5+4)="9;$" 5+4)="" 6.="" 7)="" 7,="" \="" \div="" \div)="" \div)2)="\max\{0+3,2+3,3+1\}="5;$" \}="\max\{0+5,5+4\}="9;$" \}="\max\{0+5,5+4\}="9;$" \}="\max\{0+5,5+4\}="12." 12.="" 12.5,="" 12.5,5)="" 12.5,5+="" 12.5,5+1,="" 12.5,5+1,="" 12.5,5+1,="" 12.5,5+1,="" 12.5,5+1,="" 12.5,5+1,="" 12.5,5+1,="" 12.5,5+1,="" 12.5,5}="" 12.5,5}$="" 12.5,5}$="" 12.5,5}$)="" 12.5,5}$)="" 12.5,5}$)="" 12.5,5}$)="" 12.5,5}$)="" 12.5,5+="" 12.5,5+1,="" 12.5,5}="" 12.5,5}$) </g.numvertices;j++)>
<!-- page: 274 -->
2027年数据结构考研复习指导
则事件 2 在时刻 11 发生，事件 5 在时刻 $11 + k$ 发生。要使工程不延期，需要满足 $11 + w(k) \leqslant 12$，解得 $w(k) \leqslant 1$。因此，需压缩活动 $k$ 的持续时间（从 2 压缩到 1）。
## 四纳总结
### 1. 关于图的基本操作
本章中介绍的多数图算法均可适配邻接矩阵或邻接表存储结构，主要原因是在图的基本操作函数中保持了相同的参数和返回值，封装了内部实现细节。例如，函数 NextNeighbor $(G, x, y)$ 用于返回顶点 $x$ 在邻接顶点 $y$ 之后的下一个邻接顶点。
### 1）使用邻接矩阵作为存储结构
```c
int NextNeighbor(MGraph&amp; G, int x, int y) {
if (x != -1 &amp;&amp; y != -1) {
for (int col = y + 1; col &lt; G.vexnum; col++)
if (G.Edge[x] [col] &gt; 0 &amp;&amp; G.Edge[x] [col] &lt; maxWeight)
return col; //maxWeight 代表 ∞
}
return -1;
}
### 2）使用邻接表作为存储结构
int NextNeighbor(ALGraph&amp; G, int x, int y) {
if (x != -1) {
//顶点 x 存在
ArcNode *p = G.vertices[x].first; //对应边链表第一个边结点
while (p != NULL &amp;&amp; p-&gt;data != y) //寻找邻接顶点 y
p = p-&gt;next;
if (p != NULL &amp;&amp; p-&gt;next != NULL)
return p-&gt;next-&gt;data; //返回下一个邻接顶点
}
return -1;
}
### 2. 关于图的遍历、连通性、生成树、关键路径的几个要点
1）在执行图的遍历时，由于图中可能存在回路，且任意顶点都可能与其他顶点相连，访问完某个顶点后可能沿某些边回到已访问过的顶点。因此，需设置辅助数组 visited[] 标记顶点是否已被访问，以避免重复访问。
2）深度优先搜索（DFS）采用回溯策略遍历图，通常通过递归实现。在递归访问某一邻接顶点前，必须先判断该顶点是否已被访问。此外，所有递归算法均可借助栈转换为非递归形式，DFS 也不例外，具体实现参见 6.3.4 节综合应用题 03。
3）广度优先搜索（BFS）是一种分层遍历过程，每向前推进一层可能访问一批顶点，不存在回退操作，因此它不是递归过程。
4）一个给定图的邻接矩阵表示是唯一的；但邻接表表示则依赖于边的输入顺序，若输入次序不同，生成的邻接表也可能不同。
5）最小生成树针对带权连通无向图，是从图中选出 $n - 1$ 条边构成的连通无环子图，使得所有边的权值总和最小。
6）加速某一关键活动不一定能缩短整个工程的工期，因为 AOE 网中可能存在多条关键路径。只有那些出现在所有关键路径上的关键活动被加速时，才能有效缩短总工期。
<!-- page: 275 -->
第6章 图
263
# 思维拓展
【网易有道笔试题】求一个无向连通图的割点。割点的定义是，若除去此顶点和与其相关的边，无向图不再连通，描述算法。
## 提示
要判断一个点是否为割点，最简单直接的方法是，先把这个点和所有与它相关的边从图中去掉，再用深搜或广搜来判断剩下的图的连通性，这种方法适合判断给定顶点是否为割点；还有一种比较复杂的方法可以快速找出所有割点，有兴趣的读者可自行搜索相关资料。
# 购买王道书，就上
# 王道官方考研书店
wangdao.taobao.com
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 276 --> # 第7章 # 查找 ## 【考纲内容】 （一）查找的基本概念 （二）顺序查找法 （三）分块查找法 （四）折半查找法 （五）树形查找 二叉搜索树：平衡二叉树；红黑树 （六）B树及其基本操作、B+树的基本概念 （七）散列（Hash）表 （八）查找算法的分析及应用 ## 【知识框架】
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
程频讲解
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 【复习提示】
本章是考研命题的重点。对于折半查找，应掌握折半查找的过程、构造判定树、分析平均查找长度等。对于二叉排序树、二叉平衡树和红黑树，要了解它们的概念、性质和相关操作等。B树和B+树是本章的难点。对于B树，考研大纲要求掌握插入、删除和查找的操作过程；对于B+树，仅要求了解其基本概念和性质。对于散列查找，应掌握散列表的构造、冲突处理方法（各种方法的处理过程）、查找成功和查找失败的平均查找长度、散列查找的特征和性能分析。
## 7.1 查找的基本概念
1）查找。在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为两种：一是查找成功，即在数据集合中找到了满足条件的数据元素；二是查找失败。
<!-- page: 277 -->
第7章 查找
265
2）查找表。用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成。对查找表的常见操作有：① 查询符合条件的数据元素；② 插入或删除数据元素。
3）静态查找表。若一个查找表的操作仅涉及查找，无须动态修改，则称为静态查找表；反之，需要支持插入或删除操作的查找表称为动态查找表。适合静态查找表的查找方法包括顺序查找、折半查找等；适合动态查找表的查找方法包括二叉排序树查找等。散列查找既可用于静态表，也可用于动态表（取决于具体实现）。
4）关键字。数据元素中唯一标识该元素的某个数据项的值，基于关键字的查找应返回唯一结果。例如，在学生记录集合中，“学号”这一数据项可唯一标识一名学生。
5）平均查找长度。在查找过程中，一次查找的长度是指该次查找中关键字的比较次数，而平均查找长度则是所有查找操作中关键字比较次数的加权平均值，其数学定义为
$$
\mathrm {A S L} = \sum_ {i = 1} ^ {n} P _ {i} C _ {i}
$$
式中， $n$ 是查找表的长度； $P_{i}$ 是查找第 $i$ 个数据元素的概率，若为等概率则 $P_{i} = 1 / n$ ； $C_{i}$ 是找到第 $i$ 个数据元素所需进行的比较次数。ASL 是衡量查找算法效率的核心指标。
## 7.2 顺序查找和折半查找
### 7.2.1 顺序查找
顺序查找（又称线性查找）适用于顺序表和链表：对于顺序表，可通过递增数组下标依次访问每个元素；对于链表，则通过指针 next 逐个遍历结点。顺序查找可用于一般的无序线性表，也可用于按关键字有序的线性表。下面分别讨论其在无序表和有序表中的应用。
### 1. 一般线性表的顺序查找
作为一种最直观的查找方法，顺序查找的基本思想：① 从线性表的一端开始，逐个检查元素的关键字是否满足给定条件；② 若查找到某个元素的关键字满足条件，则查找成功，返回该元素在线性表中的位置；③ 若已查至表的另一端仍未找到符合条件的元素，则返回查找失败的信息。下面给出其算法实现，后面说明其中“哨兵”的作用。
上述算法中，将 ST.elem[0] 称为哨兵。引入哨兵的目的是避免在循环中反复判断数组下标是否越界。算法从表尾（下标 TableLen）向前查找，一旦 ST.elem[i] == key，即返回 i，表示查找成功；否则，否则，循环最终会在 $i = 0$ 时终止（因为 ST.elem[0] == key），此时返回 0，表示查找失败。通过设置哨兵，可以省去边界判断，从而提高程序效率。
对于含 $n$ 个元素的表，若给定关键字 key 与表中第 $i$ 个元素相等，即定位第 $i$ 个元素时，需进行 $n - i + 1$ 次关键字比较，即 $C_i = n - i + 1$ 。查找成功的平均查找长度为
<!-- page: 278 -->
2027年数据结构考研复习指导
$$
\mathrm{ASL}_{\text{成功}} = \sum_{i=1}^{n} P_{i}(n - i + 1)
$$
当每个元素的查找概率相等（$P_{i} = 1/n$）时，有
$$
\mathrm{ASL}_{\text{成功}} = \sum_{i=1}^{n} P_{i}(n - i + 1) = \frac{n + 1}{2}
$$
查找不成功时，与表中各关键字的比较次数显然是 $n + 1$ 次，即 $\mathrm{ASL}_{\text{不成功}} = n + 1$。
通常，查找表中记录的查找概率并不相等。若能预先获知各记录的查找概率，则应将记录按查找概率由大到小重新排列，使高频元素靠近查找起点，从而降低平均查找长度。
综上所述，顺序查找的主要缺点是当 $n$ 较大时，平均查找长度较大，效率较低；其优点是对存储结构无要求——无论是顺序存储还是链式存储均可使用，且不要求表中记录按关键字有序。此外还需注意，链表只能采用顺序查找。
## 2. 有序线性表的顺序查找
若在查找之前已知表是关键字有序的，则在查找失败时，无须继续比较到表的另一端即可提前返回查找失败的信息，从而降低查找失败的平均查找长度。假设表 $L$ 按关键字从小到大排列，查找顺序为从前往后，待查元素的关键字为 key。当查找到第 $i$ 个元素时，若发现该元素的关键字小于 key，而第 $i + 1$ 个元素的关键字大于 key，则可立即判定查找失败。因为表中第 $i$ 个元素之后的所有元素关键字均大于 key，故表中不存在关键字等于 key 的元素。
**有序线性表的顺序查找的应用（2013）**
可以用如图 7.1 所示的判定树来描述有序线性表的查找过程。树中的圆形结点表示表中实际存在的元素；矩形结点称为失败结点（若有 $n$ 个结点，则相应的有 $n + 1$ 个失败结点），它描述了那些不在表中的关键字范围的集合。若最终查找到某个矩形结点，则表示查找失败。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 7.1 有序顺序表上的顺序查找判定树
在有序线性表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序查找相同。
而查找失败时，查找过程一定会走到某个失败结点。这些失败结点是虚构的空结点，实际并不存在。因此，到达某一失败结点时所经历的比较次数，等于其父结点（路径上最后一个真实元素结点）所在的层数。在等概率查找失败的情形下，查找失败的平均查找长度为：
$$
\mathrm{ASL}_{\text{失败}} = \sum_{j=1}^{n} q_{j}(l_{j} - 1) = \frac{1 + 2 + \cdots + n + n}{n + 1} = \frac{n}{2} + \frac{n}{n + 1}
$$
其中，$q_{j}$ 是到达第 $j$ 个失败结点的概率，在等概率假设下为 $1/(n + 1)$：$l_{j}$ 是第 $j$ 个失败结点所在的层数。例如，当 $n = 6$ 时，$\mathrm{ASL}_{\text{失败}} = 6/2 + 6/7 = 3.86$，比一般的顺序查找要好一些。
注意，有序线性表的顺序查找与后续介绍的折半查找在思想上有本质区别。此外，有序线性
<!-- page: 279 -->
第7章 查找
267
表的顺序查找的线性表可以是链式存储结构，而折半查找的线性表只能是顺序存储结构。