数据结构与算法6

. 第六次作业 一、选择题 1、深度优先遍历类似与二叉树的 A ： A. 先根遍历 B. 中根遍历 C. 后根遍历 D. 层次遍历 2、广度优先遍历类似与二叉树的 D ： A. 先根遍历 B. 中根遍历 C. 后根遍历 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 B. a, c, f, e, b, d C. a, e, b, c, f, d D. a, e, d, f, c, b 7、在如上图所示的图中，从顶点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 8、设网(带权的图)有n个顶点和e条边，则采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为 C 。 23 A. O(n) B. O(n+e) C. O(n) D. O(n) 9、设图有n个顶点和e条边，求解最短路径的Floyd算法的时间复杂度为 D 。 23 A. O(n) B. O(n+e) C. O(n) D. O(n) 10、最小生成树是指 C 。 A. 由连通网所得到的边数最少的生成树。 B. 由连通网所得到的顶点数相对较少的生成树。 C. 连通网中所有生成树中权值之和为最小的生成树。 D. 连通网的极小连通子图。 11、下面关于工程计划的AOE网的叙述中，不正确的是 B 。 A. 关键活动不按期完成就会影响整个工程的完成时间。 B. 任何一个关键活动提前完成，那么整个工程将会提前完成。 C. 所有关键活动都提前完成，那么整个工程将会提前完成。 D. 某些关键工程若提前完成，那么整个工程将会提前完成。 12、在AOE网中，始点和汇点的个数为 D 。 A. 1个始点，若干个汇点 B. 若干个始点，若干个汇点 C. 若干个始点，1个汇点 D. 1个始点，1个汇点 13、在下图所示的无向图中，从顶点v1开始采用Prim算法生成最小生成树，算法过程中产生的顶点次序为 B 。 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 14、在上图所示的途中，采用Cruskal算法生成最小生成树，过程中产生的边的次序是 C 。 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) 15、如下图所示的图中，其中一个拓扑排序的结果是 A 。 A. v1v2v3v6v4v5v7v8 B. v1v2v3v4v5v6v7v8 C. v1v6v4v5v2v3v7v8 D. v1v6v2v3v7v8v4v5 16、在下图所示的AOE网中，活动a9的最早开始时间为 B 。 A. 13 B. 14 C. 15 D. 16 17、在上图所示的AOE网中，活动a4的最迟开始时间为 D A. 4 B. 5 C. 6 D. 7 二、填空题 1、图的遍历有 深度优先遍历 和广度优先遍历等方法。 2、在深度优先搜索和广度优先搜索中，都采用visitedi= false 的方式设置第i个顶点为 new，而采用visitedi= true 的方式标识第i个结点为old。 3、由于深度优先算法的特点，深度优先往往采用 递归 的方式实现。 4、由于广度优先算法的特点，在广度优先实现过程中，往往要借助于另一种数据结构 队列 实现。 5、在深度优先搜索和广度优先搜索中，在搜索过程中所经过的边都称为 树边 。 6、连通而且无环路的无向图称为 开放树 。 7、对于含有n个顶点e条边的连通图，利用Prim算法求其最小生成树的时间复杂度为 2O(n) ，利用Kruscal算法求最小生成树的时间复杂度是 O(n) 。 8、顶点表示活动的网简称为 AOV ；边表示活动的网简称为 AOE 。 9、一个含有n个顶点的无向连通图，其每条边的权重都是a(a0)，则其最小生成树的权重等于 (n-1)*a 。 三、已知一个连通图如下图所示，分别给出一个按深度优先遍历和广度优先遍历的顶点序列（假设从顶点v1出发）。并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写相关基本操作，并在主函数中求出深度优先序列和广度优先序列。 v1 v2 v3 v4 v5 v6 0 1 0 1 0 1 v1 1 0 1 1 1 0 v2 0 1 0 0 1 0 v3 1 1 0 0 1 1 v4 0 1 1 1 0 0 v5 1 0 0 1 0 0 v6 HEAD v1 v2 v4 v6 v2 v1 v3 v4 v5 v3 v2 v5 v4 v1 v2 v5 v6 v5 v2 v3 v4 v6 v1 v4 深度优先：v1 v2 v3 v5 v4 v6 广度优先：v1 v2 v4 v6 v3 v5 #include #include using namespace std; typedef char VertexData; typedef int EdgeData; typedef struct node int adjvex; EdgeData cost; struct node *next; EdgeNode; typedef struct VertexData vertex; EdgeNode * firstedge; VertexNode; typedef struct VertexNode vexlistNumVertices+1; int n, e; AdjGraph; / 邻接表表示 BOOLEAN visitedNumVertices; int dfnNumVertices;/深度优先 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 ( ! visitedi ) DFS1( &G, i+1 ); void DFS1 (AdjGraph* G, int i) static int count=0; EdgeNode *p; coutvexlisti.vertex; visitedi=TRUE; dfni=count+; p=G-vexlisti.firstedge; while( 1 ) if( !visitedp-adjvex ) DFS1(G, p-adjvex); p=p-next; if(p=NULL) break; int bfnNumVertices;/广度优先 void BFS1 (AdjGraph *G, int k) EdgeNode *p; QUEUE Q; MAKENULL(Q); cout vexlist k .vertex; visited k = true; ENQUEUE (k, Q); while ( !EMPTY (Q) ) i = FRONT(Q)-element; DEQUEUE(Q); p = G-vexlisti.firstedge; while ( p ) if (!visitedp-adjvex ) cout vexlist p-adjvex .vertex; visited p-adjvex =TRUE; ENQUEUE ( p-adjvex , Q ); p = p-next; int main() AdjGraph G; IniADJGraph(&G); VertexData v6 = a, b, c, d, e, f; EdgeData e6NumVertices = 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0; CreateADJGraph(&G, v, e, 6); DFSTraverse(G); cout endl; BFS1(&G, 1); coutendl; /连接矩阵表示 BOOLEAN visitedNumVertices; int dfnNumVertices;/深度优先 void DFSTraverse(MTGraph G) int i , count = 1; for ( i = 0; i G.n; i+ ) visited i =FALSE; for ( i = 0; i G.n; i+ ) if ( ! visitedi ) DFS2( &G, i ); void DFS2(MTGraph *G, int i) int j; static int count=0; coutvexlisti; visitedi=TRUE; dfni=count; count +; for( j=0; jn; j+) if(G-edgeij = 1) & !visitedj ) DFS2( G, j ); int bfnNumVertices; /广度优先 void BFS2 (MTGraph *G, int k) int i , j; QUEUE Q; MAKENULL(Q); cout vexlist k ; visited k = TRUE; ENQUEUE (k, Q); while ( ! EMPTY (Q) ) i=FRONT(Q)-element; DEQUEUE(Q); for(j=0; jn; j+) if ( G-edge i j =1 & !visited j ) cout vexlist j ; visitedj=TRUE; ENQUEUE( j , Q ); int main() MTGraph G; IniMGraph(&G); VertexData v6=a, b, c, d, e, f; EdgeData e6NumVertices = 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0; CreateMGraph(&G, v, e, 6); PrintMT(&G); DFSTraverse(G); coutendl; BFS2(&G, 0); coutendl; 四、基于深度优先搜索算法，写出求无向图连通分量的算法。 typedef char VertexData; typedef int EdgeData; typedef struct VertexData vexlistNumVertices; EdgeData edgeNumVerticesNumVertices; int n; int e; MTGraph; bool visitedNumVertices; int dfnNumVertices; void DFS2(MTGraph *G, int i) int count = 0; cout vexlisti; visitedi=true; dfni=count; count+; for( int j=0; jn; j+) if(G-edgeij = 1) & !visitedj ) DFS2( G, j ); void DFSTraverse(MTGraph G) for ( int i = 0; i G.n; i+ ) visited i = false; int count = 0; for ( int i = 0; i G.n; i+ ) if ( ! visitedi ) count+; cout count n; for ( int i = 0; i n; i+ ) for ( int j = 0; j eij; VertexData vNumEdges; for ( int i = 0; i n; i+ ) vi = a + i - 0; CreateMGraph(&G, v, e, n); DFSTraverse(G); coutendl; reuturn 0; 五、网络G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。 六、下图是一个无向带权图，请给出该图的邻接矩阵，并分别按Prim算法和Kruskal算法求最小生成树（包括算法代码和画图）。 邻接矩阵如下： a b c d e f 0 6 3 0 0 0 a 6 0 0 1 0 5 b 3 0 0 6 6 0 c 0 1 6 0 0 5 d 0 0 6 0 0 2 e 0 5 0 5 2 0 f 最小生成树： Prim算法 void Prim(MTGraph G, TREE_ARRAY T) int i, j, k; EdgeData min; EdgeData LOWCOSTNumVertices; int CLOSSETNumVertices; int n=G.n; for( i=1; in; i+ ) LOWCOSTi = G.edge0i; CLOSSETi = 0; Ti+1.data=G.vexlisti; Ti+1.parent=0; T1.data=G.vexlist0; T1.parent=0; for( i = 1; i n; i+ ) min = LOWCOSTi; k = i; for( j = 1; j n; j+ ) if ( LOWCOSTj min ) min = LOWCOSTj ; k=j; cout ( G.vexlistCLOSSETk , G.vexlistk ): G.edgeCLOSSETkk endl; Tk.parent=CLOSSETk; LOWCOSTk = INT_MAX ; for ( j = 1; j n; j+ ) if ( G.edgekj LOWCOSTj & LOWCOSTj!=INT_MAX) LOWCOSTj=G.edgekj; CLOSSETj=k; void main() MTGraph G; IniMGraph(&G); VertexData v6= a, b, c, d, e, f; EdgeData e6NumVertices=INT_MAX-1, 6, 3, INT_MAX-1, INT_MAX-1, INT_MAX-1, 6, INT_MAX-1, INT_MAX-1, 1, INT_MAX-1, 5, 3, INT_MAX-1, INT_MAX-1, 6, 6, INT_MAX-1, INT_MAX-1, 1, 6, INT_MAX-1, INT_MAX-1, 5, INT_MAX-1, INT_MAX-1, 6, INT_MAX-1, INT_MAX-1, 2, INT_MAX-1, 5, INT_MAX-1, 5, 2, INT_MAX-1; CreateMGraph(&G, v, e, 6); TREE_ARRAY T; Prim(G, T); PreOrder(T, 1); coutendl; Kruskal算法 struct node_tmp int i, j; EdgeData v; ; int Find(TREE_ARRAY T, int n) if(Tn.parent=n) return n; else Find(T, Tn.parent); void Union(TREE_ARRAY T, int m, int n) if(Find(T, m)!=Find(T, n) Tn.parent=m; void Kruskal(MTGraph G, TREE_ARRAY T) for(int i=0; iG.n; i+) Ti+1.data=G.vexlisti; Ti+1.parent=i+1; node_tmp tmpNumVertices*NumVertices, t1; int k=0; for(int i=0; iG.n; i+) for(int j=i+1; jG.n; j+) if(G.edgeij!=INT_MAX-1) tmpk.i=i; tmpk.j=j; tmpk.v=G.edgeij; k+; for(int i=0; ik-1; i+) for(int j=i+1; jtmpj.v) t1=tmpi, tmpi=tmpj, tmpj=t1; for(int i=0; ik; i+) Union(T, tmpi.i+1, tmpi.j+1); k=Find(T, 1); Tk.parent=0; void main() MTGraph G; IniMGraph(&G); VertexData v6= a, b, c, d, e, f; EdgeData e6NumVertices=INT_MAX-1, 6, 3, INT_MAX-1, INT_MAX-1, INT_MAX-1, 6, INT_MAX-1, INT_MAX-1, 1, INT_MAX-1, 5, 3, INT_MAX-1, INT_MAX-1, 6, 6, INT_MAX-1, INT_MAX-1, 1, 6, INT_MAX-1, INT_MAX-1, 5, INT_MAX-1, INT_MAX-1, 6, INT_MAX-1, INT_MAX-1, 2, INT_MAX-1, 5, INT_MAX-1, 5, 2, INT_MAX-1; CreateMGraph(&G, v, e, 6); TREE_ARRAY T; Kruskal(G, T); PreOrder(T, 1); coutendl; 七、已知如下图所示的AOE网，顶点表示事件，弧及权重表示活动的时间(单位为天)。找出关键路径，并求出事件v3的最早开始时间，然后编程实现。 关键路径： 事件v3的最早开始时间：13 程序如下： void aoe(AdjGraph G, int start) int i, j; EdgeData ENumVerticesNumVertices, VENumVertices, LNumVerticesNumVertices, LNumVertices; int aovNumVertices; EdgeNode *tmp; Topologicalsort( G, aov); for(i=0; iG.n; i+) for(j=0; jG.n; j+) Eij=-1; Lij=-1; VEaov0-1=0; for(i=1; iG.n; i+) VEaovi-1=0; for(j=0; jadjvex=aovi) if(tmp-cost+VEaovj-1VEaovi-1) VEaovi-1=tmp-cost+VEaovj-1; tmp=tmp-next; for(i=0; iadjvex-1=VEaovi-1; tmp=tmp-next; VLaovG.n-1-1=VEaovG.n-1-1; for(i=G.n-2; i=0; i-) VLaovi-1=VEaovG.n-1-1; tmp=G.vexlistaovi.firstedge; while(1) if(tmp=NULL) break; else if(VLaovi-1VLtmp-adjvex -1-tmp-cost) VLaovi-1=VLtmp-adjvex -1-tmp-cost; tmp=tmp-next; for(i=0; iadjvex-1=VLaovtmp-adjvex-1-1-tmp-cost; tmp=tmp-next; cout关键活动为: endl; for(i=0; iG.n; i+) for(j=0; jG.n; j+) if(Eij!=-1 & Lij!=-1 & Eij=Lij) couti+1j+1endl; void main() AdjGraph G1; IniADJGraph(&G1); VertexData v16=1, 2, 3, 4, 5,6; EdgeData e16NumVertices=0, 6, 0, 4, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 9, 11, 0, 0, 0, 0, 0, 21, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0; CreateADJGraph_directed(&G1, v1, e1, 6); aoe(G1, 0); 八、已知一个图的顶点集V和边集G分别为V=0, 1, 2, 3, 4, 5, 6, 7, 8，E=, , , , , , , , , , , , ，若采用 邻接表存储，并且每个顶点邻接表中的边结点都是按照终点序号从大到小的次序连接的，则按照拓扑排序算法，写出得到的拓扑序列，并编程实现。 拓扑序列：8 5 6 7 3 4 1 2 0 程序如下： BOOLEAN connect(AdjGraph G, int v1, int v2) EdgeNode *tmp; tmp=G.vexlistv1.firstedge; if(tmp=NULL) return FALSE; while(1) if(tmp-adjvex=v2) return TRUE; tmp=tmp-next; if(tmp=NULL) break; return FALSE; void Topologicalsort( AdjGraph G, int aovNumVertices ) int v, w, nodes; EdgeNode *tmp; EdgeData indegreeNumVertices+1=0; QUEUE Q ; MAKENULL( Q ) ; for( v=1; vadjvex+; tmp=tmp-next; for(v=1; velement ; DEQUEUE( Q ) ; aovnodes=v; nodes + ; for( w=1; w=G.n; w+) if(connect(G, v, w) -indegreew; if( !(indegreew) ENQUEUE(w,Q) ; coutendl; if ( nodes G.n ) cout图中有环路endl; void main() AdjGraph G1; IniADJGraph(&G1); VertexData v19=0, 1, 2, 3, 4,5, 6, 7, 8; EdgeData e19NumVertices = 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0; CreateADJGraph_directed(&G1, v1, e1, 9); int aovNumVertices; Topologicalsort( G1, aov); for(int i=0; i9; i+) coutaovi ; coutendl; 思考题1：跳马周游棋盘问题：在nn（n15）的国际象棋上的某一位置（键盘输入）上放置一个马，然后采用象棋中“马走日字”的规则，要求这个马能不重复地走完 nn个格子，试用计算机求马能够走的一条路径。 提示：用深度优先搜索法 #include using namespace std; #define xSize 8 #define ySize 8 #define MAXSTEP 100000 int iStep = 0, allStep = 0, xRecord = 0, yRecord = 0, chessboardxSizeySize2; int init_chess() for(int i=0;ixSize;i+) for(int j=0;jySize;j+) chessboardj0=0; chessboardj1=0; int print_chess() for(int i=0;ixSize;i+) for(int j=0;jySize;j+) cout chessboardj0; cout endl endl; int search_x(int count) for(int i=0;ixSize;i+) for(int j=0;jySize;j+) if(chessboardj0=count) return i; return 0; int search_y(int count) if(count=0) return 0; for(int i=0;ixSize;i+) for(int j=0;j;=0&m;=0&n; MAXSTEP) xRecord = i; yRecord = j; iStep = 0; return; switch(level) case 0: m = i-2; n = j+1; break; case 1: m = i-1;