《数据结构与算法7》由会员分享，可在线阅读，更多相关《数据结构与算法7（77页珍藏版）》请在金锄头文库上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date数据结构与算法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, 1
2、30)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(n2) ；如果采用邻接表表示该图，则时间复杂度为 O(e)
3、。2、在用Dijkstra算法求单源最短路径的过程中，将顶点集合V划分为两个集合S和V-S，其中S中的点为最短路径 已经确定的顶点集合 ，V-S中的点为 最短路径尚未确定的顶点集合 。3、求每一对顶点之间的最短路径，可以用两种方法，一种是分别对每个顶点采用 Dijkstra 算法，另一种方法是 Floyd 。4、假设有向图的邻接矩阵C的传递闭包为A，则Aij=1表示 当且仅当有一条路径从i到j 。5、有向图的中心点是指 具有最小偏心度的顶点 。6、一个无序序列可以通过构造一棵 二叉排序 树而变为一个有序学列，构造树的过程几位对无序序列进行排序的过程。7、对于一棵二叉排序树，按 先序 方法遍历得
4、出的结点序列是从小到大排列的。三、如下图所示的有向网络，利用Dijkstra算法求从顶点v1到其他各顶点的最短路径(要求写出如教材P155表4-2所示的Dijkstra算法的执行过程)，并编程验证。循环SWDv2Dv3Dv4Dv5Dv6初态v14515151v1,v3v3251575152v1,v3,v2v225157515403v1,v3,v2,v4v425156515404v1,v3,v2,v4,v5v525156515405v1,v3,v2,v4,v5,v6v62515651540#includeusing namespace std;int mincost(EdgeData DNumV
5、ertices, BOOLEAN SNumVertices, int n) int w;EdgeData temp =MaxValue ; w=0; for (int i=1 ; in ; i+ )if (!Si & Ditemp) temp = Di ; w = i ; return w ;void Dijkstra(MTGraph G, EdgeData DNumVertices, int PNumVertices) BOOLEAN SNumVertices=FALSE;int i, v, w;EdgeData sum; D0=MaxValue;for ( i=1 ; iG.n; i+ )
6、 Di=G.edge0i ; Si=FALSE ; S0= TRUE; for(i=1; iG.n; i+) w=mincost ( D, S, G.n ); Sw=TRUE ; for ( v=1 ; vG.n ; v+ ) if ( Sv!=TRUE & G.edgewv!=MaxValue) sum=Dw + G.edgewv ; if (sum Dv ) Dv = sum ; Pv=w; void main()MTGraph G;IniMGraph_directed(&G);VertexData v6=v1, v2, v3, v4, v5 ,v6;EdgeData e6NumVerti
7、ces=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_dir
8、ected(&G, v, e, 6);PrintMT(&G);coutendl;EdgeData D6; int P6=0;Dijkstra(G, D, P);for(int i=1; i6; i+)coutDit;coutendl;for(i=1; i6; i+)coutG.vexlistPiG.vexlistiendl;coutendl;四、应用Floyd算法，编程求下图所示有向图的每对顶点之间的最短路径(写出相应的矩阵)，并求该图的中心点。并利用Warshall算法，编程求该图的传递闭包(矩阵)。最短路径矩阵：中心点为：dvoid Floyd(int ANumVerticesNumVer
9、tices,MTGraph C,int PNumVerticesNumVertices,int n) int i, j, k;for ( i = 0; i n; i+ ) for ( j = 0; jn; j+ ) Aij = C.edgeij ; Pij = -1; for ( k = 0; k n; k+ ) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if ( Aik + Akj Aij ) Aij = Aik + Akj ; Pij = k; void Path(int PNumVerticesNumVertices, int i, in
10、t j)int k=Pij;if(k!=-1)Path(P, i, k);coutk+1endl;Path(P, k, j);void CenterPoint(EdgeData ANumVerticesNumVertices, int n, int &cp)EdgeData ENumVertices=0;int min=MaxValue/2;for(int j=0; jn; j+)for(int i=0; in; i+)if(AijMaxValue/2)Ej+=Aij;if(Ej=0)Ej=MaxValue/2;if(Ejmin)min=Ej;cp=j;void main()int i, j, cp;MTGraph G;IniMGraph_directed(&G);VertexData v6=a, b, c, d, e ,f;EdgeData e6NumVertices=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, M
