第六章 图
一、选择题
1．图中有关路径的定义是（A ）。
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列
C．由不同边所形成的序列 D．上述定义都不是
2．设无向图的顶点个数为n，则该图最多有（B）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2
3．一个n个顶点的连通无向图，其边的个数至少为（ A ）。
A．n-1 B．n C．n+1 D．nlogn；
4．要连通具有n个顶点的有向图，至少需要（ B）条边。
A．n-l B．n C．n+l D．2n
5．n个结点的完全有向图含有边的数目（D ）。
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）
6．一个有n个结点的图，最少有（B）个连通分量，最多有（D ）个连通分量。
A．0 B．1 C．n-1 D．n
7．在一个无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。
A．1/2 B．2 C．1 D．4
8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为(A )。
A．5 B．6 C．8 D．9
9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是(A )。
A．逆拓扑有序 B．拓扑有序 C．无序的
10．下面结构中最适于表示稀疏无向图的是（C ），适于表示稀疏有向图的是（BE ）。
A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表
11．下列哪一种图的邻接矩阵是对称矩阵？（ B ）
A．有向图 B．无向图 C．AOV网 D．AOE网
12．用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m 的路径相连，则只要检查（C ）的第i行第j列的元素是否为零即可。
A．mA B．A C．Am D．Am-1
13. 下列说法不正确的是（ C ）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图
B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程
14．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（D ）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
15．下面哪一方法可以判断出一个有向图是否有环（回路）：AB
A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
16. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( B )。
A. O(n) B. O(n+e) C. O(n2) D. O(n3)
17. 下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ 1C ），下面步骤重复n-1次: a：（A 2 ）；b：（ 3B ）；最后：（ 4A ）。
（1）．A．VT，ET为空 B．VT为所有顶点，ET为空
C．VT为网中任意一点，ET为空 D．VT为空，ET为网中所有边
（2）．A. 选i属于VT，j不属于VT，且（i，j）上的权最小
B．选i属于VT，j不属于VT，且（i，j）上的权最大
C．选i不属于VT，j不属于VT，且（i，j）上的权最小
D．选i不属于VT，j不属于VT，且（i，j）上的权最大
（3）．A．顶点i加入VT，（i,j）加入ET B. 顶点j加入VT，（i,j）加入ET
C. 顶点j加入VT，（i,j）从ET中删去 D．顶点i,j加入VT，（i,j）加入ET
（4）．A．ET 中为最小生成树 B．不在ET中的边构成最小生成树
C．ET中有n-1条边时为生成树，否则无解 D．ET中无回路时，为生成树，否则无解
18．当各边上的权值( A)时，BFS算法可用来解决单源最短路径问题。
A．均相等 B．均互不相等 C．不一定相等
19．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（ A ）。
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7
C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
20．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（ A ）。
A．存在 B．不存在
21．一个有向无环图的拓扑排序序列（ B ）是唯一的。
A．一定 B．不一定
22. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ D）。
A．G中有弧<Vi，Vj> B．G中有一条从Vi到Vj的路径
C．G中没有弧<Vi,Vj> D．G中有一条从Vj到Vi的路径
23. 在用邻接表表示图时，拓扑排序算法时间复杂度为( B )。
A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n)
24. 关键路径是事件结点网络中（A）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路
25. 下面关于求关键路径的说法不正确的是（C ）。
A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上
26．下列关于AOE网的叙述中，不正确的是（ B ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成
C．所有的关键活动提前完成，那么整个工程将会提前完成
D．某些关键活动提前完成，那么整个工程将会提前完成
二、填空题
1.判断一个无向图是一棵树的条件是_n个顶点，n-1条边的无向连通图_____。
2．有向图G的强连通分量是指___极大强连通子图___。
3．一个连通图的___生成树___是一个极小连通子图。
4．具有10个顶点的无向图，边的总数最多为__45____。
5．若用n表示图中顶点数目，则有____n*（n-1）/2___条边的无向图成为完全图。
6. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1<=i<=n〉，则e=_（d1
+d2+……+dn）/2_____
7．G是一个非连通无向图，共有28条边，则该图至少有__9__个顶点。
8. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要___n___条弧。
9．在有n个顶点的有向图中，每个顶点的度最大可达___2*（n-1）___。
10．设G为具有N个顶点的无向连通图，则G中至少有__N-1____条边。
11．n个顶点的连通无向图，其边的条数至少为____n-1__。
12．如果含n个顶点的图形形成一个环，则它有____n__棵生成树。
13．N个顶点的连通图的生成树含有___N-1___条边。
14．构造n个结点的强连通图，至少有___n___条弧。
15．有N个顶点的有向图，至少需要量____N__条弧才能保证是连通的。
16．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的___度___；对于有向图来说等于该顶点的_出度_____。
17. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是_第I列非零元的个数_____。
19. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为__n____，邻接表的边结点个数为___2*e___。
20．构造连通网最小生成树的两个典型算法是_prim和kruskal算法_____。
21．求图的最小生成树有两种算法，_kruskal_____算法适合于求稀疏图的最小生成树。
22. Prim（普里姆）算法适用于求__稠密____的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求___稀疏___的网的最小生成树。
23.有向图G=(V,E),其中V(G)={0,1,2,3,4,5}，用<a,b,d>三元组表示弧<a,b>及弧上的权d.E(G)为{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>}，则从源点0到顶点3的最短路径长度是__50____，经过的中间顶点是__4____。
24. 上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为_125_____。