计算机软件基础第二章课后答案(共19页).doc
精选优质文档-倾情为你奉上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）：三元组 带行辅助向量行列值1115142216-15221123334-651916328 (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，29<N<210 à完全二叉的深度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=19àN=20àN0=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，29<N<210 à完全二叉的深度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=500N2=N-N0-N1=1000-500-1=499度为3的树，1个度为1的结点，3个度为2的结点，4个度为3的结点，求叶子结点数？N=N0+N1+N2+N3=N0+1+3+4B=N-1=N1+2*N2+3*N3=1+2*3+3*4=19àN=20àN0=122.30 设一棵二叉树的中序遍历和后序遍历结果为：中序：BDCEAFHG后序：DECBHGFA求先序？ABCDEFGHABFCDEGHDLR 先序LDR 中序LRD 后序2.32给定一组元素17，28，36，54，30，27，94，15，21，83，40，画出由此生成的二叉排序树。17283654302794152183402.33给定一组权值W=8，2，5，3，2，17，4，画出由此生成的哈夫曼树。下标数据双亲左孩子右孩子0810-1-1127-1-1259-1-1338-1-1427-1-151712-1-1648-1-174914871036991172101511801124129101241-15114117249154522873401111110000017： 08： 1115： 1014： 11013： 11002： 10002： 1001234 有一图如题图所示：（1）写出此图的邻接表与邻接矩阵；（2）由结点V1作深度优先搜索和广度优先搜索；（3）试说明上述搜索的用途。2101191918812172016713156145413邻接矩阵：12345678910111213141516171819201010010010000000000002101000000100000000003010100000001000000004001010000000010000005100101000000000000006000010100000001000007000001010000000010008100000101000000000009000000010100000001001001000000101000000000110000000001010000001120010000000101000000013000000000001010000011400010000000010100000150000010000000101000016000000000000001010011700000010000000010100180000000010000000101019000000000010000001012000000000000010010010邻接表：V1V2V3V4V5V6V7V8V9V10V11V12V13V14V15V16V17V18V19V20258 1310 2412 3514 146 5715 6817 179 81018 2911 101219 31113 121420 41315 61416 151720 71618 91719 111820 131619 DFS：V1，V2，V3，V4，V5，V6，V7，V8，V9，V10，V11，V12，V13，V14，V15，V16，V17，V18，V19，V20BFS：V1，V2，V5，V8，V3，V10，V4，V6，V7，V9，V12，V11，V14，V15，V18，V13，V19，V16，V17，V20235 有一有向图如下：（1）写出每一个结点的入度和出度各为多少；（2）写出此图的邻接矩阵与邻接表；顶点入度出度V130V222V312V421V521V614156423 V1V2V3V4V5V6V1000000V2100100V3010001V4001010V5100000V6110110V1V2V3V4V5V6 14 6 35 1 124 5 DFS：V6àV1àV2àV4àV3àV5BFS：V6àV1àV2àV4àV5àV3236 求下图中结点a到各结点之间的最短路径。abcdefhg23122412321237 求下图中所示AOV网所有可能的拓扑排序结果。21738546V1V2V3V4V5V6 0000013 8 68 4 8 V7 0V8 0 0 8 4 拓扑排序：V7->V5->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=（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专心-专注-专业
