數(shù)據(jù)結(jié)構(gòu)非線性部分(樹(shù)二叉樹(shù))自測(cè)題及解答

1、一、概念題(每空1分，共55分)1樹(shù)(及一切樹(shù)形結(jié)構(gòu))是一種“ ”結(jié)構(gòu)。在樹(shù)上， 結(jié)點(diǎn)沒(méi)有直接前趨。對(duì)樹(shù)上任一結(jié)點(diǎn)X來(lái)說(shuō)，X是它的任一子樹(shù)的根結(jié)點(diǎn)惟一的 。2. 由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有 _種形態(tài)。3. 棵深度為 6的滿(mǎn)二叉樹(shù)有 個(gè)分支結(jié)點(diǎn)和 個(gè)葉子。4. 一棵具有2 5 7個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的深度為 。5. 二叉樹(shù)第i(i>=1)層上至多有 個(gè)結(jié)點(diǎn)；深度為k(k>=1)的二叉樹(shù)至多有 個(gè)結(jié)點(diǎn)。6. 對(duì)任何二叉樹(shù)，若度為2的節(jié)點(diǎn)數(shù)為n2,則葉子數(shù)no=。7. 滿(mǎn)二叉樹(shù)上各層的節(jié)點(diǎn)數(shù)已達(dá)到了二叉樹(shù)可以容納的 。滿(mǎn)二叉樹(shù)也是 二叉樹(shù),但反之不然。&設(shè)一棵完全二叉樹(shù)有 70

2、0個(gè)結(jié)點(diǎn)，則共有 個(gè)葉子結(jié)點(diǎn)。9設(shè)一棵完全二叉樹(shù)具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹(shù)有 個(gè)葉子結(jié)點(diǎn)，有 個(gè)度為2的結(jié)點(diǎn)，有 個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，有 個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。10. 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹(shù)，可能達(dá)到的最大深，最小深度為 。11. 二叉樹(shù)的基本組成部分是：根(N)、左子樹(shù)(L)和右子樹(shù)(R)。因而二叉樹(shù)的遍歷次序有六種。最常用的是三種：前序法(即按 N L R次序)，后序法(即按 次序)和中序法(也稱(chēng)對(duì)稱(chēng)序法，即按 LN R次序)。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹(shù)的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是 。12中序遍歷的遞歸算法平均空間復(fù)雜

3、度為。13.二叉樹(shù)通常有 存儲(chǔ)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩類(lèi)存儲(chǔ)結(jié)構(gòu)。14如果將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層編號(hào)，則對(duì)任一編號(hào)為i(1<=i<=n)的結(jié)點(diǎn)X有：(1) 若i=1,則結(jié)點(diǎn)X是;若i1,則X的雙親PARENT(X)的編號(hào)為 。(2) 若2i>n，則結(jié)點(diǎn)X無(wú)且無(wú);否則，X的左孩子LCHILD(X)的編號(hào)為(3) 若2i+1>n，則結(jié)點(diǎn)X無(wú);否則，X的右孩子RCHILD(X)的編號(hào)為 。15. 每個(gè)二叉鏈表的訪問(wèn)只能從 結(jié)點(diǎn)的指針，該指針具有標(biāo)識(shí)二叉鏈表的作用。16. 二叉鏈表中每個(gè)存儲(chǔ)結(jié)點(diǎn)的每個(gè)指針域必須有一個(gè)值，這個(gè)值或者是的指針，或者是。17. 具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)

4、中，一共有個(gè)指針域，其中只有 個(gè)用來(lái)指向結(jié)點(diǎn)的左右孩子，其余的個(gè)指針域?yàn)镹ULL。18. 二叉樹(shù)有不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其中最常用的是 與。19. 若二叉樹(shù)的一個(gè)葉子是某子樹(shù)的中根遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的后根遍歷序列中的個(gè)結(jié)點(diǎn)。20. 樹(shù)與二叉樹(shù)之間最主要的差別是：二叉樹(shù)中各結(jié)點(diǎn)的子樹(shù)要區(qū)分為和，即使在結(jié)點(diǎn)只有一棵子樹(shù)的情況下，也要明確指出該子樹(shù)是 還是。21. 樹(shù)的結(jié)點(diǎn)數(shù)目至少為 ，二叉樹(shù)的結(jié)點(diǎn)數(shù)目至少為 。22. 下面是中序線索樹(shù)的遍歷算法，樹(shù)有頭結(jié)點(diǎn)且由指針thr指向。樹(shù)的結(jié)點(diǎn)有五個(gè)域，分別為：數(shù)據(jù)域data,左、右孩子域Ichild、rchild和左、右標(biāo)志域ltag,r

5、tag。規(guī)定，標(biāo)志域?yàn)?是線索，0是指向孩子的指針。inordethread(thr)p=thr->lchild;while (p<>thr) /未循環(huán)結(jié)束 while(d) p= (2Uprintf(p->data);while(3) ) p=(4)_; printf(p->data);p=I5K 23. 由轉(zhuǎn)換成二叉樹(shù)時(shí)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。24. 哈夫曼(Huffman )樹(shù)是帶權(quán)路徑長(zhǎng)度 的樹(shù)，通常權(quán)值較大的結(jié)點(diǎn)離根 25. 用5個(gè)權(quán)值3, 2, 4, 5, 1構(gòu)造的哈夫曼(Huffman )樹(shù)的帶權(quán)路徑長(zhǎng)度是 。二、選擇題(每空1分，共10分) (

6、)1. 不含任何結(jié)點(diǎn)的空樹(shù)。(A)(C)是一棵樹(shù)也是一棵二叉樹(shù) ；(D)既不是樹(shù)也不是二叉樹(shù)()2.二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)，所以 。(A)它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)；(E)它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)(C)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)；(D)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用()3.具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 。(A ) log 2(n) ( B )og 2(n)(C )og 2(n)刃 (D) "log2(n)+1 1()4.把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是 。(A)唯一的(B)有多種(C)有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子(D)有多種，但根結(jié)點(diǎn)都沒(méi)有右

7、孩子5.樹(shù)是結(jié)點(diǎn)的有限集合，它_A 根結(jié)點(diǎn)，記為T(mén)。其余的結(jié)點(diǎn)分成為 m( m> 0 )個(gè)_B的集合T1, T2,，Tm每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn) T稱(chēng)為T(mén)的父結(jié)點(diǎn)，Ti稱(chēng)為T(mén)的子結(jié)點(diǎn)(1 <i <m)o 一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的c 。供選擇的答案A:有0個(gè)或1個(gè)有0個(gè)或多個(gè)有且只有1個(gè)有1個(gè)或1個(gè)以上B:互不相交允許相交允許葉結(jié)點(diǎn)相交允許樹(shù)枝結(jié)點(diǎn)相交C:權(quán)維數(shù)次數(shù)序答案A=B=C=6.二叉樹(shù)_A_。在完全的二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有_B，則它必定是葉結(jié)點(diǎn)。每棵樹(shù)都N的左子女是 N在原樹(shù)能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹(shù)。由樹(shù)轉(zhuǎn)換成的二叉樹(shù)里，一個(gè)結(jié)點(diǎn) 里對(duì)應(yīng)結(jié)點(diǎn)的_c。供選

8、擇的答案A:是特殊的樹(shù) 形結(jié)構(gòu)B:C:弟不是樹(shù)的特殊形式是兩棵樹(shù)的總稱(chēng)有是只有二個(gè)根結(jié)點(diǎn)的樹(shù)左子結(jié)點(diǎn)最左子結(jié)點(diǎn)右子結(jié)點(diǎn)左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn)最右子結(jié)點(diǎn)最鄰近的右兄弟兄弟最鄰近的左兄最左的兄弟答案：A=B=最右的兄弟-C=三、綜合題(1-7每題3分，8-10每題4分,共33分)1給定二叉樹(shù)的兩種遍歷序列，分別是：前序遍歷序列：D,A,C,E,B, H, F,G,I ;中序遍歷序列：D,C,B,E,H,A, G I , F,試畫(huà)出二叉樹(shù)B。2.給定如圖所示二叉樹(shù) T,請(qǐng)畫(huà)出與其對(duì)應(yīng)的中序線索二叉樹(shù)。2825333將算術(shù)表達(dá)式(a+b) +c*(d+e)+f ) *(g+h)轉(zhuǎn)化為二叉樹(shù)。4. 試

9、寫(xiě)出如圖所示的二叉樹(shù)分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。5. 編寫(xiě)遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。6. 寫(xiě)出求二叉樹(shù)深度的算法。7. 編寫(xiě)遞歸算法，求二叉樹(shù)中以元素值為x的結(jié)點(diǎn)為根的子樹(shù)的深度。&設(shè)度為m的樹(shù)采用多重鏈表存儲(chǔ)。每個(gè)結(jié)點(diǎn)有m+1個(gè)域，其中有一個(gè)數(shù)據(jù)域，m個(gè)指向孩子的指針。則空指針的數(shù)目是多少？說(shuō)明這種存儲(chǔ)方式的利弊。9. 假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07 , 0.19 , 0.02 ,0.06 , 0.32 , 0.03 , 0.21 , 0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。使用07的二進(jìn)制表示形式是另一種編碼方案

10、。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。10. 試編寫(xiě)最大堆的向上調(diào)整算法函數(shù)。要求：寫(xiě)成內(nèi)聯(lián)函數(shù)的形式，程序頭已給出，已通過(guò)數(shù)組heap建堆，建堆區(qū)間由遍歷器first、mid和last指向，即mid, last-1 )是一個(gè)堆，現(xiàn)自底向上將mid,last)調(diào)整為一個(gè)堆。template <class Ran iter, class T>in li ne void _fixup(Ra niter first, Ran iter mid, Ran iter last, T t)參考答案一、概念題(每空1分，共55分)1、分支層次、根、直接前趨2、53、31324、95、22 -16

11、、n2+17、最大值、完全8、350(n/2 = 350)9、500 499 1 010、n 211、L R N F E G H D C B12、0( n)13、順序、鏈?zhǔn)?4、根、左孩子、右孩子、2i、右孩子、2i+115、根16、指向該結(jié)點(diǎn)的一個(gè)孩子、空指針 NULL17、2n、n-1、n+118、二叉鏈表、三叉鏈表19、第一20、左子樹(shù)、右子樹(shù)、左子樹(shù)、右子樹(shù)21、1、 022、(1) p->ltag=0(2)p->lchild(3)p->rtag=1 && p->rchild!=thr (4) p=p->rchild(5)p=p->r

12、child22、樹(shù)23、最短、較近24、33二、選擇題(每空1分，共10分)1. C 2. C 3. C 4. A 5. A= B= C=6. A=B=C=三、綜合題(1-9每題3分，10-11每題4分,共35分)1.解：方法是：由前序先確定root，由中序可確定root的左、右子樹(shù)。然后由其左子樹(shù)的元素集 合和右子樹(shù)的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問(wèn)題得解。2.解：要遵循中序遍歷的軌跡來(lái)畫(huà)出每個(gè)前驅(qū)和后繼。 中序遍歷序列：55 40 25 60 28 08 33 54283該算術(shù)表達(dá)式轉(zhuǎn)化的二叉

13、樹(shù)如圖所示。55N第3題圖4.答：DLR : A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD : J F K G D B H L M I E C A5思路：輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用任何一種遍歷遞歸算法，凡是左右指針均空者，則為葉子, 將其打印出來(lái)。法一：核心部分為：DLR(BinaryTreeNode *root)/* 中序遍歷遞歸函數(shù) */if(root!=NULL)if(root->lchild=NULL)&&(root->rchild=NULL)sum+; cout<<roo

14、t->data<<e ndl; DLR(root->lchild);DLR(root->rchild); return(O);法二：int LeafCount_BiTree(BinaryTree T)/ 求二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目 -if(!T) return 0; /空樹(shù)沒(méi)有葉子else if(!T->lchild&&!T->rchild) return 1; /葉子結(jié)點(diǎn)else return Leaf_Cou nt(T->lchild)+Leaf_Cou nt(T->rchild);左子樹(shù)的葉子數(shù)加上右子樹(shù)的葉子數(shù)/Lea

15、fCou nt_BiTree 6解答略(參考教材)7. int Get_Sub_Depth(BinaryTree T,int x) 求二叉樹(shù)中以值為 x的結(jié)點(diǎn)為根的子樹(shù)深度 if(T->data=x) cout«Get_Depth(T)vvendl; /找到了值為 x的結(jié)點(diǎn)，求其深度 exit 1;elseif(T->lchild) Get_Sub_Depth(T->lchild,x);if(T->rchild) Get_Sub_Depth(T->rchild,x); / 在左右子樹(shù)中繼續(xù)尋找Get_Sub_Depthint Get_Depth(Bina

16、ryTree T) 求子樹(shù)深度的遞歸算法if(!T) return 0;else m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return (m>n?m:n)+1;/Get_Depth8. n(n>0)個(gè)結(jié)點(diǎn)的m叉樹(shù)共有n*m個(gè)鏈域，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均有一個(gè)指針?biāo)福试摌?shù)的空鏈域有n*m-( n-1)=n( m-1)+1個(gè)。這種存儲(chǔ)結(jié)構(gòu)統(tǒng)便于處理，但空鏈域造成存儲(chǔ)效率低。9. 解：方案1;哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則:構(gòu)造哈夫曼樹(shù)如下：(100).(40)-”( 60)” 192132.(2810 623子母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率111000.072000.193Imo0.02可mo0.065io0.326iiiii0.037010.21r 8110