數(shù)據(jù)結(jié)構(gòu)第五章自測(cè)題及解答

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

2、棵完全二叉樹(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)和存儲(chǔ)結(jié)構(gòu)兩類(lèi)存儲(chǔ)

3、結(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） 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ù)中，一共有個(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ù)的主要遍歷方法有、等三種。23 .由轉(zhuǎn)換成二叉樹(shù)時(shí)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。24 .哈夫曼（Huffman）樹(shù)是帶權(quán)路徑度的樹(shù)，通常權(quán)值較大的結(jié)點(diǎn)離根。25 .用5個(gè)權(quán)值3,2,4,5,1構(gòu)造的哈夫曼（Huffman）樹(shù)的

5、帶權(quán)路徑長(zhǎng)度是。二、選擇題（每空1分，共12分）（）1不含任何結(jié)點(diǎn)的空樹(shù)。（A）是一;（B）是一;（C）是一棵樹(shù)也是一棵二叉樹(shù)；（D）既不是樹(shù)也不是二叉樹(shù)（）2二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)，所以。(B)它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)(D)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(A)它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)；(C)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)都不能使用()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)有多

6、種，但根結(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,，Tmi每個(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<mDo一個(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ù)ja。在完全的二叉樹(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,而N的右子

7、女是它在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的D。供選擇的答案A:是特殊的樹(shù)不是樹(shù)的特殊形式是兩棵樹(shù)的總稱(chēng)有是只有二個(gè)根結(jié)點(diǎn)的樹(shù)形結(jié)構(gòu)B：左子結(jié)點(diǎn)右子結(jié)點(diǎn)左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn)兄弟CD:最左子結(jié)點(diǎn)最右子結(jié)點(diǎn)最鄰近的右兄弟最鄰近的左兄弟最左的兄弟最右的兄弟答案：A=B=C=D=7 .以下說(shuō)法錯(cuò)誤的是()一般在哈夫曼樹(shù)中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近哈夫曼樹(shù)中沒(méi)有度數(shù)為1的分支結(jié)點(diǎn)若初始森林中共有n裸二叉樹(shù)，最終求得的哈夫曼樹(shù)共有2n-1個(gè)結(jié)點(diǎn)若初始森林中共有n裸二叉樹(shù)，進(jìn)行2n-1次合并后才能剩下一棵最終的哈夫曼樹(shù)三、綜合題(1-9每題3分，10-11每題4分，共35分)1.給定二叉樹(shù)的兩種遍歷序列，分別是：前序遍歷

8、序列：D,A,C,E,B,H,F,G,I；中序遍歷序列：D,C,B,E,H,A,QI,F,2.給定如圖所示二叉樹(shù) T,請(qǐng)畫(huà)出與其對(duì)應(yīng)的中序線索二叉樹(shù)。試畫(huà)出二叉樹(shù)Bo282533八/4060085433 .試寫(xiě)出如圖所示的二叉樹(shù)分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序歹U。4.把如圖所示的樹(shù)轉(zhuǎn)化成二叉樹(shù)。5 .編寫(xiě)遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。6 .寫(xiě)出求二叉樹(shù)深度的算法。7 .編寫(xiě)遞歸算法，求二叉樹(shù)中以元素值為x的結(jié)點(diǎn)為根的子樹(shù)的深度。8 .編寫(xiě)算法判別給定二叉樹(shù)是否為完全二叉樹(shù)。9 .假設(shè)用于通信白電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07,0.19,0.02,0.

9、06,0.32,0.03,0.21,0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。使用07的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。10 .試編寫(xiě)最小堆類(lèi)的下滑調(diào)整算法成員函數(shù)。（注：程序頭已給出，類(lèi)定義略：已通過(guò)數(shù)組heap建堆）template<classT>voidMinHeap<T>:siftDown(intstart,intm)11 .Supposeyouhaveabinarytreewhosedatafieldsaresinglecharacters.Whenthedatafieldsofthenodesareoutputininorder,theou