第七次作业一、选择题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. LL B. LR C. RL D. RR 二、填空题1、具有 n个顶点的有向图，如果采用邻接矩阵表示该图，则求某顶点到其他各顶点的最短路径的 Dijkstra 算法的时间复杂度是 O(n2) ；如果采用邻接表表示该图，则时间复杂度为O(e) 。2、在用 Dijkstra 算法求单源最短路径的过程中，将顶点集合V 划分为两个集合S和 V-S，其中 S中的点为 最短路径已经确定的顶点集合，V-S 中的点为最短路径尚未确定的顶点集合。3、求每一对顶点之间的最短路径，可以用两种方法，一种是分别对每个顶点采用Dijkstra算法，另一种方法是 Floyd。4、假设有向图的邻接矩阵C 的传递闭包为A，则 Aij=1表示当且仅当有一条路径从i到 j。5、有向图的中心点是指具有最小偏心度的顶点。6、一个无序序列可以通过构造一棵二叉排序树而变为一个有序学列，构造树的过程几位对无序序列进行排序的过程。7、对于一棵二叉排序树，按先序方法遍历得出的结点序列是从小到大排列的。三、如下图所示的有向网络，利用Dijkstra 算法求从顶点v1 到其他各顶点的最短路径(要求写出如教材P155 表 4-2 所示的 Dijkstra 算法的执行过程)，并编程验证。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 18 页 - - - - - - - - - 循环S W Dv2 Dv3 Dv4 Dv5 Dv6 初态v1 45 15 15 1 v1,v3 v3 25 15 75 15 2 v1,v3,v2 v2 25 15 75 15 40 3 v1,v3,v2,v4 v4 25 15 65 15 40 4 v1,v3,v2,v4,v5 v5 25 15 65 15 40 5 v1,v3,v2,v4,v5,v6 v6 25 15 65 15 40 #include using namespace std; int mincost(EdgeData DNumVertices, 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+ ) Di=G .edge0i ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 18 页 - - - - - - - - - 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 e6NumVertices= 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; EdgeData D6; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 18 页 - - - - - - - - - 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 算法，编程求该图的传递闭包(矩阵 )。最短路径矩阵：中心点为： d void Floyd(int ANumVerticesNumVertices,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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 18 页 - - - - - - - - - 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, int 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 18 页 - - - - - - - - - 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, 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); EdgeData ANumVerticesNumVertices=0; int A1NumVerticesNumVertices=0; int PNumVerticesNumVertices; Floyd(A, G , P, G .n); cout每一对顶点之间的最短路径:endl; for(i=0; iG .n; i+) for(int j=0; jG .n; j+) coutAijt; coutendl; CenterPoint(A, G.n, cp); coutnn 中心点为 : G.vexlistcp+1endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 18 页 - - - - - - - - - 传递闭包：#include using namespace std; void Warshall(int ANumVerticesNumVertices,MTGraph C,int n) int i, j, k; for ( i = 0; i n; i+ ) for ( j = 0; jn; j+ ) if(C.edgeij!=MaxValue/2) Aij =1 ; else Aij=0; 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) ; void main() int i, j, cp; MTGraph G; IniMGraph_directed(&G); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 18 页 - - - - - - - - - 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, 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); EdgeData ANumVerticesNumVertices=0; int A1NumVerticesNumVertices=0; int PNumVerticesNumVertices; Warshall(A1, G, G.n); coutn 传递闭包为 :endl; for(i=0; iG .n; i+) for(int j=0; jG .n; j+) coutA1ijt; coutendl; 五、依次输入表(30, 15, 28, 20, 24, 10, 12, 68, 35, 50, 46, 55)中的元素，生成一棵二叉排序数，要求： 1、试画出生成之后的二叉排序树。 2、对该二叉排序数作中根遍历，写出遍历序列。 3、编程构建一个二叉排序数，并中根遍历验证上述结果。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 18 页 - - - - - - - - - 二叉排序树：中根遍历： 10 12 15 20 24 28 30 35 46 50 55 68 #include using namespace std; typedef struct TreeNode int key; struct TreeNode *left; struct TreeNode *right; treeNode; class BiSortTree public: BiSortTree(void); void desplayTree(void); void insertTree(int key); deleteTree(int key); treeNode* searchTree(int key); BiSortTree(); private: treeNode* buildTree(treeNode* head,int number); treeNode* search(treeNode* head ,int key); treeNode* BiSortTree:searchParent(treeNode* head,treeNode* p); treeNode* BiSortTree:searchMinRight(treeNode* head); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 18 页 - - - - - - - - - void showTree(treeNode* head); void destroyTree(treeNode* head); treeNode *Head; ; BiSortTree:BiSortTree() cout 建立一棵二叉排序树,请输入你要建树的所有数(以-1 作为结束标志 !): number; while(number!=-1) Head=buildTree(Head,number); cinnumber; treeNode* BiSortTree:buildTree(treeNode* head,int number) treeNode *p; p=new treeNode; p-key=number; p-left =p-right=NULL; if(head=NULL) return p; else if(p-key key) head-left=buildTree(head-left,number); else head-right=buildTree(head-right,number); return head; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 18 页 - - - - - - - - - 六、试画出从空树开始，有字符序列(t, d, e, s, u, g, b, j, a, k, r, i)构成的二叉平衡树，并为每一次平衡处理指明旋转类型。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 18 页 - - - - - - - - - 思考题 1：Poj1125 Floyd算法Stockbroker Grapevine Description Stockbrokers are known to overreact to rumours. You have been contracted to develop a method of spreading disinformation amongst the stockbrokers to give your employer the tactical edge in the stock market. For maximum effect, you have to spread the rumours in the fastest possible way. Unfortunately for you, stockbrokers only trust information coming from their Trusted sources This means you have to take into account the structure of their contacts when starting a rumour. It takes a certain amount of time for a specific stockbroker to pass the rumour on to each of his colleagues. Your task will be to write a program that tells you which stockbroker to choose as your starting point for the rumour, as well as the time it will take for the rumour to spread throughout the stockbroker community. This duration is measured as the time needed for the last person to receive the information. Input Your program will input data for different sets of stockbrokers. Each set starts with a line with the number of stockbrokers. Following this is a line for each stockbroker which contains the number of people who they have contact with, who these people are, and the time taken for them to pass the 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 18 页 - - - - - - - - - message to each person. The format of each stockbroker line is as follows: The line starts with the number of contacts (n), followed by n pairs of integers, one pair for each contact. Each pair lists first a number referring to the contact (e.g. a 1 means person number one in the set), followed by the time in minutes taken to pass a message to that person. There are no special punctuation symbols or spacing rules. Each person is numbered 1 through to the number of stockbrokers. The time taken to pass the message on will be between 1 and 10 minutes (inclusive), and the number of contacts will range between 0 and one less than the number of stockbrokers. The number of stockbrokers will range from 1 to 100. The input is terminated by a set of stockbrokers containing 0 (zero) people. Output For each set of data, your program must output a single line containing the person who results in the fastest message transmission, and how long before the last person will receive any given message after you give it to this person, measured in integer minutes. It is possible that your program will receive a network of connections that excludes some persons, i.e. some people may be unreachable. If your program detects such a broken network, simply output the message disjoint. Note that the time taken to pass the message from person A to person B is not necessarily the same as the time taken to pass it from B to A, if such transmission is possible at all. Sample Input 3 2 2 4 3 5 2 1 2 3 6 2 1 2 2 2 5 3 4 4 2 8 5 3 1 5 8 4 1 6 4 10 2 7 5 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 18 页 - - - - - - - - - 0 2 2 5 1 5 0 Sample Output 3 2 3 10 #include using namespace std; const int inf=20; int dist101101; int i,j,k; int n; void floyd() for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j distik + distkj) distij = distik + distkj; int maxlength; int min_in_max=inf; int flag_source; for(i=1;i=n;i+) maxlength=0; for(j=1;j=n;j+) if(i!=j & maxlengthmaxlength) min_in_max=maxlength; flag_source=i; if(min_in_maxinf) coutflag_source min_in_maxendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 18 页 - - - - - - - - - else coutdisjointn; if(!n)break; for(i=1;ipair; for(j=1;jcattime; disticat=time; floyd(); return 0; 思考题 2 1203 dijkstra 算法Timetable Description You are the owner of a railway system between n cities, numbered by integers from 1 to n. Each train travels from the start station to the end station according to a very specific timetable (always on time), not stopping anywhere between. On each station a departure timetable is available. Unfortunately each timetable contains only direct 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 18 页 - - - - - - - - - connections. A passenger that wants to travel from city p to city q is not limited to direct connections however - he or she can change trains. Each change takes zero time, but a passenger cannot change from one train to the other if it departs before the first one arrives. People would like to have a timetable of all optimal connections. A connection departing from city p at A oclock and arriving in city q at B oclock is called optimal if there is no connection that begins in p not sooner than at A and ends in q not later than at B. We are only interested in connections that can be completed during same day. Write a program that: reads the number n and departure timetable for each of n cities from the standard input, creates a timetable of optimal connections from city 1 to city n, writes the answer to the standard output. Input The first line of the input contains an integer n (2 = n = 100000). The following lines contain n timetables for cities 1, 2, ., n respectively. The first line of the timetable description contains only one integer m. Each of the following m lines corresponds to one position in the timetable and contains: departure time A, arrival time B (A B) and destination city number t (1 = t = n) separated by single spaces. Departure time A and arrival time B are written in format hh:mm, where hh are two digits representing full hours (00 = hh = 23) and mm are two digits representing minutes (00 = mm = 59). Positions in the timetable are given in non-decreasing order according to the departure times. The number of all positions in all timetables does not exceed 1000000. Output The first line of the output contains an integer r - the number of positions in the timetable being the solution. Each of the following r lines contains a departure time A and an arrival time B separated by single space. The time format should be like in the input and positions in the timetable should be ordered increasingly according to the departure times. If there is more then one optimal connection with the same departure and arrival time, your program should output just one. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 18 页 - - - - - - - - - Sample Input 3 3 09:00 15:00 3 10:00 12:00 2 11:00 20:00 3 2 11:30 13:00 3 12:30 14:00 3 0 Sample Output 2 10:00 14:00 11:00 20:00 #include using namespace std; int n; double p130130,dp130130; int main() int i,j,k; while(scanf(%d,&n)!=EOF) if(n=-1) break; for(i=0;i(1n);i+) for(j=0;j(1n);j+) scanf(%lf,&pij); memset(dp,0,sizeof(dp); for(i=0;i(1n);i+) dp0i=1; for(i=1;i=n;i+) for(j=0;j(1n);j+) for(k=0;k(1(i-1)1)=(j(i-1) dpij+=dpi-1j*dpi-1k*pjk; int ans=0; printf(%d=%lft,i,dpni);*/ for(i=0;i(1dpnans) ans=i; printf(%dn,ans+1); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 18 页 - - - - - - - - - 要求：1、上述作业要求在单独完成；2、完成后，于规定期限内提交到教学辅助系统中，注意，在提交时将所编写的程序统一拷贝到一个 Word 文件中。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 18 页 - - - - - - - - -