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

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

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

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

4、中，一共有個指針域，其中只有 個用來指向結點的左右孩子，其余的個指針域為NULL。18. 二叉樹有不同的鏈式存儲結構，其中最常用的是 與。19. 若二叉樹的一個葉子是某子樹的中根遍歷序列中的第一個結點，則它必是該子樹的后根遍歷序列中的個結點。20. 樹與二叉樹之間最主要的差別是：二叉樹中各結點的子樹要區(qū)分為和，即使在結點只有一棵子樹的情況下，也要明確指出該子樹是 還是。21. 樹的結點數(shù)目至少為 ，二叉樹的結點數(shù)目至少為 。22. 下面是中序線索樹的遍歷算法，樹有頭結點且由指針thr指向。樹的結點有五個域，分別為：數(shù)據(jù)域data,左、右孩子域Ichild、rchild和左、右標志域ltag,r

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

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

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

8、擇的答案A:是特殊的樹 形結構B:C:弟不是樹的特殊形式是兩棵樹的總稱有是只有二個根結點的樹左子結點最左子結點右子結點左子結點或者沒有右子結點最右子結點最鄰近的右兄弟兄弟最鄰近的左兄最左的兄弟答案：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,請畫出與其對應的中序線索二叉樹。2825333將算術表達式(a+b) +c*(d+e)+f ) *(g+h)轉化為二叉樹。4. 試

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

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

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思路：輸出葉子結點比較簡單，用任何一種遍歷遞歸算法，凡是左右指針均空者，則為葉子, 將其打印出來。法一：核心部分為：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ù)目 -if(!T) return 0; /空樹沒有葉子else if(!T->lchild&&!T->rchild) return 1; /葉子結點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的結點為根的子樹深度 if(T->data=x) cout«Get_Depth(T)vvendl; /找到了值為 x的結點，求其深度 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)個結點的m叉樹共有n*m個鏈域，除根結點外，每個結點均有一個指針所指，故該樹的空鏈域有n*m-( n-1)=n( m-1)+1個。這種存儲結構統(tǒng)便于處理，但空鏈域造成存儲效率低。9. 解：方案1;哈夫曼編碼先將概率放大100倍，以方便構造哈夫曼樹。w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則:構造哈夫曼樹如下：(100).(40)-”( 60)” 192132.(2810 623子母編號對應編碼出現(xiàn)頻率111000.072000.193Imo0.02可mo0.065io0.326iiiii0.037010.21r 8110