數(shù)據(jù)結構 課后題答案(1-4章)

1、數(shù)據(jù)結構部分課后習題答案第一章1.1數(shù)據(jù)的邏輯結構是從具體問題中抽象出來的數(shù)學模型，體現(xiàn)了事物的組成和事物之間的邏輯關系。數(shù)據(jù)的存儲結構主要用來解決各種邏輯結構在計算機中物理存儲表示的問題。1.2事前分析和事后統(tǒng)計事前分析：優(yōu)點，程序不必運行，所得結果只依賴于算法本身 缺點，不夠精確事后統(tǒng)計：優(yōu)點，精確缺點，必須運行程序，所得結果依賴于硬件、環(huán)境等因素1.3void func(int n)int i = 1, k = 100;while(i < n) k+; i+=2;考慮賦值、運算操作執(zhí)行的次數(shù)第3行賦值2次第6行賦值執(zhí)行n次，加法執(zhí)行n次所以，總共2n+2次操作，算法復雜度為O(n)

2、1.4y= y + i * j 執(zhí)行次數(shù)：i=1n2n-2i+1=n24+n21.5n!>32n>2n2>n-n3+7n5>n3>n2+logn>nlogn>n>n+logn>logn第二章2.9內(nèi)存中一片連續(xù)空間（不妨假設地址從1到m）提供給兩個棧S1和S2使用，怎樣分配這部分存儲空間，使得對任一個棧，僅當這部分空間全滿時才發(fā)生上溢。答：S1和S2共享內(nèi)存中一片連續(xù)空間（地址1到m），可以將S1和S2的棧底設在兩端，兩棧頂向共享空間的中心延伸，僅當兩棧頂指針相鄰（兩棧頂指針值之差的絕對值等于1）時，判斷為棧滿，當一個棧頂指針為0，另一個棧

3、頂指針m+1時為兩棧均空。2.10 線性表是數(shù)據(jù)項組成的一種有限且有序的序列，各元素之間呈線性關系。從邏輯結構來說，棧和隊列與線性表相同，都是典型的線性結構。與線性表不同的是，棧和隊列的操作特殊，受到一定的限制，僅允許在線性表的一端或兩端進行。棧是限定僅在一端進行插入刪除的線性表，無論插入、刪除還是讀取都在一端進行，按后進先出的原則。隊列的元素只能從一端插入，從另一端刪除，按先進先出的原則進行數(shù)據(jù)的存取。2.11共有132種合法序列。235641序列可以。154623序列不可以。對于每一個數(shù)來說，必須進棧一次、出棧一次。我們把進棧設為狀態(tài)1，出棧設為狀態(tài)0。n個數(shù)的所有狀態(tài)對應n個1和n個0組

4、成的2n位二進制數(shù)。由于等待入棧的操作數(shù)按照1n的順序排列、入棧的操作數(shù)b大于等于出棧的操作數(shù)a(ab)，因此輸出序列的總數(shù)目=由左而右掃描由n個1和n個0組成的2n位二進制數(shù)，1的累計數(shù)不小于0的累計數(shù)的方案種數(shù)。 在2n位二進制數(shù)中填入n個1的方案數(shù)為c(2n,n),不填1的其余n位自動填0。從中減去不符合要求（由左而右掃描，0的累計數(shù)大于1的累計數(shù)）的方案數(shù)即為所求。 不符合要求的數(shù)的特征是由左而右掃描時，必然在某一奇數(shù)位2m+1位上首先出現(xiàn)m+1個0的累計數(shù)和m個1的累計數(shù)，此后的2(n-m)-1位上有n-m個 1和n-m-1個0。如若把后面這2(n-m)-1位上的0和1互換，使之成為

5、n-m個0和n-m-1個1，結果得1個由n+1個0和n-1個1組成的2n位數(shù)，即一個不合要求的數(shù)對應于一個由n+1個0和n-1個1組成的排列。 反過來，任何一個由n+1個0和n-1個1組成的2n位二進制數(shù)，由于0的個數(shù)多2個，2n為偶數(shù)，故必在某一個奇數(shù)位上出現(xiàn)0的累計數(shù)超過1的累計數(shù)。同樣在后面部分0和1互換，使之成為由n個0和n個1組成的2n位數(shù)，即n+1個0和n-1個1組成的2n位數(shù)必對應一個不符合要求的數(shù)。 因而不合要求的2n位數(shù)與n1個0，n1個1組成的排列一一對應。 顯然，不符合要求的方案數(shù)為c(2n,n+1)。由此得出 輸出序列的總數(shù)目=c(2n,n)-c(2n,n+1)=1/(

6、n+1)*c(2n,n)2.16next數(shù)組值：0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1,2第三章3.1 （1）n個結點可構造出多少種不同形態(tài)的二叉樹？解：當n=1時，只有1個根節(jié)點，則只能組成1種形態(tài)的二叉樹，令n個節(jié)點可組成的二叉樹數(shù)量表示為f(n)，則f(1)=1;當n=2時，1個根節(jié)點固定，還有n-1個節(jié)點，可以作為左子樹，也可以作為右子樹，即：f(2)=f(0)*f(1)+f(1)*f(0)=2，則能組成2種形態(tài)的二叉樹。這里f(0)表示空，所以只能算一種形態(tài)，即f(0)=1;當n=3時，1個根節(jié)點固定，還有n-1=2個節(jié)點，可以在左子樹或右子樹，即：f(3)=

7、f(0)*f(2)+f(1)*f(1)+f(2)*f(0)=5，則能組成5種形態(tài)的二叉樹。以此類推，當n>=2時，可組成的二叉樹數(shù)量為f(n)=f(0)*f(n-1)+f(1)*f(n-2)+.+f(n-1)*f(0)種。即符合Catalan數(shù)的定義，可直接利用通項公式得出結果。遞歸式：h(n)=h(n-1)*(4*n-2)/(n+1);該遞推關系的解為：h(n)=C(2n,n)/(n+1) (n=1,2,3,.)（2）若有3個數(shù)據(jù)1,2,3，輸入它們構造出來的中序遍歷結果都為1,2,3的不同二叉樹有哪些？解：有五種，如下：3.2 樹深度為6，17個葉子結點，度為1的節(jié)點為03.3 某二

8、叉樹有20個葉結點，有30個結點僅有一個孩子，求該二叉樹的總結點數(shù)是多少？解：設二叉樹中度為0、1、2的結點數(shù)分別為n0、n1 、n2。由題可知：n0=20, n1 =30。由性質(zhì)：任何一棵二叉樹，度為0的結點比度為2的結點多一個，可知n2= n0-1=20-1=19，即度為2 的結點個數(shù)為19個。因此總結點數(shù)n= n0+n1 +n2=20+30+19=69個。3.43.7 在中序線索二叉樹中如何查找給定結點的前序后繼,后序后繼 前序后繼：如果節(jié)點的ltag=0，那么后繼是節(jié)點的左孩子，否則，如果ltag=1&&rtag=0，后繼是右孩子，如果ltag=1&&r

9、tag=1，那么找到節(jié)點的父節(jié)點p，如果該節(jié)點是p的左孩子，且p->rtag=0，那么p的右孩子是節(jié)點的后繼，如果p->rtag=1，那么q=p->rchild，q是節(jié)點p在中序時的后繼，如果q->rtag=0，q的右孩子是后繼，否則q=q->rchild,直到找到q->rtag=0的節(jié)點或者q=null為止，q=null說明所求節(jié)點沒有后繼。 后序后繼：先根據(jù)中序全線索二叉樹的性質(zhì)找出p的父節(jié)點r：1）如果r->RightChild ！= p則對r的右子樹進行后序遍歷后訪問的第一個節(jié)點就是p在后序序列中的后繼；如果沒有右子樹，p在后序遍歷中的后繼就是

10、r2）如果r->RightChild = p 則r就是p在后序序列中的后繼。3.9(1)(2)3.103.11解答：高度為h的AVL樹，最少節(jié)點數(shù)為：N=(1+52)h+25-1當節(jié)點數(shù)為n時，根據(jù)上式可求得，數(shù)的最大高度為:hmax=log5+n+1-2其中=1+52最小高度為:hmin=log2(n+1)注：以上最少節(jié)點數(shù)可以利用歸納法可以得到，如下規(guī)律：當h=1，N(1)=1當h=2，N(2)=2當h=3，N(3)=4當h=4，N(4)=7當h=5，N(5)=12歸納可以發(fā)現(xiàn)類似于斐波那契數(shù)列的規(guī)律：Nh=Nh-1+Nh-2+1其中h>2。利用特征根求數(shù)列的方法，可以求得結果

11、。3.12 若關鍵字的輸入序列為20,9,2,11,13,30,22,16,17,15,18,10。（1）試從空樹開始順序輸入各關鍵字建立平衡二叉樹。畫出每次插入時二叉樹的形態(tài)，若需要平衡化旋轉(zhuǎn)則做旋轉(zhuǎn)并注明旋轉(zhuǎn)類型；解：插入過程及旋轉(zhuǎn)如圖所示：（2）計算該平衡二叉搜索樹在等概率下的查找成功的平均查找長度；解：12個結點在等概率查找的情況下，每個結點被查找的概率為112。由上題所得最后的結果可知：查找長度為0的結點個數(shù)為1，查找長度為1的結點個數(shù)為2，查找長度為2的結點個數(shù)為4，查找長度為3的結點個數(shù)為4，查找長度為4的結點個數(shù)為1。因此：查找成功的平均查找長度=1×0×1

12、12+2×1×112+4×2×112+4×3×112+4×1×112=2612=136（3）基于上面的建樹的結果，畫出從樹中刪除22，刪除2，刪除10與9后樹的形態(tài)和旋轉(zhuǎn)類型。解：刪除后的結果和旋轉(zhuǎn)如下：3.133.15、假定用于通信的電文僅由8個字母A，B，C，D，E，F(xiàn)，G，H組成,各字母在電文中出現(xiàn)的頻率分別為5,25,3,6,10,11,36,4。試為這8個字母設計不等長Huffman編碼,并給出該電文的總碼數(shù)。A:0110 B:10 C:0000 D:0111 E:001 F:010 G:11 H:000

13、1對應字母的碼數(shù)加和為4+2+4+4+3+3+2+4=26。3.16解答：高度最小為2，n-1個葉結點，1個分支結點。 高度最大為n，1個葉結點，n-1個分支結點3.173.18先根序列：ABCDEF GHIJK LMNPQRO后根序列：BDEFCA IJKHG MPRQNOL層次序列：ABCDRF GHIJK LMNOPQR3.193.20 3.21（1）孩子表示法：（2）孩子兄弟表示法：（3）雙親表示法：第四章4.1v2v0v1v3v4廣度優(yōu)先生成樹(黑體加粗邊)：v2v0v1v3v4深度拓撲排序序列：v0-v2-v3-v1-v44.24.3、 如圖所示為一個有6個頂點u1,u2,u3,u

14、4,u5,u6的帶權有向圖的鄰接矩陣。根據(jù)此鄰接矩陣畫出相應的帶權有向圖，利用dijkstra算法求第一個頂點u1到其余各頂點的最短路徑，并給出計算過程。4.4證明在圖中邊權為負時Dijkstra算法不能正確運行若允許邊上帶有負權值，有可能出現(xiàn)當與S（已求得最短路徑的頂點集，歸入S內(nèi)的結點的最短路徑不再變更）內(nèi)某點（記為a）以負邊相連的點（記為b）確定其最短路徑時，它的最短路徑長度加上這條負邊的權值結果小于a原先確定的最短路徑長度，而此時a在Dijkstra算法下是無法更新的。4.54.6 Dijkstra算法如何應用到無向圖？答：Dijkstra算法通常是運用在帶非負權值的有向圖中，但是無向

15、圖其實就是兩點之間兩條有向邊權值相同的特殊的有向圖，這樣就能將Dijkstra算法運用到無向圖中。4.7用FLOYD算法求出任意兩頂點的最短路徑（如圖A（6）所示）。A(0)= A(1)= A(2)= A(3)= A(4)= A(5)= A(6)=V1到V2、V3、V4、V5、V6往返路徑長度分別為5，9，5，9，9，最長為9，總的往返路程為37同理V2到V1、V3、V4、V5、V6分別為5，8，4，4，13，最長為13，總和34V3對應分別為9，8，12，8，9，最長為12，總和為46V4對應分別為5，4，12，4，9，最長為12，總和為34V5對應分別為9，4，8，4，9，最長為9，總和為34V6對應分別為9，13，9，9，9，最長為13，總和為49題目要求娛樂中心“距其它各結點的最長往返路程最短”，結點V1， V5最長往返路徑最短都是9。按“相同條件下總的往返路徑越短越好”，選頂點V