408 真题做题本·数据结构部分

第 5 章 图

5.1 图的基本概念

1. 【2009】下列关于无向连通图特性的叙述中, 正确的是（ ）。 I. 所有顶点的度之和为偶数 II. 边数大于顶点个数减1 III. 至少有一个顶点的度为1

A. 只有I
B. 只有II
C. I 和II
D. I 和III

答案： A。

解析： 无向图中每条边都给两个端点各贡献 $1$ 个度，因此由握手定理，

$\sum _{v\in V}d(v)=2|E|$，

顶点度数之和必为偶数，故 I 正确。

无向连通图只要求 $|E|\ge |V|-1$，树恰有 $|V|-1$ 条边，所以 II 中“边数大于顶点数减 $1$”不一定成立。连通图也不一定有度为 $1$ 的顶点，例如环中所有顶点的度都为 $2$，故 III 错误。

2. 【2010】若无向图G = V,E 中含有7 个顶点, 要保证图G 在任何情况下都是连通的，则需要的边数最少是（ ）。

A. 6
B. 15
C. 16
D. 21

答案： C。

解析： 要保证含 $7$ 个顶点的无向图在任何情况下都连通，应使边数超过“不连通图可能具有的最大边数”。

不连通时，为使边数最多，应让 $6$ 个顶点构成完全图，另一个顶点孤立，此时

$|E{|}_{\max }=(\genfrac{}{}{0ex}{}{6}{2})=15$。

因此至少需要 $15+1=16$ 条边。

3. 【2017】已知无向图G 含有16 条边，其中度为4 的顶点个数为3, 度为3 的顶点个数为4, 其他顶点的度均小于3。图G 所含的顶点个数至少是（ ）。

A. 10
B. 11
C. 13
D. 15

答案： B。

解析： 由握手定理，图中所有顶点的度数之和为

$2|E|=2\times 16=32$。

已知顶点贡献的度数之和为

$3\times 4+4\times 3=24$，

其余顶点的度数之和至少为 $32-24=8$。其余每个顶点的度均小于 $3$，最多为 $2$，因此至少还需

$\frac{8}{2}=4$

个顶点。故顶点总数至少为 $3+4+4=11$。

4. 【2022】对于无向图G = V,E, 下列选项中, 正确的是（ ）。

A. 当 $V>E$ 时, G 一定是连通的
B. 当 $V<E$ 时, G 一定是连通的
C. 当V = E - 1 时, G 一定是不连通的
D. 当 $V>E+1$ 时, G 一定是不连通的

答案： D。

解析： 含 $|V|$ 个顶点的无向连通图至少有 $|V|-1$ 条边。若

$|V|>|E|+1$，

则 $|E|<|V|-1$，边数不足以连通所有顶点，所以图一定不连通。

其余条件均不能保证连通性：边数较多时仍可能由一个稠密连通分量和若干孤立顶点组成。

5.2 图的基本存储及基本操作

1. 【2013】设图的邻接矩阵

$$A=\left(\begin{array}{cccc}0& 1& 0& 1\\ 0& 0& 1& 1\\ 0& 1& 0& 0\\ 1& 0& 0& 0\end{array}\right)$$

各顶点的度依次是（ ）。

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

答案： C。

解析： 该邻接矩阵不对称，因此表示有向图。顶点的出度等于对应行元素之和，入度等于对应列元素之和。

各行之和为 $(2,2,1,1)$，各列之和为 $(1,2,1,2)$，故各顶点的总度依次为

$(2+1,2+2,1+1,1+2)=(3,4,2,3)$。

2. 【2024】若无向图G = V,E 的邻接多重表如下图所示，则G 中顶点b 与d 的度分别是（ ）。

A. 0,2
B. 2,4
C. 2,5
D. 3,4

答案： B。

解析： 从邻接多重表中读取各边结点的两个端点，可得边集为

$\{(a,b),(b,d),(c,a),(d,c),(e,c),(a,d),(e,d)\}$。

因此，与顶点 $b$ 关联的边有 $(a,b),(b,d)$ 两条，故 $d(b)=2$；与顶点 $d$ 关联的边有 $(b,d),(d,c),(a,d),(e,d)$ 四条，故 $d(d)=4$。

3. 【2015】已知含有5 个顶点的图G 如图所示。请回答下列问题: (1) 写出图G 的邻接矩阵A(行、列的下标从0 开始计算)。 (2) 求A2, 矩阵A2中位于0 行3 列元素值的含义是什么？ (3) 若已知具有 $n(n\ge 2)$ 个顶点的图的邻接矩阵为B，则 $B^m(2\le m\le n)$ 中非零元素的含义是什么?

答案： 见解析。

解析： （1）邻接矩阵

由图可读出无向边

$(0,1),(0,2),(0,4),(1,3),(1,4),(2,3),(3,4)$，

故邻接矩阵为

$$A=\left(\begin{array}{ccccc}0& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 1& 0& 0& 1& 0\\ 0& 1& 1& 0& 1\\ 1& 1& 0& 1& 0\end{array}\right).$$

（2）计算 $A^2$

$$A^2=\left(\begin{array}{ccccc}3& 1& 0& 3& 1\\ 1& 3& 2& 1& 2\\ 0& 2& 2& 0& 2\\ 3& 1& 0& 3& 1\\ 1& 2& 2& 1& 3\end{array}\right).$$

其中第 $0$ 行第 $3$ 列元素为 $3$，表示从顶点 $0$ 到顶点 $3$ 的长度为 $2$ 的通路共有 $3$ 条，分别经过顶点 $1,2,4$。

（3）一般结论

若 $B$ 是图的邻接矩阵，则 $(B^m{)}_{ij}$ 等于从顶点 $i$ 到顶点 $j$ 的长度为 $m$ 的通路数。因此，$B^m$ 中元素 $(i,j)$ 非零，表示从顶点 $i$ 到顶点 $j$ 至少存在一条长度为 $m$ 的通路；若 $i=j$，则表示存在长度为 $m$ 的闭通路。

4. 【2021】已知无向连通图G 由顶点集V 和边集E 组成, $E>0$, 当G 中度为奇数的顶点个数为不大于2 的偶数时, G 存在包含所有边且长度为E 的路径(称为EL 路径)。设图G 采用邻接矩阵存储,类型定义如下:

C

typedef struct {                    // 图的定义
    int numVertices, numEdges;      // 图中实际的顶点数和边数
    char VerticesList[MAXV];        // 顶点表，MAXV为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

请设计算法: int IsExistEL(MGraph G), 判断G 是否存在EL 路径，若存在，则返回1, 否则返回0。要求: (1) 给出算法的基本设计思想。 (2) 根据设计思想，采用C 或C++ 语言描述算法，关键之处给出注释。 (3) 说明你所设计算法的时间复杂度和空间复杂度。

答案： 见解析。

解析： 题设中的 EL 路径就是无向连通图的欧拉通路。无向连通图存在欧拉通路的充要条件是：度为奇数的顶点数为 $0$ 或 $2$。

（1）基本设计思想

逐行扫描邻接矩阵。第 $i$ 行元素之和就是顶点 $i$ 的度，统计度为奇数的顶点个数。若奇度顶点数为 $0$ 或 $2$，返回 $1$；否则返回 $0$。题目已知 $G$ 为无向连通图，因此无需再次判断连通性。

（2）算法

C

int IsExistEL(MGraph G) {
    int odd = 0;

    for (int i = 0; i < G.numVertices; ++i) {
        int degree = 0;
        for (int j = 0; j < G.numVertices; ++j) {
            degree += G.Edge[i][j];   // 无向图中第 i 行之和为顶点 i 的度
        }
        if (degree % 2 != 0) {
            ++odd;
            if (odd > 2)              // 已不可能存在欧拉通路
                return 0;
        }
    }

    return (odd == 0 || odd == 2) ? 1 : 0;
}

（3）复杂度

需要扫描整个邻接矩阵，时间复杂度为 $O(|V{|}^2)$；只使用常数个辅助变量，空间复杂度为 $O(1)$。

5. 【2023】(13 分) 已知有向图G 采用邻接矩阵存储, 类型定义如下:

C

typedef struct {                    // 图的定义
    int numVertices, numEdges;      // 图中实际的顶点数和边数
    char VerticesList[MAXV];        // 顶点表，MAXV为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

将图中出度大于入度的顶点称为K 顶点。例如: 在右图中, 顶点a 和顶点b 都是K 顶点。请设计算法:int printVertices(MGraph G),对给定的任意非空有向图G, 输出图G 中所有的K 顶点, 并返回K 顶点的个数。要求: (1) 给出算法的基本设计思想。 (2) 根据设计思想，采用C 或C++ 语言描述算法，关键之处给出注释。

答案： 见解析。

解析： （1）基本设计思想

在有向图的邻接矩阵中，第 $i$ 行元素之和是顶点 $i$ 的出度，第 $i$ 列元素之和是其入度。对每个顶点分别计算出度和入度，若出度大于入度，则输出该顶点并将计数器加 $1$。

（2）算法

C

int printVertices(MGraph G) {
    int count = 0;

    for (int i = 0; i < G.numVertices; ++i) {
        int outDegree = 0;
        int inDegree = 0;

        for (int j = 0; j < G.numVertices; ++j) {
            outDegree += G.Edge[i][j]; // 第 i 行：从 i 指向其他顶点
            inDegree  += G.Edge[j][i]; // 第 i 列：其他顶点指向 i
        }

        if (outDegree > inDegree) {
            printf("%c ", G.VerticesList[i]);
            ++count;
        }
    }

    return count;
}

算法扫描邻接矩阵，时间复杂度为 $O(|V{|}^2)$，额外空间复杂度为 $O(1)$。

6. 【2024】(13 分)2023 年10 月26 日, 神舟十七号载人飞船发射取得圆满成功, 再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程, 为了保证工程的有序开展,需要明确各子工程的前导子工程, 以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图G 采用邻接矩阵存储, 类型定义如下:

C

typedef struct {                    // 图的定义
    int numVertices, numEdges;      // 图中实际的顶点数和边数
    char VerticesList[MAXV];        // 顶点表，MAXV为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

请设计算法:int uniquely(MGraph G), 判定G 是否存在唯一的拓扑序列，若是则返回1,否则返回0。要求如下: (1) 给出算法的基本设计思想。(4 分) (2) 根据设计思想，采用C 或C++ 语言描述算法，关键之处给出注释。(9 分)

答案： 见解析。

解析： （1）基本设计思想

采用基于入度的拓扑排序算法。先计算所有顶点的入度，然后重复执行：

• 在所有尚未输出的顶点中查找入度为 $0$ 的顶点；
• 若当前没有这样的顶点，则图中存在有向环，不存在拓扑序列；
• 若当前有两个或两个以上入度为 $0$ 的顶点，则下一位置有多种选择，拓扑序列不唯一；
• 只有当每一步恰有一个入度为 $0$ 的顶点，且最终输出全部顶点时，拓扑序列才唯一。

（2）算法

C

int uniquely(MGraph G) {
    int n = G.numVertices;
    int indegree[MAXV] = {0};
    int removed[MAXV] = {0};

    // 计算各顶点入度
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (G.Edge[i][j] != 0)
                ++indegree[j];

    for (int k = 0; k < n; ++k) {
        int zeroCount = 0;
        int u = -1;

        // 查找尚未删除且入度为 0 的顶点
        for (int i = 0; i < n; ++i) {
            if (!removed[i] && indegree[i] == 0) {
                ++zeroCount;
                u = i;
            }
        }

        // 0 个：有环；多于 1 个：拓扑序列不唯一
        if (zeroCount != 1)
            return 0;

        removed[u] = 1;

        // 删除顶点 u 及其所有出边
        for (int v = 0; v < n; ++v) {
            if (G.Edge[u][v] != 0)
                --indegree[v];
        }
    }

    return 1;
}

采用邻接矩阵时，计算入度和每轮查找、更新均需扫描矩阵或顶点数组，时间复杂度为 $O(|V{|}^2)$；辅助数组空间复杂度为 $O(|V|)$。

5.3 图的遍历

1. 【2012】对有n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历, 其算法时间复杂度是（ ）。

A. $O(n)$
B. $O(e)$
C. $O(n+e)$
D. $O(ne)$

答案： C。

解析： 邻接表中每个顶点表结点访问一次，共 $n$ 次；每条有向边在边表中扫描一次，共 $e$ 次。因此广度优先遍历的时间复杂度为 $O(n+e)$。

2. 【2013】若对右图所示的无向图进行遍历，则下列选项中,不是广度优先遍历序列的是（ ）。

A. h,c,a,b,d,e,g,f
B. e,a,f,g,b,h,c,d
C. d,b,c,a,h,e,f,g
D. a,b,c,d,h,e,f,g

答案： D。

解析： 广度优先遍历要求先访问起点的所有相邻顶点，再访问距离起点为 $2$ 的顶点。

从 $a$ 出发时，$b,h,e$ 都是与 $a$ 直接相邻的第一层顶点，而 $c,d$ 是第二层顶点。序列 D 在访问 $b$ 后立即访问第二层顶点 $c,d$，却尚未访问第一层顶点 $h,e$，不可能由广度优先遍历得到。

其余三个序列均可通过适当安排同层邻接点的访问次序得到。

3. 【2015】设有向图G = V,E, 顶点集V = $v_0$,$v_1$,$v_2$,$v_3$, 边集E = <$v_0$,$v_1$>,<$v_0$,$v_2$>,<$v_0$,$v_3$>,<$v_1$,$v_3$> 。若从顶点v0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（ ）。

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

答案： D。

解析： 从 $v_0$ 开始，可能的深度优先遍历序列为

$v_0,v_1,v_3,v_2$；

$v_0,v_2,v_1,v_3$；

$v_0,v_2,v_3,v_1$；

$v_0,v_3,v_1,v_2$；

$v_0,v_3,v_2,v_1$。

共 $5$ 种。关键在于若先访问 $v_1$，则必须沿边 $v_1\to v_3$ 继续深入，因此只有第一种以 $v_1$ 为第二个顶点的序列。

4. 【2016】下列选项中, 不是右图深度优先搜索序列的是（ ）．

A. V1,V5,V4,V3,V2
B. V1,V3,V2,V5,V4
C. V1,V2,V5,V4,V3
D. V1,V2,V3,V4,V5

答案： D。

解析： 图中存在有向边

$V_1\to V_2,V_1\to V_3,V_1\to V_5,V_3\to V_2,V_2\to V_5,V_5\to V_4,V_4\to V_3$。

若从 $V_1$ 首先访问 $V_2$，深度优先搜索必须沿

$V_2\to V_5\to V_4\to V_3$

继续深入，因此相应序列应为 $V_1,V_2,V_5,V_4,V_3$，不可能得到选项 D 的 $V_1,V_2,V_3,V_4,V_5$。

5.4 图的基本应用

1. 【2010】对右图进行拓扑排序,可得不同拓扑排序的个数是（ ）。

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

答案： B。

解析： 图中的先后约束为

$a\to e\to d,a\to b\to c\to d,a\to c$。

因此 $a$ 必须最先，$d$ 必须最后；中间的 $e,b,c$ 只要求 $b$ 在 $c$ 前。三者共有

$\frac{3!}{2}=3$

种合法排列，所以不同拓扑序列共有 $3$ 个。

2. 【2011】下列关于图的叙述中, 正确的是（ ）。 I. 回路是简单路径 II. 存储稀疏图,用邻接矩阵比邻接表更省空间 III. 若有向图中存在拓扑序列，则该图不存在回路

A. 仅II
B. 仅I、II
C. 仅III
D. 仅I、III

答案： C。

解析： I 错误：回路的起点与终点相同，不属于通常意义下顶点不重复的简单路径。

II 错误：稀疏图中 $|E|$ 远小于 $|V{|}^2$，邻接表空间为 $O(|V|+|E|)$，比邻接矩阵的 $O(|V{|}^2)$ 更省空间。

III 正确：有向图存在拓扑序列的充要条件是该图为有向无环图。

3. 【2012】若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零，则关于该图的拓扑序列的结论是（ ）。

A. 存在, 且唯一
B. 存在,且不唯一
C. 存在, 可能不唯一
D. 无法确定是否存在

答案： C。

解析： 主对角线以下元素全为零，说明只有编号较小的顶点可能指向编号较大的顶点，即所有边都形如 $v_i\to v_j(i<j)$。因此不可能形成有向环，按顶点编号递增排列必为一个拓扑序列。

但若某些顶点之间不存在直接或间接的先后约束，则还可以交换它们的位置，所以拓扑序列可能不唯一。

4. 【2014】对右图所示的有向图进行拓扑排序, 得到的拓扑序列可能是（ ）．

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

答案： D。

解析： 由图可得约束

$3\to 1,3\to 6,1\to 2,1\to 4,4\to 2,4\to 6,2\to 5,6\to 5$。

选项 D 的序列 $3,1,4,2,6,5$ 满足所有边的起点都位于终点之前。

A、B 都把 $2$ 放在 $4$ 前，违反 $4\to 2$；C 把 $5$ 放在 $6$ 前，违反 $6\to 5$。

5. 【2016】若n 个顶点、e 条弧的有向图用邻接表存储，则拓扑排序算法时间复杂度是（ ）。

A. $O(n)$
B. $O(n+e)$
C. $O(n^2)$
D. $O(ne)$

答案： B。

解析： 用邻接表进行拓扑排序时，初始化入度需要扫描所有顶点和边；每个顶点入队、出队至多一次，每条弧在删除其起点时扫描一次。因此时间复杂度为 $O(n+e)$。

6. 【2018】下列选项中不是右侧有向图的拓扑序列的是（ ）。

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

答案： D。

解析： 图中的主要约束包括

$1\to 2,1\to 3,2\to 3,2\to 6,3\to 4,6\to 4,5\to 2,5\to 4$。

选项 D 为 $5,2,1,6,3,4$，其中顶点 $2$ 出现在顶点 $1$ 之前，违反有向边 $1\to 2$ 的先后关系，因此不是拓扑序列。

7. 【2021】给定右侧有向图, 该图的拓扑有序序列的个数是（ ）。

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

答案： A。

解析： 图中的约束形成如下顺序链：

$A\to B\to C\to D\to E\to F$。

虽然图中还存在若干跨层边，但不会产生新的可交换顶点。因此每一步都只有一个入度为 $0$ 的顶点，拓扑序列唯一，即只有 $1$ 个。

8. 【2012】下列关于最小生成树的叙述中,正确的是（ ）。 I. 最小生成树的代价唯一 II. 所有权值最小的边一定会出现在所有的最小生成树中 III. 使用Prim 算法从不同顶点开始得到的最小生成树一定相同 IV. 使用Prim 算法和Kruskal 算法得到的最小生成树总不相同

A. 仅I
B. 仅II
C. 仅I、III
D. 仅II、IV

答案： A。

解析： I 正确：同一带权连通图即使存在多棵不同的最小生成树，它们的总权值都等于全局最小代价，因此最小生成树的代价唯一。

II 错误：当多条最小权边构成环时，不可能把它们全部加入生成树，且某条最小权边不一定出现在所有最小生成树中。

III 错误：存在多棵最小生成树时，Prim 算法从不同顶点开始或采用不同的并列选择策略，结果可能不同。

IV 错误：Prim 与 Kruskal 算法完全可能得到同一棵最小生成树。

9. 【2015】求右侧带权图的最小(代价) 生成树时, 可能是Kruskal 算法第2 次选中但不是Prim 算法(从V4开始) 第2 次选中的边是（ ）。

A. V1,V3
B. V1,V4
C. V2,V3
D. V3,V4

答案： C。

解析： 图中权值为 $5$ 的边 $(V_1,V_4)$ 最小，因此 Kruskal 算法第一次选择该边。随后权值为 $8$ 的边有多条，Kruskal 第二次可能选择 $(V_2,V_3)$。

Prim 算法从 $V_4$ 开始时，第一次同样选择 $(V_4,V_1)$。此时生成树顶点集为 $\{V_4,V_1\}$，第二次只能选择一端在该集合内、另一端在集合外的边；$(V_2,V_3)$ 的两个端点都不在集合内，故不可能成为 Prim 的第二条边。

10. 【2020】已知无向图G 如右所示, 使用克鲁斯卡尔(Kruskal) 算法求图G 的最小生成树, 加到最小生成树中的边依次是（ ）．

A. b,f, b,d, a,e, c,e, b,e
B. b,f, b,d, b,e, a,e, c,e
C. a,e, b,e, c,e, b,d, b,f
D. a,e, c,e, b,e, b,f, b,d

答案： A。

解析： Kruskal 算法按权值从小到大考察边，并跳过会形成回路的边。依次选择：

$(b,f)$，权值 $5$；

$(b,d)$，权值 $6$；

权值为 $7$ 的 $(d,f)$ 会与前两条边形成回路，跳过；

再选择 $(a,e)$、$(c,e)$ 和 $(b,e)$。

故加入最小生成树的边依次为

$(b,f),(b,d),(a,e),(c,e),(b,e)$。

11. 【2012】对右图所示的有向带权图,若采用Dijkstra 算法求从源点a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b, 第二条最短路径的目标顶点是c, 后续得到的其余各最短路径的目标顶点依次是（ ）．

A. d,e,f
B. e,d,f
C. f,d,e
D. f,e,d

答案： C。

解析： 从源点 $a$ 出发，初始可确定 $d(a,b)=2$、$d(a,c)=5$，故前两条最短路径的目标顶点依次为 $b,c$。

经顶点 $b$ 松弛后，$d(a,c)=3$、$d(a,d)=5$；经顶点 $c$ 松弛后，可得 $d(a,f)=4$，因此下一个确定的是 $f$。随后确定 $d$，再由 $d$ 松弛得到到 $e$ 的更短距离，最后确定 $e$。

后续目标顶点依次为 $f,d,e$。

12. 【2016】使用Dijkstra 算法求右图中从顶点1 到其他各顶点的最短路径, 依次得到的各最短路径的目标顶点是（ ）。

A. 5,2,3,4,6
B. 5,2,3,6,4
C. 5,2,4,3,6
D. 5,2,6,3,4

答案： B。

解析： 从顶点 $1$ 出发，初始距离中最小的是到顶点 $5$ 的距离 $4$，故先确定顶点 $5$；其次确定顶点 $2$，距离为 $5$。

随后通过顶点 $2$ 到顶点 $3$ 的距离为 $7$，再确定顶点 $6$，最后确定顶点 $4$。因此目标顶点顺序为

$5,2,3,6,4$。

13. 【2021】使用Dijkstra 算法求右图中从顶点1 到其余各顶点的最短路径, 将当前找到的从顶点1 到顶点2,3,4,5 的最短路径长度保存在数组dist 中,求出第二条最短路径后, dist 内容更新为（ ）．

A. 26,3,14,6
B. 25,3,14,6
C. 21,3,14,6
D. 15,3,14,6

答案： C。

解析： 以数组下标顺序 $2,3,4,5$ 记录距离。初始时

$dist=(26,3,\infty ,6)$。

第一条最短路径到顶点 $3$，距离为 $3$，松弛后到顶点 $2$ 的距离变为 $3+22=25$。第二条最短路径到顶点 $5$，距离为 $6$；由顶点 $5$ 松弛可得

$d(1,2)=\min (25,6+15)=21$，

$d(1,4)=6+8=14$。

故此时

$dist=(21,3,14,6)$。

14. 【2013】右侧的AOE 网表示一项包含8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中, 加快其进度就可以缩短工期工程的是（ ）．

A. c 和e
B. d 和c
C. f 和d
D. f 和h

答案： C。

解析： 各条从源点到汇点的路径长度中，最长工期为 $27$。关键路径有：

$1\stackrel{b}{\to }3\stackrel{d}{\to }2\stackrel{c}{\to }4\stackrel{g}{\to }6$；

$1\stackrel{b}{\to }3\stackrel{d}{\to }2\stackrel{e}{\to }5\stackrel{h}{\to }6$；

$1\stackrel{b}{\to }3\stackrel{f}{\to }5\stackrel{h}{\to }6$。

若要保证缩短整个工程工期，所加快的活动集合必须覆盖所有关键路径。活动 $d$ 覆盖前两条关键路径，活动 $f$ 覆盖第三条关键路径，因此同时加快 $f$ 和 $d$ 可以缩短工期。

15. 【2019】如右图所示的AOE 网表示一项包含8 个活动的工程。活动d 的最早开始时间和最迟开始时间分别是（ ）．

A. 3 和7
B. 12 和12
C. 12 和14
D. 15 和15

答案： C。

解析： 先计算事件最早发生时间：

$ve(1)=0,ve(3)=8,ve(2)=\max (3,8+4)=12$，

$ve(4)=12+7=19,ve(5)=\max (12+6,8+10)=18$，

$ve(6)=\max (19+6,18+9)=27$。

再逆推事件最迟发生时间：

$vl(6)=27,vl(4)=21,vl(5)=18$，

$vl(2)=\min (21-7,18-6)=12$。

活动 $d$ 为边 $2\to 4$，持续时间为 $7$，其最早开始时间为

$e(d)=ve(2)=12$，

最迟开始时间为

$l(d)=vl(4)-7=21-7=14$。

16. 【2020】若使用AOE 网估算工程进度，则下列叙述中正确的是（ ）。

A. 关键路径是从源点到汇点边数最多的一条路径
B. 关键路径是从源点到汇点路径长度最长的路径
C. 增加任一关键活动的时间不会延长工程的工期
D. 缩短任一关键活动的时间将会缩短工程的工期

答案： B。

解析： AOE 网中，一条路径的长度是该路径上各活动持续时间之和。工程完成时间由源点到汇点的最长路径决定，因此关键路径是从源点到汇点路径长度最长的路径。

A 把“边数最多”误作“时间最长”；C 错在增加关键活动时间通常会延长至少一条关键路径；D 也不一定成立，因为可能存在多条关键路径，缩短只属于其中一条的关键活动后，另一条关键路径仍可能决定总工期。

17. 【2022】右图是一个有10 个活动的AOE 网,时间余量最大的活动是（ ）．

A. c
B. g
C. h
D. j

答案： B。

解析： 计算事件最早发生时间：

$ve(1)=0,ve(2)=2,ve(3)=\max (5,2+3)=5$，

$ve(4)=\max (2+3,5+3)=8$，

$ve(5)=\max (5+3,8+1)=9$，

$ve(6)=\max (5+1,8+4,9+1)=12$。

逆推最迟发生时间可得

$vl(6)=12,vl(5)=11,vl(4)=8,vl(3)=5,vl(2)=2$。

各备选活动的时间余量为

$\Delta c=vl(3)-ve(2)-3=0$，

$\Delta g=vl(6)-ve(3)-1=6$，

$\Delta h=vl(5)-ve(4)-1=2$，

$\Delta j=vl(6)-ve(5)-1=2$。

故时间余量最大的是活动 $g$。

18. 【2019】用有向无环图描述表达式x+y * x+y /x, 需要的顶点个数至少是（ ）。

A. 5
B. 6
C. 8
D. 9

答案： B。

解析： 按通常的运算优先级，表达式为

$x+(y\times x)+(y÷x)$。

用有向无环图表示时，相同的操作数结点可以共享，因此只需两个操作数结点 $x,y$。运算结点包括一次乘法、一次除法和两次加法，共 $4$ 个。因此至少需要

$2+4=6$

个顶点。

19. 【2020】修改递归方式实现的图的深度优先搜索(DFS) 算法，将输出(访问) 顶点信息的语句移到退出递归前(即执行输出语句后立刻退出递归)。采用修改后的算法遍历有向无环图G，若输出结果中包含G 中的全部顶点，则输出的顶点序列是G 的（ ）。

A. 拓扑有序序列
B. 逆拓扑有序序列
C. 广度优先搜索序列
D. 深度优先搜索序列

答案： B。

解析： 修改后的 DFS 在一个顶点的所有后继顶点都完成访问后，才输出该顶点，即按“完成时间”输出。

对于任意有向边 $u\to v$，若遍历结果包含全部顶点，则顶点 $v$ 必在 $u$ 退出递归前完成并输出，所以输出序列中 $v$ 位于 $u$ 之前。这恰好满足逆拓扑序列的定义。

20. 【2023】已知无向连通图G 中各边的权值均为1。下列算法中, 一定能够求出图G 中从某顶点到其余各个顶点最短路径的是（ ）。 I. 普里姆(Prim) 算法 II. 克鲁斯卡尔(Kruskal) 算法 III. 图的广度优先搜索算法

A. 仅I
B. 仅III
C. I、II
D. I、II、III

答案： B。

解析： 图中所有边权均为 $1$，从源点到某顶点的最短路径长度就是所经过的最少边数。广度优先搜索按与源点距离从小到大的层次访问顶点，第一次访问某顶点时得到的路径一定是最短路径。

Prim 和 Kruskal 算法求的是全图的最小生成树，目标是使生成树总权值最小，并不保证生成树中从指定源点到各顶点的路径最短。故只有 III 正确。

21. 【2009】带权图(权值非负, 表示边连接的两顶点间的距离) 的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径, 假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法: (1) 设最短路径初始时仅包含初始顶点, 令当前顶点u 为初始顶点。 (2) 选择离u 最近且尚未在最短路径中的一个顶点v, 加入最短路径, 修改当前顶点u = v。 (3) 重复步骤(2), 直到u 是目标顶点时为止。请问上述方法能否求得最短路径？若该方法可行，请证明；否则，请举例说明。

答案： 该方法不能保证求得最短路径。

解析： 该方法每一步只根据“当前顶点”选择距离最近的下一顶点，属于局部贪心策略。它没有比较从初始顶点到各候选顶点的累计路径长度，因此局部最优选择不一定能得到全局最短路径。

构造如下带权无向图，设初始顶点为 $s$，目标顶点为 $t$：

Text

s --1-- a --100-- t
 \                 
  \--2-- b --2---- t

各边权值均非负。按照题述方法：

1. 在顶点 $s$ 处，因 $w(s,a)=1<w(s,b)=2$，先选择顶点 $a$；
2. 到达 $a$ 后，只能沿边 $(a,t)$ 到达目标顶点 $t$。

由此得到的路径为

$s\to a\to t$，

其长度为

$1+100=101$。

但另一条路径

$s\to b\to t$

的长度为

$2+2=4$。

显然 $4<101$，所以题述方法得到的路径不是最短路径。最短路径算法必须考虑从初始顶点出发的累计距离，例如非负权图可使用 Dijkstra 算法。

22. 【2011】已知有6 个顶点(顶点编号为0~5) 的有向带权图G, 其邻接矩阵A 为上三角矩阵, 按行为主序(行优先) 保存在如下的一维数组中。

$4,6,\infty ,\infty ,\infty ,5,\infty ,\infty ,\infty ,4,3,\infty ,\infty ,3,3$

要求: (1) 写出图G 的邻接矩阵A。 (2) 画出有向带权图G。 (3) 求图G 的关键路径, 并计算该关键路径的长度。

答案：

(1)

$$A=\left(\begin{array}{cccccc}0& 4& 6& \infty & \infty & \infty \\ \infty & 0& 5& \infty & \infty & \infty \\ \infty & \infty & 0& 4& 3& \infty \\ \infty & \infty & \infty & 0& \infty & 3\\ \infty & \infty & \infty & \infty & 0& 3\\ \infty & \infty & \infty & \infty & \infty & 0\end{array}\right)$$

(2) 图中的有向边及其权值为：

$0\to 1(4),0\to 2(6),1\to 2(5),2\to 3(4),2\to 4(3),3\to 5(3),4\to 5(3)$。

示意图如下：

Text

      4        5        4        3
0 --------> 1 -----> 2 -----> 3 -----> 5
 \                    \
  \------ 6 ---------->\---- 3 -----> 4 ---- 3 ----> 5

(3) 关键路径为

$0\to 1\to 2\to 3\to 5$，

关键路径长度为 $16$。

解析： 一维数组共有

$\frac{6\times (6-1)}{2}=15$

个元素，恰好对应六阶邻接矩阵主对角线以上的全部元素。按照行优先顺序依次填入

$a_{01},a_{02},\dots ,a_{05},a_{12},\dots ,a_{15},\dots ,a_{45}$，

即可得到上述邻接矩阵。主对角线元素为 $0$，主对角线以下均为 $\infty$。

将顶点看作事件，计算各事件的最早发生时间：

$ve(0)=0$，

$ve(1)=ve(0)+4=4$，

$ve(2)=\max \{ve(0)+6,ve(1)+5\}=\max \{6,9\}=9$，

$ve(3)=ve(2)+4=13$，

$ve(4)=ve(2)+3=12$，

$ve(5)=\max \{ve(3)+3,ve(4)+3\}=\max \{16,15\}=16$。

因此整个工程的最短完成时间为 $16$。达到该长度的路径为

$0\to 1\to 2\to 3\to 5$，

其长度为

$4+5+4+3=16$，

故它是关键路径。

23. 【2014】某网络中的路由器运行OSPF 路由协议,表5.1 是路由器R1 维护的主要链路状态信息 (LSI), R1 构造的网络拓扑图如图5.1 所示, 是根据下表及R1 的接口名构造出来的网络拓扑。请回答下列问题: (1) 本题中的网络可抽象为数据结构中的哪种逻辑结构？ (2) 针对表中的内容, 设计合理的链式存储结构, 以保存表中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义,并画出对应表的链式存储结构示意图(示意图中可仅以ID 标识结点)。 (3) 按照Dijkstra 算法的策略, 依次给出R1 到达子网192.1.x.x 的最短路径及费用。

表5.1 R1 所维护的 LSI

项目	字段	R1 的 LSI	R2 的 LSI	R3 的 LSI	R4 的 LSI	备注
Router ID		10.1.1.1	10.1.1.2	10.1.1.5	10.1.1.6	标识路由器的 IP 地址
Link1	ID	10.1.1.2	10.1.1.1	10.1.1.6	10.1.1.5	所连路由器的 Router ID
Link1	IP	10.1.1.1	10.1.1.2	10.1.1.5	10.1.1.6	Link1 的本地 IP 地址
Link1	Metric	3	3	6	6	Link1 的费用
Link2	ID	10.1.1.5	10.1.1.6	10.1.1.1	10.1.1.2	所连路由器的 Router ID
Link2	IP	10.1.1.9	10.1.1.13	10.1.1.10	10.1.1.14	Link2 的本地 IP 地址
Link2	Metric	2	4	2	4	Link2 的费用
Net1	Prefix	192.1.1.0/24	192.1.6.0/24	192.1.5.0/24	192.1.7.0/24	直连网络 Net1 的网络前缀
Net1	Metric	1	1	1	1	到达直连网络 Net1 的费用

答案：

(1) 该网络可抽象为图结构，具体为带权无向图。路由器和子网可看作顶点，链路可看作边，链路费用可看作边权。

(2) 可采用邻接表保存链路状态信息。每个路由器对应一个顶点结点，每条链路对应一个边结点；顶点结点中同时保存该路由器直连子网的信息。

一种数据类型定义如下：

C

typedef struct LinkNode {
    char neighborID[16];      // 相邻路由器的 Router ID
    char localIP[16];         // 本地接口 IP 地址
    int metric;               // 链路费用
    struct LinkNode *next;
} LinkNode;

typedef struct RouterNode {
    char routerID[16];        // 本路由器的 Router ID
    char netPrefix[20];       // 直连网络前缀
    int netMetric;            // 到直连网络的费用
    LinkNode *firstLink;      // 第一条链路
} RouterNode;

typedef struct {
    RouterNode routers[4];
    int routerNum;
} LSIAdjList;

对应表5.1 的邻接表示意如下：

Text

R1(10.1.1.1，Net=192.1.1.0/24，1)
  -> R2(10.1.1.2，localIP=10.1.1.1，3)
  -> R3(10.1.1.5，localIP=10.1.1.9，2)

R2(10.1.1.2，Net=192.1.6.0/24，1)
  -> R1(10.1.1.1，localIP=10.1.1.2，3)
  -> R4(10.1.1.6，localIP=10.1.1.13，4)

R3(10.1.1.5，Net=192.1.5.0/24，1)
  -> R4(10.1.1.6，localIP=10.1.1.5，6)
  -> R1(10.1.1.1，localIP=10.1.1.10，2)

R4(10.1.1.6，Net=192.1.7.0/24，1)
  -> R3(10.1.1.5，localIP=10.1.1.6，6)
  -> R2(10.1.1.2，localIP=10.1.1.14，4)

(3) R1 到各子网的最短路径及费用依次为：

目标子网	最短路径	费用
$192.1.1.0/24$	$R1\to 192.1.1.0/24$	$1$
$192.1.5.0/24$	$R1\to R3\to 192.1.5.0/24$	$2+1=3$
$192.1.6.0/24$	$R1\to R2\to 192.1.6.0/24$	$3+1=4$
$192.1.7.0/24$	$R1\to R2\to R4\to 192.1.7.0/24$	$3+4+1=8$

解析： 从 $R1$ 出发，各路由器的初始暂定距离为

$d(R3)=2,d(R2)=3,d(R4)=\infty$。

先确定距离最小的 $R3$，由 $R3$ 到 $R4$ 可得到暂定距离

$2+6=8$。

再确定 $R2$，经 $R2$ 到 $R4$ 的距离为

$3+4=7<8$，

故将 $d(R4)$ 更新为 $7$。每个路由器到其直连子网的费用均为 $1$，因此上述四个子网的最短费用依次为 $1,3,4,8$。

24. 【2017】使用Prim 算法求带权连通图的最小(代价) 生成树(MST)。请回答下列问题: (1) 右图G, 从顶点A 开始求G 的MST, 依次给出按算法选出的边。 (2) 图G 的MST 是唯一的吗? (3) 对任意的带权连通图, 满足什么条件时, 其MST 是唯一的？

答案：

(1) 从顶点 $A$ 开始，Prim 算法依次选出的边为

$(A,D),(D,E),(E,C),(C,B)$。

(2) 图 $G$ 的最小生成树唯一，其总权值为

$4+4+5+4=17$。

(3) 对任意带权连通图，若所有边的权值互不相同，则其最小生成树一定唯一。

解析： 初始顶点集合为

$U=\{A\}$。

1. 与 $A$ 相连的边中，$(A,D)$ 的权值 $4$ 最小，选择 $(A,D)$，此时 $U=\{A,D\}$；
2. 横跨 $U$ 与 $V-U$ 的边中，$(D,E)$ 的权值 $4$ 最小，选择 $(D,E)$；
3. 此时连接树内顶点与树外顶点的最小权边为 $(E,C)$，权值为 $5$，选择该边；
4. 最后顶点 $B$ 可通过 $(C,B)$ 以权值 $4$ 接入生成树。

所得边集为

$T=\{(A,D),(D,E),(E,C),(C,B)\}$。

说明唯一性时，可以按权值从小到大考察：图中三条权值为 $4$ 的边

$(A,D),(D,E),(B,C)$

互不构成回路，均应被选入。它们形成两个连通分量 $\{A,D,E\}$ 和 $\{B,C\}$。连接这两个分量的最小权边只有 $(E,C)$，其权值为 $5$，因此生成树无法用其他等权边替换，故本图的 MST 唯一。

“所有边权值互不相同”是保证 MST 唯一的充分条件，但不是必要条件；本题虽然存在相同权值，MST 仍然唯一。

25. 【2018】拟建设一个光通信骨干网络连通BJ, CS, XA, QD, JN, NJ, TL 和WH 等8 个城市,右图中无向边上的权值表示两个城市之间备选光缆的铺设费用。请回答下列问题: (1) 仅从铺设费用角度出发, 给出所有可能的最经济的光缆铺设方案(用带权图表示),并计算相应方案的总费用。 (2) 该图可采用图的哪种存储结构？给出求解问题(1) 所用的算法名称。 (3) 假设每个城市采用一个路由器按(1) 中得到的最经济方案组网, 主机H1 直接连接在TL 的路由器上, 主机H2 直接连接在BJ 的路由器上。若H1 向H2 发送一个TTL = 5 的IP分组，则H2 是否可以收到该IP分组?

答案：

(1) 共有两种最经济的光缆铺设方案。

方案一的边集为

$\{(XA,BJ,2),(XA,WH,2),(QD,NJ,2),(TL,JN,2),(QD,JN,2),(CS,QD,3),(BJ,TL,3)\}$。

方案二的边集为

$\{(XA,BJ,2),(XA,WH,2),(QD,NJ,2),(TL,JN,2),(QD,JN,2),(CS,QD,3),(WH,QD,3)\}$。

两种方案的总费用均为

$2+2+2+2+2+3+3=16$。

(2) 该带权无向图可采用邻接矩阵或邻接表存储。求解问题(1) 可使用 Kruskal 算法；也可使用 Prim 算法。为找出全部最小生成树，采用 Kruskal 算法并对相同权值的候选边分别讨论更方便。

(3) 结论与采用的最经济方案有关：

• 采用方案一时，$TL$ 与 $BJ$ 直接相连，$H2$ 可以收到该 IP 分组；
• 采用方案二时，$H2$ 不能收到该 IP 分组。

解析： 按 Kruskal 算法，先选择全部不会构成回路的权值为 $2$ 的边：

$(XA,BJ),(XA,WH),(QD,NJ),(TL,JN),(QD,JN)$。

此时形成三个连通分量：

$\{XA,BJ,WH\},\{TL,JN,QD,NJ\},\{CS\}$。

为了将 $CS$ 接入，必须选择权值为 $3$ 的边 $(CS,QD)$。连接前两个较大连通分量时，可选择权值同为 $3$ 的

$(BJ,TL)$

或

$(WH,QD)$。

因此恰有上述两种最小生成树。边 $(JN,NJ)$ 的权值虽然也是 $3$，但在已选权值为 $2$ 的边后，它会与 $(JN,QD)$、$(QD,NJ)$ 构成回路，故不能选入。

在方案一中，主机间的路由为

$H1\to TL\to BJ\to H2$，

路径很短，TTL 初值为 $5$ 时可以到达。

在方案二中，路由器之间的路径为

$TL\to JN\to QD\to WH\to XA\to BJ$。

该路径包含 $5$ 次路由器到路由器的转发。IP 分组到达路由器时，每次转发前 TTL 都减 $1$。分组到达 $XA$ 时 TTL 已为 $1$，$XA$ 将其减为 $0$ 后丢弃，不能继续转发到 $BJ$，所以 $H2$ 不能收到该分组。