内容发布更新时间 : 2024/5/22 7:40:17星期一 下面是文章的全部内容请认真阅读。
第七章 图习题
1 单项选择题
1、图中有关路径的定义是（ ）。
A、由顶点和相邻顶点序偶构成的边所形成的序列 B、由不同顶点所形成的序列 C、由不同边所形成的序列 D、上述定义都不对
2、设无向图的顶点个数为n，则该图最多有（ ）条边。 A、n – 1
B、n (n – 1)/2
C、n (n+1)/2
D、n2
3、一个n个顶点的连通无向图，其边的个数至少为（ ）。 A、n – 1
B、n
C、n+1
D、nlogn
4、下面结构中最适于表示稀疏无向图的是（ ）。 A、邻接矩阵
B、逆邻接表
C、邻接多重表
D、十字链表
5、下列哪一种图的邻接矩阵是对称矩阵？（ ） A、有向图
B、无向图
C、AOV网
D、AOE网
6、当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。 A、第j列所有元素之和 C、不确定
B、第i行所有元素之和
D、第j列所有元素之和+第i行所有元素之和
7、下面哪一方法可以判断出一个有向图是否有环（回路）（ ）。 A、深度优先遍历 C、求最短路径
B、拓扑排序 D、求关键路径
8、在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。 A、O(n)
B、O(n+e)
C、O(n2)
D、O(n3)
9、求解最短路径的Floyd算法的时间复杂度为( )。 A、O(n)
B、O(n+e)
C、O(n2)
D、O(n3)
10、已知有向图G=(V, E)，其中V={v1, v2, v3, v4, v5, v6, v7}，E={
A、v1,v3,v4,v6,v2,v5,v7
B、v1,v3,v2,v6,v4,v5,v7
C、v1,v,v4,v5,v2,v6,v7
D、v1,v2,v5,v3,v4,v6,v7
11、在用邻接表表示图时，拓扑排序算法时间复杂度为( )。
A、O(n)
B、O(n+e)
C、O(n2)
D、O(n3)
12、关键路径是事件结点网络中（ ）。
A、从源点到汇点的最长路径 C、最长路径
B、从源点到汇点的最短路径 D、最短路径
13、下面关于求关键路径的说法不正确的是（ ）。
A、求关键路径是以拓扑排序为基础的
B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D、关键活动一定位于关键路径上
14、下列关于AOE网的叙述中，不正确的是（ ）。
A、关键活动不按期完成就会影响整个工程的完成时间 B、任何一个关键活动提前完成，那么整个工程将会提前完成 C、所有的关键活动提前完成，那么整个工程将会提前完成 D、某些关键活动提前完成，那么整个工程将会提前完成 15、采用邻接表存储图的深度优先遍历算法类似于二叉树的（
A、层序遍历
B、先序遍历
C、中序遍历
）。
D、后序遍历 ）倍。 D、1/2
）。
16、图G中，所有顶点的度数之和等于所有边数的（
A、1
B、2
C、3
17、一个具有n个顶点的无向图若采用邻接矩阵存储，则该矩阵的大小是（
A、n – 1
B、n+1
C、(n – 1)2
D、n2
18、要连通n个顶点的有向图，至少需要（
A、n – 1
B、n
）条边。
D、nlogn
C、n+1
?01o???19、从图的邻接矩阵A??101?中可以看出，该图有（ ① ）个顶点，如果是有向图，
?010???该图有（ ② ）条弧，如果是无向图，则有（ ③ ）条边。 ① A、9
B、3
C、6
D、1
② A、5 ③ A、5
B、4 B、4
C、3 C、3
D、2 D、2
20、设图V={a, b, c, d, e, f}，E={(a,b), (a, e),(a, c),(b, e),(c, f), (f, d),(e, d)}，对该图进行深度优先遍历，得到的顶点序列是（ ）。
A、abecdf
B、acfebd
C、aebcfd
D、aedfcb
21、在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下面情况不可能出现的是（ ）。
A、G中有弧
B、G中有一条从vi到vj的路径 D、G中有一条从vj到vi的路径
C、G中没有弧
2 填空题
1、如果含n个顶点的图形成一个环，则它有（ 2、下图所示的强连通分量有（
）个。
）棵生成树。
3、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有（ 4、求图的最小生成树有两种算法，其中（ 5、有向图G可以拓扑排序的判别条件是（ 6、在AOV网中，存在环意味着（ 表明存在（ ）。
）个非零元素。
）算法适合求解稀疏图的最小生成树。
）。
）；对程序的数据流图来说，它
7、已知一个图的广度优先生成树如下图所示，则与此相应的广度优先遍历序列为（ ）。
a b c d e f g
）。
8、在有n个顶点的有向图中，每个顶点的度最大可达（