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

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

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

3、存儲(chǔ)稀疏數(shù)組時(shí)，才能節(jié)省存儲(chǔ)空間。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） 哪個(gè)是根結(jié)點(diǎn)？（2） 哪些是葉結(jié)點(diǎn)？（3） 哪個(gè)是g的雙親？（4） 哪些是g的祖先？（5） 哪些是g的孩子？（6） 哪些是e的子孫？（7） 哪些是e的兄弟？哪些是f的兄弟？（8） 結(jié)點(diǎn)b和n的層次號(hào)分別是什么？（9） 樹的深度是多少？（10） 以結(jié)點(diǎn)c為根的子樹的深度是多少？（11） 樹的度數(shù)是多少？ 略。2、 設(shè)一棵完全二叉樹葉子結(jié)點(diǎn)數(shù)為k，試證明該二叉樹的高度為。 證明略。3、 已知一棵度為m的樹中有個(gè)度為1的結(jié)點(diǎn)，個(gè)度為2的結(jié)點(diǎn)，個(gè)度為m的結(jié)點(diǎn)，問該樹中有多少片葉子？

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

6、結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是多少？（4） 編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？ 答案分別為，7、 試找出分別滿足下面條件的所有二叉樹：（1） 先序序列和中序序列相同。（2） 中序序列和后序序列相同。（3） 先序序列和后序序列相同。 略。8、 證明：一棵滿k叉樹上的葉結(jié)點(diǎn)數(shù)和非葉子結(jié)點(diǎn)數(shù)m之間滿足下列關(guān)系： =（k-1）m+1 證明：總結(jié)點(diǎn)數(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)用題中