第6章 图
一、填空题
1、用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网（AOV-网）。2、有n(n-1)/2条边的无向图称为_无向完全图__；有n(n-1)条边的有向图称为_有向完全图。 3、一个含n个结点的完全无向图中，其最大边数为__ n(n-1)/2_。
4、顶点表示事件，弧表示活动，权表示活动持续时间的有向图称为AOE-网。
二、判断题
1、任何无向图都存在生成树。（ ）
2、连通分量是无向图中的极小连通子图。（ ） 3、强连通分量是有向图中的极大强连通子图。（ ）
4、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。（ ）
5、邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（ ） 6、求最小生成树的Prim算法在边较少、结点较多时效率较高。（ ） 7、图的最小生成树的形状可能不唯一。（ ）
8、一个AOV网的拓扑序列一定是唯一的。 （ ） 9、若AOV网中存在环，则不能求它的拓扑排序序列。（ ）
10、若AOV网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。（ ） 11、缩短关键路径上活动的工期一定能够缩短整个工程的工期。（ ） 12、AOE网中一定只有一条关键路径。（ ）
三、单项选择题
1、在一个图中，所有顶点的度数之和等于图的边数的（ C ）倍。 A．1/2 B．1 C．2 D．4
2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。 A．1/2 B．1 C．2 D．4 解释：有向图所有顶点入度之和等于所有顶点出度之和。
3、具有n个顶点的有向图最多有（ B ）条边。
A．n B．n(n-1) C．n(n+1) D．n2
解释：有向图的边有方向之分，即为从n个顶点中选取2个顶点有序排列，结果为n(n-1)。
4、n个顶点的连通图用邻接距阵表示时，该距阵至少有（ B ）个非零元素。 A．n B．2(n-1) C．n/2 D．n2
5、G是一个非连通无向图，共有28条边，则该图至少有（ C ）个顶点。 A．7 B．8 C．9 D．10
解释：8个顶点的无向图最多有8*7/2=28条边，再添加一个点即构成非连通无向图，故至少有9个顶点。
6、若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ B ）图。
A．非连通 B．连通 C．强连通 D．有向
解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。 7、下面（A ）算法适合构造一个稠密图G的最小生成树。
1
A． Prim算法 B．Kruskal算法 C．Floyd算法 D．Dijkstra算法
解释：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏图G的最小生成树。
8、用邻接表表示图进行广度优先遍历时，通常借助（ B ）来实现算法。 A．栈 B. 队列 C. 树 D．图
解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。
9、用邻接表表示图进行深度优先遍历时，通常借助（ A ）来实现算法。 A．栈 B. 队列 C. 树 D．图
解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。
10、深度优先遍历类似于二叉树的（ A ）。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 11、广度优先遍历类似于二叉树的（ D ）。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 12、图的BFS生成树的树高比DFS生成树的树高（ C ）。
A．小 B．相等 C．小或相等 D．大或相等
解释：对于一些特殊的图，比如只有一个顶点的图，其BFS生成树的树高和DFS生成树的树高相等。一般的图，根据图的BFS生成树和DFS树的算法思想，BFS生成树的树高比DFS生成树的树高小。
13、已知图的邻接矩阵如图6.30所示，则从顶点v0出发按深度优先遍历的结果是（ ）。
图6.30 邻接矩阵
14、已知图的邻接表如图6.31所示，则从顶点v0出发按广度优先遍历的结果是（ D ），按深度优先遍历的结果是（ D ）。
图6.31 邻接表
A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3
15、下面（ B ）方法可以判断出一个有向图是否有环。
A．深度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径
四、应用题
1、已知图6.32所示的有向图，请给出： 1）每个顶点的入度和出度； 2）邻接矩阵；
2
3）邻接表；
4）逆邻接表。
图6.32 有向图
图6.33 无向网
答案：
2、已知如图6.33所示的无向网，请给出： 1）邻接矩阵； 2）邻接表； 3）最小生成树
答案：
??43?????? ?4 ? 5
?59????? 3 5 ? 5 ? ? ? 5 ??
???55?7654?? ??9?7?3?
???????63?2?? ??????5?2?6?
????54??6????
3