數(shù)據(jù)結(jié)構(gòu)復習6樹習題課件

第六章樹和二叉樹(選擇題)1．已知一算術(shù)表達式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE2．算術(shù)表達式a+b*（c+d/e）轉(zhuǎn)為后綴表達式后為（）A．a(chǎn)b+cde/*B．a(chǎn)bcde/+*+C．a(chǎn)bcde/*++D．a(chǎn)bcde*/++√√2023/6/613.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1則T中的葉子數(shù)為（）A．5B．6C．7D．84.在下述結(jié)論中，正確的是（）①只有一個結(jié)點的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換;④深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。A．①②③B．②③④C．②④D．①④√因為每個結(jié)點都有一條枝指向它，分支數(shù)為1*4+2*2*3*1+4*1所有結(jié)點數(shù)為分支數(shù)+1，所以1*4+2*2*3*1+4*1=4+2+1+1+xx=8√2023/6/626．若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（）A．9B．11C．15D．不確定7.設(shè)森林F對應的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（）A．m-nB．m-n-1C．n+1D．條件不足，無法確定8．設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（）。A．M1B．M1+M2C．M3D．M2+M3√√森林轉(zhuǎn)換得到的二叉樹中，其左子樹加根為森林的第一棵樹√2023/6/639．一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）A．250B．500C．254D．50110.設(shè)給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點總數(shù)為()A．不確定B．2nC．2n+1D．2n-1完全二叉樹中度為1的結(jié)點最多只有1個，由二叉樹的度和結(jié)點的關(guān)系n=n0+n1+n2n=n1+2n2+1得n=2n0+n1-1√哈夫曼樹中沒有度為1的節(jié)點，葉子節(jié)點個數(shù)為n√2023/6/6411.有關(guān)二叉樹下列說法正確的是（）A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個結(jié)點的度為2D．二叉樹中任何一個結(jié)點的度都為212.一個具有1025個結(jié)點的二叉樹的高h為（）A．11B．10C．11至1025之間D．10至1024之間13．一棵二叉樹高度為h,所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有()結(jié)點A．2hB．2h-1C．2h+1D．h+1√√完全二叉樹和單枝樹之間√2023/6/6514．對于有n個結(jié)點的二叉樹,其高度為（）A．nlog2nB．log2nC．log2n|+1D．不確定15.一棵具有n個結(jié)點的完全二叉樹的樹高度（深度）是（）A．logn+1B．logn+1C．lognD．logn-116．深度為h的滿m叉樹的第k層有（）個結(jié)點。(1=<k=<h)A．mk-1B．mk-1C．mh-1D．mh-1√√完全二叉樹可以確定，一般二叉樹不能確定√2023/6/6617.一棵樹高為K的完全二叉樹至少有（）個結(jié)點A．2k–1B.2k-1–1C.2k-1D.2k18.將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度（）A．4B．5C．6D．719.利用二叉鏈表存儲樹，則根結(jié)點的右指針是（）A．指向最左孩子B．指向最右孩子C．空D．非空2k-1-1+1=2k-1√h=log3n+1√√2023/6/6720．對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用()次序的遍歷實現(xiàn)編號。A．先序B.中序C.后序D.從根開始按層次遍歷21．樹的后根遍歷序列等同于該樹對應的二叉樹的().A.先序序列B.中序序列C.后序序列22．一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（）A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG√√√當該二叉樹所有結(jié)點的左子樹為空時，先序遍歷序列和中序遍歷序列相同。2023/6/6823．已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定24.某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E則前序序列是：A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不對25.上題的二叉樹對應的森林包括多少棵樹（）A．1B．2C．3D．概念上是錯誤的√√√左孩子，右兄弟2023/6/6926．二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是：A、EB、F

C、G

D、H27.某二叉樹T有n個結(jié)點，設(shè)按某種順序?qū)中的每個結(jié)點進行編號，編號為1，2，…，n，且有如下性質(zhì)：T中任一結(jié)點V，其編號等于左子樹上的最小編號減1，而V的右子樹的結(jié)點中，其最小編號等于V左子樹上結(jié)點的最大編號加1。這時是按()編號的。A.中序遍歷序列B.前序遍歷序列C.后序遍歷序列D.層次順序√√2023/6/61028．對于前序遍歷與中序遍歷結(jié)果相同的二叉樹為（1）;對于前序遍歷和后序遍歷結(jié)果相同的二叉樹為（2）。A．一般二叉樹B．只有根結(jié)點的二叉樹C．根結(jié)點無左孩子的二叉樹D．根結(jié)點無右孩子的二叉樹E．所有結(jié)點只有左子數(shù)的二叉樹F．所有結(jié)點只有右子樹的二叉樹29．一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）A．所有的結(jié)點均無左孩子B．所有的結(jié)點均無右孩子C．只有一個葉子結(jié)點D．是任意一棵二叉樹FB√前序序列是“根左右”，后序序列是“左右根”，若要這兩個序列相反，只有單支樹，所以本題的A和B均對，單支樹的特點是只有一個葉子結(jié)點2023/6/61130．在二叉樹結(jié)點的先序序列，中序序列和后序序列中，所有葉子結(jié)點的先后順序（）A．都不相同B．完全相同C．先序和中序相同，而與后序不同D．中序和后序相同，而與先序不同31．某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A．空或只有一個結(jié)點B．任一結(jié)點無左子樹C．高度等于其結(jié)點數(shù)D．任一結(jié)點無右子樹√√2023/6/61232.一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：()A．不確定B.0C.1D.233.一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：()。A.0B.1C.2D.不確定√左子樹為空的二叉樹的根結(jié)點的左線索為空（無前驅(qū)），先序序列的最后結(jié)點的右線索為空（無后繼），共2個空鏈域√只有最后一個葉結(jié)點沒有后繼2023/6/61334.線索二叉樹是一種（）結(jié)構(gòu)。A．邏輯B．邏輯和存儲C．物理D．線性35．n個結(jié)點的線索二叉樹上含有的線索數(shù)為（）A．2nB．n－1C．n＋1D．n36.設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有（）個。A．n-1B．nC．n+1D．n+2√√N個結(jié)點共有2n個指針域，二叉鏈表用了n-1個，剩下n+1個√每一個終端結(jié)點的孩子中都會貢獻出一個空的右指針2023/6/61437．下述編碼中哪一個不是前綴碼（）。A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）38．由3個結(jié)點可以構(gòu)造出多少種不同的二叉樹？（）A．2B．3C．4D．539.引入二叉線索樹的目的是（）A．加快查找結(jié)點的前驅(qū)或后繼的速度B．為了能在二叉樹中方便的進行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結(jié)果唯一√√√2023/6/615第六章樹和二叉樹(判斷題)1.二叉樹的遍歷結(jié)果不是唯一的.2.二叉樹的遍歷只是為了在應用中找到一種線性次序。3．采用二叉鏈表作存儲結(jié)構(gòu)，樹的前序遍歷和其相應的二叉樹的前序遍歷的結(jié)果是一樣的。4．完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是樹葉。√√√√2023/6/6165.給定一棵樹，可以找到唯一的一棵二叉樹與之對應。6．霍夫曼樹的結(jié)點個數(shù)不能是偶數(shù)。7．哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。8.線索二叉樹的優(yōu)點是便于是在中序下查找前驅(qū)結(jié)點和后繼結(jié)點。9．完全二叉樹的存儲結(jié)構(gòu)通常采用順序存儲結(jié)構(gòu)。√√√√√2023/6/617第六章樹和二叉樹(填空題)1．二叉樹由

三個基本單元組成。2．在二叉樹中，指針p所指結(jié)點為葉子結(jié)點的條件是3．已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有______個葉子結(jié)點。根結(jié)點,左子樹,右子樹p->lchild==null&&p->rchlid==null122023/6/6184．在完全二叉樹中，編號為i和j的兩個結(jié)點處于同一層的條件是5．在順序存儲的二叉樹中，編號為i和j的兩個結(jié)點處在同一層的條件是

。6．一棵有n個結(jié)點的滿二叉樹有___個度為1的結(jié)點、有___個分支（非終端）結(jié)點和___個葉子，該滿二叉樹的深度為___。log2i=log2j

log2s=log2t

用順序存儲二叉樹時，要按完全二叉樹的形式存儲，非完全二叉樹存儲時，要加“虛結(jié)點”。設(shè)編號為i和j的結(jié)點在順序存儲中的下標為s和t,則結(jié)點i和j在同一層上的條件是log2s=log2t。0(n-1)/2(n+1)/2log2n+12023/6/6197．設(shè)有N個結(jié)點的完全二叉樹順序存放在向量A[1:N]中，其下標值最大的分支結(jié)點為______。8．高度為K的完全二叉樹至少有___

__個葉子結(jié)點。9．已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少是______。10．一個有2001個結(jié)點的完全二叉樹的高度為____。11．如果結(jié)點A有3個兄弟，而且B是A的雙親，則B的度是______。N/22k-2991142023/6/62012．設(shè)F是由T1,T2,T3三棵樹組成的森林,與F對應的二叉樹為B,已知T1,T2,T3的結(jié)點數(shù)分別為n1,n2和n3則二叉樹B的左子樹中有___個結(jié)點，右子樹中有___個結(jié)點13．對于一個具有n個結(jié)點的二元樹，當它為一棵__二元樹時具有最小高度，當它為一棵__時，具有最大高度。14．含4個度為2的結(jié)點和5個葉子結(jié)點的二叉樹，可有______個度為1的結(jié)點。n1-1n2+n3完全二叉樹單枝樹0至多個任意二叉樹，度為１的結(jié)點個數(shù)沒限制。只有完全二叉樹，度為１的結(jié)點個數(shù)才至多為1。2023/6/62115．利用樹的孩子兄弟表示法存儲，可以將一棵樹轉(zhuǎn)換為______

16．有一份電文中共使用6個字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，試構(gòu)造一棵哈夫曼樹，則其加權(quán)路徑長度WPL為___，字符c的編碼是___。17．將二叉樹bt中每一個結(jié)點的左右子樹互換的C語言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進隊，出隊和判別隊列是否為空的函數(shù)，請?zhí)顚懰惴ㄖ械每瞻滋帲瓿善涔δ堋?0二叉樹0012023/6/622typedefstructnode{intdata;structnode*lchild,*rchild;}btnode;voidEXCHANGE(btnode*bt){btnode*p,*q;if(bt){ADDQ(Q,bt);while(!EMPTY(Q)){p=DELQ(Q);q=___;p->rchild=(2)___

(3)___=q;if(p->lchild)(4)___;if(p->rchild)(5)___;}}}//p->rchildp->lchildp->lchildADDQ(Q,p->lchild)ADDQ(Q,p->rchild)2023/6/62318．設(shè)t是給定的一棵二叉樹，下面的遞歸程序count(t)用于求得:二叉樹t中具有非空的左,右兩個兒子的結(jié)點個數(shù)N2;只有非空左兒子的個數(shù)NL;只有非空右兒子的結(jié)點個數(shù)NR和葉子結(jié)點個數(shù)N0。N2、NL、NR、N0都是全局量，且在調(diào)用count(t)之前都置為0.typedefstructnode{intdata;structnode*lchild,*rchild;}node;intN2,NL,NR,N0;voidcount(node*t){if(t->lchild!=NULL)if(1)___N2++;elseNL++;elseif(2)___NR++;else(3)__;if(t->lchild!=NULL)(4)____;if(t->rchild!=NULL)(5)____;}t->rchild!=nullt->rchild!=nullN0++count(t->lchild)count(t->rchild)2023/6/62419．下面是求二叉樹高度的類C寫的遞歸算法試補充完整

[說明]二叉樹的兩指針域為lchild與rchild,算法中p為二叉樹的根，lh和rh分別為以p為根的二叉樹的左子樹和右子樹的高，hi為以p為根的二叉樹的高，hi最后返回。height(p){if((1)___){if(p->lchild==null)lh=(2)___;elselh=(3)_______;if(p->rchild==null)rh=(4)___;elserh=(5)_______;if(lh>rh)hi=(6)__；elsehi=(7)_______;}elsehi=(8)_______;returnhi;}//p!=null0height(p->lchild)0height(p->rchild)lh+1rh+102023/6/62520．下列是先序遍歷二叉樹的非遞歸子程序，請閱讀子程序填充空格，使其成為完整的算法。voidexample(b)btree*b;{btree*stack[20],*p；

inttop;if(b!=null){top=1;stack[top]=b;while(top>0){p=stack[top];top--;printf(“%d”,p->data);if(p->rchild!=null){(1)__;(2)___;}if(p->lchild!=null){(3)_;(4)__;}}}}top++stack[top]=p->rchildtop++stack[top]=p->lchild2023/6/626第六章樹和二叉樹(應用題)1．按下面要求解下圖中二叉樹的有關(guān)問題：(1)對此二叉樹進行后序后繼線索化；(2)將此二叉樹變換為森林；(3)用后根序遍歷該森林，；寫出遍歷后的結(jié)點序列。LJGIABEFKCDHMONP2023/6/627后續(xù)遍歷二叉樹:DCBIJHGFLPONMKEA2023/6/628M K L N P O I G E F H J C A B D 后續(xù)遍歷森林:BDCAIFJGHELOPMNK2023/6/6292．設(shè)有正文AADBAACACCDACACAAD,字符集為A,B,C,D,設(shè)計一套二進制編碼，使得上