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

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

3、(S,C), push(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

4、; dacb; dbac; dbca; dcab.3，0123456-8034234567 rear front34153648 front rear4，队列长度L 的计算公式为：L = ( N+rear-front ) % N 说明：当 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-fro

5、nt ) % N; . 习题 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.已知一个堆为

6、 12,15,40,38,26,52,48,64,若从堆中依次删除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

7、,72),试依次插入结点分别生成一棵二叉搜索树，并求查找每个元素的平均查找长度.1.2.删除 72删除 12删除 49删除 28广义表： 46( 52 (12 , 37 ( 29 ) , 78 ( 62 ( ,70 )3.385.4.3864删除 123864521526403864524815385264删除 151538526473263840486452153840647352删除 261538406473524838484052641538405573524864删除 38广义表： (2,3),6),10),(7,8),14)15264038735248645540486452WPL=

8、(10+14) ×2+(6+7+8) ×3+(2+3)×4121540382652486455736.7.9.字符编码码长a00004b012×2+2×3+3×4+2×5)/10ASL=(1+2c0013d00014e11. 电文总长=4×4+7×2+5×3+2×4+9×1. 习题 7-1 运算题1、如图 7-13 （ a）和图7-13 （ b）所示，求：（ 1）每一个图的二元组表示。（ 2）图 7-13 （a ）中每个顶点的度，以及每个顶点的所有邻接点和所有边。（ 3）图

9、7-13 （b ）中每个顶点的入度、出度和度，以及每顶点的所有入边的出边。（ 4）图 7-13 （a ）中从 v0 到 v4 的所有简单路径及相应路径长度。（ 5）图 7-13 （b ）中从 v0 到 v4 的所有简单路径及相应带权路径长度。（ a）无向图（ b）有向图图 7 13 运算题图 12、根据图7-13 （ a）和图 7-13 （b ），画出：（ 1）每个图的邻接邻接矩阵。（ 2）每个图的邻接表。（ 3）每个图的边集数组。3、如图 7-14 所示，按下列条件分别写出从顶点v0 出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。（ 1）假定它们均采用邻接矩阵表示。

10、（ 2）假定它们均采用邻接表表示，并且每个顶点邻接表中的结点都是按顶点序号从大到小的次序链接的。（ a）无向图（ b ）有向图图 7 14 运算题图 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出发，给出邻接表表示的图的深度优先和广度优先搜索遍历的顶

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

12、依次得到的各条边写出来。图8 18 无向带权图(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)，(4,5)2、如图8-19 所示，利用狄克特拉算法求从顶点V0 到其余各顶点的最短路径，并画出对应的图形表示。不画图了，只写出边的序列。以下各点的最短路径是按顺序生成的：0 3： < 0,3>0 5： < 0,5>0 1： < 0,3> , < 3,1>0 6： < 0,5> , < 5,6&

13、gt;0 4： < 0,5> , < 5,6> , < 6,4>0 2： < 0,5> , < 5,6> , < 6,4> , < 4,2>图8 19 有向带权图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）

14、 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)03：(0,3)05：(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 所示，利用弗洛伊德算法

15、求每对顶点之间的最短路径，即仿照如图形8-8 的运算过程，给出从邻接矩阵出发每加入一个中间每加入一个中间点后矩阵状态。图8 20 有向带权图5 如图形8-21 所示，试给出一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出唯一一种拓扑序列。图821AOV网答案一个 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网的邻接表存储中,若各顶点邻接表中的边结点是按照邻接顶点序号从大到小链接的,请写出按此邻接表和介绍表和介绍的拓扑排序算法得到得到的拓扑排序算法得到的拓扑序列。提示：先画出图形再运算。答案:1024357689107、如图形8-22 所示的 AOV 网，求：（ 1 ）每个事件的最早发生时间和最迟发生时间。（ 2 ）完成整个工程至少需要多长时间。（ 3 ）每项活动的最早开

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

18、= 15ve( 5 ) = ve( 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 ) = 23vl( 8 ) = vl( 9 ) a14 = 21vl( 7 ) = vl( 8 ) a

19、13 = 19vl( 6 ) = vl( 8 ) a12 = 16vl( 5 ) = vl( 9 ) a11 = 19vl( 4 ) = Min vl( 6 )a9 , vl( 7 ) - a10 = Min 15 , 17 = 15vl( 3 ) = Min vl( 5 )a7 , vl( 6 ) a8, vl( 4 ) a3 = Min 15 , 12, 12 = 12vl( 2 ) = Min vl( 3 )a4 , vl( 4 ) a5 = Min 6 , 12 = 6vl( 1 ) = vl( 3 ) a3 = 9vl( 0 ) = 0( 2 ) 因为 ve( 9 ) = 23，所以

20、完成整个工程至少的时间为 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

21、< 2,3>ve( 2 ) = 6vl( 3 ) a4=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=

22、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 的活动)为关键活动，所以图中的关键活动为：< 0,2>，< 2,3>， < 3,4>，< 3,6> ，< 4,6> ，< 6,8> ，< 8,9>。所以图中的关键路径有两条： < 0,2&g

23、t;，< 2,3>，< 3,4>，< 4,6>，< 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.

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

25、SL = (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 代入公式得 ASL = 5.62 .一次探测成功时，H(key) = key %13线性探测再散列的哈希函数为Hi =( H( key ) + d i) %m (d i =1， 2 ，

26、3 ， ， m-1 且 1 i m-1)32%13 = 6探测 1次75%13 = 10探测 1次29%13 = 3探测 1次63%13= 11探测1 次48%13= 9探测1 次94%13= 3有冲突，再探测H 1= (3+1)%13 = 4探测 2次25%13= 12探测1 次46%13= 7探测1 次18%13= 5探测1 次70%13=5有冲突，再探测H 1= (5+1)%13 = 6有冲突，再探测H2= (6+2)%13 = 8探测3 次.56%13=4有冲突，再探测H 1= (4+1)%13 = 5有冲突，再探测H2= (5+2)%13 = 7有冲突，再探测H3= (7+3)%13

27、 = 10有冲突，再探测H4= (10+4)%13 =1探测 5次ASL=(1+1+1+1+1+2+1+1+1+3+5)/11=1.63X3275296348942546187056H(X)61031193127554冲突后 线性探查的次数124处理冲突后 的实际地址481012345678910111256299418324670487563253.对于线性探测再散列，ASL， =n/m ， n 为记录数，m 为哈希表长(散列表长 )。联立以上两式得：10-1 运算题已知一组元素的排序码为：（ 46 ， 74， 16 ， 53， 14 ， 26， 40， 38 ， 86， 65， 27 ，

28、34 ）1利用直接插入排序的方法写出每次向前面有序表插入一个元素后的排列结果。2利用直接选择排序方法写出每次选择和交换后的排列结果。3利用堆排序的方法写出在构成初始堆和利用堆排序的过程中，每次筛运算后的排列结果，并画出初始堆所对应的完全二叉树。4利用快速排序的方法写出每一层划分后的排列结果，并画出此快速排列得到的二叉搜索树。5利用归并排序的方法写出每一趟二路归并排序后的结果。运算操作题 10-1-2运算操作题 10-1-1红色数字为已经排好序的部分，蓝色数字为每趟结束前被交换的数据红色数字为已经排好序的部分（和最后一个红色数字交换）第1趟：467416531426403886652734第1趟

29、：147416534626403886652734第2趟：164674531426403886652734第2趟：141674534626403886652734第3趟：164653741426403886652734第3趟：141626534674403886652734第4趟：141646537426403886652734第4趟：141626274674403886655334第5趟：141626465374403886652734第5趟：141626273474403886655346第6趟：141626404653743886652734第6趟：141626273438407486655346第7趟：141626384046537486652734第7趟：141626273438407486655346第8趟：141626384046