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

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

C、G

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

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

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

log2s=log2t

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

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

16．有一份電文中共使用6個(gè)字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，試構(gòu)造一棵哈夫曼樹，則其加權(quán)路徑長(zhǎng)度WPL為___，字符c的編碼是___。17．將二叉樹bt中每一個(gè)結(jié)點(diǎn)的左右子樹互換的C語(yǔ)言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進(jìn)隊(duì)，出隊(duì)和判別隊(duì)列是否為空的函數(shù)，請(qǐng)?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中具有非空的左,右兩個(gè)兒子的結(jié)點(diǎn)個(gè)數(shù)N2;只有非空左兒子的個(gè)數(shù)NL;只有非空右兒子的結(jié)點(diǎn)個(gè)數(shù)NR和葉子結(jié)點(diǎn)個(gè)數(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寫的遞歸算法試補(bǔ)充完整

[說(shuō)明]二叉樹的兩指針域?yàn)閘child與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．下列是先序遍歷二叉樹的非遞歸子程序，請(qǐng)閱讀子程序填充空格，使其成為完整的算法。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第六章樹和二叉樹(應(yīng)用題)1．按下面要求解下圖中二叉樹的有關(guān)問(wèn)題：(1)對(duì)此二叉樹進(jìn)行后序后繼線索化；(2)將此二叉樹變換為森林；(3)用后根序遍歷該森林，；寫出遍歷后的結(jié)點(diǎn)序列。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è)計(jì)一套二進(jìn)制編碼，使得上