第5课 图

第五课 图

一、选择题

1．图中有关路径的定义是（ ）。

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 参考答案：A

2．设无向图的顶点个数为n，则该图最多有（ ）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 参考答案：B

3．一个n个顶点的连通无向图，其边的个数至少为（ ）。

A．n-1 B．n C．n+1 D．nlogn 参考答案：A

4．要连通具有n个顶点的有向图，至少需要（ ）条边。

A．n-l B．n C．n+l D．2n 参考答案：B

5．n个结点的完全有向图含有边的数目（ ）。

A．n*n Ｂ．n（n+1） C．n／2 D．n*（n-1） 参考答案：D

6．一个有n个结点的图，最少有（ ）个连通分量。

A．0 B．1 C．n-1 D．n 参考答案：B

7．一个有n个结点的图，最多有（ ）个连通分量。

A．0 B．1 C．n-1 D．n 参考答案：D

8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为（ ）。

A．5 B．6 C．8 D．9 参考答案：A 9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（A．逆拓扑有序 B．拓扑有序 C．无序的 参考答案：A

10．下面结构中最适于表示稀疏无向图的是（ ）。

A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表 参考答案：C

11．下列哪一种图的邻接矩阵是对称矩阵？（ ）

A．有向图 B．无向图 C．AOV网 D．AOE网

。 ）

参考答案：B

12．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。

A．

?A[i,j]i?1n B．

?A?i,j?j?1n C．

?A[j,i]i?1n D．

?A[i,j]?A?j,i?i?1nn+

j?1

参考答案：B

13．下列说法不正确的是（ ）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 参考答案：C

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)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。

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 参考答案：D

15．设图如右所示， ，在下面的5个序列中，符合深度优先遍历的序列有（ ）个。

a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c

A．5个 B．4个 C．3个 D．2个 参考答案：D

16．下列方法中可以判断出一个有向图是否有环（回路）的是（ ）。

A．广度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 参考答案：B

17．在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（ ）。

A．O(n) B．O(n+e) C．O(n2) D．O(n3) 参考答案：B

18．当各边上的权值（ ）时，BFS算法可用来解决单源最短路径问题。

A．均相等 B．均互不相等 C．不一定相等 参考答案：A

19．求解最短路径的Floyd算法的时间复杂度为（ ）。

A．O（n） B．O（n+c） C．O（n*n） D．O（n*n*n） 参考答案：D

20．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,, ,,,,}，G的拓扑序列是（ ）。

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

参考答案：A

21．若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列（ ）。

A．存在 B．不存在 参考答案：A

22．一个有向无环图的拓扑排序序列（ ）是唯一的。

A．一定 B．不一定 参考答案：A

23．在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。

A．O(n) B．O(n+e) C．O(n*n) D．O(n*n*n) 参考答案：B

24．关键路径是事件结点网络中（ ）。

A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 参考答案：A

25．下面关于求关键路径的说法不正确的是（ ）。 A．求关键路径是以拓扑排序为基础的

B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差

D．关键活动一定位于关键路径上 参考答案：C

26．下列关于AOE网的叙述中，不正确的是（ ）。

A．关键活动不按期完成就会影响整个工程的完成时间

B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 参考答案：B

27．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍。

A．1/2 B．2 C．1 D．4 参考答案：B

28．在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。

A．1/2 B．2 C．1 D．4 参考答案：C

二、应用题 1．

（1）如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？ 参考答案：G1最多n(n-1)/2条边，最少n-1条边。

（2）如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？ 参考答案：G2最多n(n-1)条边，最少n条边。

2．n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？ 参考答案：n-1，n

3．证明：具有n个顶点和多于n-1条边的无向连通图G一定不是树。 参考答案：

具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。

4．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？ 参考答案：

设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n2，即顶点个数的平方，与图的边数无关。

5．请回答下列关于图(Graph)的一些问题：

（1）有n个顶点的有向强连通图最多有多少条边?最少有多少条边?

（2）表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？ （3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？ 参考答案： （1）n(n-1)，n

（2）106，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律）

（3）使用深度优先遍历，按退出DFS过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行DFS (v)未退出前，出现顶点u到v的回边，则说明存在包含顶点v和顶点u的环。

6．设有数据逻辑结构为：B = (K, R), K = {k1, k2, ?, k9}

R={, , ,, , ,, , , , }

（1）画出这个逻辑结构的图示。

（2）相对于关系r，指出所有的开始接点和终端结点。

（3）分别对关系r中的开始结点，举出一个拓扑序列的例子。 （4）分别画出该逻辑结构的正向邻接表和逆向邻接表。 参考答案： （1）略。

（2）开始结点：（入度为0）K1，K2，终端结点（出度为0）K6，K7。 （3）拓扑序列K1，K2，K3，K4，K5，K6，K8，K9，K7

K2，K1，K3，K4，K5，K6，K8，K9，K7

规则：开始结点为K1或K2，之后，若遇多个入度为0的顶点，按顶点编号顺序选择。 （4）略。

7．有向图的邻接表存储如下，要求：（1）画出其邻接矩阵存储；（2）写出图的所有强连通分量；（3）写