計(jì)算機(jī)軟件基礎(chǔ)課后答案

1、2.8 已知線性表L（a1,a2,an）元素按遞增有序排列，用向量作存儲(chǔ)結(jié)構(gòu)，試編寫算法：刪除表中在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 有一鐵路交換站如題圖（棧），火車從右邊開進(jìn)交換站，然后再開到左邊，每節(jié)車廂均有編號(hào)如1，2，3，n。請(qǐng)問： （1）當(dāng)n=3和n=4時(shí)有哪幾種排序方式？哪幾種排序方式不可能發(fā)生？ （2）當(dāng)n=

2、6時(shí)，325641這樣的排列是否能發(fā)生？154623的排列是否能發(fā)生？ N=3時(shí)可能的出棧序列： 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時(shí)，325641可能 154623不可能 2.23 試畫出表達(dá)式A*(B-D)/D+C*(E*F)執(zhí)行過程中NS,OS棧的變化情況。B-D=T1D/T1=T2 T2*A=T3 E*F=T4

3、 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 -1262274481791129429669930i123456789POS147101213141516NUM333211

4、1142.28DEFIJKGLABC2.29前8行：1+2+4+8+16+32+64+128+256=511第9行：滿的尾512 加起來(lái)超過10001000-511=489這是第9行的度為1的結(jié)點(diǎn)489/2=244余1256-244=12 12-1=11 這是第8行度為1的結(jié)點(diǎn)則度為1的結(jié)點(diǎn)數(shù)：n1=489+11=500度為2的結(jié)點(diǎn)數(shù)：n2=n1-1=499度為0的節(jié)點(diǎn)數(shù)：n0=11個(gè)節(jié)點(diǎn)只有非空左子樹11個(gè)結(jié)點(diǎn)只有非空右子樹第一種做法： N1=0/1，N是奇àN1=0；N是偶àN1=1 N=1000，N1=1 1000=N0+1+N2 1 N0=N2+1 2 N0=500

5、，N2=499 第二法： N=1000，29<N<210 à完全二叉的深度H=10 第10層葉子結(jié)點(diǎn)數(shù)：N01=N-(29-1)=1000-511=489 第10層總結(jié)點(diǎn)數(shù)：29 =512 第10層空的結(jié)點(diǎn)數(shù)：512-489=23 空結(jié)點(diǎn)數(shù)是奇數(shù)àN1=1 第9層葉子結(jié)點(diǎn)數(shù)：N02=（23-1）/2=11 總?cè)~子結(jié)點(diǎn)數(shù)：N0=N01+N02=489+11=500 N2=N-N0-N1=1000-500-1=499 度為3的樹，1個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，求葉子結(jié)點(diǎn)數(shù)？ N=N0+N1+N2+N3=N0+1+3+4 B=N-1=N1+2*

6、N2+3*N3=1+2*3+3*4=19àN=20àN0=122.30 設(shè)一棵二叉樹其中序和后序遍歷為中序：BDCEAFHG 后序：DECBHGFA畫出這棵二叉樹的邏輯結(jié)構(gòu)，并寫出先序遍歷結(jié)果。 先序遍歷：ABCDEFGH其邏輯結(jié)構(gòu)如下：ABFCDEGH1，2，3依次進(jìn)棧，求可能的出棧序列。123 1S1X2S2X3S3X132 1S1X2S3S3X2X213 1S2S2X1X3S3X231 1S2S2X3S3X1X312 CAB321 1S2S3S3X2X1X1，2，3，44312 4213 4231 4123 41323124 3142 3412142324133256

7、41 154623ABCDEFGIJKL2.29 完全二叉樹有1000個(gè)結(jié)點(diǎn)，問：葉子結(jié)點(diǎn)有多少？度為2的結(jié)點(diǎn)有多少？多少個(gè)結(jié)點(diǎn)只有非空的左子樹？第一種做法：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層葉子結(jié)點(diǎn)數(shù)：N01=N-(29-1)=1000-511=489第10層總結(jié)點(diǎn)數(shù)：29 =512第10層空的結(jié)點(diǎn)數(shù)：512-489=23空結(jié)點(diǎn)數(shù)是奇數(shù)àN1=1第9層葉子結(jié)點(diǎn)數(shù)：

8、N02=（23-1）/2=11總?cè)~子結(jié)點(diǎn)數(shù)：N0=N01+N02=489+11=500N2=N-N0-N1=1000-500-1=499度為3的樹，1個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，求葉子結(jié)點(diǎn)數(shù)？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 設(shè)一棵二叉樹的中序遍歷和后序遍歷結(jié)果為：中序：BDCEAFHG后序：DECBHGFA求先序？ABCDEFGHABFCDEGHDLR 先序LDR 中序LRD 后序2.32給定一組元素17，28，36，54，30，27，94，15

9、，21，83，40，畫出由此生成的二叉排序樹。17283654302794152183402.33給定一組權(quán)值W=8，2，5，3，2，17，4，畫出由此生成的哈夫曼樹。下標(biāo)數(shù)據(jù)雙親左孩子右孩子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）由結(jié)

10、點(diǎn)V1作深度優(yōu)先搜索和廣度優(yōu)先搜索；（3）試說明上述搜索的用途。2101191918812172016713156145413鄰接矩陣：1234567891011121314151617181920101001001000000000000210100000010000000000301010000000100000000400101000000001000000510010100000000000000600001010000000100000700000101000000001000810000010100000000000900000001010000000100100100000010

11、1000000000110000000001010000001120010000000101000000013000000000001010000011400010000000010100000150000010000000101000016000000000000001010011700000010000000010100180000000010000000101019000000000010000001012000000000000010010010鄰接表：V1V2V3V4V5V6V7V8V9V10V11V12V13V14V15V16V17V18V19V20258 1310 2412 35

12、14 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）寫出每一個(gè)結(jié)點(diǎn)的入度和出度各為多少；（2）寫出此圖的鄰接矩陣與鄰接表；頂點(diǎn)入度出

13、度V130V222V312V421V521V614156423 V1V2V3V4V5V6V1000000V2100100V3010001V4001010V5100000V6110110V1V2V3V4V5V6 14 6 35 1 124 5 DFS：V6àV1àV2àV4àV3àV5BFS：V6àV1àV2àV4àV5àV3236 求下圖中結(jié)點(diǎn)a到各結(jié)點(diǎn)之間的最短路徑。abcdefhg23122412321237 求下圖中所示AOV網(wǎng)所有可能的拓?fù)渑判蚪Y(jié)果。21738546V1V2V3V4V5V

14、6 0000013 8 68 4 8 V7 0V8 0 0 8 4 拓?fù)渑判颍篤7->V5->V2->V4->V6->V3->V1->V82.38 下圖所示AOE網(wǎng)，求（1）每一事件最早開始時(shí)間和最晚開始時(shí)間；（2）該計(jì)劃最早完成時(shí)間為多少。1開始2345768910結(jié)束a2=6a1=5a3=3a4=6a5=3a10=4a9=1a6=7a8=4a7=4a11=4a14=2a13=2a12=5活動(dòng)最早最遲開始時(shí)間a1a2a3a4a5a6a7a8a9a10a11a12a13a14E00566121212191916202325L409616121916191923202325L-E404010074007000事件最早最遲開始時(shí)間V1V2V3V4V5V6V7V8V9V10VE05612191620232527VL09612192320232527畫一棵以20個(gè)記錄進(jìn)行對(duì)分查找的判定樹，并求等概率下的平均查找長(zhǎng)度。1234567891011121314151617181920434524345143452453451015527134689121811131416191720ASL=(1+2*2+3*4+4*8+5*5)/20=?(13,29,01,23,44,55,20,84,27,68,11,10,7