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

習(xí)題五

一、單項(xiàng)選擇題

1.以下說(shuō)法錯(cuò)誤的是（）

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

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

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

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

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

2.下列說(shuō)法中正確的是（）

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

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

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

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

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

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

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

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

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

4.樹(shù)最適合用來(lái)表示（）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為（）。

A.CBEFDAB.FEDCBAC.CBEDFAD.不定

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

（）o

A.acbedB.decabC.deabcD.cedba

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

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

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

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

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.在下列情況中，可稱(chēng)為二叉樹(shù)的是（）

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

B.哈夫曼樹(shù)

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

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

E.以上答案都不對(duì)

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

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

18.引入二叉線(xiàn)索樹(shù)的目的是（）

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

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

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

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

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

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

21.下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（）。

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個(gè)結(jié)點(diǎn)的二叉樹(shù)，按層次從上到下，同一層從左到右順序存儲(chǔ)在一維數(shù)組

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

位置是（）

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

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

23、以下說(shuō)法錯(cuò)誤的是（)

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

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

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

C.已知二叉樹(shù)的前序遍歷和后序遍歷序列并不能惟一地確定這棵樹(shù)，因?yàn)椴恢罉?shù)的

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

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

后。

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

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

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

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

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

歷是一致的。（）

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

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

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

8.二叉樹(shù)只能用二叉鏈表表示。（）

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

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

指針.（）

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

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

13.度為二的樹(shù)就是二叉樹(shù)。（）

14.二叉樹(shù)中序線(xiàn)索化后，不存在空指針域。（）

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

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

三、填空題

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

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

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

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

的左右孩子，其余的_______個(gè)指針域?yàn)镹ULL。

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

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

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

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

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

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

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

為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。

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

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

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

12.以下程序段采用先根遍歷方法求二叉樹(shù)的葉子數(shù)，請(qǐng)?jiān)跈M線(xiàn)處填充適當(dāng)?shù)恼Z(yǔ)句。

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

0*/

{if(t!=NULL)

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

countleaf(t->lchiId,&count);

)

)

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

型的定義如下：

typedefstructnode/*C語(yǔ)言/

{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.二叉樹(shù)存儲(chǔ)結(jié)構(gòu)同上題，以下程序?yàn)榍蠖鏄?shù)深度的遞歸算法，請(qǐng)?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.將二叉樹(shù)bt中每一個(gè)結(jié)點(diǎn)的左右子樹(shù)互換的C語(yǔ)言算法如下，其中

ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進(jìn)隊(duì)，出隊(duì)和判別隊(duì)列是否為空的函數(shù)，請(qǐng)?zhí)顚?xiě)算法

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

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.樹(shù)和二叉樹(shù)之間有什么樣的區(qū)別與聯(lián)系？

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

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

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

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

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

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

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

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

請(qǐng)給出計(jì)算和推導(dǎo)過(guò)程。

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

B)<C

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

12345678910

Lchild00237580101

DataJHFDBACEGI

Rchild0009400000

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

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

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

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

（3）畫(huà)出二叉樹(shù)的后序線(xiàn)索樹(shù).

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

的編碼最短。

第六章樹(shù)和二叉樹(shù)

一、單項(xiàng)選擇題

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

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

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

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

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

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

歷是一致的。X

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

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

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

8.二叉樹(shù)只能用二叉鏈表表示。X

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

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

指針。X

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

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

13.度為二的樹(shù)就是二叉樹(shù)。X

14.二叉樹(shù)中序線(xiàn)索化后，不存在空指針域。X

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

16.哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(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個(gè)結(jié)點(diǎn)，總結(jié)點(diǎn)個(gè)數(shù)是2HT,其雙親是2HT/2=2k-2)(2)Llog2iJ+l

7.4

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

9.二叉排序樹(shù)

10.前序

11.69

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

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

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

15.(1)p->rchild