第四章 - 图

数据结构与算法上机作业

第四章

图

一、选择题

1、在一个无向图中，所有顶点的度数之和等于所有边数的c倍。a.1/2b.1c.2d.4

2、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的b倍。a.1/2b.1c.2d.4

3、g是一个非连通无向图，共有28条边，则该图至少有c个顶点。a.6b.7c.8d.9

4、有n个顶点的图的邻接矩阵使用b数组存储的。a.一维b.n行n列c.任意行n列d.n行任意列5、对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头数组大小至少为（假设下标为0的数组参与使用）a。a.n-1b.n+1c.nd.n+e6、下列说法正确的是c。a.有向图的邻接矩阵一定是不对称的b.有向图的邻接矩阵一定是对称的c.无向图的邻接矩阵一定是对称的d.无向图的邻接矩阵可以不对称

7、深度优先遍历类似与二叉树的a：

a.先根遍历b.中根遍历c.后根遍历d.层次遍历8、广度优先遍历类似与二叉树的d：

a.先根遍历b.中根遍历c.后根遍历d.层次遍历9、下列关于开放树（freetree）的说法错误的是c：a.具有n个结点的开放树包含n-1条边b.开放树没有回路

c.开放树可以是非连通图

d.在开放树中任意加一条边，一定会产生回路

10、在如下图所示的图中，从顶点a出发，按深度优先遍历，则可能得到的一种顶点的序列为d。

a.a，b，e，c，d，fb.a，c，f，e，b，dc.a，e，b，c，f，dd.a，e，d，f，c，b

11、在如上图所示的图中，从顶点a出发，按广度优先遍历，则可能得到的一种顶点的序列为a。a.a，b，e，c，d，fb.a，b，e，c，f，dc.a，e，b，c，f，dd.a，e，d，f，c，b

12、设网（带权的图）有n个顶点和e条边，则采用邻接表存储时，求最小生成树的prim算法的时间复杂度为c。

a.o（n）b.o（n+e）c.o（n2）d.o（n3）

13、设图有n个顶点和e条边，求解最短路径的floyd算法的时间复杂度为b。a.o（n）b.o（n+e）c.o（n2）d.o（n3）14、最小生成树是指c。a.由连通网所得到的边数最少的生成树。b.由连通网所得到的顶点数相对较少的生成树。c.连通网中所有生成树中权值之和为最小的生成树。d.连通网的极小连通子图。

15、下面关于工程计划的aoe网的叙述中，不正确的是b。a.关键活动不按期完成就会影响整个工程的完成时间。b.任何一个关键活动提前完成，那么整个工程将会提前完成。c.所有关键活动都提前完成，那么整个工程将会提前完成。d.某些关键工程若提前完成，那么整个工程将会提前完成。

16、在aoe网中，始点和汇点的个数为d。

a.1个始点，若干个汇点b.若干个始点，若干个汇点c.若干个始点，1个汇点c.1个始点，1个汇点

17、在下图所示的无向图中，从顶点v1开始采用prim算法生成最小生成树，算法过程中产生的顶点次序为a。a.v1，v3，v4，v2，v5，v6b.v1，v3，v6，v2，v5，v4c.v1，v2，v3，v4，v5，v6d.v1，v3，v6，v4，v2，v5