數(shù)據(jù)結(jié)構(gòu)第二單元練習(xí)題答案

1、數(shù)據(jù)結(jié)構(gòu)第二單元練習(xí)題答案一、選擇1.樹最適合用來表示( )A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素 C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)2.在下述結(jié)論中，正確的是( )只有一個結(jié)點的二叉樹的度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換;深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。 A. B. C. D.3.以下說法正確的是( )A.任何一棵二叉樹中至少有一個結(jié)點的度為2B.任何一棵二叉樹中每個結(jié)點的度都為2C.任何一棵二叉樹的度肯定等于2D.任何一棵二叉樹的度可以小于24.在下列情況中，可稱為二叉樹的是( )A.每個結(jié)點至多有兩棵子樹的樹 B.哈夫曼

2、樹C.每個結(jié)點至多有兩棵子樹的有序樹 D.每個結(jié)點只有一棵右子樹 E.以上答案都不對5.深度為h的滿m叉樹的第k層有( )個結(jié)點(1=<k=<h) A.mk-1 B.mk-1 C.mh-1 D.mh-16.在一棵高度為k的滿二叉樹中，結(jié)點總數(shù)為( )A.2k-1 B.2k C.2k-1 D.ëlog2kû+17.在一棵三元樹中度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為( )個 A.4 B.5 C.6 D.7 8.具有10個葉結(jié)點的二叉樹中有( )個度為2的結(jié)點。 A.8 B.9 C.10 D.ll9.二叉樹有n個結(jié)點，則

3、其深度為（ ）A.n-1 B.n C.(log2n)+1 D.無法確定該題是二叉樹不是完全二叉樹由二叉樹結(jié)點的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1， 因為n=1001,所以1002=2n0+n1,在完全二叉樹樹中，n1只能取0或1,在本題中只能取0，故n=501，因此選E。10.一個具有1025個結(jié)點的二叉樹的高h為( )A.11 B10 C.11至1025之間 D.10至1024之間11.一棵具有 n個結(jié)點的完全二叉樹的深度是( )A.ëlog2nû+1 B.log2n+1 C.ëlog2nû D.log2n-112.

4、將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度( )A.4 B.5 C.6 D.7 13.將一棵有100個結(jié)點的完全二叉樹從根結(jié)點這一層開始，每一層上從左到右依次對結(jié)點編號，根結(jié)點的編號為1，則編號為49的結(jié)點的左孩子編號為（ ）A.98 B.99 C.50 D.48利用二叉樹的性質(zhì)514.在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒( )A.左子結(jié)點 B.右子結(jié)點 C.左子結(jié)點和右子結(jié)點 D.左子結(jié)點，右子結(jié)點和兄弟結(jié)點15.當(dāng)一棵有n個結(jié)點的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在一維數(shù)組 Al.n中時，數(shù)組中第i個結(jié)點的左孩子為( )A.A2i(2i=<

5、;n) B.A2i+1(2i+1=<n) C.Ai/2 D.無法確定16.在下列存儲形式中，( )不是樹的存儲形式？A.雙親表示法 B.孩子鏈表表示法 C.孩子兄弟表示法 D.順序存儲表示法17.以下說法錯誤的是( )A.完全二叉樹上結(jié)點之間的父子關(guān)系可由它們編號之間的關(guān)系來表達B.三叉鏈表，二叉樹求雙親運算很容易實現(xiàn)C在二叉鏈表上，求左.右孩子等很容易實現(xiàn)D.在二叉鏈表上，求雙親運算的時間性能很好18.對二叉樹從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左右孩子的編號，同一個結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用（ ）次序的遍歷實現(xiàn)編號。 A.先序遍歷 B.中序

6、遍歷C.后序遍歷 D.從根開始的層次遍歷19.某二叉樹T有n個結(jié)點，設(shè)按某種順序?qū)中的每個結(jié)點進行編號，編號為1，2， ，n，且有如下性質(zhì)：T中任一結(jié)點V，其編號等于左子樹上的最小編號減1，而V的右子樹的結(jié)點中，其最小編號等于V左子樹上結(jié)點的最大編號加1。這時是按( )編號的。A.中序遍歷序列 B.前序遍歷序列 C.后序遍歷序列 D.層次順序 20.一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反,則該二叉樹一定滿足( )A.所有的結(jié)點均無左孩子 B.所有的結(jié)點均無右孩子 C.只有一個葉子結(jié)點D.是任意一棵二叉樹先序序列是“根左右”，后序序列是“左右根”，若要這兩個序列相反，只有單支樹，

7、所以本題的A和B均對，單支樹的特點是只有一個葉子結(jié)點，故C是最合適的，選C。A或B都不全21.對含有( )個結(jié)點的非空二叉樹，采用任何一種遍歷方式，其結(jié)點訪問序列均相同。A.0 B.1 C.2 D.不存在這樣的二叉樹22.下面的說法中正確的是( )(1)任何一棵二叉樹的葉子結(jié)點在三種遍歷中的相對次序不變；(2)按二叉樹定義，具有三個結(jié)點的二叉樹共有6種。A. (1)(2) B. (1) C. (2) D. (1).(2)都錯 23.以下說法錯誤的是( )A.存在這樣的二叉樹，對它采用任何次序的遍歷，其結(jié)點訪問序列均相同B.二叉樹是樹的特殊情形C.由樹轉(zhuǎn)換成二叉樹，根結(jié)點右子樹總是空的D.在二叉

8、樹只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹24.以下說法正確的是( )A.一般來說，若深度為k的n個結(jié)點的二叉樹具有最小路徑長度，那么從根結(jié)點到第k-1層具有最多的結(jié)點數(shù)為2k-1-1余下的n-2k-1+1個結(jié)點在第k層的任一位置上B.若有一個結(jié)點是某二叉樹子樹的先序遍歷序列中的最后一個結(jié)點，則它必是該子樹的后序遍歷序列中的最后一個結(jié)點。C.若一個結(jié)點是某二叉樹子樹的前序遍歷序列中的最后一個結(jié)點，則它必是該子樹的中序遍歷序列中的最后一個結(jié)點。25.以下說法正確的是( )A.若一個樹葉是某二叉樹子樹的前序遍歷序列中的最后一個結(jié)點，則它必是該子樹的后序遍歷序列中的最后一個結(jié)點。B.

9、若一個樹葉是某二叉樹子樹的前序遍歷序列中的最后一個結(jié)點，則它必是該子樹的中序離歷序列中的最后一個結(jié)點C.二叉樹中，具有兩個孩子的父結(jié)點，在中序遍歷序列中，它的后繼結(jié)點最多只能有一個孩子結(jié)點。D.在二叉樹中，具有一個孩子結(jié)點，在中序遍歷序列中，它沒有后繼孩子結(jié)點。26.以下說法錯誤的是( )A.赫夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。B.若一個二叉樹的樹葉是某子樹的中序遍歷序列中的第一個結(jié)點，則它必是該子樹的后序遍歷序列中的第一個結(jié)點。C.已知二叉樹的前序遍歷和后序遍歷序列并不能惟一地確定這棵樹，因為不知道樹的根結(jié)點是哪一個。D.在前序遍歷二叉樹的序列中，任何結(jié)點的子樹的所

10、有結(jié)點都是直接根在該結(jié)點的之后。27.以下說法正確的是( )A.若一個樹葉是某二叉樹前序遍歷序列中的最后一個結(jié)點,則它必是該子樹后序遍歷序列中的最后一個結(jié)點.B.若一個樹葉是某二叉樹前序遍歷序列中的最后一個結(jié)點,則它必是該子樹中序遍歷序列中的最后一個結(jié)點.C.在二叉樹中,具有兩個子女的父結(jié)點,在中序遍歷序列中,它的后繼結(jié)點最多只能有一個子女結(jié)點.D.在二叉樹中,具有一個子女的父結(jié)點,在中序遍歷序列中,它沒有后繼子女結(jié)點28.二叉樹先序遍歷：EFHIGJK；中序遍歷: HFIEJKG 。該二叉樹根的右子樹的根是( )A.E B.F C.G D.H 29.已知某二叉樹的后續(xù)遍歷序列是dabec,中

11、序遍歷序列是deabc,它的前序遍歷序列是( )A.acbed B.deabc C.decab D.cedba30.某二叉樹的前序遍歷結(jié)點訪問順序是abdgcefh,中序遍歷的結(jié)點訪問順序是dgbaechf,其后序遍歷的結(jié)點訪問順序是( )A.bdgcefha B.gdbecfha C.bdgechfa D.gdbehfca31.若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左.右子樹的位置，利用( )遍歷方法最合適。A.前序 B.中序 C.后序 D.按層次32已知一算術(shù)表達式的中綴形式為 A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為( )A.-A+B*C/DE B.-A

12、+B*CD/EC.-+*ABC/DE D.-+A*BC/DE33.算術(shù)表達式a+b*（c+d/e）轉(zhuǎn)為后綴表達式后為( )A.ab+cde/* B.abcde/+*+ C.abcde/*+ D.abcde*/+34.一棵左右子樹均不空的二叉樹在先序線索化后，其空指針域數(shù)為（ ） A.0 B.1 C.2 D.不確定二叉樹先序遍歷序列的第一個結(jié)點無前驅(qū)，但第一個結(jié)點為根結(jié)點，有左孩子，所以左指針域不為空。最后一個結(jié)點無后繼，而且是葉子結(jié)點，無右孩子，所以仍為空。其余結(jié)點均有前驅(qū)和后繼，所以不會為空。35.一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是( )A.不確定 B.0 C.1 D

13、.2 左子樹為空的二叉樹的根結(jié)點的左線索為空（無前驅(qū)），先序序列的最后結(jié)點的右線索為空（無后繼），共2個空鏈域。36.若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則x的前驅(qū)為( )A.X的雙親 B.X的右子樹中最左的結(jié)點 C.X的左子樹中最右結(jié)點 D.X的左子樹中最右葉結(jié)點37.引入二叉線索樹的目的是( )A.加快查找結(jié)點的前驅(qū)或后繼的速度 B.為了能在二叉樹中方便的進行插入與刪除C.為了能方便的找到雙親 D.使二叉樹的遍歷結(jié)果唯一38.n個結(jié)點的線索二叉樹上含有的線索數(shù)為( )A.2n B.nl C.nl D.n 線索二叉樹是利用二叉樹的空鏈域加上線索，n個結(jié)點的二叉樹有n+1個空

14、鏈域。39.討論樹.森林和二叉樹的關(guān)系，目的是為了( )A.借助二叉樹上的運算方法去實現(xiàn)對樹的一些運算B.將樹.森林按二叉樹的存儲方式進行存儲C.將樹.森林轉(zhuǎn)換成二叉樹D.體現(xiàn)一種技巧，沒有什么實際意義40.利用二叉鏈表存儲樹，則根結(jié)點的右指針是( )A.指向最左孩子 B.指向最右孩子 C.空 D.非空41.如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的后序就是T2中結(jié)點的( )A.先序 B.中序 C.后序 D.層次序42.樹的基本遍歷策略可分為先根遍歷和后根遍歷;二叉樹的基本遍歷策略可分為先序.中序和后序三種遍歷。我們把由樹轉(zhuǎn)化得到的二叉樹稱該樹對應(yīng)的二叉樹，則下面 ( )是正確的。A

15、.樹的先根遍歷序列與其對應(yīng)的二叉樹先序遍歷序列相同B.樹的后根遍歷序列與其對應(yīng)的二叉樹后序遍歷序列相同C.樹的先根遍歷序列與其對應(yīng)的二叉樹中序遍歷序列相同D.以上都不對43.以下說法正確的是( )A.先根遍歷樹和先序遍歷與該樹對應(yīng)的二叉樹，其結(jié)果不同B.后根遍歷樹和先序遍歷與該樹對應(yīng)的二叉樹，其結(jié)果不同C.先序遍歷森林和先序遍歷與該森林對應(yīng)的二叉樹，其結(jié)果不同D.中序遍歷森林和中序遍歷與該森林對應(yīng)的二叉樹，其結(jié)果不同44.森林T中有4棵樹，第一.二.三.四棵樹的結(jié)點個數(shù)分別是n1,n2,n3,n4,那么當(dāng)把森林T轉(zhuǎn)換成一棵二叉樹后，且根結(jié)點的左孩子上有( )個結(jié)點。A.n1-1 B.n1 C.

16、n1+n2+n3 D.n2+n3+n445.設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是( ) A.m-n B.m-n-1 C.n+1 D.條件不足，無法確定 46.設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有( )個A.n-1 B.n C.n+1 D.n+2 47.以下說法錯誤的是( )A.一般在哈夫曼樹中,權(quán)值越大的葉子離根結(jié)點越近B.哈夫曼樹中沒有度數(shù)為1的分支結(jié)點C.若初始森林中共有N棵二樹,最終求得的哈夫曼樹中共有2N-1個結(jié)點D.若初始森林中共有N棵二叉樹,進行2N-1次合并后

17、才能剩下最終的哈夫曼樹48.以下說法錯誤的是( )A.一般在赫夫曼樹中，權(quán)值越大的葉子離根結(jié)點越近B.赫夫曼樹中沒有度數(shù)為1的分支結(jié)點C.若初始森林中共有n棵二叉樹，最終求得的赫夫曼樹共有2n-1個結(jié)點D.若初始森林中共有n棵二叉樹，進行2n-1次合并后才能剩下一棵最終的赫夫曼樹49.設(shè)有13個值,用它們組成一棵哈夫曼樹,則該哈夫曼樹共有( )個結(jié)點.A.13 B.12 C.26 D.2550.若度為m的哈夫曼樹中，其葉結(jié)點個數(shù)為n，則非葉結(jié)點的個數(shù)為( )A.n-1 B.ën/mû-1 C.é(n-1)/(m-1)ù D. én/(m-1)&

18、#249;-1 E.é(n+1)/(m+1)ù-151.下述編碼中哪一個不是前綴碼( )A.00,01,10,11 B.0,1,00,11 C.0,10,110,111 D. 1,01,000,001二、填空1.n（n>1）個結(jié)點的各棵樹中，其深度最小的那棵樹的深度是_(1) 2 _。它共有_(2) n-1 _個葉子結(jié)點和_(3) 1 _個非葉子結(jié)點，其中深度最大的那棵樹的深度是_(4) n _，它共有_(5)_ 1 _個葉子結(jié)點和_(6) n-1_個非葉子結(jié)點。2.如果結(jié)點A有 3個兄弟，而且B是A的雙親，則B的度是_4 _。3.二叉樹由_(1) 根結(jié)點_，_(2)

19、 左子樹_，_(3) 右子樹 _三個基本單元組成。4設(shè)只含根結(jié)點的二叉樹的高度為0，則高度為k的二叉樹的最大結(jié)點數(shù)為_(1)2K+1-1_,最小結(jié)點數(shù)為_(2)_ k+1_。5.在一棵二叉樹中，度為零的結(jié)點的個數(shù)為N0,度為2的結(jié)點的個數(shù)為N2,則有N0 =_ N2+1_6.如某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)為_69_。7.高度為K的完全二叉樹至少有_2k-2_個葉子結(jié)點。8.高度為8的完全二叉樹至少有_64 _個葉子結(jié)點。9.已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少是_ 99_。10.已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，

20、4個度為3的結(jié)點，則該樹有_12 _個葉子結(jié)點。11.一棵樹T中，包括一個度為1的結(jié)點，兩個度為2的結(jié)點，三個度為3的結(jié)點，四個度為4的結(jié)點和若干葉子結(jié)點，則T的葉結(jié)點數(shù)為_21_。11.一棵有n個結(jié)點的滿二叉樹有_(1) 0 _個度為1的結(jié)點、有_(2) (n-1)/2_個分支 （非 終端）結(jié)點和_(3) (n+1)/2 _個葉子，該滿二叉樹的深度為_(4) ëlog2nû +1_。12.深度為k（設(shè)根的層數(shù)為1）的完全二叉樹至少有 (1) 2k-1 個結(jié)點，至多有 (2) 2k-1 個結(jié)點，k和結(jié)點數(shù)n之間的關(guān)系是 (3) k= ë log2n û

21、1 。13在完全二叉樹中，編號為i和j的兩個結(jié)點處于同一層的條件是_ëlog2iû=ëlog2jû _。14.對于一個具有n個結(jié)點的二叉樹，當(dāng)它為一棵_(1) 完全二叉樹_二叉樹時具有最小高度，當(dāng)它為一棵_(2) 單枝樹，樹中任一結(jié)點（除最后一個結(jié)點是葉子外）,只有左子女或只有右子女。_時，具有最大高度。15.假設(shè)根結(jié)點的層數(shù)為，具有個結(jié)點的二叉樹的最大高度是_ n _。16.具有256個結(jié)點的完全二叉樹的深度為_9 _。17.一棵完全二叉樹有999個結(jié)點，它的深度是 10 。18.一個有2001個結(jié)點的完全二叉樹的高度為_ 11 _。19.二叉樹有不同

22、的鏈式存儲結(jié)構(gòu)，其中最常用的是 (1)二叉鏈表 與 三叉鏈表 。20.二叉樹的先序序列和中序序列相同的條件是_任一結(jié)點均無左孩子_。21.在一棵二叉樹中，若有一個結(jié)點是它的雙親的左子女，且它的雙親有右子女，則這個結(jié)點在后序遍歷中的后繼結(jié)點是_雙親的右子樹中最左下的葉子結(jié)點_。22.每一棵樹都能唯一的轉(zhuǎn)換為它所對應(yīng)的二叉樹。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列是_(1) FEGHDCB _。設(shè)上述二叉樹是由某棵樹（或森林）轉(zhuǎn)換而成，則第一棵樹的先根次序序列是_(2)_ BEF23.二叉樹結(jié)點的中序序列為ABCDEFG,后序序列為BDCAFGE,則該

23、二叉樹結(jié)點的前序序列為_(1) EACBDGF _,則該二叉樹對應(yīng)的樹林包括_(2) 2_棵樹。24.已知一棵二叉樹的前序序列為abdecfhg,中序序列為dbeahfcg，則該二叉樹的根為_(1) a _，左子樹中結(jié)點有_(2) dbe _， 右子樹中結(jié)點有_(3) hfcg _。25.現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有_(1) 5 _種不同的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是_(2)_ 略 _（畫出樹型）。26.中綴式a+b*3+4*（c-d）對應(yīng)的前綴式為_(1) +a*b3*4-cd _，若a=1，b=2，c=3，d=4，則后綴式db/cc*a-b*+的運算結(jié)果為_(2

24、) 18_。27.線索二叉樹的左線索指向其 (1) 前驅(qū) ,右線索指向其 (2) 后繼 .28.一棵左子樹為空的二叉樹在先序線索化后，其中的空鏈域的個數(shù)為：_2_。29.樹在計算機內(nèi)的表示方式有_(1) 雙親表示法_，_(2) 孩子表示法_，_(3) 孩子兄弟表示法30.利用樹的孩子兄弟表示法存儲，可以將一棵樹轉(zhuǎn)換為_二叉樹 _。31.設(shè)F是由T1,T2,T3三棵樹組成的森林,與F對應(yīng)的二叉樹為B,已知T1,T2,T3的結(jié)點數(shù)分別為n1,n2和n3則二叉樹B的左子樹中有_(1) n1-1_個結(jié)點，右子樹中有_(2) n2+n3 _個結(jié)點。32.先根次序遍歷樹林正好等同于按_(1) 先序_遍歷對

25、應(yīng)的二叉樹，后根次序遍歷樹林正好等同于按_(2) 中序_遍歷對應(yīng)的二叉樹。33.先根次序遍歷森林正好等同于按_先序_遍歷對應(yīng)的二叉樹；中根次序遍歷森林正好等同于_中序_遍歷對應(yīng)的二叉樹。34.哈夫曼樹是_帶權(quán)路徑長度最小的二叉樹，又稱最優(yōu)二叉樹_。35.設(shè)n0為哈夫曼樹的葉子結(jié)點數(shù)目，則該哈夫曼樹共有 2n0-1 個結(jié)點。36.哈夫曼樹是帶權(quán)路徑長度 最短 的樹,通常權(quán)值較大的結(jié)點離根 較近 .37.若以4，5，6，7，8作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是_69 _。38.有一份電文中共使用 6個字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，試構(gòu)造一

26、棵哈夫曼樹，則其加權(quán)路徑長度WPL為_(1) 80_，字符c的編碼是_(2) 001（不唯一）_。39.下面是求二叉樹高度的類C寫的遞歸算法試補充完整。二叉樹的兩指針域為lchild與rchild, 算法中p為二叉樹的根，lh和rh分別為以p為根的二叉樹的左子樹和右子樹的高，hi為以p為根的二叉樹的高，hi最后返回。height(p)if (1) p _) if(p->lchild=null) lh=(2)_ 0_; else lh=(3)_ height(p->lchild)_;if(p->rchild=null) rh=(4)_ 0_; else rh=(5)_ heig

27、ht(p->rchild)_;if (lh>rh) hi=(6) lh+1_；else hi=(7)_ rh+1_; else hi=(8) 0_;return hi;/ 40.二叉樹用二叉鏈表存儲，以下程序為求二叉樹深度的遞歸算法，請?zhí)羁胀晟浦?int depth(bitree bt) /*bt為根結(jié)點的指針*/int hl,hr; if (bt=NULL) return(1) 0 _); hl=depth(bt->lchild); hr=depth(bt->rchild); if(2) hl>hr _) (3)_ hr=hl _； return(hr+1);

28、三、判斷題1.二叉樹是一般樹的特殊情形。×2.由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹，這種說法( X )3.二叉樹中每個結(jié)點至多有兩個子結(jié)點,而對一般樹則無此限制.因此,二叉樹是樹的特殊情形. ×4.樹形結(jié)構(gòu)中元素之間存在一個對多個的關(guān)系。5.二叉樹是度為2的有序樹。×6.如果二叉樹中某結(jié)點的度為1，則說該結(jié)點只有一棵子樹( )7.深度為K的二叉樹中結(jié)點總數(shù)2k-1。8.完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是樹葉。9.對于有N個結(jié)點的二叉樹，其高度為log2n。×10.深度為k具有n個結(jié)點的完全二叉樹，其編號最小的結(jié)點序號為 &

29、#235;2k-2û+1。×11.用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點。×12.完全二叉樹的存儲結(jié)構(gòu)通常采用順序存儲結(jié)構(gòu)。13.二叉樹只能用二叉鏈表表示。14.用鏈表存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n-1個空指針。×15.二叉樹的遍歷結(jié)果不是唯一的. 只有在確定何序（前序、中序、后序或?qū)哟危┍闅v后，遍歷結(jié)果才唯一。16.二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序。17.二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面，這種說法( )18.非空的二叉樹一定滿足：某結(jié)點若有左孩子，則其中序前驅(qū)一定沒有右孩子其中序前

30、驅(qū)是其左子樹上按中序遍歷的最右邊的結(jié)點（葉子或無右子女），該結(jié)點無右孩子。19.由一棵二叉樹的前序序列和后序序列可以唯一確定它。×20.在中序線索二叉樹中，每一非空的線索均指向其祖先結(jié)點。在二叉樹上，對有左右子女的結(jié)點，其中序前驅(qū)是其左子樹上按中序遍歷的最右邊的結(jié)點（該結(jié)點的后繼指針指向祖先），中序后繼是其右子樹上按中序遍歷的最左邊的結(jié)點（該結(jié)點的前驅(qū)指針指向祖先）。21.線索二叉樹的優(yōu)點是便于是在中序下查找前驅(qū)結(jié)點和后繼結(jié)點。22.二叉樹中序線索化后，不存在空指針域。×非空二叉樹中序遍歷第一個結(jié)點無前驅(qū)，最后一個結(jié)點無后繼，這兩個結(jié)點的前驅(qū)線索和后繼線索為空指針。23.給

31、定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。24.必須把一般樹轉(zhuǎn)換成二叉樹后才能進行存儲。×25.將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點沒有左子樹；×26.采用二叉鏈表作存儲結(jié)構(gòu)，樹的前序遍歷和其相應(yīng)的二叉樹的前序遍歷的結(jié)果是一樣的。27.一棵一般樹的結(jié)點的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點前序遍歷和后序遍歷是一致的。×28.一棵樹中的葉子數(shù)一定等于與其對應(yīng)的二叉樹的葉子數(shù)。×29.在葉子數(shù)目和權(quán)值相同的所有二叉樹中，最優(yōu)二叉樹一定是完全二叉樹，該說法（ X）。30.在二叉樹中插入結(jié)點，則它不再是二叉樹了。×31.哈夫曼樹的結(jié)點個數(shù)不能是偶數(shù)。32

32、.一棵哈夫曼樹的帶權(quán)路徑長度等于其中所有分支結(jié)點的權(quán)值之和。×33.當(dāng)一棵具有n個葉子結(jié)點的二叉樹的WPL值為最小時，稱其樹為Huffman樹，且其二叉樹的形狀必是唯一的。×四解答應(yīng)用題1. 一棵二叉樹中的結(jié)點的度或為0或為2，則二叉樹的枝數(shù)為2(n0-1)，其中n0是度為0的結(jié)點的個數(shù)。 證明：設(shè)二叉樹度為0和2的結(jié)點數(shù)及總的結(jié)點數(shù)分別為n0，n2 和n，則n=n0+n2 (1)再設(shè)二叉樹的分支數(shù)為B,除根結(jié)點外，每個結(jié)點都有一個分支所指，則 n=B+1 (2)度為零的結(jié)點是葉子，沒有分支，而度為2的結(jié)點有兩個分支，因此（2）式可寫為n=2*n2+1 (3)由（1）、（3）得n2=n0-1,代入（1），并由（1）和（2）得B=2*(n0-1)。 證畢。2任意一個有n個結(jié)點的二叉樹，已知它有m個葉子結(jié)點，試證明非葉子結(jié)點有（m-1）個度為2，其余度為1。證明：設(shè)度為1和2 的結(jié)點數(shù)是n1和n2，則二叉樹結(jié)點數(shù)n為n=m+n1