数据结构与算法7

第七次作业一、选择题1、设图有n个顶点和e条边，当用邻接矩阵表示该图时，则求解最短路径的Floyd算法的时间复杂度为D。A.O(n)B.O(n+e)C.O(n2)D.O(n3)2、分别以下列序列构造二叉排序数（二叉查找树），与用其他3个序列所构造的结果不同的是C：A.(100,80,90,60,120,110,130)B.(100,120,110,130,80,60,90)C.(100,60,80,90,120,110,130)D.(100,80,60,90,120,130,110)3、在二叉平衡树中插入一个结点造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作C型调整使其平衡。A.LLB.LRC.RLD.RR二、填空题1、具有n个顶点的有向图，如果采用邻接矩阵表示该图，则求某顶点到其他各顶点的最短路径的Dijkstra算法的时间复杂度是O(n^2)；如果采用邻接表表示该图，则时间复杂度为O(e)。2、在用Dijkstra算法求单源最短路径的过程中，将顶点集合V划分为两个集合S和V-S，其中S中的点为最短路径已经确定的顶点集合，V-S中的点为最短路径尚未确定的顶点集合。3、求每一对顶点之间的最短路径，可以用两种方法，一种是分别对每个顶点采用Dijkstra算法，另一种方法是Floyd。4、假设有向图的邻接矩阵C的传递闭包为A，则A[i][j]=1表示当且仅当有一条路径从i到j。5、有向图的中心点是指具有最小偏心度的顶点。6、一个无序序列可以通过构造一棵二叉排序树而变为一个有序学列，构造树的过程几位对无序序列进行排序的过程。7、对于一棵二叉排序树，按先序方法遍历得出的结点序列是从小到大排列的。三、如下图所示的有向网络，利用Dijkstra算法求从顶点v1到其他各顶点的最短路径(要求写出如教材P155表4-2所示的Dijkstra算法的执行过程)，并编程验证。循环SWD[v2]D[v3]D[v4]D[v5]D[v6]初态{v1}—4515∞15∞1{v1,v3}v325157515∞2{v1,v3,v2}v225157515403{v1,v3,v2,v4}v425156515404{v1,v3,v2,v4,v5}v525156515405{v1,v3,v2,v4,v5,v6}v62515651540#includeiostreamusingnamespacestd;intmincost(EdgeDataD[NumVertices],BOOLEANS[NumVertices],intn){intw;EdgeDatatemp=MaxValue;w=0;for(inti=1;in;i++)if(!S[i]&&D[i]temp){temp=D[i];w=i;}returnw;}voidDijkstra(MTGraphG,EdgeDataD[NumVertices],intP[NumVertices]){BOOLEANS[NumVertices]={FALSE};inti,v,w;EdgeDatasum;D[0]=MaxValue;for(i=1;iG.n;i++){D[i]=G.edge[0][i];S[i]=FALSE;}S[0]=TRUE;for(i=1;iG.n;i++){w=mincost(D,S,G.n);S[w]=TRUE;for(v=1;vG.n;v++)if(S[v]!=TRUE&&G.edge[w][v]!=MaxValue){sum=D[w]+G.edge[w][v];if(sumD[v])D[v]=sum;P[v]=w;}}}voidmain(){MTGraphG;IniMGraph_directed(&G);VertexDatav[6]={'v1','v2','v3','v4','v5','v6'};EdgeDatae[6][NumVertices]={{MaxValue,45,15,30,15,MaxValue},{MaxValue,MaxValue,MaxValue,20,15,15},{10,10,MaxValue,60,MaxValue,MaxValue},{MaxValue,30,MaxValue,MaxValue,MaxValue,20},{MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,MaxValue},{MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,MaxValue}};CreateMGraph_directed(&G,v,e,6);PrintMT(&G);coutendl;EdgeDataD[6];intP[6]={0};Dijkstra(G,D,P);for(inti=1;i6;i++)coutD[i]'\t';coutendl;for(i=1;i6;i++)coutG.vexlist[P[i]]-G.vexlist[i]endl;coutendl;}四、应用Floyd算法，编程求下图所示有向图的每对顶点之间的最短路径(写出相应的矩阵)，并求该图的中心点。并利用Warshall算法，编程求该图的传递闭包(矩阵)。最短路径矩阵：中心点为：dvoidFloyd(intA[NumVertices][NumVertices],MTGraphC,intP[NumVertices][NumVertices],intn){inti,j,k;for(i=0;in;i++)for(j=0;jn;j++){A[i][j]=C.edge[i][j];P[i][j]=-1;}for(k=0;kn;k++)for(i=0;in;i++)for(j=0;jn;j++)if(A[i][k]+A[k][j]A[i][j]){A[i][j]=A[i][k]+A[k][j];P[i][j]=k;}}voidPath(intP[NumVertices][NumVertices],inti,intj){intk=P[i][j];if(k!=-1){Path(P,i,k);coutk+1endl;Path(P,k,j);}}voidCenterPoint(EdgeDataA[NumVertices][NumVertices],intn,int&cp){EdgeDataE[NumVertices]={0};intmin=MaxValue/2;for(intj=0;jn;j++){for(inti=0;in;i++)if(A[i][j]MaxValue/2)E[j]+=A[i][j];if(E[j]==0)E[j]=MaxValue/2;if(E[j]min){min=E[j];cp=j;}}}voidmain(){inti,j,cp;MTGraphG;IniMGraph_directed(&G);VertexDatav[6]={'a','b','c','d','e','f'};EdgeDatae[6][NumVertices]={{MaxValue/2,3,MaxValue/2,4,MaxValue/2,5},{MaxValue/2,MaxValue/2,1,MaxValue/2,MaxValue/2,1},{MaxValue/2,MaxValue/2,MaxValue/2,2,MaxValue/2,MaxValue/2},{MaxValue/2,3,MaxValue/2,MaxValue/2,MaxValue/2,MaxValue/2},{MaxValue/2,MaxValue/2,MaxValue/2,3,MaxValue/2,2}{MaxValue/2,MaxValue/2,MaxValue/2,2,MaxValue/2,MaxValue/2}};CreateMGraph_directed(&G,v,e,6);EdgeDataA[NumVertices][NumVertices]={0};intA1[NumVertices][NumVertices]={0};intP[NumVertices][NumVertices];Floyd(A,G,P,G.n);cout每一对顶点之间的最短路径:endl;for(i=0;iG.n;i++){for(intj=0;jG.n;j++)coutA[i][j]'\t';coutendl;}CenterPoint(A,G.n,cp);cout\n\n中心点为:G.vexlist[cp+1]endl;}传递闭包：#includeiostreamusingnamespacestd;voidWarshall(intA[NumVertices][NumVertices],MTGraphC,intn){inti,j,k;for(i=0;in;i++)for(j=0;jn;j++){if(C.edge[i][j]!=MaxValue/2)A[i][j]=1;elseA[i][j]=0;}for(k=0;kn;k++)for(i=0;in;i++)for(j=0;jn;j++)if(A[i][k]&&A[k][j]){A[i][j]=A[i][j]||(A[i][k]&&A[k][j]);}}voidmain(){inti,j,cp;MTGraphG;IniMGraph_directed(&G);VertexDatav[6]={'a','b','c','d','e','f'};EdgeDatae[6][NumVertices]={{MaxValue/2,3,MaxValue/2,4,MaxValue/2,5},{MaxValue/2,MaxValue/2,1,MaxValue/2,MaxValue/2,1},{MaxValue/2,MaxValue/2,MaxValue/2,2,MaxValue/2,MaxValue/2},{MaxValue/2,3,MaxValue/2,MaxValue/2,MaxValue/2,MaxValue/2},{MaxValue/2,MaxValue/2,MaxValue/2,3,MaxValue/2,2}{MaxValue/2,MaxValue/2,MaxValue/2,2,MaxValue/2,MaxValue/2}};CreateMGraph_directed(&G,v,e,6);EdgeDataA[NumVertices][NumVertices]={0};intA1[NumVertices][NumVertices]={0};intP[NumVertices][NumVertices];Warshall(A1,G,G.n);cout\n传递闭包为:endl;for(i=0;iG.n;i++){for(intj=0;jG.n;j++)coutA1[i][j]'\t';coutendl;}}五、依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序数，要求：1、试画出生成之后的二叉排序树。2、对该二叉排序数作中根遍历，写出遍历序列。3、编程构建一个二叉排序数，并中根遍历验证上述结果。二叉排序树：中根遍历：101215202428303546505568#includeiostreamusingnamespacestd;typedefstructTreeNode{intkey;structTreeNode*left;structTreeNode*right;}treeNode;classBiSortTree{public:BiSortTree(void);voiddesplayTree(void);voidinsertTree(intkey);deleteTree(intkey);treeNode*searchTre