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

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 ，请画出 对应的存储状

2、态，当连续做 4 次出队运算后，再让15， 36，48 元素依次进队，请再次画出对应的存储状态。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

3、(S,D), push(S,E), pop(S), pop(S), push(S,F), pop(S), pop(S).(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

4、.3，01 23 45 6803423 45 67f rearf front34 15f front36 48f rear4，队列长度 L 的计算公式为：L = ( N+rear-front ) % N 说明：当 rear>front 时， L = rear - front = ( N+rear-front ) % N;N-1-front ,后部分在数组的首部，其元素个数为 rear+1 , 所以：当 rear<front 时，队列被分为两个部分，前部分在数组的尾部，其元素个数为L =( rear+1+N-1 - front )%N= ( N+rear-front ) % N; 习

5、题6-1运算题1.已知一组元素为(46,25,78,62,12,37,70,29),画出按元素排列顺序输入生成的一棵二叉搜索树,再以广义表的形式给出该二叉搜索树2.已知一棵搜索树的广义表表示为28(12(,16),49(34(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,若

6、从堆中依次删除4个元素,请给出每删除一个元素后的堆的状态5. 有7个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶子结点构造一棵哈夫曼树,给出其广义表表示.并计算出带权路径长度 WPL.*6.在一份电文中共使用 5种字符，即a.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),试依次插入结点分别生成一棵二叉搜索树，并求查找每个元素的平均查找长度广义

7、表：46( 52 (12,37 ( 29 ) , 78 ( 62 ( ,70 )删除72删除12删除49删除2812.：4?16：科.28：1 /“ J434/ in3H2.384.3864删除123864521526403815385264删除15153852647326384048153840647352删除26153840647352 4838484052153840557352 48 64删除38152640387352 48 64 5540486452121540382652 48 64 55 733.5.广义表：(2,3 ) , 6 ) , 10 ) , ( ( 7 , 8 ) ,

8、 14 )WPL = ( 10 + 14 ) X 2 + ( 6 + 7 + 8 ) X 3 + ( 2 + 3 ) X 46.字符编码码长a00004b012c0013d00014e11电文总长=4X 4 + 7 X2 + 5 X 3 + 2X 4 + 9X1习题7-1运算题1、如图7-13 （ a）和图7-13 （b）所示，求：（1）每一个图的二元组表示。（2）图7-13（a）中每个顶点的度，以及每个顶点的所有邻接点和所有边。（3）图7-13（ b）中每个顶点的入度、出度和度，以及每顶点的所有入边的出边。（4）图7-13（a）中从vO到v4的所有简单路径及相应路径长度。（5）图7-13（

9、b）中从vO到v4的所有简单路径及相应带权路径长度。©（b）有向图（a）无向图图713运算题图12、根据图7-13 （ a）和图7-13 （ b）,画出：（1）每个图的邻接邻接矩阵。（2）每个图的邻接表。（3）每个图的边集数组。3、如图7-14所示，按下列条件分别写出从顶点v0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。（1）假定它们均采用邻接矩阵表示。（2）假定它们均采用邻接表表示，并且每个顶点邻接表中的结点都是按顶点序号从大到小的次序链接的。（a）无向图（b）有向图图7 14运算题图24、已知一个图的二元组表示如下:V=0, 1, 2，3, 4，5，6

10、, 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图：深度优先遍历：0 1 2 8 3 4 5 6 7 9广度优先遍历：0 1 4 2 7 3 8

11、6 9 5b图：深度优先遍历：0 1 4 5 8 7 2 3 6广度优先遍历：0 1 3 4 2 6 7 5 84.深度优先遍历：0 3 6 7 4 1 2 5 8广度优先遍历：0 3 4 6 7 1 2 8 5习题8-1运算题1、如图形8-18所示,针对有向图操作如下。(1) 画出最小生成树并求出它的权。(2) 从顶点vO出发，要据普里姆算法求出最小生成树的过程中，把依次得到的各条边按序写出来。(3) 根据克鲁斯卡算法求出最小生成树的过程中，把依次得到的各条边写出来。(2) 普里姆算法的边的序列：(0,1 )，( 1 ,6 )，( 6 ,2 )，( 2 ,3 )， ( 3 ,4 )，( 4

12、,5 )(3) 克鲁斯卡算法的边的序列： (1 ,6 )，( 2 ,3 )，( 0 ,1 ) ，( 6 ,2 )， ( 3 ,4 )，( 4 ,5 )2、 如图8-19所示，利用狄克特拉算法求从顶点V0到其余各顶点的最短路径，并画出对应的图形表示。不画图了，只写出边的序列。以下各点的最短路径是按顺序生成的：0 3:< 0,3>Of 5:< 0,5>0 1:< 0,3>,< 3,1>0 6:< 0,5>,< 5,6>0 4:< 0,5>,< 5,6>,< 6,4>0 2:< 0,5&

13、gt;,< 5,6>,< 6,4>,< 4,2>0 7:< 0,5>,< 5,6>,< 6,4>,< 4,2> , < 2,7>3、 已知一个图的二元组表示为：V= 0 , 1 , 2, 3 , 4 , 5 , 6 , 7 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)

14、 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 ),(3 ,6 )0 2:(0 ,1 ),(1 ,2 )0 7:(0 ,3 ),(3 ,6 ),(6 ,7 )0 4:(0 ,3 ),(3 ,6 ),(6 ,7 ), ( 7 ,4 )4、如图形8-20所示，利用

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

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

17、最早开始时间和最迟开始时间以及开始时间余量。(4) 画出由所有关键活动所构成的图。(5) 哪些活动加速可使整个工程提前完成？图 8 22 AOE 网答案：(1 )设ve( i )和vl( i ) 分别表示事件i的最早发生时间和最迟发生时间ve( 0 ) = 0ve( 1 ) = ve( 0 ) + al = 5ve( 2 ) = ve( 0 ) + a2 = 6ve( 3 ) = Max ve( 1 ) + a3 , ve( 2 )+a4 = Max8,12 =12ve( 4 ) = Max ve( 2 ) + a5 , ve( 3 )+a6 = Max9,15 =15ve( 5 ) = ve

18、( 3 ) + a7 = 16ve( 6 ) = Max ve( 3 ) + a8 , ve( 4 ) + a9 = Max 16,16 = 16ve( 7 ) = ve( 4 ) + a10 = 17ve( 8 ) = Max ve( 6 ) + a12 , ve( 7 ) + a13 = Max 21 , 19 = 21ve( 9 ) = Max ve( 5 ) + a11 , ve( 8 ) + a14 = Max 20,23 = 23vl( 9 ) = 23 vl( 8 ) = vl( 9 ) vl( 7 ) = vl( 8 ) vl( 6 ) = vl( 8 ) vl( 5 ) =

19、vl( 9 ) vl( 4 ) = Min vl( 6 ) vl( 3 ) = Min vl( 5 ) vl( 2 ) = Min vl( 3 ) vl( 1 ) = vl( 3 )vl( 0 ) = 0-a14 =21-a13 =19-a12 =16-a11 =19-a9 , vl( 7 ) - a10 = Min 15 , 17 = 15-a7 , vl( 6 )-a8, vl( 4 )-a3 = Min 15 , 12, 12 = 12-a4 , vl( 4 )-a5 = Min 6,12 = 6-a3 = 9(2 ) 因为ve( 9 ) = 23，所以完成整个工程至少的时间为23(3

20、) 设e( i )和1( i ) 分别为活动i的最早开始时间和最迟开始时间，则l( i ) e( i )为每个活动的开始时间余量。活动i由弧< j,k >表示。根据(1 )题所得的结果和关系e( i ) = ve( j )、1( i ) = vl( k ) w<j,k>，得出下表:活动el-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

21、=60< 2,4>ve( 2 ) = 6vl( 4 ) a5=126< 3,4>ve(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=16

22、0< 7,8>ve( 7 ) = 17vl( 8 )a13=192< 8,9>ve( 7 ) = 21vl( 9 )a14=210(4 ) e( i ) 等于l( i ) 的活动(即开始时间剩余量为0的活动)为关键活动，所以图中的关键活动为：< 0,2> , < 2,3> , < 3,4> , < 3,6> , < 4,6> , < 6,8> ,< 8,9>。所以图中的关键路径有两条： < 0,2>, < 2,3> ,< 3,4>, < 4,6&

23、gt; ,< 6,8>, < 8,9> < 0,2>, < 2,3> ,< 3,6>, < 6,8> ,< 8,9>它们的路径长度都为23。所有关键活动所构成的图为：(5 )关键活动决定整个工程的持续时间。所以加速关键活动< 0,2> , < 2,3> ,< 3,4>< 3,6> , < 4,6> , < 6,8> , < 8,9>可以整个工程提前完成9-1运算题1.若查找有序表 A30中每一元素的概率相等,试分别求出进行顺序,

24、二分和分块（若被分为5块,每块6个元素）查找每一个元素时的平均查找长度2. 一个待散列存储的数据集合为32,75,29,63,48,94,25,46,18,70,56,散列地址空间为HT13,若采用除留余数法构造散列函数和线性探查法处理冲突,试求每一元素的散列地址,画出最后得到的散列表，求平均查找长度则散列表的长度应至少为多3. 设有一个含有200个元素的表待散列存储，用线性探查法处理冲突，按关键字查询时找到一个元素的平均查找长度（即平均探查次数）不能超过1.5,少？1.若进行顺序查找，将n=30代入公式 ASL = （n + 1） / 2 得ASL = 15.5若进行二分（折半）查找，将n=

25、30代入公式ASL=得 ASL = 4.1也可以通过二叉判定树来确定ASL。若进行分块查找，由于原表有序，所以可分两种情况讨论: 若用顺序查找确定所在块，则将s=6，n=30代入公式ASL = （ n/s + s ）/2 + 1中，得ASL = 6.5若用二分查找确定所在块，则将s=6，n=30代入公式A3L a(+!) + y得 ASL = 5.62 .一次探测成功时，H(key) = key %13线性探测再散列的哈希函数为H =( H( key ) + d i ) %m (d i =1, 2, 3,，m-1且1 < i < m-1)32%13 =6探测1次75%13 =10探

26、测1次29%13 =3探测1次63%13=11探测1次48%13= 9 探测1次94%13= 3有冲突，再探测H1= (3+1)%13=4 探测2次25%13= 12 探测1次46%13= 7探测1次18%13= 5探测1次70%13=5有冲突，再探测H1：二(5+1)%13 二:6有冲突，再探测H2= (6+2)%13 = 8探测3次56%13=4有冲突，再探测H1：二(4+1)%13 二:5有冲突，再探测H2= (5+2)%13 = 7有冲突，再探测H3 =(7+3)%13 =10有冲突，再探测H4= (10+4)%13 =1探测5次ASL =(1 + 1 + 1 + 1 + 1 + 2

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

28、入一个元素后的排列结果。2. 利用直接选择排序方法写出每次选择和交换后的排列结果。3. 利用堆排序的方法写出在构成初始堆和利用堆排序的过程中，每次筛运算后的排列结果，并画出初始堆所对应的完全二叉树。4. 利用快速排序的方法写出每一层划分后的排列结果，并画出此快速排列得到的二叉搜索树。5. 利用归并排序的方法写出每一趟二路归并排序后的结果。运算操作题10-1-1红色数字为已经排好序的部分第 1 趟：46 7416 53 14 26 40 38 86 65 27 34第 2 趟：16 46 7453 14 26 40 38 86 65 27 34第 3 趟：16 46 5374 14 26 40

29、38 86 65 27 34第 4 趟：1416 46 5374 26 40 38 86 65 27 34第 5 趟：1416 2646 5374 40 38 86 65 27 34第 6 趟：14_16 26 40 _46 53 _74 38 86 65 27 34第 7 趟：1416263840465374 86 65 27 34第 8 趟：1416263840465374 86 65 27 34第 9 趟：14_16263840_4653_65_74_86 27 34第 10 趟：1416 26 2738 4046 53657486 34第 11 趟：1416 26 273438 404

30、6 53657486运算操作题10-1-2红色数字为已经排好序的部分，蓝色数字为每趟结束前被交换的数据（和最后一个红色数字交换）第1趟：147416534626403886652734第2趟：141674534626403886652734第3趟：141626534674403886652734第4趟：141626274674403886655334第5趟：141626273474403886655346第6趟：141626273438407486655346第7趟：141626273438407486655346第8趟：141626273438404686655374第9趟：141626273438404653658674第10趟:141626273438404653658674第11趟:141626273438404