數(shù)據(jù)結(jié)構(gòu) 課后題答案(1-4章)

1、數(shù)據(jù)結(jié)構(gòu)部分課后習(xí)題答案第一章1.1數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題中抽象出來的數(shù)學(xué)模型，體現(xiàn)了事物的組成和事物之間的邏輯關(guān)系。數(shù)據(jù)的存儲結(jié)構(gòu)主要用來解決各種邏輯結(jié)構(gòu)在計算機中物理存儲表示的問題。1.2事前分析和事后統(tǒng)計事前分析：優(yōu)點，程序不必運行，所得結(jié)果只依賴于算法本身 缺點，不夠精確事后統(tǒng)計：優(yōu)點，精確缺點，必須運行程序，所得結(jié)果依賴于硬件、環(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次操作，算法復(fù)雜度為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ù)空間（不妨假設(shè)地址從1到m）提供給兩個棧S1和S2使用，怎樣分配這部分存儲空間，使得對任一個棧，僅當(dāng)這部分空間全滿時才發(fā)生上溢。答：S1和S2共享內(nèi)存中一片連續(xù)空間（地址1到m），可以將S1和S2的棧底設(shè)在兩端，兩棧頂向共享空間的中心延伸，僅當(dāng)兩棧頂指針相鄰（兩棧頂指針值之差的絕對值等于1）時，判斷為棧滿，當(dāng)一個棧頂指針為0，另一個棧

3、頂指針m+1時為兩棧均空。2.10 線性表是數(shù)據(jù)項組成的一種有限且有序的序列，各元素之間呈線性關(guān)系。從邏輯結(jié)構(gòu)來說，棧和隊列與線性表相同，都是典型的線性結(jié)構(gòu)。與線性表不同的是，棧和隊列的操作特殊，受到一定的限制，僅允許在線性表的一端或兩端進行。棧是限定僅在一端進行插入刪除的線性表，無論插入、刪除還是讀取都在一端進行，按后進先出的原則。隊列的元素只能從一端插入，從另一端刪除，按先進先出的原則進行數(shù)據(jù)的存取。2.11共有132種合法序列。235641序列可以。154623序列不可以。對于每一個數(shù)來說，必須進棧一次、出棧一次。我們把進棧設(shè)為狀態(tài)1，出棧設(shè)為狀態(tài)0。n個數(shù)的所有狀態(tài)對應(yīng)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，結(jié)果得1個由n+1個0和n-1個1組成的2n位數(shù)，即一個不合要求的數(shù)對應(yīng)于一個由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ù)必對應(yīng)一個不符合要求的數(shù)。 因而不合要求的2n位數(shù)與n1個0，n1個1組成的排列一一對應(yīng)。 顯然，不符合要求的方案數(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個結(jié)點可構(gòu)造出多少種不同形態(tài)的二叉樹？解：當(dāng)n=1時，只有1個根節(jié)點，則只能組成1種形態(tài)的二叉樹，令n個節(jié)點可組成的二叉樹數(shù)量表示為f(n)，則f(1)=1;當(dāng)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;當(dāng)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)的二叉樹。以此類推，當(dāng)n>=2時，可組成的二叉樹數(shù)量為f(n)=f(0)*f(n-1)+f(1)*f(n-2)+.+f(n-1)*f(0)種。即符合Catalan數(shù)的定義，可直接利用通項公式得出結(jié)果。遞歸式：h(n)=h(n-1)*(4*n-2)/(n+1);該遞推關(guān)系的解為：h(n)=C(2n,n)/(n+1) (n=1,2,3,.)（2）若有3個數(shù)據(jù)1,2,3，輸入它們構(gòu)造出來的中序遍歷結(jié)果都為1,2,3的不同二叉樹有哪些？解：有五種，如下：3.2 樹深度為6，17個葉子結(jié)點，度為1的節(jié)點為03.3 某二

8、叉樹有20個葉結(jié)點，有30個結(jié)點僅有一個孩子，求該二叉樹的總結(jié)點數(shù)是多少？解：設(shè)二叉樹中度為0、1、2的結(jié)點數(shù)分別為n0、n1 、n2。由題可知：n0=20, n1 =30。由性質(zhì)：任何一棵二叉樹，度為0的結(jié)點比度為2的結(jié)點多一個，可知n2= n0-1=20-1=19，即度為2 的結(jié)點個數(shù)為19個。因此總結(jié)點數(shù)n= n0+n1 +n2=20+30+19=69個。3.43.7 在中序線索二叉樹中如何查找給定結(jié)點的前序后繼,后序后繼 前序后繼：如果節(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當(dāng)節(jié)點數(shù)為n時，根據(jù)上式可求得，數(shù)的最大高度為:hmax=log5+n+1-2其中=1+52最小高度為:hmin=log2(n+1)注：以上最少節(jié)點數(shù)可以利用歸納法可以得到，如下規(guī)律：當(dāng)h=1，N(1)=1當(dāng)h=2，N(2)=2當(dāng)h=3，N(3)=4當(dāng)h=4，N(4)=7當(dāng)h=5，N(5)=12歸納可以發(fā)現(xiàn)類似于斐波那契數(shù)列的規(guī)律：Nh=Nh-1+Nh-2+1其中h>2。利用特征根求數(shù)列的方法，可以求得結(jié)果

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

12、12+2×1×112+4×2×112+4×3×112+4×1×112=2612=136（3）基于上面的建樹的結(jié)果，畫出從樹中刪除22，刪除2，刪除10與9后樹的形態(tài)和旋轉(zhuǎn)類型。解：刪除后的結(jié)果和旋轉(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個字母設(shè)計不等長Huffman編碼,并給出該電文的總碼數(shù)。A:0110 B:10 C:0000 D:0111 E:001 F:010 G:11 H:000

13、1對應(yīng)字母的碼數(shù)加和為4+2+4+4+3+3+2+4=26。3.16解答：高度最小為2，n-1個葉結(jié)點，1個分支結(jié)點。 高度最大為n，1個葉結(jié)點，n-1個分支結(jié)點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的帶權(quán)有向圖的鄰接矩陣。根據(jù)此鄰接矩陣畫出相應(yīng)的帶權(quán)有向圖，利用dijkstra算法求第一個頂點u1到其余各頂點的最短路徑，并給出計算過程。4.4證明在圖中邊權(quán)為負時Dijkstra算法不能正確運行若允許邊上帶有負權(quán)值，有可能出現(xiàn)當(dāng)與S（已求得最短路徑的頂點集，歸入S內(nèi)的結(jié)點的最短路徑不再變更）內(nèi)某點（記為a）以負邊相連的點（記為b）確定其最短路徑時，它的最短路徑長度加上這條負邊的權(quán)值結(jié)果小于a原先確定的最短路徑長度，而此時a在Dijkstra算法下是無法更新的。4.54.6 Dijkstra算法如何應(yīng)用到無向圖？答：Dijkstra算法通常是運用在帶非負權(quán)值的有向圖中，但是無向

15、圖其實就是兩點之間兩條有向邊權(quán)值相同的特殊的有向圖，這樣就能將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對應(yīng)分別為9，8，12，8，9，最長為12，總和為46V4對應(yīng)分別為5，4，12，4，9，最長為12，總和為34V5對應(yīng)分別為9，4，8，4，9，最長為9，總和為34V6對應(yīng)分別為9，13，9，9，9，最長為13，總和為49題目要求娛樂中心“距其它各結(jié)點的最長往返路程最短”，結(jié)點V1， V5最長往返路徑最短都是9。按“相同條件下總的往返路徑越短越好”，選頂點V