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

1、頁(yè)眉內(nèi)容一、概念題(每空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的滿二叉樹(shù)有個(gè)分支結(jié)點(diǎn)和個(gè)葉子。4 .一棵具有257個(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 .滿二叉樹(shù)上各層的節(jié)點(diǎn)數(shù)已達(dá)到了二叉樹(shù)可以容納的。滿二叉樹(shù)也是二叉樹(shù),但反之不然。8 .設(shè)一棵完全二叉樹(shù)有700個(gè)結(jié)點(diǎn)，則共有個(gè)葉子

2、結(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ù)的遍歷次序有六種。最常用的是三種：前序法(即按NLR次序)，后序法(即按次序)和中序法(也稱(chēng)對(duì)稱(chēng)序法，即按LNR次序)。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹(shù)的前序序列是BEFCGDH,中序序列是FEBGCHD,則它的后序序列必是。12 .中序遍歷的遞歸算法平均空間復(fù)雜度為。13 .二叉樹(shù)通常有存儲(chǔ)結(jié)構(gòu)和

3、存儲(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)為若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ù)中，一共有個(gè)指針域淇中只有個(gè)用來(lái)指向結(jié)點(diǎn)的左右

4、孩子，其余的個(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,左、右孩子域lchild、rchild和左、右標(biāo)志域ltag,rtag。規(guī)定，標(biāo)志域?yàn)?是線索，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)換成二叉樹(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分)()1.不含任何結(jié)點(diǎn)的空樹(shù)。(A)是一棵樹(shù)；(C)是一棵樹(shù)也是一棵二叉樹(shù)()2.二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)，所以。(A

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

7、是樹(shù)，此時(shí)結(jié)點(diǎn)T稱(chēng)為T(mén)的父結(jié)點(diǎn)，下稱(chēng)為T(mén)的子結(jié)點(diǎn)(1<i<nDo一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的C。供選擇的答案A:有。個(gè)或1個(gè)有。個(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ù))。在完全的二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有B,則它必定是葉結(jié)點(diǎn)。每棵樹(shù)都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹(shù)。由樹(shù)轉(zhuǎn)換成的二叉樹(shù)里，一個(gè)結(jié)點(diǎn)N的左子女是N在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的C。供選擇的答案A:是特殊的樹(shù) 形結(jié)構(gòu)B:左子結(jié)點(diǎn)C:最左子結(jié)點(diǎn)不是樹(shù)的特殊形式是兩棵樹(shù)的總稱(chēng)有是只有二個(gè)根結(jié)點(diǎn)的樹(shù)右子結(jié)點(diǎn)左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn)兄弟弟最左的兄弟最

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

9、x的結(jié)點(diǎn)為根的子樹(shù)的深度。8 .設(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)制表示形式是另一種編碼方案。對(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-

10、1)是一個(gè)堆，現(xiàn)自底向上將mid,last)調(diào)整為一個(gè)堆。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é)點(diǎn)的一個(gè)孩子、空指針2n、n-1、n+1二叉鏈表、三叉鏈表左子樹(shù)、右子樹(shù)、左子樹(shù)、右子樹(shù)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、 樹(shù)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的左、右子樹(shù)。然后由其左子樹(shù)的元素集合和右子樹(shù)的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root,不斷遞歸，則所有元素都將被唯一確定，問(wèn)題得解。2.解：要遵循中序遍歷的軌跡來(lái)畫(huà)出每個(gè)前驅(qū)和后繼。中序遍歷序列：55 40 25 60 28 08 33 542840600854553.該算術(shù)表達(dá)式轉(zhuǎn)化的二叉樹(shù)如圖所示。LRD:JFKGDBHLMIECA5思路：輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用任何一種遍歷遞歸算法，凡是左右指針均空者，則為葉子,將其打印出來(lái)。法一：核心部分為：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)/求二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目一if(!T)return0;/空樹(shù)沒(méi)有葉子elseif(!T->lchild&&!T->rchild)return1;/葉子結(jié)點(diǎn)els

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

15、et_Sub_Depth(T->rchild,x);在左右子樹(shù)中繼續(xù)尋找/Get_Sub_DepthintGet_Depth(BinaryTreeT)求子樹(shù)深度的遞歸算法一if(!T)return0;elsem=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)子母編P對(duì)應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.1