数据结构作业参考答案.doc

第一章1.10 1.12 (1)和(4)正确.1.13 n450第二章2.11Status Insert_SqList(SqList &va,int x)/把x插入递增有序表va中if(va.length+1va.listsize) return ERROR;va.length+;for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;return OK;/Insert_SqList 2.21 void reverse(SqList &A)/顺序表的就地逆置for(i=1,j=A.length;ij;i+,j-)A.elemiA.elemj;/reverse 第三章3.12 输出结果char3.13 利用栈作辅助,将队列中的数据进行逆置.第四章4.3 Strlength(s)=14 Strlength(t)=4 SubString(s,8,7)=STUDEBT SubString(t,2,1)=o Index(s,A)=3 Index(s,t)=0 Replace(s,STUDENT,9)=I AM A WORKER Concat(Substring(s,6,2),concat(t,SubString(s,7,8)=A GOOD STUDENT第五章5.1(1)288 (2)1282 (3)1072 (4)12765.2(1)100 (2) 776 (3)1784 (4)44165.3 (0,0,0,0) (1,0,0,0) (0,1,0,0) (1,1,0,0)(1,1,2,2)5.121 1 1 1 0 e11 1 1 11110 c0 b bb0 a1 0 d1 1 11 0 e0 d0 f1 1 11 0 b11 11 0 a5.13 (1) (x,(y),(),(),(z)(2) (a,b,(),(),(a,(b),()第六章6.1(1)A (2) DMNFJKL (3) C (4)AC (5)JK (6) IMN (7)结点的兄弟结点的兄弟（）（）（）6.2 树两种二叉树五种6.5叶子节点数为 n0 =1+ki=1 (i-1)ni6.6 总结点数 为n, 设度为k 的节点数为 nk , 度为0 的节点数为n-nk , 则有 n=knk +1 nk =(n-1)/k 所以叶子节点为 n-(n-1)/k6.7 能答到最大深度的是单支树,其深度为n,深度最小的是完全k叉树.6.8 略6.17A6.19 （b）BCABCEDIFJGKH（d）6.21 AEBDHKGJCFIM6.22(1)先根序序列: A BC ABCEIJFGKHD(2)后根序序列: CBABIJEFKGHCDA6.23GFHCKBJDAEI6.246.26 10.60.40.280.320.190.210.110.170.050.060.070.100.020.03则对映的哈夫曼编码频率0.070.190.020.060.320.030.210.01哈夫曼编码001010000000001010000111011等长编码000001010011100101110111哈夫曼编码WPLHF 2.61等长编码WPLEQ 36.27EBFADCHGIKJ6.28ABCGDIHJKFE6.29JABDGCHFIE第七章7.1(1)顶点123456入度321122出度022313(2)0 0 0 0 0 01 0 0 1 0 00 1 0 0 0 10 0 1 0 1 11 0 0 0 0 01 1 0 0 1 0461 5653 21 2 1 (3) 1 2 3 4 5 66 4 643 2 4 3 652 (4) 123456 (5) 有3个强连同分量632451 7.5深度优先生成树:1734859610002 广度优先生成树efdghcb7.7 (1) (2)邻接表7.9561234516234512634512364156234152634152364其中，第一个序列为算法topsort所求的序列。7.10顶点vevi00A120B624C1726D319E3434F48G33H1313I17J3131K22224444边ejj-e(,A)0 1919(,B)01818(,D)01616(,F)044(,G)000(,I)066(A,C)12019(B,C)62418(D,C)31916(D,E)32623(D,J)32522(F,E)42319(F,H)484(G,)32320(G,H)330(I,H)176(C,E)17269(H,C)13229(H,J)132714(H,K)13130(K,J)22220(J,E)31310(J,)31321(E,)34340关键路径只有一条（，G，H，K，J，E，）7.11终点DistbcdefgS(终点集)K=115（a,b）2(a,c)12(a,d)a,cK=215（a,b）12(a,d)10(a,c,e)6(a,c,f)a,c,fK=315（a,b）11(a,c,f,d)10(a,c,e)16(a,c,f,g)a,c,f,eK=415（a,b）11(a,c,f,d)16(a,c,f,g)a,c.f.e.dK=515（a,b）14(a,c,f,d,g)a,c.f.e.d.gK=615（a,b）a,c,f,e,d,g,b第九章9.9(1)ASLsucc=1/12(11+22+33+43+52+61)=42/12=7/2JanAprAugJuneDecMayJulyNovFebOctMarSept(2) Apr Aug Dec Feb Jan July June Mar May Nov Oct Sept 3 4 2 3 4 1 3 4 2 4 3 4ASLsucc=1/12(11+22+34+45)=37/12(3)平衡二叉树:ASL=1/12(11+22+34+44+51)=38/129.21(1) ASLsucc=31/12 , ASLunsucc=60/14 (2) ASLsucc=18/12 , ASLunsucc=12/14ASLunsucc=(1*3+2*3+1*3)14=12/14(Z的