數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)練習(xí)(第5章 二叉樹(shù))

1、數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)練習(xí)（二叉樹(shù)）數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)練習(xí)（二叉樹(shù)）學(xué)號(hào)姓名班級(jí).一、選擇題一、選擇題1按照二叉樹(shù)定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)共有C種形態(tài)。(A)3(B)4(C)5(D)62具有五層結(jié)點(diǎn)的完全二叉樹(shù)至少有D個(gè)結(jié)點(diǎn)。(A)9(B)15(C)31(D)163以下有關(guān)二叉樹(shù)的說(shuō)法正確的是B。(A)二叉樹(shù)的度為2(B)一棵二叉樹(shù)的度可以小于2(C)至少有一個(gè)結(jié)點(diǎn)的度為2(D)任一結(jié)點(diǎn)的度均為24已知二叉樹(shù)的后序遍歷是dabec，中序遍歷是deba

2、c，則其前序遍歷是D。（A）acbed（B）decab(C)deabc(D)cedba5將一棵有1000個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下，從左到右依次進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的右孩子編號(hào)為B。(A)98(B)99(C)50(D)沒(méi)有右孩子6對(duì)具有100個(gè)結(jié)點(diǎn)的二叉樹(shù)，若有二叉鏈表存儲(chǔ)，則其指針域共有D為空。(A)50(B)99(C)100(D)1017設(shè)二叉樹(shù)的深度為h，且只有度為1和0的結(jié)點(diǎn)，則此二叉樹(shù)的結(jié)點(diǎn)總數(shù)為C。

3、(A)2h(B)2h1(C)h(D)h18對(duì)一棵滿二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)結(jié)點(diǎn)，深度為h，則D。(A)n=hm(B)hm=2n(C)m=h1(D)n=2h19某二叉樹(shù)的先序序列和后序序列正好相反，則下列說(shuō)法錯(cuò)誤的是A。(A)二叉樹(shù)不存在(B)若二叉樹(shù)不為空，則二叉樹(shù)的深度等于結(jié)點(diǎn)數(shù)(C)若二叉樹(shù)不為空，則任一結(jié)點(diǎn)不能同時(shí)擁有左孩子和右孩子(D)若二叉樹(shù)不為空，則任一結(jié)點(diǎn)的度均為110對(duì)二叉樹(shù)的結(jié)點(diǎn)從1開(kāi)始進(jìn)行編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其

4、左右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用C遍歷實(shí)現(xiàn)編號(hào)。(A)先序(B)中序(C)后序(D)層序11一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為C。(A)10(B)11(C)11~1025(D)10~102412設(shè)nm為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是C。(A)n在m右方(B)n是m祖先(C)n在m左方(D)n是m子孫二、填空題1對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)它為一棵完全二叉樹(shù)時(shí)具有

5、最小高度；當(dāng)它為單分支二叉樹(shù)時(shí)，具有最大高度。2在二叉樹(shù)的第i（i≥1）層上至多有2i1個(gè)結(jié)點(diǎn)，深度為k（k≥1）的完全二叉樹(shù)至多2k1個(gè)結(jié)點(diǎn)，最少2k1個(gè)結(jié)點(diǎn)；BTreeNodeBTreeSwopX(BTreeNodeBT)if(BT==NULL)returnNULLelseBTreeNodept=newBTreeNodeptdata=BTdataptright=BTreeSwopX(BTleft)ptleft=BTreeSwopX(

6、BTright)returnpt函數(shù)的功能：交換二叉樹(shù)的左右子樹(shù)，生成新的二叉樹(shù)。4.指出下面函數(shù)的功能。voidBTC(BTreeNodeBT)if(BT!=NULL)if(BTleft!=NULLBTleft=BTrightBTright=tBTC(BTleft)BTC(BTright)函數(shù)的功能：調(diào)整二叉樹(shù)，使樹(shù)中左子樹(shù)結(jié)點(diǎn)的值小于等于右子樹(shù)結(jié)點(diǎn)的值。5.設(shè)BT指向一顆二叉樹(shù)，該二叉樹(shù)的廣義表表示為a(b(ad(f))c(e(a(