第七章 图的作业（共 50 分） 一、选择题（每空 2 分，共 18 分）。 1．下列哪一种图的邻接矩阵是对称矩阵？（ B ）。 A．有向图 C．AOV 网 B．无向图 D．AOE 网 2．在边表示活动的 AOE 网中，关键活动的最迟开始时间（ D ）最早开始时间。 A．> C．>= D．= B．< 3．带权有向图 G 用邻接矩阵 A 存储，则顶点 i 的入度等于 A 中（ D ）。 A．第 i 行非∞的元素之和 C．第 i 行非∞且非 0 的元素个数 B．第 i 列非∞的元素之和 D．第 i 列非∞且非 0 的元素个数 4.在一个无向图中，所有顶点的度数之和等于所有边数的（ C ）倍。 A．1/2 B. 1 C. 2 D. 4 5.对于一个具有 n 个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ D ）。 A．n B．(n-1)2 C．n-1 D．n2 6. 如下有关拓扑序列的叙述，（ C ）不对。 A. 拓扑序列包含了有向图的全部顶点 C. 有向无环图不一定有拓扑序列 B. 有向有环图一定没有拓扑序列 D. 拓扑序列不一定唯一 7. 对于描述工程的 AOE 网，（ D ）说法正确。 A. 网中唯一的出度为零的顶点，称为源点 C. 关键路径是源点到汇点的最短路径 B. 网中唯一的入度为零的顶点，称为汇点 D. 关键路径可能有多条 8. 最小生成树指的是（ C ）。 A. 由连通网所得到的边数最少的生成树 B. 由连通网所得到的顶点数相对较少的生成树 C. 连通网中所有生成树中权值之和为最小的成生树 D. 连通网的极小连通子图 9．一个有向图，共有 n 条弧，则所有顶点的度的总和为（ A ）。 A．2n C．n-1 B．n D．n/2 二、填空题（每空 3 分，共 9 分）。 1．有 n 个顶点的连通图至少有_n-1__条边。有 n 个顶点的无向图至多有_n(n-1)/2_条边。 2. 图的广度优先遍历算法中用到辅助队列，每个顶点最多进队 1 次。 3．在一个具有 n 个顶点的有向完全图中包含有 n(n-1) 条边。 三、综合题（共 23 分）。 1. （共 7 分）无向网如下： 

v2 13 v1 8 5 v4 3 6 19 33 v3 5 v5 v6 7 1 (1) 给出该无向网的邻接矩阵表示（3 分）。 0 13 ∝ 8 ∝ ∝ 13 0 ∝ 3 8 5 ∝ 6 ∝ 33 3 0 5 6 ∝ 5 33 7 ∝ 0 19 ∝ 5 7 19 0 ∝ 1 1 0 (2) 画出最小生成树（4 分）： v2 3 v1 8 5 v4 v6 1 v3 5 v5 2 .（共 8 分）已知一个连通图如图所示，试给出图的邻接矩阵和邻接链表存储示意图。 (1) 邻接矩阵存储示意图为（4 分）: 

(2) 邻接链表存储示意图为（4 分）: 0 1 2 3 4 5 V1 V2 V3 V4 V5 V6 1 0 1 0 1 0 5 ^ 3 4 3 ^ 4 5 ^ ^ 3 2 4 1 2 3 ^ ^ 3. （共 8 分）如图所示的带权无向图，请用克鲁斯卡尔算法给出最小生成树的求解过程。（注：酌情给步骤分） 最小生成树为：