数据结构与算法7.doc

《数据结构与算法7.doc》由会员分享，可在线阅读，更多相关《数据结构与算法7.doc（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,

11、 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,M

12、axValue/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

13、=0; iG.n; i+)for(int j=0; jG.n; j+)coutAijt;coutendl;CenterPoint(A, G.n, cp);coutnn中心点为: G.vexlistcp+1endl;传递闭包：#includeusing 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 ; elseAij=0; f

14、or ( 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);VertexData v6=a, b, c, d, e ,f;EdgeData e6NumVertices=MaxValue/2, 3, MaxValue/2, 4, MaxValue/2, 5,MaxValue/2, MaxValue/2, 1, MaxValu

15、e/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 A

16、NumVerticesNumVertices=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、编程构建

17、一个二叉排序数，并中根遍历验证上述结果。二叉排序树：中根遍历：10 12 15 20 24 28 30 35 46 50 55 68#includeusing namespace std;typedefstruct TreeNodeint key;struct TreeNode *left;struct TreeNode *right;treeNode;class BiSortTreepublic: BiSortTree(void);void desplayTree(void);void insertTree(int key); deleteTree(int key); treeNode* s

18、earchTree(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);void showTree(treeNode* head);void destroyTree(treeNode*

19、 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

20、if(p-key key)head-left=buildTree(head-left,number); else head-right=buildTree(head-right,number); return head;六、试画出从空树开始，有字符序列(t, d, e, s, u, g, b, j, a, k, r, i)构成的二叉平衡树，并为每一次平衡处理指明旋转类型。 思考题1： Poj1125 Floyd算法Stockbroker GrapevineDescriptionStockbrokers are known to overreact to rumours. You have be

21、en 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 th

22、eir 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

23、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.InputYour program will input data for different sets of stockbroke

24、rs. 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 message to each person. The format of each stockbroker line is

25、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. Ther

26、e 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

27、 number of stockbrokers will range from 1 to 100. The input is terminated by a set of stockbrokers containing 0 (zero) people.OutputFor 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

28、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 messag

29、e 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 Input32 2 4 3 52 1 2 3 62 1 2 2 253 4 4 2 8 5 31 5 84 1 6 4 10 2 7 5 202 2 5 1 50Sample Output3 23 1

30、0#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 & maxlengthmax

31、length) min_in_max=maxlength; flag_source=i; if(min_in_maxinf) coutflag_source min_in_maxendl; else coutdisjointn; if(!n)break; for(i=1;ipair; for(j=1;jcattime; disticat=time; floyd(); return 0; 思考题21203 dijkstra算法TimetableDescriptionYou are the owner of a railway system between n cities, numbered b

32、y 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 connections. A passenger

33、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 optim

34、al 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

35、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. InputThe first line of the input contains an integer n (2 = n = 100000). The following li

36、nes 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