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

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

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

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

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

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

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