第七章 图

第七章 图

一．选择题

1．任何一个无向连通图的最小生成树________。 A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在

2．下列算法中，________算法用来求图中每对顶点之间的最短路径。 A．Dijkstra B．Floyed C．Prim D．Kruskal 3．由N个顶点组成的有向图，最多可以有________条边。 A．N*N B．N（N+1） C．N（N-1） D．N(N-1)/2 4．关键路径是结点网络中________。 A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路

5．在一个图中，所有顶点的度数之和等于所有边数的________倍。 A．2 B．3 C．1 D．1.5 6. 下面关于图的存储的叙述中正确的是________ 。

A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关

B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关

7. AOV 网是一种________。

A．有向图 B．无向图 C．无向无环图 D．有向无环图 8. 在一个具有n个顶点的无向完全图中，包含有 n(n-1)/2 条边，在一个具有 n 个顶点的有向完全图中，包含有 ________ 条边。

A．n+2 B．n(n-1) C．n2 D．2n

9. 设完全无向图中有n个顶点，则该完全无向图中有________条边。 A．n(n-1)/2 B．n(n-1) C．n(n+1)/2 D．(n-1)/2

10.设有向无环图 G 中的有向边集合 E={<1，2> ，<2，3>，<3，4> ，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是________。 A．1，2，3，4 B．2，3，4，1 C．1，4，2，3 D．1，2，4，3

11.设某无向图有n个顶点，则该无向图的邻接表中有________个表头结点。 A．2n B．n C．n/2 D．n(n-1)

12.设无向图G 中有n个顶点，则该无向图的最小生成树上有________条边。 A．n B．n-1 C．2n D．2n-1

13.设无向图G 中的边的集合E={(a ，b) ，(a，e)，(a，c)，(b，e)，(e，d) ，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为________。

A．aedfcb B．acfebd C．aebcfd D．aedfbc

14.有n个顶点 e 条边的无向图 G,它的邻接表中的表结点总数是________。 A．2n B．n C．2e D．e

15.连通图 G 中有n 个顶点,G 的生成树是________连通子图。 A．包含 G 的所有顶点 B．包含 G 的所有边

C．不必包含 G 的所有顶点

D．必须包含 G 的所有顶点和所有的边

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

B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C．一个事件的最迟开始时间同以该事件为尾的弧的活动最迟开始时间相同与该活动的持续时间的和

D．关键活动一定在关键路径上

17．设某强连通图中有n 个顶点，则该强连通图中至少有________条边。 A．n(n-1) B．n+1 C．n D．n(n+1)

18．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为________。

A．n B．e C．2n D．2e 19. 设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有________条有向边。

A．n B．n-1 C．m D．m-1

20．设用邻接矩阵A表示有向图G的存储结构，则有向图 G中顶点i 的入度为________。

A．第i行非0元素的个数之和 B．第i列非0 元素的个数之和 C．第i行0元素的个数之和 D．第i列0元素的个数之和

21．设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为________。

A．O(n+e) B．O(n2) C．O(ne) D．O(n)

22．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的________。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历 23. 可以判断一个有向图中是否含有环（回路）的方法为________。 A．广度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 24. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的________。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历 25. 一个具有8个顶点的有向图中，所有顶点的入度之和与所有顶点的出度之和的差为________。

A．16 B．8 C．0 D．2 26．在有向图中每个顶点的度等于该顶点的________。 A. 入度 B. 出度

C. 入度与出度之和 D. 入度与出度之差

二．填空题

1.在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的________，对于有向图来说等于该顶点的________。 2.已知一个无向图的邻接矩阵如下所示，则从顶点A出发按深度优先搜索遍历得到的顶点序列为________，按广度优先搜索遍历得到的顶点序列为________。

A B C D E F ┏0 1 1 0 1 0┓A ┃1 0 0 0 1 1┃B ┃1 0 0 1 0 0┃C ┃0 0 1 0 0 1┃D ┃1 1 0 0 0 1┃E ┗0 1 0 1 1 0┛F

3.有n个顶点的有向连通图最多有________条边，最少有________条边。

4.具有n个顶点的完全无向图有________条边，完全有向图有________条边。 5. 设无向图G 中有n 个顶点e 条边，所有顶点的度数之和为m，则e 和m 有______关系。

6. 设一个连通图G 中有n 个顶点e 条边，则其最小生成树上有________条边。 7. 表示图的五种常用的存储结构为_______________________________。 8. 在有12 个结点的无向图中，其边数最多为________条。

9. 设无向图G 中有n 个顶点和e 条边，则其对应的邻接表中有_________个表头结点和_________个边结点。

10. n 个顶点的连通图至少____条边。

11. 在无权图G 的邻接矩阵A 中，若(vi,vj)或＜vi,vj＞属于图G 的边集合，则对应元素A[i][j]等于____，否则等于____。

12. 在无向图G 的邻接矩阵A 中，若A[i][j]等于1，则A[j][i]等于____。 13. 已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。 14. 在一个具有10 个顶点的无向完全图中，包含有________条边，在一个具有n 个顶点的有向完全图中，包含有________条边。

15. 设无向图G 中有n 个顶点，则该无向图中每个顶点的度数最多是_________。

16. 对于一个具有n 个顶点和e 条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。

17. 设某无向图G 中有n 个顶点，用邻接矩阵A 作为该图的存储结构，则顶点i 和顶点j互为邻接点的条件是______________________。 18. 设无向图对应的邻接矩阵为A，则A 中第i 行上非0 元素的个数_________第i 列上非0元素的个数（填等于，大于或小于）。

19. 设有向图G 用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i 行上所有元素之和等于顶点i 的________，第i 列上所有元素之和等于顶点i 的________。

20. 在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。

21. 设无向图G 中有n 个顶点e 条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_________；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。 22. 设某无向图G 的邻接表为V1->3->2->4; V2->1->3; V3->1->2->4; V4->1->3;

则从顶点V1 开始的深度优先遍历序列为___________；广度优先遍历序列为

____________。

23. 设有向图G 的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。

24. AOV 网以结点和有向边分别代表 ____________ 25. AOV 网是一种___________________的图。

三、判断题

1. 如果某个有向图的邻接表中第i 条单链表为空，则第i 个顶点的出度为零。（ ）

2. 有向图的邻接表和逆邻接表中表结点的个数不一定相等。（ ）

3. 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。（ ）

4. 邻接矩阵表示图所用的存储空间大小与图的边数成正比。（ ）

5. 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。（ ）

6. n 个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。（ ） 7. 调用一次深度优先遍历可以访问到图中的所有顶点。（ ） 8．带权无向图的最小生成树是唯一的。（ ）

9. 图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（ ）

10. 对连通图进行深度优先遍历可以访问到该图中的所有顶点。（ ）

11. 在AOV-网中，不应该出现有向环，因为存在环就意味着活动可以以自己为先决条件。（ ）

四．简答题 1． 对于一个有向图，不用拓扑排序，如何判定图中是否存在环？ 2． 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边数是否相关？

3. 无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树。

4.设有无向图G（如右图所示），要求给出用普里姆算法构造最小生成树所走过的边的集合。