计算机软件基础第二章课后答案

2.8 已知线性表L（a1,a2,an）元素按递增有序排列，用向量作存储结构，试编写算法：删除表中在c与d（cd）之间的元素。 解：dele(L,n,c,d) 1. k=0 2. for i=1 to n 3. if Lic.and. Lid 4. kk+1 5. endif 6. if Lid 7. Li-kLi 8. endif 9. endfor 10. nn-k 11. return2.92.21 有一铁路交换站如题图（栈），火车从右边开进交换站，然后再开到左边，每节车厢均有编号如1，2，3，n。请问： （1）当n=3和n=4时有哪几种排序方式？哪几种排序方式不可能发生？ （2）当n=6时，这样的排列是否能发生？的排列是否能发生？ N=3时可能的出栈序列： 123 1S1X2S2X3S3X 132 1S1X2S3S3X2X 213 1S2S2X1X3S3X 231 1S2S2X3S3X1X 312 CAB 321 1S2S3S3X2X1XN=4，不可能的排列： 4312 4213 4231 4123 4132 3124 3142 3412 1423 2413 N=6时，可能 不可能 2.23 试画出表达式A*(B-D)/D+C*(E*F)执行过程中NS,OS栈的变化情况。B-D=T1D/T1=T2 T2*A=T3 E*F=T4 T4*C=T5 T5+T3=T6D)B-(*A;C+T2*A;)F*E(*C+T3;T4*C+T3;T5+T3;D/T1*A;T6;2.222.26 用三元组和带行辅助向量形式表示下列稀疏矩阵： （1）： （2）： （1）：三元组 带行辅助向量行列值1115142216651916328 (2): 三元组 i123456POS146778NUM321011行列值11815-131926211524628532-334436344248453 -1262274481791129429669930i123456789POS147101213141516NUM3332111142.28DEFIJKGLABC2.29前8行：1+2+4+8+16+32+64+128+256=511第9行：满的尾512 加起来超过10001000-511=489这是第9行的度为1的结点489/2=244余1256-244=12 12-1=11 这是第8行度为1的结点则度为1的结点数：n1=489+11=500度为2的结点数：n2=n1-1=499度为0的节点数：n0=11个节点只有非空左子树11个结点只有非空右子树第一种做法： N1=0/1，N是奇N1=0；N是偶N1=1 N=1000，N1=1 1000=N0+1+N2 1 N0=N2+1 2 N0=500，N2=499 第二法： N=1000，29N210 完全二叉的深度H=10 第10层叶子结点数：N01=N-(29-1)=1000-511=489 第10层总结点数：29 =512 第10层空的结点数：512-489=23 空结点数是奇数N1=1 第9层叶子结点数：N02=（23-1）/2=11 总叶子结点数：N0=N01+N02=489+11=500 N2=N-N0-N1=1000-500-1=499 度为3的树，1个度为1的结点，3个度为2的结点，4个度为3的结点，求叶子结点数？ N=N0+N1+N2+N3=N0+1+3+4 B=N-1=N1+2*N2+3*N3=1+2*3+3*4=19N=20N0=122.30 设一棵二叉树其中序和后序遍历为中序：BDCEAFHG 后序：DECBHGFA画出这棵二叉树的逻辑结构，并写出先序遍历结果。 先序遍历：ABCDEFGH其逻辑结构如下：ABFCDEGH1，2，3依次进栈，求可能的出栈序列。123 1S1X2S2X3S3X132 1S1X2S3S3X2X213 1S2S2X1X3S3X231 1S2S2X3S3X1X312 CAB321 1S2S3S3X2X1X1，2，3，44312 4213 4231 4123 41323124 3142 341214232413 ABCDEFGIJKL2.29 完全二叉树有1000个结点，问：叶子结点有多少？度为2的结点有多少？多少个结点只有非空的左子树？第一种做法：N1=0/1，N是奇N1=0；N是偶N1=1N=1000，N1=11000=N0+1+N2 1N0=N2+1 2N0=500，N2=499第二法：N=1000，29NV5-V2-V4-V6-V3-V1-V82.38 下图所示AOE网，求（1）每一事件最早开始时间和最晚开始时间；（2）该计划最早完成时间为多少。1开始2345768910结束a2=6a1=5a3=3a4=6a5=3a10=4a9=1a6=7a8=4a7=4a11=4a14=2a13=2a12=5活动最早最迟开始时间a1a2a3a4a5a6a7a8a9a10a11a12a13a14E00566121212191916202325L409616121916191923202325L-E404010074007000事件最早最迟开始时间V1V2V3V4V5V6V7V8V9V10VE05612191620232527VL09612192320232527画一棵以20个记录进行对分查找的判定树，并求等概率下的平均查找长度。1234567891011121314151617181920434524345143452453451015527134689121811131416191720ASL=(1+2*2+3*4+4*8+5*5)/20=?(13,29,01,23,44,55,20,84,27,68,11,10,79,14)下标0123456789101112131415161718数据6801205523442729131110847914次数11111121146175线性探测再散列：p=17,m=19ASL1=（