第六次作业
一、选择题
1、深度优先遍历类似与二叉树的 A ：
A. 先根遍历 A. 先根遍历
B. 中根遍历 B. 中根遍历
C. 后根遍历 C. 后根遍历
D. 层次遍历 D. 层次遍历
2、广度优先遍历类似与二叉树的 D ：
3、下列关于开放树(Free Tree)的说法错误的是 C ： A. 具有n个结点的开放树包含n-1条边 B. 开放树没有回路 C. 开放树可以是非连通图
D. 在开放树中任意加一条边，一定会产生回路 4、关于最小生成树，下列说法错误的是 C ： A. 最小生成树是一棵开放树
B. 最小生成树各边的和是所有生成树中最小的 C. 任何图都只有一个最小生成树
D. 能够产生最小生成树的图，其边一定有权值 5、任何一个无向连通图的最小生成树 B ： A. 只有1棵
B. 1棵或多棵
C. 一定有多棵
D. 可能不存在
6、在如下图所示的图中，从顶点a出发，按深度优先遍历，则可能得到的一种顶点的序列为 C和D 。 A. a, b, e, c, d, f C. a, e, b, c, f, d
B. a, c, f, e, b, d D. a, e, d, f, c, b
7、在如上图所示的图中，从顶点a出发，按广度优先遍历，则可能得到的一种顶点的序列为 A 。
A. a, b, e, c, d, f C. a, e, b, c, f, d
B. a, b, e, c, f, d D. a, e, d, f, c, b
8、设网(带权的图)有n个顶点和e条边，则采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为 C 。
A. O(n) A. O(n)
B. O(n+e) B. O(n+e)
C. O(n2) C. O(n2)
D. O(n3) D. O(n3)
9、设图有n个顶点和e条边，求解最短路径的Floyd算法的时间复杂度为 D 。
10、最小生成树是指 C 。
A. 由连通网所得到的边数最少的生成树。 B. 由连通网所得到的顶点数相对较少的生成树。 C. 连通网中所有生成树中权值之和为最小的生成树。 D. 连通网的极小连通子图。
A. 关键活动不按期完成就会影响整个工程的完成时间。 B. 任何一个关键活动提前完成，那么整个工程将会提前完成。 C. 所有关键活动都提前完成，那么整个工程将会提前完成。 D. 某些关键工程若提前完成，那么整个工程将会提前完成。 A. 1个始点，若干个汇点 C. 若干个始点，1个汇点 产生的顶点次序为 B 。
A. v1, v3, v4, v2, v5, v6 C. v1, v2, v3, v4, v5, v6
B. v1, v3, v6, v2, v5, v4 D. v1, v3, v6, v4, v2, v5 B. 若干个始点，若干个汇点 D. 1个始点，1个汇点
11、下面关于工程计划的AOE网的叙述中，不正确的是 B 。
12、在AOE网中，始点和汇点的个数为 D 。
13、在下图所示的无向图中，从顶点v1开始采用Prim算法生成最小生成树，算法过程中
14、在上图所示的途中，采用Cruskal算法生成最小生成树，过程中产生的边的次序是 C 。
A. (v1, v2), (v2, v3), (v5, v6), (v1, v5) C. (v1, v3), (v2, v5), (v3, v6), (v4, v5) 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
B. (v1, v3), (v2, v6), (v2, v5), (v1, v4) D. (v2, v5), (v1, v3), (v5, v6), (v4, v5)
15、如下图所示的图中，其中一个拓扑排序的结果是 A 。
16、在下图所示的AOE网中，活动a9的最早开始时间为 B 。
A. 13
B. 14
C. 15
D. 16
17、在上图所示的AOE网中，活动a4的最迟开始时间为 D
二、填空题
1、图的遍历有 深度优先遍历 和广度优先遍历等方法。
2、在深度优先搜索和广度优先搜索中，都采用visited[i]= false 的方式设置第i个顶点为new，而采用visited[i]= true 的方式标识第i个结点为old。
3、由于深度优先算法的特点，深度优先往往采用 递归 的方式实现。
4、由于广度优先算法的特点，在广度优先实现过程中，往往要借助于另一种数据结构 队列 实现。
5、在深度优先搜索和广度优先搜索中，在搜索过程中所经过的边都称为 树边 。 6、连通而且无环路的无向图称为 开放树 。
7、对于含有n个顶点e条边的连通图，利用Prim算法求其最小生成树的时间复杂度为 O(n2) ，利用Kruscal算法求最小生成树的时间复杂度是 O(n) 。 8、顶点表示活动的网简称为 AOV ；边表示活动的网简称为 AOE 。 9、一个含有n个顶点的无向连通图，其每条边的权重都是a(a>0)，则其最小生成树的权重等于 (n-1)*a 。
三、已知一个连通图如下图所示，分别给出一个按深度优先遍历和广度优先遍历的顶点序列（假设从顶点v1出发）。并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写相关基本操作，并在主函数中求出深度优先序列和广度优先序列。
A. 4
B. 5
C. 6
D. 7
v1 v2 v3 v4 v5 v6 v1 0 1 0 1 0 1 v2 1 0 1 1 1 0 v3 0 1 0 0 1 0 v4 1 1 0 0 1 1 v5 0 1 1 1 0 0 v6 1 0 0 1 0 0
HEAD v1 v2 v3 v4 v5 v6
v2 v1 v2 v1 v2 v1 v4 v3 v5 ^ v2 v3 v4 ^ v6 ^ v4 v5 v4 ^ v5 ^ v6 ^
深度优先：v1 v2 v3 v5 v4 v6 广度优先：v1 v2 v4 v6 v3 v5
#include
VertexNode vexlist[NumVertices+1]; int n, e;
} AdjGraph; // 邻接表表示
BOOLEAN visited[NumVertices]; int dfn[NumVertices];//深度优先 void DFSTraverse(AdjGraph G) {
int i , count = 1;
for ( i = 0; i < G.n; i++ ) visited [i] =FALSE; for ( i = 0; i < G.n; i++ ) if ( ! visited[i] ) DFS1( &G, i+1 ); }
void DFS1 (AdjGraph* G, int i) {
static int count=0; EdgeNode *p;
cout<
p=G->vexlist[i].firstedge; while( 1 )
{
if( !visited[p->adjvex] ) DFS1(G, p->adjvex); p=p->next; } }
int bfn[NumVertices];//广度优先 void BFS1 (AdjGraph *G, int k) {
EdgeNode *p; QUEUE Q; MAKENULL(Q);
cout << G->vexlist[ k ] .vertex; visited[ k ] = true;
if(p==NULL)
break;