《算法與數(shù)據(jù)結(jié)構(gòu)》習(xí)題五

習(xí)題五

一、單項選擇題

1.以下說法錯誤的是（）

A.樹形結(jié)構(gòu)的特點(diǎn)是一個結(jié)點(diǎn)可以有多個直接前趨

B.線性結(jié)構(gòu)中的一個結(jié)點(diǎn)至多只有一個直接后繼

C.樹形結(jié)構(gòu)可以表達(dá)（組織）更復(fù)雜的數(shù)據(jù)

D.樹（及一切樹形結(jié)構(gòu)）是一種“分支層次"結(jié)構(gòu)

E.任何只含一個結(jié)點(diǎn)的集合是一棵樹

2.下列說法中正確的是（）

A.任何一棵二叉樹中至少有一個結(jié)點(diǎn)的度為2

B.任何一棵二叉樹中每個結(jié)點(diǎn)的度都為2

C.任何一棵二叉樹中的度肯定等于2

D.任何一棵二叉樹中的度可以小于2

3.討論樹、森林和二叉樹的關(guān)系，目的是為了（）

A.借助二叉樹上的運(yùn)算方法去實現(xiàn)對樹的一些運(yùn)算

B.將樹、森林按二叉樹的存儲方式進(jìn)行存儲

C.將樹、森林轉(zhuǎn)換成二叉樹

D.體現(xiàn)一種技巧，沒有什么實際意義

4.樹最適合用來表示（）

A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素

C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)

5.若一棵二叉樹具有10個度為2的結(jié)點(diǎn)，5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個數(shù)是（）

A.9B.11C.15D.不確定

6.設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個數(shù)分別為Ml,M2和M3。與森林F

對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個數(shù)是（）。

A.MlB.M1+M2C.M3D.M2+M3

7.一棵完全二叉樹上有1001個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是（501）

A.250B.500C.254I）.505E.以上答案都不對

8.設(shè)給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）

A.不確定B.2nC.2n+lD.2n-l

9.二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為（）

A.2'B.2'-1C.2'TD.2'-1

10.一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或為0,或為2,則這棵二叉樹最少有（）結(jié)點(diǎn)

A.2hB.2h-lC.2h+lD.h+1

11.利用三叉鏈表存儲樹，則根結(jié)點(diǎn)的右指針是（）。

A.指向最左孩子B.指向最右孩子C.空D.非空

12.已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果

為（）。

A.CBEFDAB.FEDCBAC.CBEDFAD.不定

13.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷是

（）o

A.acbedB.decabC.deabcD.cedba

14.在二叉樹結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（）

A.都不相同B.完全相同

C.先序和中序相同，而與后序不同D.中序和后序相同，而與先序不同

15.在完全二叉樹中，若一個結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒（）。

A.左子結(jié)點(diǎn)B.右子結(jié)點(diǎn)

C.左子結(jié)點(diǎn)和右子結(jié)點(diǎn)D.左子結(jié)點(diǎn)，右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)

16.在下列情況中，可稱為二叉樹的是（）

A.每個結(jié)點(diǎn)至多有兩棵子樹的樹

B.哈夫曼樹

C.每個結(jié)點(diǎn)至多有兩棵子樹的有序樹

D.每個結(jié)點(diǎn)只有一棵右子樹

E.以上答案都不對

17.一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：（）。

A.0B.1C.2D.不確定

18.引入二叉線索樹的目的是（）

A.加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B.為了能在二叉樹中方便的進(jìn)行插入與刪除

C.為了能方便的找到雙親D.使二叉樹的遍歷結(jié)果唯一

19.n個結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為（）

A.2nB.n—1C.n+1D.n

20.由3個結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（）

A.2B.3C.4D.5

21.下面幾個符號串編碼集合中，不是前綴編碼的是（）。

A.{0,10,110,1111}B.{11,10,001,101,0001}

C.{00,010,0110,1000}D.（b,c,aa,ac,aba,abb,abc}

22.一棵有n個結(jié)點(diǎn)的二叉樹，按層次從上到下，同一層從左到右順序存儲在一維數(shù)組

中，則二叉樹中第i個結(jié)點(diǎn)（i從1開始用上述方法編號）的右孩子在數(shù)組A中的

位置是（）

A.A[2i]（2i<=n）B.A[2i+l]（2i+K=n）

C.A[i-2]D.條件不充分，無法確定

23、以下說法錯誤的是（)

A.哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。

B.若一個二叉樹的樹葉是某子樹的中序遍歷序列中的第一個結(jié)點(diǎn)，則它必是該子樹的

后序遍歷序列中的第一個結(jié)點(diǎn)。

C.已知二叉樹的前序遍歷和后序遍歷序列并不能惟一地確定這棵樹，因為不知道樹的

根結(jié)點(diǎn)是哪一個。

I）.在前序遍歷二叉樹的序列中，任何結(jié)點(diǎn)的子樹的所有結(jié)點(diǎn)都是直接跟在該結(jié)點(diǎn)的之

后。

二、判斷題（在各題后填寫“或“X”）

1.完全二叉樹一定存在度為1的結(jié)點(diǎn).（）

2.對于有N個結(jié)點(diǎn)的二叉樹，其高度為logzn。（）

3.二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序。（）

4.一棵一般樹的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點(diǎn)前序遍歷和后序遍

歷是一致的。（）

5.用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點(diǎn)。（）

6.中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列。（）

7.完全二叉樹中，若一個結(jié)點(diǎn)沒有左孩子，則它必是樹葉。（）

8.二叉樹只能用二叉鏈表表示。（）

9.給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。（）

10.用鏈表（llink-rlink）存儲包含n個結(jié)點(diǎn)的二叉樹,結(jié)點(diǎn)的2n個指針區(qū)域中有n-1個空

指針.（）

11.樹形結(jié)構(gòu)中元素之間存在一個對多個的關(guān)系。（）

12.將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點(diǎn)沒有左子樹。（）

13.度為二的樹就是二叉樹。（）

14.二叉樹中序線索化后，不存在空指針域。（）

15.霍夫曼樹的結(jié)點(diǎn)個數(shù)不能是偶數(shù)。（）

16.哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。（）

三、填空題

1.在二叉樹中，指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是,

2.深度為k的完全二叉樹至少有個結(jié)點(diǎn)，至多有個結(jié)點(diǎn)。

3.高度為8的完全二叉樹至少有個葉子結(jié)點(diǎn)。

4.具有n個結(jié)點(diǎn)的二叉樹中,一共有個指針域，其中只有個用來指向結(jié)點(diǎn)

的左右孩子，其余的_______個指針域為NULL。

5.樹的主要遍歷方法有_—__、_、__等三種。

6.一個深度為k的，具有最少結(jié)點(diǎn)數(shù)的完全二叉樹按層次，（同層次從左到右）用自然數(shù)依

此對結(jié)點(diǎn)編號，則編號最小的葉子的序號是；編號是i的結(jié)點(diǎn)所在的層次號

是（根所在的層次號規(guī)定為1層）。

7.如果結(jié)點(diǎn)A有3個兄弟，而且B是A的雙親，則B的度是o

8.二叉樹的先序序列和中序序列相同的條件是=

9.一個無序序列可以通過構(gòu)造一棵樹而變成一個有序序列，構(gòu)造樹的過程即

為對無序序列進(jìn)行排序的過程。

10.若一個二叉樹的葉子結(jié)點(diǎn)是某子樹的中序遍歷序列中的最后一個結(jié)點(diǎn)，則它必是該子樹

的序列中的最后一個結(jié)點(diǎn)。

11.若以｛4,5,6,7,8｝作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是。

12.以下程序段采用先根遍歷方法求二叉樹的葉子數(shù)，請在橫線處填充適當(dāng)?shù)恼Z句。

Voidcountleaf（bitreptrt,int*count）/*根指針為t,假定葉子數(shù)count的初值為

0*/

{if(t!=NULL)

{if((t->lchild==NULL)&&(t->rchild==NULL))—;

countleaf(t->lchiId,&count);

)

)

13.以下程序是二叉鏈表樹中序遍歷的非遞歸算法，請?zhí)羁帐怪晟?。二叉樹鏈表的結(jié)點(diǎn)類

型的定義如下：

typedefstructnode/*C語言/

{chardata;structnode*lchild,*rchild;}*bitree;

voidvst(bitreebt)/*bt為根結(jié)點(diǎn)的指針*/

{bitreep;p=bt;initstack(s);/*初始化棧s為空棧*/

while(pj!empty(s))/*棧s不為空*/

if(p){push(s,p);⑴；}/*P入棧*/

else{p=pop(s);printf("%c”,p->data);(2);}/*棧頂元素出棧*/

)

14.二叉樹存儲結(jié)構(gòu)同上題，以下程序為求二叉樹深度的遞歸算法，請?zhí)羁胀晟浦?/p>

intdepth(bitreebt)/*bt為根結(jié)點(diǎn)的指針*/

(inthl,hr;

if(bt==NULL)return(GJ);

hl=depth(bt->lchild);hr=depth(bt->rchiId);

if(12))0)；

return(hr+1);

)

15.將二叉樹bt中每一個結(jié)點(diǎn)的左右子樹互換的C語言算法如下，其中

ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進(jìn)隊，出隊和判別隊列是否為空的函數(shù)，請?zhí)顚懰惴?/p>

中得空白處，完成其功能。

typedefstructnode

{intdata;structnode*lchild,*rchild;}btnode;

voidEXCHANGE(btnode*bt)

{btnode*p,*q;

if(bt)(ADDQ(Q,bt);

while(!EMPTY(Q))

{p=DELQ(Q);q=(l):p->rchild=(2):(3)=q：

if(p->lchild)(4);if(p->rchild)(5);

)

)}//

四、應(yīng)用題

1.樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？

分別畫出具有3個結(jié)點(diǎn)的樹和3個結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。

分別給出下圖所示二叉樹的先根、中根和后根序列。

4.一個深度為L的滿K叉樹有以下性質(zhì)：第L層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個

結(jié)點(diǎn)都有K棵非空子樹，如果按層次順序從1開始對全部結(jié)點(diǎn)進(jìn)行編號，求：

1）各層的結(jié)點(diǎn)的數(shù)目是多少？

2）編號為n的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號是多少？

3）編號為n的結(jié)點(diǎn)的第i個孩子結(jié)點(diǎn)（若存在）的編號是多少？

4）編號為n的結(jié)點(diǎn)有右兄弟的條件是什么？如果有，其右兄弟的編號是多少？

請給出計算和推導(dǎo)過程。

5.將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹。（只要求給出轉(zhuǎn)換結(jié)果）

B)<C

6.設(shè)二叉樹BT的存儲結(jié)構(gòu)如下：

12345678910

Lchild00237580101

DataJHFDBACEGI

Rchild0009400000

其中BT為樹根結(jié)點(diǎn)的指針，其值為6,Lchild,Rchild分別為結(jié)點(diǎn)的左、右孩子指針域,data

為結(jié)點(diǎn)的數(shù)據(jù)域。試完成下列各題：

（1）畫出二叉樹BT的邏輯結(jié)構(gòu)；

（2）寫出按前序、中序、后序遍歷該二叉樹所得到的結(jié)點(diǎn)序列；

（3）畫出二叉樹的后序線索樹.

7.設(shè)有正文AADBAACACCDACACAAD,字符集為A,B,C,D,設(shè)計一套二進(jìn)制編碼，使得上述正文

的編碼最短。

第六章樹和二叉樹

一、單項選擇題

1.A

2.D

3.A

4.C

5.B

6.D

7.E

8.D

9.C

10.B

11.C

12.A

13.D

14.B

15.C

16.B

17.B

18.A

19.C

20.D

21.B

22.D

23.C

二、判斷題(在各題后填寫“或“X”)

1.完全二叉樹一定存在度為1的結(jié)點(diǎn)。X

2.對于有N個結(jié)點(diǎn)的二叉樹，其高度為log.m。X

3.二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序。V

4.一棵一般樹的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點(diǎn)前序遍歷和后序遍

歷是一致的。X

5.用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點(diǎn)。X

6.中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列V

7.完全二叉樹中，若一個結(jié)點(diǎn)沒有左孩子，則它必是樹葉。V

8.二叉樹只能用二叉鏈表表示。X

9.給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。V

10.用鏈表(llink-rlink)存儲包含n個結(jié)點(diǎn)的二叉樹,結(jié)點(diǎn)的2n個指針區(qū)域中有nT個空

指針。X

11.樹形結(jié)構(gòu)中元素之間存在一個對多個的關(guān)系。V

12.將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點(diǎn)沒有左子樹。X

13.度為二的樹就是二叉樹。X

14.二叉樹中序線索化后，不存在空指針域。X

15.霍夫曼樹的結(jié)點(diǎn)個數(shù)不能是偶數(shù)。V

16.哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。V

三、填空題

1.p->lchild==null&&p->rchlid==null

2.(l)2k-l(2)2k-l

3.64

4.2nn-ln+1

5.先序遍歷后序遍歷中序遍歷

6..(l)2k-2+l(第k層1個結(jié)點(diǎn)，總結(jié)點(diǎn)個數(shù)是2HT,其雙親是2HT/2=2k-2)(2)Llog2iJ+l

7.4

8.任何結(jié)點(diǎn)至多只有右子女的二叉樹。

9.二叉排序樹

10.前序

11.69

12.*count++,countleaf(l->rchile,count)

13.(1)p=p->lchiId//沿左子樹向下(2)p=p->rchild

14.(1)0(2)hl>hr(3)hr=hl

15.(1)p->rchild