数据结构与算法6

第六次作业一、选择题1、深度优先遍历类似与二叉树的 A： A.先根遍历B,中根遍历C.后根遍历D,层次遍历2、广度优先遍历类似与二叉树的 D： A.先根遍历B.中根遍历C.后根遍历D,层次遍历3、下列关于开放树(FreeTree)的说法错误的是 C：A.具有n个结点的开放树包含n-1条边B.开放树没有回路 C.开放树可以是非连通图D.在开放树中任意加一条边，一定会产生回路4、关于最小生成树，下列说法错误的是C：A.最小生成树是一棵开放树B.最小生成树各边的和是所有生成树中最小的C.任何图都只有一个最小生成树D,能够产生最小生成树的图，其边一定有权值5、任何一个无向连通图的最小生成树 B：A,只有1棵B,1棵或多棵C.一定有多棵D,可能不存在6、在如下图所示的图中，从顶点a出发，按深度优先遍历，则可能得到的一种顶点的序列为A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,bA.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b7、在如上图所示的图中，从顶点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,b8、设网(带权的图)有n个顶点和e条边，则采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为CC。 23A.O(n)B,O(n+e)C.O(n)D,O(n)9、设图有n个顶点和e条边，求解最短路径的Floyd算法的时间复杂度为D。 23A.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网中，始点和汇点的个数为DA.1个始点，若干个汇点B.若干个始点，若干个汇点C.若干个始点，1个汇点D.1个始点，1个汇点13、在下图所示的无向图中，从顶点^开始采用Prim算法生成最小生成树，算法过程中产生的顶点次序为B。A.v1,v3,v4,v2,v5,v6B.v1,v3,v6,v2,v5,v4C.v1,v2,v3,v4,v5,v6D.v1,v3,v6,v4,v2,v514、在整理范本上图所示的途中，采用6「央卜如算法生成最小生成树，过程中产生的边的次序是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.v1*v2*v3*v6*v4*v5*v7*v8B.v1*v2*v3*v4*v5*v6*v7*v8C.v1*v6*v4*v5*v2*v3*v7*v8D.v1*v6*v2*v3*v7*v8*v4*v516、在下图所示的AOE网中，活动a9的最早开始时间为B。A.13B.14C.15D.16 17、在上图所示的AOE网中，活动a4的最迟开始时间为DA.4B.5C.6D.7二、填空题1、图的遍历有深度优先遍历和广度优先遍历等方法。2、在深度优先搜索和广度优先搜索中，都采用司虹©g]=false的方式设置第i个顶点为小卬，而采用水送4国=true的方式标识第i个结点为。也。3、由于深度优先算法的特点，深度优先往往采用递归的方式实现。4、由于广度优先算法的特点，在广度优先实现过程中，往往要借助于另一种数据结构 队列实现。5、在深度优先搜索和广度优先搜索中，在搜索过程中所经过的边都称为树边。6、连通而且无环路的无向图称为开放树 。7、对于含有n个顶点。条边的连通图，利用Prim算法求其最小生成树的时间复杂度为 2O(n)利用Kruscal算法求最小生成树的时间复杂度是O(n)8、顶点表示活动的网简称为 AOV；边表示活动的网简称为AOE。 9、一个含有n个顶点的无向连通图，其整理范本每条边的权重都是a(a>0),则其最小生成树的权重等于(n-1)*a 。三、已知一个连通图如下图所示，分别给出一个按深度优先遍历和广度优先遍历的顶点序列(假设从顶点^出发)。并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写相关基本操作，并在主函数中求出深度优先序列和广度优先序列。v1v2v3v4v5v6010101v1101110v20100 10v3 110 011v401 1100v510010 0v6HEADv1 v2v4v6八v2v1v3v4v5八v3v2v5人v4v1v2v5v6人v5v2v3v4人v6v1v4人 深度优先：v1v2v3v5v4v6广度优先：v1v2v4v6v3v5#include<iostream>#include<string>usingnamespacestd;typedefcharVertexData;typedefintEdgeData;typedefstructnode{intadjvex;EdgeDatacost;structnode*next;}EdgeNode;typedefstruct{VertexDatavertex;EdgeNode*firstedge;}VertexNode;typedefstruct{VertexNodevexlist[NumVertices+1];intn,e;}AdjGraph;//邻接表表示BOOLEANvisited[NumVertices];intdfn[NumVertices];//深度优先voidDFSTraverse(AdjGraphG){inti,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);}voidDFS1(AdjGraph*G,inti){staticintcount=0;EdgeNode*p;cout<<G->vexlist[i].vertex;visited[i]=TRUE;dfn[i]=count++;p=G->vexlist[i].firstedge;while(1){if(!visited[p->adjvex])DFS1(G,p->adjvex);p=p->next;if(p==NULL)break;}}intbfn[NumVertices];//广度优先voidBFS1(AdjGraph*G,intk){EdgeNode*p;QUEUEQ;MAKENULL(Q);cout<<G->vexlist[k].vertex;visited[k]=true;整理范本ENQUEUE(k,Q);while(!EMPTY(Q)){i=FRONT(Q)->element;DEQUEUE(Q); p=G->vexlist[i].firstedge;while(p){if(!visited[p->adjvex]){ cout<<G->vexlist[p->adjvex].vertex;visited[p->adjvex]=TRUE;ENQUEUE(p->adjvex,Q); } p=p->next;} }}intmain。{AdjGraphG;IniADJGraph(&G);VertexDatav[6]={'a','b','c','d','e','£};EdgeDatae[6][NumVertices]={{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);cout<<endl;}〃连接矩阵表示BOOLEANvisited[NumVertices];intdfn[NumVertices];//深度优先voidDFSTraverse(MTGraphG){inti,count=1;for(i=0;i<G.n;i++)visited[i]=FALSE;for(i=0;i<G.n;i++)if(!visited[i])DFS2(&G,i);}voidDFS2(MTGraph*G,inti){intj;staticintcount=0;cout<<G->vexlist[i];visited[i]=TRUE;dfn[i]=count;count++;for(j=0;j<G->n;j++)if((G->edge[i][j]==1)&&!visited[j])DFS2(G,j);}intbfn[NumVertices];〃广度优先voidBFS2(MTGraph*G,intk){inti,j;QUEUEQ;MAKENULL(Q);cout<<G->vexlist[k];visited[k]=TRUE;ENQUEUE(k,Q);while(!EMPTY(Q)) {i=FRONT(Q)->element;DEQUEUE(Q);for(j=0;j<G->n;j++){ if(G->edge[i][j]==1&&!visited[j]){ cout<<G->vexlist[j];visited[j]=TRUE;ENQUEUE(j,Q);} } } }intmain。{MTGraphG;IniMGraph(&G);VertexDatav[6]={'a','b','c','d','e','f};EdgeDatae[6][NumVertices]={{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);整理范本cout<<endl;BFS2(&G,0);cout<<endl;}四、基于深度优先搜索算法，写出求无向图连通分量的算法。typedefcharVertexData;typedefintEdgeData;typedefstruct{VertexDatavexlist[NumVertices];EdgeDataedge[NumVertices][NumVertices];intn;inte;}MTGraph;boolvisited[NumVertices];intdfn[NumVertices];voidDFS2(MTGraph*G,inti){intcount=0;cout<<G->vexlist[i];visited[i]=true;dfn[i]=count;count++;for(intj=0;j<G->n;j++)if((G->edge[i][j]==1)&&!visited[j])DFS2(G,j);}voidDFSTraverse(MTGraphG){for(inti=0;i<G.n;i++)visited[i]=false;intcount=0;for(inti=0;i<G.n;i++)if(!visited[i]){ count++;cout<<count<<":";DFS2(&G,i); }}intmain。{MTGraphG;EdgeDatae[NumEdges][NumVertices];intn;cin>>n;for(inti=0;i<n;i++)for(intj=0;j<n;j++)cin>>e[i][j];VertexDatav[NumEdges];for(inti=0;i<n;i++)v[i]='a'+i-0;CreateMGraph(&G,v,e,n);DFSTraverse(G);cout<<endl;reuturn0;}五、网络G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。六、下图是一个无向带权图，请给出该图的邻接矩阵，并分别按Prim算法和Kruskal算法求最小生成树(包括算法代码和画图)。邻接矩阵如下：abcdef 06 3000a 60 0105b 30 0660c01 6005 d0060 02e0505 20f最小生成树：Prim算法voidPrim(MTGraphG,TREE_ARRAYT){inti,j,k;EdgeDatamin;EdgeDataLOWCOST[NumVertices];intCLOSSET[NumVertices];intn=G.n;for(i=1;i<n;i++){LOWCOST[i]=G.edge[0][i];CLOSSET[i]=0;T[i+1].data=G.vexlist[i];T[i+1].parent=0;}T[1].data=G.vexlist[0];整理范本

T[1].parent=0;for(i=1;i<n;i++){min=LOWCOST[i];k=i;for(j=1;j<n;j++)if(LOWCOST[j]<min){min=LOWCOST[j];k=j;}cout<<"("<<G.vexlist[CLOSSET[k]]<<","<<G.vexlist[k]<<"):"<<G.edge[CLOSSET[k]][k]<<endl;T[k].parent=CLOSSET[k];LOWCOST[k]=INT_MAX;for(j=1;j<n;j++)if(G.edge[k][j]<LOWCOST[j]&&LOWCOST[j]!=INT_MAX){LOWCOST[j]=G.edge[k][j];CLOSSET[j]=k;}}}voidmain。{MTGraphG;IniMGraph(&G);VertexDatav[6]={'a','b','c','d','e','f};EdgeDatae[6][NumVertices]={{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_ARRAYT;Prim(G,T);PreOrder(T,1);cout<<endl;}Kruskal算法structnode_tmp