发布时间 : 星期日 文章第7章图习题及答案更新完毕开始阅读986578b6cbaedd3383c4bb4cf7ec4afe05a1b1e9
第7章 图 一、选择题
1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）
A） O(n) B） O(n+e) C） O(n*n) D） O(n*n*n) 【答案】B
2．设无向图的顶点个数为n，则该图最多有（ ）条边。 A）n-1 【答案】B
3．连通分量指的是（ ） A） 无向图中的极小连通子图 B） 无向图中的极大连通子图 C） 有向图中的极小连通子图 D） 有向图中的极大连通子图 【答案】B
4．n个结点的完全有向图含有边的数目（ ） A）n*n B）n（n+1） 【答案】D
5．关键路径是（ ）
A） AOE网中从源点到汇点的最长路径 B） AOE网中从源点到汇点的最短路径 C） AOV网中从源点到汇点的最长路径 D） AOV网中从源点到汇点的最短路径 【答案】A
6．有向图中一个顶点的度是该顶点的（ ）
A）入度 B） 出度 C） 入度与出度之和 D） （入度+出度）/2 【答案】C
7．有e条边的无向图，若用邻接表存储，表中有（ ）边结点。 A） e B） 2e C） e-1 D） 2(e-1)
C）n/2
D）n*（n-1）
B）n(n-1)/2
C） n(n+1)/2
D）n2
【答案】B
8．实现图的广度优先搜索算法需使用的辅助数据结构为（ ） A） 栈 B） 队列 C） 二叉树 D） 树 【答案】B
9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（ ） A） 栈 B） 队列 C） 二叉树 D） 树 【答案】A
10．存储无向图的邻接矩阵一定是一个（ ）
A） 上三角矩阵 B）稀疏矩阵 C） 对称矩阵 D） 对角矩阵 【答案】C
11．在一个有向图中所有顶点的入度之和等于出度之和的（ ）倍 A） 1/2 【答案】B
12．在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（ ） A） O(n) B） O(n+e) C） O(n2) D） O(n3) 【答案】B
13．下列关于AOE网的叙述中，不正确的是（ ） A）关键活动不按期完成就会影响整个工程的完成时间 B）任何一个关键活动提前完成，那么整个工程将会提前完成 C）所有的关键活动提前完成，那么整个工程将会提前完成 D）某些关键活动提前完成，那么整个工程将会提前完成 【答案】B
14．具有10个顶点的无向图至少有多少条边才能保证连通（ ） A） 9 B）10 【答案】A
15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ ） A） e B）2e 【答案】D
16.对于一个具有n个顶点和e条边的无向图，如果采用邻接表来表示，则其表
C） n2-e D）n2-2e C） 11
D） 12
B）1 C） 2 D） 4
头向量的大小为 。
A、n B、n+1 C、n-1 D、n+e 【答案】 A 二、填空题
1．无向图中所有顶点的度数之和等于所有边数的_____________倍。 【答案】2
2．具有n个顶点的无向完全图中包含有_____________条边，具有n个顶点的有向完全图中包含有_____________条边。 【答案】（1）n(n-1)/2 （2） n(n-1)
3．一个具有n个顶点的无向图中，要连通所有顶点则至少需要_____________条边。 【答案】n-1
5．对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为_____________，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_____________。 【答案】（1）O(n2) （2） O(n+e)
6．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_____________和_____________条。 【答案】（1）e （2）2e
7． 在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有_____________和_____________结点。 【答案】（1）出边 （2） 入边
8． 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的时间复杂度依次为_____________和_____________。 【答案】（1）O(n) （2）O(e)
9．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为_____________和_____________。 【答案】（1）n （2） n-1
10．Prim算法和Kruscal算法的时间复杂度分别为_____________和_____________。
【答案】（1）O(n2) （2）O(eloge)
11. 假设图G中含有n个顶点，e条边，且知每个顶点的度数为di，则它们三者之间满足的关系为： 。 【答案】 e=1/2∑di
12.我们把图中所有顶点加上遍历时经过的所有边构成的子图称为 。
【答案】 生成树
13、有n个顶点的无向图，其边数最大可达 ，像这样的有最大边数的无向图通常被称为 。
【答案】 n(n-1)/2 完全无向图
14、树被定义为连通而不具有 的（无向）图。
【答案】 回路
15、对于一个图G的遍历，通常有两种方法，它们分别是 和 。
【答案】 深度优先法 广度优先法
16. AOV网中，结点表示活动 ， 边表示活动的先后顺序 ， AOE网中，结点表示事件 ， 边表示活动 .
7-16 试对右图所示的AOE网络，解答下列问题。 (1) 这个工程最早可能在什么时间结束。
(2) 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[I]。
(3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。 (4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。 【解答】
按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。
1 Ve 0 2 19 3 15 4 29 5 38 6 43 Vl 0 <1, 2> 0 17 17 19 <1, 3> 0 0 0 15 <3, 2> 15 15 0 37 <2, 4> 19 27 8 38 <2, 5> 19 19 0 43 <3, 5> 15 27 12 <4, 6> 29 37 8 <5, 6> 38 38 0
e l l-e
此工程最早完成时间为43。关键路径为<1, 3><3, 2><2, 5><5, 6>