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

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

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

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

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

5、rdethread(thr)p=thr->lchild;while(p<>thr)/未循環(huán)結(jié)束while(14P=；printf(p->data);while(3)p=(4)_；printf(p->data);23 .由轉(zhuǎn)換成二叉樹時，其根結(jié)點的右子樹總是空的。24 .哈夫曼(Huffman)樹是帶權(quán)路徑長度的樹，通常權(quán)值較大的結(jié)點離根25 .用5個權(quán)值3,2,4,5,1構(gòu)造的哈夫曼(Huffman)樹的帶權(quán)路徑長度是。二、選擇題(每空1分，共10分)()1.不含任何結(jié)點的空樹。(A)是一棵樹；(C)是一棵樹也是一棵二叉樹()2.二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以。(A

6、)它不能用順序存儲結(jié)構(gòu)存儲；(C)順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲都不能使用(B)是一棵二叉樹；(D)既不是樹也不是二叉樹(B)它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲(D)順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)()3.具有n(n>0)個結(jié)點的完全二叉樹的深度為。(A)log2(n)(B)log2(n)(C)log2(n)+1(D)log2(n)+1()4.把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是。(A)唯一的(B)有多種(C)有多種，但根結(jié)點都沒有左孩子(D)有多種，但根結(jié)點都沒有右孩子5 .樹是結(jié)點的有PM集合，它A根結(jié)點，記為To其余的結(jié)點分成為m(m>0)jB的集合T1,T2,，Tm,每個集合又都

7、是樹，此時結(jié)點T稱為T的父結(jié)點，下稱為T的子結(jié)點(1<i<nDo一個結(jié)點的子結(jié)點個數(shù)為該結(jié)點的C。供選擇的答案A:有。個或1個有。個或多個有且只有1個有1個或1個以上B：互不相交允許相交允許葉結(jié)點相交允許樹枝結(jié)點相交C:權(quán)維數(shù)次數(shù)序答案：A=B=C=6 .二叉樹)。在完全的二叉樹中，若一個結(jié)點沒有B,則它必定是葉結(jié)點。每棵樹都能惟一地轉(zhuǎn)換成與它對應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹里，一個結(jié)點N的左子女是N在原樹里對應(yīng)結(jié)點的C。供選擇的答案A:是特殊的樹 形結(jié)構(gòu)B:左子結(jié)點C:最左子結(jié)點不是樹的特殊形式是兩棵樹的總稱有是只有二個根結(jié)點的樹右子結(jié)點左子結(jié)點或者沒有右子結(jié)點兄弟弟最左的兄弟最

8、右的兄弟最右子結(jié)點最鄰近的右兄弟最鄰近的左兄答案：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,QI,F,試畫出二叉樹B。2 .給定如圖所示二叉樹T,請畫出與其對應(yīng)的中序線索二叉樹。3 .將算術(shù)表達(dá)式(a+b)+c*(d+e)+f)*(g+h)轉(zhuǎn)化為二叉樹。4 .試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結(jié)點序歹U。5 .編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。6 .寫出求二叉樹深度的算法。7 .編寫遞歸算法，求二叉樹中以元素值為

9、x的結(jié)點為根的子樹的深度。8 .設(shè)度為m的樹采用多重鏈表存儲。每個結(jié)點有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è)計哈夫曼編碼。使用07的二進(jìn)制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。10 .試編寫最大堆的向上調(diào)整算法函數(shù)。要求：寫成內(nèi)聯(lián)函數(shù)的形式，程序頭已給出，已通過數(shù)組heap建堆，建堆區(qū)間由遍歷器first、mid和last指向，即mid,last-

10、1)是一個堆，現(xiàn)自底向上將mid,last)調(diào)整為一個堆。template<classRaniter,classT>inlinevoid_fixup(Raniterfirst,Ranitermid,Raniterlast,Tt)參考答案一、概念題(每空1分，共55分)1、分支層次、根、直接前趨2、53、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、31 3292i-12 k-1n2+1最大值、完全350 (n/2 = 350)500 499 1 0n 2L R N F E G H D C BO順序、鏈?zhǔn)礁?、i / 2、左孩子、右孩子

11、、根指向該結(jié)點的一個孩子、空指針2n、n-1、n+1二叉鏈表、三叉鏈表左子樹、右子樹、左子樹、右子樹1、 02i、右孩子、2i+1NULL22、(1)p->ltag=0(2)p->lchild(5)p=p->rchild(3)p->rtag=1&&p->rchild!=thr(4)p=p->rchild22、 樹23、 最短、較近24、 33二、選擇題(每空1分，共10分)1.C2.C3.C4.A5.A=(DB=C=®6.A=(2)B=(DC=CD三、綜合題(1-9每題3分，10-11每題4分，共35分)1.解：方法是：由前序先確定

12、root,由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root,不斷遞歸，則所有元素都將被唯一確定，問題得解。2.解：要遵循中序遍歷的軌跡來畫出每個前驅(qū)和后繼。中序遍歷序列：55 40 25 60 28 08 33 542840600854553.該算術(shù)表達(dá)式轉(zhuǎn)化的二叉樹如圖所示。LRD:JFKGDBHLMIECA5思路：輸出葉子結(jié)點比較簡單，用任何一種遍歷遞歸算法，凡是左右指針均空者，則為葉子,將其打印出來。法一：核心部分為：DLR(BinaryTreeNode*root)/*中序遍歷遞

13、歸函數(shù)*/if(root!=NULL)if(root->lchild=NULL)&&(root->rchild=NULL)sum+;cout<<root->data<<endl;DLR(root->lchild);DLR(root->rchild);return(0);法二：intLeafCount_BiTree(BinaryTreeT)/求二叉樹中葉子結(jié)點的數(shù)目一if(!T)return0;/空樹沒有葉子elseif(!T->lchild&&!T->rchild)return1;/葉子結(jié)點els

14、ereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);/左子樹的葉子數(shù)加上右子樹的葉子數(shù)一一LeafCount_BiTree6.解答略(參考教材)7.intGet_Sub_Depth(BinaryTreeT,intx)求二叉樹中以值為x的結(jié)點為根的子樹深度7if(T->data=x)cout<<Get_Depth(T)<<endl;/找到了值為x的結(jié)點，求其深度exit1;elseif(T->lchild)Get_Sub_Depth(T->lchild,x);if(T->rchild)G

15、et_Sub_Depth(T->rchild,x);在左右子樹中繼續(xù)尋找/Get_Sub_DepthintGet_Depth(BinaryTreeT)求子樹深度的遞歸算法一if(!T)return0;elsem=Get_Depth(T->lchild);n=Get_Depth(T->rchild);return(m>n?m:n)+1;Get_Depth8 .n(n>0)個結(jié)點的m叉樹共有n*m個鏈域，除根結(jié)點外，每個結(jié)點均有一個指針?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)子母編P對應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.1