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

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

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

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

4、中，一共有個指針域，其中只有 個用來指向結(jié)點(diǎn)的左右孩子，其余的個指針域?yàn)镹ULL。18. 二叉樹有不同的鏈?zhǔn)酱鎯Y(jié)構(gòu)，其中最常用的是 與。19. 若二叉樹的一個葉子是某子樹的中根遍歷序列中的第一個結(jié)點(diǎn)，則它必是該子樹的后根遍歷序列中的個結(jié)點(diǎn)。20. 樹與二叉樹之間最主要的差別是：二叉樹中各結(jié)點(diǎn)的子樹要區(qū)分為和，即使在結(jié)點(diǎn)只有一棵子樹的情況下，也要明確指出該子樹是 還是。21. 樹的結(jié)點(diǎn)數(shù)目至少為 ，二叉樹的結(jié)點(diǎn)數(shù)目至少為 。22. 下面是中序線索樹的遍歷算法，樹有頭結(jié)點(diǎn)且由指針thr指向。樹的結(jié)點(diǎn)有五個域，分別為：數(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)換成二叉樹時，其根結(jié)點(diǎn)的右子樹總是空的。24. 哈夫曼(Huffman )樹是帶權(quán)路徑長度 的樹，通常權(quán)值較大的結(jié)點(diǎn)離根 25. 用5個權(quán)值3, 2, 4, 5, 1構(gòu)造的哈夫曼(Huffman )樹的帶權(quán)路徑長度是 。二、選擇題(每空1分，共10分) (

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

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

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

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

10、。對于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。10. 試編寫最大堆的向上調(diào)整算法函數(shù)。要求：寫成內(nèi)聯(lián)函數(shù)的形式，程序頭已給出，已通過數(shù)組heap建堆，建堆區(qū)間由遍歷器first、mid和last指向，即mid, last-1 )是一個堆，現(xiàn)自底向上將mid,last)調(diào)整為一個堆。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)的一個孩子、空指針 NULL17、2n、n-1、n+118、二叉鏈表、三叉鏈表19、第一20、左子樹、右子樹、左子樹、右子樹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、樹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的左、右子樹。然后由其左子樹的元素集 合和右子樹的集合對應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問題得解。2.解：要遵循中序遍歷的軌跡來畫出每個前驅(qū)和后繼。 中序遍歷序列：55 40 25 60 28 08 33 54283該算術(shù)表達(dá)式轉(zhuǎn)化的二叉

13、樹如圖所示。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)比較簡單，用任何一種遍歷遞歸算法，凡是左右指針均空者，則為葉子, 將其打印出來。法一：核心部分為：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)/ 求二叉樹中葉子結(jié)點(diǎn)的數(shù)目 -if(!T) return 0; /空樹沒有葉子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ù)/Lea

15、fCou nt_BiTree 6解答略(參考教材)7. int Get_Sub_Depth(BinaryTree T,int x) 求二叉樹中以值為 x的結(jié)點(diǎn)為根的子樹深度 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); / 在左右子樹中繼續(xù)尋找Get_Sub_Depthint Get_Depth(Bina

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