第七章图复习题及答案
一、选择题
1.在一个图中，所有顶点的度数之和等于所有边的数目的_______倍
A．1/2 B．1 C．2 D．4
2。

在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_______倍。

A．1/2 B．1 C．2 D．4
6．具有6个顶点的无向图至少应该有_______条边才能保证是一个连通图
A．4 B．5 C．6 D．7
7. 一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个_______。

A．对称矩阵B．对角矩阵
C．三角矩阵D．稀疏矩阵
8．若具有n个顶点的无向图采用邻接矩阵存储方法，则邻接矩阵的大小为________
9．具有n个顶点、e条边的无向图采用邻接表存储方法，该邻接表中一共有________个边结点。

A．n B．2n C．e D．2e
l0．图的深度优先搜索算法类似于二叉树的——。

八．先序遍历B．中序遍历
C．后序遍历D．按层次遍历
11．图的广度优先搜索算法类似于二叉树的——。

A．先序遍历B．中序遍历
C．后序遍历D．按层次遍历
12．导致图的遍历序列不惟一的因素是————。

A．出发点的不同、遍历方法的不同
B．出发点的不同、存储结构的不同
c．遍历方法的不同、存储结构的不同
D．出发点的不同、存储结构的不同、遍历方法的不同
13．任何一个带权无向连通图的最小生成树——。

A．是惟一的，B．是不惟一的
C．有可能不惟一D．有可能不存在
16．判定一个有向图中是否存在回路可以利用——方法
A．求最小生成树B．求最短路径
C．拓扑排序D．图的遍历
17．判定一个有向图中是否存在回路除了利用拓扑排序方法以外，还可以利用——方法。

A.图的遍历B．求最小生成树
c．最短路径D．求关键路径
19．下面的说法中，不正确的是——。

A．AOE网是一个带权的有向图
B AOE网是一个带权且无环路的有向图
C．AOE网是一个带权且无环路的有向连通图
D正常情况下，AOE网中只有一个源点和一个终点
20．AOE网中的关键路径是该网中的——。

A．从源点到终点的最长路径
B．从源点到终点的最短路径
c．最长的回路
D．最短的回路
A．带权连通图的某最小生成树的权值之和一定小于其他生成树的权值之和B。

从源点到终点的最短路径是惟一的
C．任意一个AOV网不一定存在拓扑序列
D．任意一个AOE网中的关键路径是惟一的
答案：
1．选择C ；2．选择B，结论是显然的；3．选择D；4．选择A；
6．选择B。

由生成树的定义可知，具有6个顶点的无向图至少应该具有5条边才能保证该无向
图是一个连通图，故本题选择B。

7．选择A。

若无向图采用邻接矩阵存储方法，则其邻接矩阵一定是一个对称矩阵。

8．选择D。

具有n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵是一个n阶方阵，具有
n2个矩阵元素，因此，此题选择D。

9．选择D。

若具有n个顶点、e条边的无向图采用邻接表存储方法，该邻接表由n个链表组成，n 个链表中一共有2e个边结点，因此，此题选择D。

10．选择A。

由图的深度优失搜索方法的过程不难看到图的深度优先搜索类似于二叉树的前序遍历过程，故选择A。

11．选择D。

由图的广度优先搜索方法的过程不难看到图的广度优先搜索类似于二叉树的按层次遍历过程，故选择D。

12．选择D。

导致对一个图进行遍历而得到的遍历序列不惟一的因素有许多，首先，遍历的出发顶点选择得不惟一，得到的遍历序列显然不是惟一的。

即使遍历的出发顶点相同，采用的遍历方法若不相同，则得到的结果也是不相同的。

另外，即使遍历的出发顶点相同，并且采用同一种遍历方法，若图的存储结构不相同，则得到的结果也可能是不相同的。

例如，对于邻接表结构而言，建立邻接表时提供边的信息的先后次序不同，边结点的链接次序也不同，从而会建立不同的邻接表；同一个图的不同邻接表结构会导致不同的遍历结果。

因此，本题应该选择D。

13．选择C
一般情况下，带权连通图的最小生成树不一定是惟一的。

14．选择Co
由求解带权连通图的最小生成树的方法可以得到结论。

15．选择Bo
由求解最短路径的迪杰斯特拉(Dijstra)方法可以得到结论。

16．选择C
拓扑排序方法可以判定一个有向图中是否存在回路。

17．选择Do
除了采用拓扑排序方法判定一个有向图中是否存在回路之外，求关键路径的过程也可以判定一个有向图中是否存在回路。

18．选择A。

按照拓扑排序方法对该图进行拓扑排序便可得到结果。

19．选择C9
说法A，B和D是正确的，只有C是错误的
有向图，但它不是连通图，故选择co
20．选择A。

由AOE网的关键路径的定义可以得到结论。

21．选择C
求出该AOE网的关键路径便可以得到结论。

22．选择C
由于带权连通图的某最小生成树的权值之和不一定小于其他生成树的权值之和；对
于一个图而言，从源点到终点的最短路径也不一定是惟一的；任意一个AOE网中的关键路径也不一定惟一，因此，只有说法c是错误的。

的确，任意一个Aov网不一定存在拓扑序列。

二、综合题
10.试对右图所示的AOE网络，解答下列问题。

(1) 这个工程最早可能在什么时间结束。

(2) 求每个事件的最早开始时间Ve[i]和最迟开始
时间Vl[I]。

(3) 求每个活动的最早开始时间e( )和最迟开始
时间l( )。

(4) 确定哪些活动是关键活动。

画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。

【解答】
按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。

然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。

此工程最早完成时间为43。

关键路径为<1, 3><3, 2><2, 5><5, 6>
三、算法设计
见图实验要求，图的存储结构建立及遍历算法是重点。