數(shù)據(jù)結(jié)構(gòu)c語言版答案

1、第五章1、設(shè)二維數(shù)組A【8】【10】是一個按行優(yōu)先順序存儲在內(nèi)存中的數(shù)組，已知A【0】【0】的起始存儲位置為1000，每個數(shù)組元素占用4個存儲單元，求：（1）A【4】【5】的起始存儲位置。 A【4】【5】的起始存儲位置為1000+（10*4+5）*4=1180；（2）起始存儲位置為1184的數(shù)組元素的下標(biāo)。 起始存儲位置為1184的數(shù)組元素的下標(biāo)為4（行下標(biāo)）、6（列下標(biāo)）。2、 畫出下列廣義表D=（c），(e)，(a，(b，c，d)）的圖形表示和它們的存儲表示。 略，參考第5·2節(jié)應(yīng)用題第5題分析與解答。3、已知A為稀疏矩陣，試從時間和空間角度比較采用兩種不同的存儲結(jié)構(gòu)（二維數(shù)組和

2、三元組表）實現(xiàn)求a(i，j)運算的優(yōu)缺點。 稀疏矩陣A采用二維數(shù)組存儲時，需要n*n個存儲單元，完成求(1in)時，由于a【i】【i】隨機存取，速度快。但采用三元組表時，若非零元素個數(shù)為t，需3t+3個存儲單元（t個分量存各非零元素的行值、列值、元素值），同時還需要三個存儲單元存儲存稀疏矩陣A的行數(shù)、列數(shù)和非零元素個數(shù)，比二維數(shù)組節(jié)省存儲單元；但在求（1in）時，要掃描整個三元組表，以便找到行列值相等的非零元素求和，其時間性能比采用二維數(shù)組時差。4、 利用三元組存儲任意稀疏數(shù)組時，在什么條件下才能節(jié)省存儲空間？ 當(dāng)m行n列稀疏矩陣中非零元素個數(shù)為t，當(dāng)滿足關(guān)系3*t<m*n時，利用三元組

3、存儲稀疏數(shù)組時，才能節(jié)省存儲空間。5、求下列各廣義表的操作結(jié)果。（1）GetHead(a,(b,c),d) GetHead(a,(b,c),d)=a（2）GetTail(a,(b,c),d) GetTail(a,(b,c),d)=(b,c),d)（3）GetHead(GetTail(a,(b,c),d) GetHead(GetTail(a,(b,c),d)=(b,c)（4）GetTail(GetHead(a,(b,c),d) GetTail(GetHead(a,(b,c),d)=()第六章1、 已知一棵樹邊的集合為（i,m）,(i,n),(e,i),(b,e),(b,d),(a,b),(g,j

4、),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用樹形表示法畫出此樹，并回答下列問題：（1） 哪個是根結(jié)點？（2） 哪些是葉結(jié)點？（3） 哪個是g的雙親？（4） 哪些是g的祖先？（5） 哪些是g的孩子？（6） 哪些是e的子孫？（7） 哪些是e的兄弟？哪些是f的兄弟？（8） 結(jié)點b和n的層次號分別是什么？（9） 樹的深度是多少？（10） 以結(jié)點c為根的子樹的深度是多少？（11） 樹的度數(shù)是多少？ 略。2、 設(shè)一棵完全二叉樹葉子結(jié)點數(shù)為k，試證明該二叉樹的高度為。 證明略。3、 已知一棵度為m的樹中有個度為1的結(jié)點，個度為2的結(jié)點，個度為m的結(jié)點，問該樹中有多少片葉子？

5、參見第6·2節(jié)應(yīng)用題中的第一題。4、已知某完全二叉樹有100個結(jié)點，試求該二叉樹的葉子樹。 該二叉樹的葉子樹為50。5、已知完全二叉樹的第6層有5個葉子，試畫出所有滿足這一條件的完全二叉樹，并指出結(jié)點最多的那棵樹的葉子數(shù)目。 根據(jù)完全二叉樹的定義，有兩種情況：（1）第6層為最高層，且有5個葉子；（2）第7層為最高層，且第6層有5個葉子。6、 一個深度為L的滿k叉樹有如下性質(zhì)，第L層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有k棵非空子樹。如果按層次順序從1開始對全部結(jié)點編號，問：（1） 第i層的結(jié)點數(shù)目是多少？（2） 編號為n的結(jié)點的雙親結(jié)點（若存在）的編號是多少？（3） 編號為n的

6、結(jié)點的第i個孩子結(jié)點（若存在）的編號是多少？（4） 編號為n的結(jié)點有右兄弟的條件是什么？其右兄弟的編號是多少？ 答案分別為，7、 試找出分別滿足下面條件的所有二叉樹：（1） 先序序列和中序序列相同。（2） 中序序列和后序序列相同。（3） 先序序列和后序序列相同。 略。8、 證明：一棵滿k叉樹上的葉結(jié)點數(shù)和非葉子結(jié)點數(shù)m之間滿足下列關(guān)系： =（k-1）m+1 證明：總結(jié)點數(shù)n=+m，又n-1=km，所以=（k-1）m+1。9、 已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，畫出這棵二叉樹。并寫出其先序遍歷序列。 先序遍歷序列為ABCDEFGH。L10、 將圖6·22所示的森林轉(zhuǎn)換為二叉樹。GANMOBHCPRQKJIFED 圖6·22 將森林轉(zhuǎn)換為二叉樹 參見第6·2節(jié)中的應(yīng)用題中的第7題。11、 寫出圖6·22所示森林的前序序列和后序序列。參見第6·2節(jié)中的應(yīng)用題中