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

.一、單項(xiàng)選擇題A．樹形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前趨B．線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼C．樹形結(jié)構(gòu)可以表達(dá)<組織>更復(fù)雜的數(shù)據(jù)D．樹<與一切樹形結(jié)構(gòu)>是一種"分支層次"結(jié)構(gòu)E．任何只含一個(gè)結(jié)點(diǎn)的集合是一棵樹2．如下說法中正確的答案是<>A．任何一棵二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2B．任何一棵二叉樹中每個(gè)結(jié)點(diǎn)的度都為2C．任何一棵二叉樹中的度肯定等于2D．任何一棵二叉樹中的度可以小于2A．借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對樹的一些運(yùn)算B．將樹、森林按二叉樹的存儲(chǔ)方式進(jìn)展存儲(chǔ)C．將樹、森林轉(zhuǎn)換成二叉樹D．表現(xiàn)一種技巧,沒有什么實(shí)際意義4．樹最適合用來表示<>A．有序數(shù)據(jù)元素B．無序數(shù)據(jù)元素C．元素之間具有分支層次關(guān)系的數(shù)據(jù)D．元素之間無聯(lián)系的數(shù)據(jù)A．9B．11C．15D．不確定A．M1B．M1+M2C．M3D．M2+M3〕ABC．254D．505E．以上答案都不對8.設(shè)給定權(quán)值總數(shù)有n個(gè),其哈夫曼樹的結(jié)點(diǎn)總數(shù)為<>A．不確定B．2nC．2n+1D．2n-1AIBICID．2I-110．一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?,或?yàn)?,如此這棵二叉樹最少有<>結(jié)點(diǎn)A．2hB．2h-1C．2h+1D．h+1A．指向最左孩子B．指向最右孩子C．空D．非空12．一棵二叉樹的前序遍歷結(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)至多有兩棵子樹的樹B.哈夫曼樹C．每個(gè)結(jié)點(diǎn)至多有兩棵子樹的有序樹D.每個(gè)結(jié)點(diǎn)只有一棵右子樹E．以上答案都不對17.一棵左右子樹均不空的二叉樹在先序線索化后,其中空的鏈域的個(gè)數(shù)是：<>.A.0B.1C.2D.不確定18.引入二叉線索樹的目的是〔〕A．加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B．為了能在二叉樹中方便的進(jìn)展插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結(jié)果唯一A．2nB．n－lC．n＋lD．n20．由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？〔〕22.一棵有n個(gè)結(jié)點(diǎn)的二叉樹,按層次從上到下,同一層從左到右順序存儲(chǔ)在一維數(shù)組A．A[2i]<2i<=n>B．A[2i+1]<2i+1<=n>C．A[i-2]D．條件不充分,無法確定23、以下說法錯(cuò)誤的答案是<>A．哈夫曼樹是帶權(quán)路徑長度最短的樹,路徑上權(quán)值較大的結(jié)點(diǎn)離根較近.B．假如一個(gè)二叉樹的樹葉是某子樹的中序遍歷序列中的第一個(gè)結(jié)點(diǎn),如此它必是該子樹的后序遍歷序列中的第一個(gè)結(jié)點(diǎn).C．二叉樹的前序遍歷和后序遍歷序列并不能惟一地確定這棵樹,因?yàn)椴恢罉涞母Y(jié)點(diǎn)是哪一個(gè).D．在前序遍歷二叉樹的序列中,任何結(jié)點(diǎn)的子樹的所有結(jié)點(diǎn)都是直接跟在該結(jié)點(diǎn)的之后.二、判斷題〔在各題后填寫"√〞或"×〞〕3.二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序.<>4.一棵一般樹的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點(diǎn)前序遍歷和后序遍歷是一致的.<>5.用一維數(shù)組存儲(chǔ)二叉樹時(shí),總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn).<>6．中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列.<>7．完全二叉樹中,假如一個(gè)結(jié)點(diǎn)沒有左孩子,如此它必是樹葉.<>.8.二叉樹只能用二叉鏈表表示.<>9.給定一棵樹,可以找到唯一的一棵二叉樹與之對應(yīng).<>指針.<>11．樹形結(jié)構(gòu)中元素之間存在一個(gè)對多個(gè)的關(guān)系.<>12．將一棵樹轉(zhuǎn)成二叉樹,根結(jié)點(diǎn)沒有左子樹.<>13．度為二的樹就是二叉樹.<>14.二叉樹中序線索化后,不存在空指針域.<>15．霍夫曼樹的結(jié)點(diǎn)個(gè)數(shù)不能是偶數(shù).<>16．哈夫曼樹是帶權(quán)路徑長度最短的樹,路徑上權(quán)值較大的結(jié)點(diǎn)離根較近.<>三、填空題2．深度為k的完全二叉樹至少有_______個(gè)結(jié)點(diǎn),至多有_______個(gè)結(jié)點(diǎn).n個(gè)結(jié)點(diǎn)的二叉樹中,一共有________個(gè)指針域,其中只有________個(gè)用來指向結(jié)點(diǎn)的左右孩子,其余的________個(gè)指針域?yàn)镹ULL.5．樹的主要遍歷方法有________、________、________等三種.i8．二叉樹的先序序列和中序序列一樣的條件是______.9．一個(gè)無序序列可以通過構(gòu)造一棵______樹而變成一個(gè)有序序列,構(gòu)造樹的過程即為對無序序列進(jìn)展排序的過程.10．假如一個(gè)二叉樹的葉子結(jié)點(diǎn)是某子樹的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn),如此它必是該子樹的______序列中的最后一個(gè)結(jié)點(diǎn).11．假如以{4,5,6,7,8}作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹,如此其帶權(quán)路徑長度是______.12．以下程序段采用先根遍歷方法求二叉樹的葉子數(shù),請?jiān)跈M線處填充適當(dāng)?shù)恼Z句.{if<<t->lchild==NULL>&&<t->rchild==NULL>>________;countleaf<t->lchild,&count>;________}}13．以下程序是二叉鏈表樹中序遍歷的非遞歸算法,請?zhí)羁帐怪晟?二叉樹鏈表的結(jié)點(diǎn)類型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．二叉樹存儲(chǔ)結(jié)構(gòu)同上題,以下程序?yàn)榍蠖鏄渖疃鹊倪f歸算法,請?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ù),請?zhí)顚懰惴ㄖ械每瞻滋?完成其功能.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二、判斷題〔在各題后填寫"√〞或"×〞〕3.二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序.√4.一棵一般樹的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點(diǎn)前序遍歷和后序遍5.用一維數(shù)組存儲(chǔ)二叉樹時(shí),總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn).×6．中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列√9.給定一棵樹,可以找到唯一的一棵二叉樹與之對應(yīng).√10.用鏈表<llink-rlink>存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹,結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n-1個(gè)空11．樹形結(jié)構(gòu)中元素之間存在一個(gè)對多個(gè)的關(guān)系.√.數(shù).√16．哈夫曼樹是帶權(quán)路徑長度最短的樹,路徑上權(quán)值較大的結(jié)點(diǎn)離根較近.√三、填空題1．p->lchild==null&&p->rchlid==null2.<1>2k-