数据结构复习之运算操作题(答案)

1、习题4-1运算题。1 .有6个元素A、B、C、D、E、F依次进栈，允许任何时候出栈，能否得到下列的每个出栈序列，若能，给出栈操作的过程，若不能，简述其理由(1) CDBEFA(2)ABEDFC(3)DCEABF(4)BAEFCD2 .有4个元素a,b,c,d依次进栈，任何时候都可以出栈，请写出所有可能的出栈序列和所有不存在的序列3 .用一维数组a7顺序储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有5个元素：23,45,67,80,34,其中，23为队首元素，front的值为3,请画出对应的存储状态，当连续做4次出队运算后，再让15,36,48元素依次进队，请再次画

2、出对应的存储状态。4 .用于顺序存储一个队列的数组的长度为N,队首和队尾指针分别为front和rear,写出求此队列长度（即所含元素个数）的公式参考答案(从简)1,(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,不符合后进先出原则。(4)不能：当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,0123456234567T front3648T rearL = ( N+rear-front ) % N8034Trear3415Tfront4,队列长度L的

4、计算公式为:说明：当rear>front时，L=rear-front=(N+rear-front)%N;当rear<front时，队列被分为两个部分，前部分在数组的尾部，其元素个数为N-1-front ,后部分在数组的首部，其元素个数为rear+1 ,所以:L二(rear+1+N-1-front)%N=(N+rear-front)%N;习题6-1运算题，再以广义表的形式给出该二叉搜索树1 .已知一组元素为(46,25,78,62,12,37,70,29),画出按元素排列顺序输入生成的一棵二叉搜索树，并写出对应的广义表2 .已知一棵搜索树的广义表表示为28(12(,16),49(34

5、(30),72(63),若从中依次删除72,12,49,28，等4个结点,试分别画出每删除一个结点后得到的图形表示的二叉搜索树表示.3 .从空堆中开始依次向小根堆中插入集合38,64,52,15,73,40,48,55,26,12中的每个元素，试以顺序表的形式给出每插入一个元素后堆的状态4 .已知一个堆为12,15,40,38,26,52,48,64,若从堆中依次删除4个元素，请给出每删除一个元素后的堆的状态5 .有7个带权结点，其权值分别为3,7,8,2,6,10,14,试以它们为叶子结点构造一棵哈夫曼树，给出其广义表表示.并计算出带权路径长度WPL.* 6.在一份电文中共使用5种字符，即a

6、.b.c.d.e,它们的出现频率依次为4,7,5,2,9,试画出对应的哈夫曼编码和传送电文的总长度* 7.一棵二叉树的广义表表示为A(B(,D(G,),)C(E(,H),F),试画出对应的图示二叉树* 9.一组关键字为(36,75,83,54,12,67,60,40,92,72),试依次插入结点分别生成一棵二叉搜索树，并求查找每个元素的平均查找长度广义表：46( 52 (12,37 ( 29 ) , 78 ( 62 ( ,70 )3.3838 6438 64 5215 38 5215 38 5215 38 4015 38 4015 38 4015 26 4012 15 406464 7364

7、73 5264 73 5255 73 5238 73 5238 26 524848 6448 64 5548 64 55 736.字符编码码长a00004b012c0013d00014e11A电文总长4X 4 + 7X2 + 5X3 + 2X4 + 9X12.删除72删除49删除28删除12Ml5.4.删除1215264038645248删除15263840486452删除2638 48 40 52 64删除3840 48 64 52广义表：(2,3 ) , 6 ) , 10 ) , ( ( 7 , 8 ) , 14 )WPL = ( 10 + 14 ) X 2 + ( 6 + 7 + 8 )

8、X3 + ( 2 + 3 )X4习题7-1运算题1、 如图7-13(a)和图7-13(b)所示，求：(1) 每一个图的二元组表示。(2) 图7-13(a)中每个顶点的度，以及每个顶点的所有邻接点和所有边。(3) 图7-13(b)中每个顶点的入度、出度和度，以及每顶点的所有入边的出边。(4) 图7-13(a)中从v0到v4的所有简单路径及相应路径长度。(5) 图7-13(b)中从v0到v4的所有简单路径及相应带权路径长度。i 11(b)有向图©石(a)无向图图713运算题图12、 根据图7-13(a)和图7-13(b),画出：(1) 每个图的邻接邻接矩阵。(2) 每个图的邻接表。(3)

9、 每个图的边集数组。3、 如图7-14所示，按下列条件分别写出从顶点v0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1) 假定它们均采用邻接矩阵表示。(2) 假定它们均采用邻接表表示，并且每个顶点邻接表中的结点都是按顶点序号从大到小的次序链接的。国P。(a)无向图1感-(b)有向图图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出发，给

10、出邻接矩阵表示图的深度优先和广度优先搜索遍历的顶点序列。(3) 假定从顶点0出发，给出邻接表表示的图的深度优先和广度优先搜索遍历的顶点序列，假定每个顶点邻接表中的结点都是按顶点序号从大到小的次序链接的。答案3.依照矩阵和邻接表所产生的两种遍历序列各自相等。a图：深度优先遍历：0128345679广度优先遍历：0142738695b图：深度优先遍历：014587236广度优先遍历：0134267584.深度优先遍历：036741258广度优先遍历：034671285习题8-1运算题1、如图形8-18所示，针对有向图操作如下。(1)画出最小生成树并求出它的权。(2)从顶点v0出发，要据普里姆算法求

11、出最小生成树的过程中，把依次得到的各条边按序写出来。(3)根据克鲁斯卡算法求出最小生成树的过程中，把依次得到的各条边写出来。(2)普里姆算法的边的序列：(0,1),(1,6),(6,2),(2,3),(3,4),(4,5)(3)克鲁斯卡算法的边的序列：(1,6),(2,3),(0,1),(6,2),(3,4),(4,5)2、如图8-19所示，利用狄克特拉算法求从顶点V0到其余各顶点的最短路径，并画出对应的图形表示。3、已知一个图的二元组表示为：V= 0, 1 , 2, 3, 4, 5, 6, 7E=(0,1)8,(0,3)2,(0,5)10,(1,2)6,(1,4)20,(1,6)12,(2,

12、4)10,(2,7)15,(3,5)5,(3,6)7,(4,7)4,(5,6)6,(6,7)8(1)按照克鲁斯卡尔算法求出最小生成树，写出依次得到的各条边。(2)按照狄克斯特算法求从顶点0到其余各顶点的最短路径。(1)(0,3),(4,7),(3,5),(5,6),(1,2),(0,1),(6,7)(2)0-3:(0,3)0-5:(0,3),(3,5)0-1: ( 0 ,1 )0-6: ( 0 ,3 ),0-2: ( 0 ,1 ),0-7： ( 0 ,3 ),0"： ( 0 ,3 ),(3 ,6 )(1 ,2 )(3 ,6), ( 6 ,7 )(3 ,6), ( 6 ,7), (7

13、,4 )4、如图形8-20所示，利用弗洛伊德算法求每对顶点之间的最短路径，即仿照如图形图 821AOV网答案：1 4 0 2 3 5 7 6 8 98-8的运算过程，给出从邻接矩阵出发每加入一个中间每加入一个中间点后矩阵状态。5如图形8-21所示，试给出一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出唯一一种拓扑序列6一个AOV网的二元组表示为：V=0,1,2,3,4,5,6,7,8,9,10E=<0,2>,<0,4>,<1,2>,<1,5>,<2,4>,<3,5>

14、,<4,6>,<4,7>,<5,7>,<6,8>,<7,6>,<7,8>,<7,9>,<8,10>,<9,10>在此AOV网的邻接表存储中，若各顶点邻接表中的边结点是按照邻接顶点序号从大到小链接的，请写出按此邻接表和介绍表和介绍的拓扑排序算法得到得到的拓扑排序算法得到的拓扑序列。提示：先画出图形再运算。答案:1024357689107、如图形8-22所示的AOV网，求：(1)每个事件的最早发生时间和最迟发生时间。(2)完成整个工程至少需要多长时间。(3)每项活动的最早开始时间和最迟开始时

15、间以及开始时间余量。(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)+a1

16、3=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)-a10=Min15,17=15vl(3)=Minvl(5)a7,vl(6)a8,vl(4)a3=Min15,12,12=12vl(2)=Minvl(3)-a4,vl(4)-a5=Min6,12=6vl(1)=vl(3)-a3=9vl(0)=0(2)因为ve(9)=23,所以完成整个工程

17、至少的时间为23。(3)设e(i)和l(i)分别为活动i的最早开始时间和最迟开始时间，则l(i)e(i)为每个活动的开始时间余量。活动i由弧<j,k>表示。根据(1)题所得的结果和关系e(i)=ve(j)、l(i)=vl(k)w<j,k>,得出下表:活动ell-e<0,1>ve(0)=0vl(1)-a1=44<0,2>ve(0)=0vl(2)a2=00<1,3>ve(1)=5vl(3)a3=94<2,3>ve(2)=6vl(3)a4=60<2,4>ve(2)=6vl(4)-a5=126<3,4>ve

18、(3)=12vl(4)-a6=120<3,5>ve(3)=12vl(5)-a7=153<3,6>ve(3)=12vl(6)-a8=120<4,6>ve(4)=15vl(6)-a9=150<4,7>ve(4)=15vl(7)a10=172<5,9>ve(5)=16vl(9)a11=193<6,8>ve(6)=16vl(8)a12=160<7,8>ve(7)=17vl(8)a13=192<8,9>ve(7)=21vl(9)a14=210(4)e(i)等于l(i)的活动(即开始时间剩余量为0的活动)为关键

19、活动，所以图中的关键活动为：<0,2>,<2,3>,<3,4>,<3,6>,<4,6>,<6,8>,<8,9>。所以图中的关键路径有两条：<0,2>,<2,3>,<3,4>,<4,6>,<6,8>,<8,9><0,2>,<2,3>,<3,6>,<6,8>,<8,9>它们的路径长度都为23。所有关键活动所构成的图为：< 3,4>, < 3,6>, < 4

20、,6>, < 6,8>, < 8,9>可以整个工程提前完成。(5)关键活动决定整个工程的持续时间。所以加速关键活动<0,2>,<2,3>,9-1运算题1. 若查找有序表A30中每一元素的概率相等，试分别求出进行顺序，二分和分块(若被分为5块，每块6个元素)查找每一个元素时的平均查找长度.2. 一个待散列存储的数据集合为32,75,29,63,48,94,25,46,18,70,56,散列地址空间为HT13,若采用除留余数法构造散列函数和线性探查法处理冲突，试求每一元素白散列地址，画出最后得到的散列表，求平均查找长度.3. 设有一个含有200

21、个元素的表待散列存储，用线性探查法处理冲突，按关键字查询时找到一个元素的平均查找长度(即平均探查次数)不能超过1.5，则散列表的长度应至少为多少？1 .若进行顺序查找，将n=30代入公式ASL=(n+1)/2得ASL=15.5。若进行二分(折半)查找，将n=30代入公式ASL=""出"'得ASL=4.1也可以通过二叉判定树来确定ASL。若进行分块查找，由于原表有序，所以可分两种情况讨论：若用顺序查找确定所在块，则将s=6,n=30代入公式ASL=(n/s+s)/2+1中，得ASL=6.5若用二分查找确定所在块，则将s=6,n=30代入公式1f2得ASL=5

22、.62 .一次探测成功时，H(key)=key%13线性探测再散列的哈希函数为Hi=(H(key)+di)%m(di=1,2,3,，m-1且1ViVm-1)32%13=6探测1次75%13=J0探测1次29%13=3探测1次63%13=11探测1次48%13=9探测1次94%13=3有冲突，再探测H1=(3+1)%13=4探测2次25%13=J2探测1次46%13=7探测1次18%13=_5探测1次70%13=5有冲突，再探测H1=(5+1)%13=6有冲突，再探测出=(6+2)%13=8探测3次56%13=4有冲突，再探测H1=(4+1)%13=5有冲突，再探测H2=(5+2)%13=7有冲

23、突，再探测H3=(7+3)%13=10有冲突，再探测H4=(10+4)%13=1探测5次ASL=(1+1+1+1+1+2+1+1+1+3+5)/11=1.63X3275296348942546187056H(X)614冲突后线性探查的次数124处理冲突后的实际地址4810123456789101112562994563253.对于线性探测再散列，ASLa=n/m,n为记录数，m为哈希表长（散列表长）。联立以上两式得:2ASL-U10-1运算题已知一组元素的排序码为：（46,74,16,53,14,26,40,38,86,65,27,34）1 .利用直接插入排序的方法写出每次向前面有序表插入一个

24、元素后的排列结果。2 .利用直接选择排序方法写出每次选择和交换后的排列结果。3 .利用堆排序的方法写出在构成初始堆和利用堆排序的过程中，每次筛运算后的排列结果，并画出初始堆所对应的完全二叉树。4 .利用快速排序的方法写出每一层划分后的排列结果，并画出此快速排列得到的二叉搜索树。5 .利用归并排序的方法写出每一趟二路归并排序后的结果。运算操作题10-1-1第1趟：467416531426403886652734第2趟：164674531426403886652734第3趟：164653741426403886652734第4趟：141646537426403886652734第5趟：141626

25、465374403886652734第6趟：141626404653743886652734第7趟：141626384046537486652734第8趟：141626384046537486652734第9趟：141626384046536574862734第10趟:141626273840465365748634第11趟:141626273438404653657486红色数字为已经排好序的部分红色数字为已经排好序的部分,蓝色数字为每趟结束前被交换的数据（和最后一个红色数字交换）第 1 趟：14 74 16 5346 26 40 38 86 65 27 34第 2 趟：14 _16 74

26、5346 26 40 38 86 65 27 34第 3 趟：14 _16_26 5346 74 40 38 86 65 27 34第 4 趟：14 16 26 2746 74 40 38 86 65 53 34第 5 趟：14 16 26 2734 74 40 38 86 65 53 46第 6 趟：14 _16_26 _27_34_38 40 74 86 65 53 46第 7 趟：14 _16_26 _27_34_38 _40 74 86 65 53 46第 8 趟：14 16 26 2734 38 40 46 86 65 53 74第 9 趟：14 16 26 2734 38 40 46