数据结构与算法上机作业
第四章
图
一、选择题
1、在一个无向图中，所有顶点的度数之和等于所有边数的 C 倍。 A. 1/2 B. 1 C. 2 D. 4
2、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的 B 倍。 A. 1/2 B. 1 C. 2 D. 4
3、G是一个非连通无向图，共有28条边，则该图至少有 C 个顶点。 A. 6 B. 7 C. 8 D. 9
4、有n个顶点的图的邻接矩阵使用 B 数组存储的。 A. 一维 B. n行n列 C. 任意行n列 D. n行任意列 5、对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头数组大小至少为（假设下标为0的数组参与使用） A 。 A. n-1 B. n+1 C. n D. n+e 6、下列说法正确的是 C 。 A. 有向图的邻接矩阵一定是不对称的 B. 有向图的邻接矩阵一定是对称的 C. 无向图的邻接矩阵一定是对称的 D. 无向图的邻接矩阵可以不对称
7、深度优先遍历类似与二叉树的 A ：
A. 先根遍历 B. 中根遍历 C. 后根遍历 D. 层次遍历 8、广度优先遍历类似与二叉树的 D ：
A. 先根遍历 B. 中根遍历 C. 后根遍历 D. 层次遍历 9、下列关于开放树(Free Tree)的说法错误的是 C ： A. 具有n个结点的开放树包含n-1条边 B. 开放树没有回路
C. 开放树可以是非连通图
D. 在开放树中任意加一条边，一定会产生回路
10、在如下图所示的图中，从顶点a出发，按深度优先遍历，则可能得到的一种顶点的序列为 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
11、在如上图所示的图中，从顶点a出发，按广度优先遍历，则可能得到的一种顶点的序列为 A 。 A. a, b, e, c, d, f B. a, b, e, c, f, d C. a, e, b, c, f, d D. 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, v6 B. v1, v3, v6, v2, v5, v4 C. v1, v2, v3, v4, v5, v6 D. v1, v3, v6, v4, v2, v5
18、在上图所示的途中，采用Cruskal算法生成最小生成树，过程中产生的边的次序是 。 A. (v1, v2), (v2, v3), (v5, v6), (v1, v5) B. (v1, v3), (v2, v6), (v2, v5), (v1, v4) C. (v1, v3), (v2, v5), (v3, v6), (v4, v5) D. (v2, v5), (v1, v3), (v5, v6), (v4, v5) 19、如下图所示的图中，其中一个拓扑排序的结果是 。 A. v1→v2→v3→v6→v4→v5→v7→v8 B. v1→v2→v3→v4→v5→v6→v7→v8
C. v1→v6→v4→v5→v2→v3→v7→v8 D. v1→v6→v2→v3→v7→v8→v4→v5
20、在下图所示的AOE网中，活动a9的最早开始时间为 B 。 A. 13 B. 14 C. 15 D. 16
21、在上图所示的AOE网中，活动a4的最迟开始时间为 C A. 2 B. 3 C. 4 D. 5
22、设图有n个顶点和e条边，当用邻接表表示该图时，则求解最短路径的Dijkstra算法的时间复杂度为 。 A. O(n) B. O(n+e) C. O(e) D. O(n2)
二、填空题
1、若无向图G中顶点数为n，则图G至多有 n(n-1)/2 条边；若G为有向图，则图G至多有 n(n-1) 条边。
2、图的存储结构主要有两种，分别是 邻接矩阵 和 邻接表 。
3、若G 是有向图，则把邻接到顶点v 的顶点数目或边数目称为顶点v 的 入度 ；把邻接于顶点v 的顶点数目或边数目称为顶点v 的 度 。 4、已知一个图的邻接矩阵表示，计算第j个顶点的入度的方法是 listofnode Pre(G,j) ，计算第j个顶点的出度的方法是 listofnode Succ(G,j) 。
5、若将图中的每条边都赋予一个权，则称这种带权的图为 带权图 。
6、无论是有向图还是无向图，顶点数n 、边数e 和各顶点的度D(vi)之间的关系为： e= 。
7、 若路径上第一个顶点v1 与最后一个顶点vm 重合, 则称这样的简单路径为 环路 。
8、 如果图中任意一对顶点都是连通的, 则称此图是 连通图 ；非连通图的极大连通子图叫
做 连通分量 。
9、创建一个邻接矩阵图的复杂度是 ；创建一个链接表图的复杂度是 。
10、图的遍历有 深度优先遍历 和广度优先遍历等方法。
11、在深度优先搜索和广度优先搜索中，都采用visited[i]= new 的方式设置第i个顶点为new，而采用visited[i]= old 的方式标识第i个结点为old。 12、由于深度优先算法的特点，深度优先往往采用 的方式实现。
13、由于广度优先算法的特点，在广度优先实现过程中，往往要借助于另一种数据结构 实现。 14、在深度优先搜索和广度优先搜索中，在搜索过程中所经过的边都称为 回退边 。 15、连通而且无环路的无向图称为 开放树 。
16、对于含有n个顶点e条边的连通图，利用Prim算法求其最小生成树的时间复杂度为 O（n2） ，利用Kruscal算法求最小生成树的时间复杂度是 O(n) 。
3、顶点表示活动的网简称为 AOV ；边表示活动的网简称为 AOE 。
17、一个含有n个顶点的无向连通图，其每条边的权重都是a(a>0)，则其最小生成树的权重等于 。
18、具有n个顶点的有向图，如果采用邻接矩阵表示该图，则求某顶点到其他各顶点的最短路径的Dijkstra算法的时间复杂度是 ；如果采用邻接表表示该图，则时间复杂度为 。
19、在用Dijkstra算法求单源最短路径的过程中，将顶点集合V划分为两个集合S和V-S，其中S中的点为 最短路径已经确定的点 ，V-S中的点为 最短路径尚未确定的点 。
20、求每一对顶点之间的最短路径，可以用两种方法，一种是分别对每个顶点采用 算法，另一种方法是 。
21、假设有向图的邻接矩阵C的传递闭包为A，则A[i][j]=1表示 。
22、有向图的中心点是指 具有最小偏心度的点 。
三、已知一个无向图如下图所示，试给出该图的邻接矩阵和邻接表存储示意图（画图，分别用矩阵和数组链表图表示），并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。