數(shù)據(jù)結(jié)構(gòu)第六章樹(shù)和二叉樹(shù)習(xí)題與答案

.一、單項(xiàng)選擇題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)的度為2B．任何一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度都為2C．任何一棵二叉樹(shù)中的度肯定等于2D．任何一棵二叉樹(shù)中的度可以小于2A．借助二叉樹(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ù)A．9B．11C．15D．不確定A．M1B．M1+M2C．M3D．M2+M3〕ABC．254D．505E．以上答案都不對(duì)8.設(shè)給定權(quán)值總數(shù)有n個(gè),其哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為<>A．不確定B．2nC．2n+1D．2n-1AIBICID．2I-110．一棵二叉樹(shù)高度為h,所有結(jié)點(diǎn)的度或?yàn)?,或?yàn)?,如此這棵二叉樹(shù)最少有<>結(jié)點(diǎn)A．2hB．2h-1C．2h+1D．h+1A．指向最左孩子B．指向最右孩子C．空D．非空12．一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,如此后序遍歷的結(jié)果為A．a(chǎn)cbedB．decabC．deabcD．cedba點(diǎn)的先后順序〔〕A．都不一樣B．完全一樣.C．先序和中序一樣,而與后序不同D．中序和后序一樣,而與先序不同A．左子結(jié)點(diǎn)B．右子結(jié)點(diǎn)CD點(diǎn),右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)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é)果唯一A．2nB．n－lC．n＋lD．n20．由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù)？〔〕22.一棵有n個(gè)結(jié)點(diǎn)的二叉樹(shù),按層次從上到下,同一層從左到右順序存儲(chǔ)在一維數(shù)組A．A[2i]<2i<=n>B．A[2i+1]<2i+1<=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è).D．在前序遍歷二叉樹(shù)的序列中,任何結(jié)點(diǎn)的子樹(shù)的所有結(jié)點(diǎn)都是直接跟在該結(jié)點(diǎn)的之后.二、判斷題〔在各題后填寫(xiě)"√〞或"×〞〕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).<>指針.<>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)離根較近.<>三、填空題2．深度為k的完全二叉樹(shù)至少有_______個(gè)結(jié)點(diǎn),至多有_______個(gè)結(jié)點(diǎn).n個(gè)結(jié)點(diǎn)的二叉樹(shù)中,一共有________個(gè)指針域,其中只有________個(gè)用來(lái)指向結(jié)點(diǎn)的左右孩子,其余的________個(gè)指針域?yàn)镹ULL.5．樹(shù)的主要遍歷方法有________、________、________等三種.i8．二叉樹(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ǔ)句.{if<<t->lchild==NULL>&&<t->rchild==NULL>>________;countleaf<t->lchild,&count>;________}}13．以下程序是二叉鏈表樹(shù)中序遍歷的非遞歸算法,請(qǐng)?zhí)羁帐怪晟?二叉樹(shù)鏈表的結(jié)點(diǎn)類(lèi)型fstructnodeC{chardata;structnode*lchild,*rchild;}*bitree;voidvst<bitreebt>/*bt為根結(jié)點(diǎn)的指針*/whilepemptyss不為空*/if<p>{push<s,p>;<1>___;}/*P入棧*/else{p=pop<s>;printf<"%c〞,p->data>;<2>____;}/*棧頂元素出棧*/.}14．二叉樹(shù)存儲(chǔ)結(jié)構(gòu)同上題,以下程序?yàn)榍蠖鏄?shù)深度的遞歸算法,請(qǐng)?zhí)羁胀晟浦?intdepth<bitreebt>/*bt為根結(jié)點(diǎn)的指針*/if<bt==NULL>return<<1>___>;hl=depth<bt->lchild>;hr=depth<bt->rchild>;>；return<hr+1>;}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>if<bt>{ADDQ<Q,bt>;while<!EMPTY<Q>>if<p->lchild><4>___;if<p->rchild><5>___;}}}//一、單項(xiàng)選擇題1.A2.D3．A4．C5．B6．D7．E8.D9．C10．B11.C12．A13．D14．B15．C16．B17.B18.A19．C20．D21．B22.D23．C二、判斷題〔在各題后填寫(xiě)"√〞或"×〞〕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)序列√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)系.√.數(shù).√16．哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù),路徑上權(quán)值較大的結(jié)點(diǎn)離根較近.√三、填空題1．p->lchild==null&&p->rchlid==null2.<1>2k-