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

《计算机软件基础第二章课后答案.docx》由会员分享，可在线阅读，更多相关《计算机软件基础第二章课后答案.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.8 线性表La1,a2,an元素按递增有序排列，用向量作存储构造，试编写算法：删除表中在c及dcd之间的元素。 解：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.21 有一铁路交换站如题图栈，火车从右边开进交换站，然后再开到左边，每节车厢均有编号如1，2，3，n。请问： 1当n=3和n=4时有哪几种排序方式？哪几种排序方式不行能发生？ 2当n=6时，325641这样的排列是

2、否能发生？154623的排列是否能发生？ 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时，325641可能 154623不行能 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=

3、T6D)B-(*A;C+T2*A;)F*E(*C+T3;T4*C+T3;T5+T3;D/T1*A;T6;2.26 用三元组和带行协助向量形式表示以下稀疏矩阵： 1： 2： 1：三元组 带行协助向量行列值1115142216-15221123334-651916328 (2): 三元组 i123456POS146778NUM321011行列值11815-131926211524628532-334436344248453 -1262274481791129429669930i123456789POS147101213141516NUM333211114DEFIJKGLABC前8行：1+2+4+8

4、+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层叶

5、子结点数：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 后序：DE

6、CBHGFA画出这棵二叉树的逻辑构造，并写出先序遍历结果。 先序遍历：ABCDEFGH其逻辑构造如下：ABFCDEGH1，2，3依次进栈，求可能的出栈序列。123 1S1X2S2X3S3X132 1S1X2S3S3X2X213 1S2S2X1X3S3X231 1S2S2X3S3X1X312 CAB321 1S2S3S3X2X1X1，2，3，44312 4213 4231 4123 41323124 3142 341214232413325641 154623ABCDEFGIJKL2.29 完全二叉树有1000个结点，问：叶子结点有多少？度为2的结点有多少？多少个结点只有非空的左子树？第一种做法

7、：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活动最早最迟开场时间a1a2a3a4a5a6a7a8a9a10a11a12a13a14E00566121212191916202325L409

8、616121916191923202325L-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=1+1+1+1+1+1+2+1+1+4+6+1+7+5/14=33/14平方探测再散列：(13,29,01,23,44,55,20,84,27,68,11,10,79,14)ASL2=(1+1+1+1+1+5+3+1+2+1+1+1+4+1)/14=24/14