《数据结构复习》由会员分享，可在线阅读，更多相关《数据结构复习（8页珍藏版）》请在金锄头文库上搜索。
1、习题4-1运算题。1. 有6个元素A、B、C、D、E、F依次进栈，允许任何时候出栈，能否得到下列的每个出栈序列，若能，给出栈操作的过程，若不能，简述其理由2. （1）CDBEFA（2）ABEDFC（3）DCEABF（4）BAEFCD有4个元素a,b,c,d依次进栈，任何时候都可以出栈，请写出所有可能的出栈序列和所有不存在的序列。用一维数组a7顺序储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有5个元素：23,45,67,80,34，其中，23为队首元素，front的值为3,请画出对应的存储状态，当连续做4次出队运算后，再让15,36,48元素依次进队，请再次画出对应
2、的存储状态。1, 用于顺序存储一个队列的数组的长度为N,队首和队尾指针分别为front和rear,写出求此队列长度（即所含元素个数）的公式参考答案（从简）(1)能:push(S,A),push(S,B),push(S,C),pop(S),push(S,D),pop(S),pop(S),push(S,E),pop(S),push(S,F),pop(S),pop(S).(2) 能:push(S,A),pop(S),push(S,B),pop(S),push(S,C),push(S,D),push(S,E),pop(S),pop(S),push(S,F),pop(S),pop(S).(3) 不能：当
3、E出栈时，AB必需在栈内，而后继A出栈先于B，不符合后进先出原则。不能：当F出栈时，CD必需在栈内，而后继C出栈先于D,不符合后进先出原则。2, 所有可能的出栈序列：abcd;abdc;acbd;acdb;adcb;bacd;badc;bcad;bcda;bdca;cbad;cbda;cdba;dcba.所有不存在的序列:adbc;bdac;cabd;cadb;cdab;dabc;dacb;dbac;dbca;dcab.3,L=（N+rear-front）%N01234568034234567frearffront34153648ffrontfrear4,队列长度L的计算公式为:说明：当rea
4、rfront时，L=rear-front=（N+rear-front）%N;N-1-front,后部分在数组的首部，其元素个数为rear+1,所以:当rear、妙H5(b)有向图图713运算题图12、根据图7-13(a)和图7-13(b)，画出：(1)每个图的邻接邻接矩阵。(2)每个图的邻接表。(3)每个图的边集数组。3、如图7-14所示，按下列条件分别写出从顶点v0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示。(2)假定它们均采用邻接表表示，并且每个顶点邻接表中的结点都是按顶点序号从大到小的次序链接的。(a)无向图1&(b)有向图图
5、714运算题图24、已知一个图的二元组表示如下:V=0，1，2，3，4，5,6，7，8E=(0，3)，(0，4)，(1，2)，(1，4)，(2，4)，(2，5)，(3，6)，(3，7)，(4，7)，(5，8)，(6，7)，(7，8)(1) 画出对应的图形。(2) 假定从顶点0出发，给出邻接矩阵表示图的深度优先和广度优先搜索遍历的顶点序列。(3) 假定从顶点0出发，给出邻接表表示的图的深度优先和广度优先搜索遍历的顶点序列，假定每个顶点邻接表中的结点都是按顶点序号从大到小的次序链接的。答案3.依照矩阵和邻接表所产生的两种遍历序列各自相等。a图：深度优先遍历：0128345679广度优先遍历：014
6、2738695b图：深度优先遍历：014587236广度优先遍历：0134267584.深度优先遍历：036741258广度优先遍历：034671285习题8-1运算题1、如图形8-18所示，针对有向图操作如下。（1）画出最小生成树并求出它的权。（2）从顶点V0出发，要据普里姆算法求出最小生成树的过程中，把依次得到的各条边按序写出来。（3）根据克鲁斯卡算法求出最小生成树的过程中，把依次得到的各条边写出来。（1）（2）普里姆算法的边的序列:(0,1)，(1,6)，(6,2)，(2,3)，(3,4)，(4,5)(3)克鲁斯卡算法的边的序列：(1,6)，(2,3)，(0,1)，(6,2)，(3,4)
7、，(4,5)E=（0，1）8，（0，3）2，（0，5）10，（1，2）6，（1，4）20，（1，6）12，（2，4）10，（2，7）15，（3，5）5,（3，6）7,（4，7）4,（5，6）6，（6,7）8（1）按照克鲁斯卡尔算法求出最小生成树，写出依次得到的各条边。(1)(0,3)，(4,7)，(3,5)，(5,6)，(1,2)，(0,1)，(6,7)(2)03:(0,3)0f5:(0,3)，(3,5)01:(0,1)06:(0,3)，(3,6)02:(0,1)，(1,2)07:(0,3)，(3,6)，(6,7)04:(0,3)，(3,6)，(6,7)，(7,4)4、如图形8-20所示，利用
8、弗洛伊德算法求每对顶点之间的最短路径，即仿照如图形（2）按照狄克斯特算法求从顶点0到其余各顶点的最短路径。8-8的运算过程，给出从邻接矩阵出发每加入一个中间每加入一个中间点后矩阵状态。5如图形8-21所示，试给出一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出唯一一种拓扑序列图821AOV网答案：14023576896一个AOV网的二元组表示为：V=0，1，2，3，4，5，6，7，8，9，10E=,在此AOV网的邻接表存储中，若各顶点邻接表中的边结点是按照邻接顶点序号从大到小链接的，请写出按此邻接表和介绍表和介绍的拓扑排序算法得到得到的
9、拓扑排序算法得到的拓扑序列。提示：先画出图形再运算。答案：1024357689107、如图形8-22所示的AOV网，求：（1）每个事件的最早发生时间和最迟发生时间。（2）完成整个工程至少需要多长时间。（3）每项活动的最早开始时间和最迟开始时间以及开始时间余量。（4）画岀由所有关键活动所构成的图。（5）哪些活动加速可使整个工程提前完成？答案:(1)设ve(i)和vl(i)分别表示事件i的最早发生时间和最迟发生时间ve(0)=0ve(1)=ve(0)+al=5ve(2)=ve(0)+a2=6ve(3)=Maxve(1)+a3,ve(2)+a4=Max8,12=12ve(4)=Maxve(2)+a5,ve(3)+a6=Max9,15=15ve(5)=ve(3)+a7=16ve(6)=Maxve(3)+a8,ve(4)+a9=Max16,16=16ve(7)=ve(4)+a10=17ve(8)=Maxve(6)+a12,ve(7)+a13=Max21,19=21ve(9)=Maxve(5)+a11,ve(8)+a14=Max20,23=23vl(9)=23vl(8)=vl(9)-a14=21vl(7)=vl(8)-a13=19vl(6)=vl(8)-a12=16vl(5)=vl(9)-a11=19vl(4)=Minvl(6)-a9,vl(7)-
