算法与数据结构第7章 图

第7章图

一、单选题（共20题，56.8分）

1、在一个图中，所有顶点的度数之和等于图的边数的（）倍。

A、1/2

B、1

C、2

D、4

正确答案：C

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

A、1/2

B、1

C、2

D、4

正确答案：B

3、有8个结点的无向图最多有（）条边。

A、14

B、28

C、56

D、112

正确答案：B

4、有8个结点的无向连通图最少有（）条边。

A、5

B、6

C、7

D、8

正确答案：C

5、有8个结点的有向完全图有（）条边。

A、14

B、28

C、56

D、112

正确答案：C

6、用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算

法的。

A、栈

B、队列

C、树

D、图

正确答案：B

7、用邻接表表示图进行深度优先遍历时，通常是采用（）来实现算法的。

A、栈

B、队列

C、树

D、图

正确答案：A

8、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是

（）o

A、0243156

B、0136542

C、0423165

D、0361542

正确答案：C

9、已知图的邻接矩阵同上题8,根据算法，则从顶点0出发，按广度

优先遍历的结点序列是（）。

A、0243651

B、0136425

C、0423156

D、0134256

正确答案：B

10、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是

（）。

A、0132

B、0231

C、0321

D、0123

正确答案：D

11、深度优先遍历类似于二叉树的（）。

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

正确答案：A

12、广度优先遍历类似于二叉树的（）。

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

正确答案：D

13、任何一个无向连通图的最小生成树（）。

A、只有一棵

B、一棵或多棵

C、一定有多棵

D、0棵

可能不存在

正确答案：A

14、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s,则所有顶点的度

数之和为（）.

A、s

B、s-1

C、s+1

D、2s

正确答案：D

15、在一个无向图中，若两顶点之间的路径长度为k,则该路径上的顶点数为（）o

A、k

B、k+1

C、k+2

D、2k

正确答案：B

16、对于一个有向图，若一个顶点的度为kl,出度为k2,则对应邻接表中该顶点单链

表中的边结点数为()o

A、kl

B、k2

C、kl-k2

D、kl+k2

正确答案：B

17、若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该图进行

深度优先搜索，得到的顶点序列可能为()。

A、A,B,C,F,D,E

B、A,C,F,D,E,B

C、A,B,D,C,F,E

D、A,B,D,F,E,C

正确答案：B

解析：

18、若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该图进行

广度优先搜索，得到的顶点序列可能为()。

A、A,B,C,D,E,F

B、A,B,C,F,D,E

C、A,B,D,C,E,F

D、A,C,B,F,D,E

正确答案：D

19、若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},贝U从顶点1开始对该图进

行深度优先搜索，得到的顶点序列可能为().

A、1,2,5,4,3

B、1,2,3,4,5

C、1,2,5,3,4

D、1,4,3,2,5

正确答案：A

20、已知一个有向图的边集为{va,b>,va,c>,va,d>,vb,d>,vb,e>,vd,e>},则由该图产生的一

种可能的拓扑序列为（）。

A、a,b,c,d,e

B^a,b,d,e,b

C、a,c,b,e,d

D>a,c,d,b,e

正确答案：A

二、填空题（共14题，37.8分）

1、图有、等存储结构，遍历图

有、等方法。

正确答案：

第1空：

邻接矩阵

第2空：

邻接表

第3空：

深度优先遍历

第4空：

广度优先遍历

2、有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的

正确答案：

第1空：

出度

3、设有一稀疏图G,则G采用存储较省空间。

正确答案：

第1空：

邻接表

4、设有一稠密图G,则G采用存储较省空间。

正确答案：

第1空：

邻接矩阵

5、图的逆邻接表存储结构只适用于图。

正确答案：

第1空：

有向

6、图的深度优先遍历序列__________________唯一的。

正确答案：

第1空：

不是

7、若要求一个稀疏图G的最小生成树，最好用算法来求解。

正确答案:

第1空：

克鲁斯卡尔(Kruskal)

8、若要求一个稠密图G的最小生成树，最好用算法来求解。

正确答案：

第1空：

普里姆(Prim)

9、拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。

正确答案：

第1空：

0

10、假定一个有向图的顶点集为集,b,c,d,e,f},边集为{<a,c>,

<a,e>,<c,f>,<d,c>,<e,b>,<e,d>},则出度为0的顶点个数为_

,入度为1的顶点个数为。

正确答案：

第1空：

2

第2空：

4

11、图中的一条路径长度为k,该路径所含的顶点数为。

正确答案:

第1空：

k+1

12^一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)},从顶点a出

发进行深度优先搜索遍历得到的顶点序列为，从顶点a

出发进行广度优先搜索遍历得到的顶点序列为o

正确答案:

第1空：

acdeb

第2空:

acedb

13、若一个连通图中每个边上的权值均不同，则得到的最小生成树是(唯一/不唯

一)的。

正确答案：

第1空：

唯一

14、假定一个有向图的边集为

{〈a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>},对该图进行拓扑排序得到

的顶点序列为o

正确答案:

第1空：

aebdcf

三、简答题(共2题，5.4分)

1、