选择题
1. 图中有关路径的定义是（ ）
A
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列
C．由不同边所形成的序列 D．上述定义都不是
2. 设无向图的顶点个数为 n，则该图最多有（ ）条边。
B
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．n^2
3. 一个 n 个顶点的连通无向图，其边的个数至少为（ ）
A
A．n-1 B．n C．n+1 D．nlogn
4. n 个结点的完全有向图含有边的数目（ ）
D
A．n*n B．n（n＋１） C．n／2 D．n*（n－l）
5. 在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍
B
A．1/2 B．2 C．1 D．4
6. 在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍
C
A．1/2 B．2 C．1 D．4
7. 下列哪一种图的邻接矩阵是对称矩阵？（ ）
B
A．有向图 B．无向图 C．AOV网 D．AOE网
8. 下列说法不正确的是（ ）
C
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图
B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程
9. 无向图 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
10. 下面哪一方法可以判断出一个有向图是否有环（回路）:( )
A
A．深度优先遍历 B. 求是否有孤立点 C. 求最短路径 D. 求关键路径
11. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )
B
A. O(n) B. O(n+e) C. O(n^2 ) D. O(n^3 )
12. 在图采用邻接矩阵存储时，求最小生成树的 Prim 算法的时间复杂度为( )
C
A. O(n) B. O(n+e) C. O(n^2 ) D. O(n^3 )
13. 已知有向图 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
14. 在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是（ ）
D
A．G 中有弧
C．G 中没有弧
15. 关键路径是事件结点网络中（ ）
A
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路
16. 下面关于求关键路径的说法不正确的是（ ）
C
A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上
17. 下列关于 AOE 网的叙述中，不正确的是（ ）
B
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成
C．所有的关键活动提前完成，那么整个工程将会提前完成
D．某些关键活动提前完成，那么整个工程将会提前完成
18. 具有6个顶点的无向图，当有（ ）条边时能确认是一个连通图
D
A.8 B.9 C.10 D.11
19. 任何一个无向连通图的最小生成树（ ）
A
A.有一棵或多棵 B.只有一棵
C.一定有多棵 D.可能不存在
20. 能有效缩短关键路径长度的方法是（ ）
D
A.缩短任意一个活动的持续时间
B.缩短关键路径上任意一个关键活动的持续时间
C.缩短多条关键路径上共有的任意一个关键活动的持续时间
D.缩短所有关键路径上共有的任意一个关键活动的持续时间