




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題及參考答案 - 第6章 樹和二叉樹一、 選擇題 1、在二叉樹的第I層(I1)上最多含有結(jié)點(diǎn)數(shù)為( ) A. 2I B. 2I-1-1 C. 2I-1 D. 2I -12、深度為6的二叉樹最多有( )個(gè)結(jié)點(diǎn) A64 B.63 C.32 D.313、一棵樹高為K的完全二叉樹至少有( )個(gè)結(jié)點(diǎn) A.2k 1 B.2k-1 1 C.2k-1 D.2 k 4、有關(guān)二叉樹下列說法正確的是( )A. 二叉樹的度為2 B. 一棵二叉樹的度可以小于2 C. 二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 D. 二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2 5、n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為( )A. 2n B. nl
2、 C. nl D. n 6、線性表和樹的結(jié)構(gòu)區(qū)別在于( )A前驅(qū)數(shù)量不同,后繼數(shù)量相同B前驅(qū)數(shù)量相同,后繼數(shù)量不同C前驅(qū)和后繼的數(shù)量都相同D前驅(qū)和后繼的數(shù)量都不同7、已知一算術(shù)表達(dá)式的中綴形式為 A+B*C-D/E,后綴形式為ABC*+DE/-,則其前綴形式為( )A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE8、設(shè)有一表示算術(shù)表達(dá)式的二叉樹(見下圖),EFDGAB/+*-C*它所表示的算術(shù)表達(dá)式是( )A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+(F-G)) D. A*
3、B+C/D*E+F-G9、一棵具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度(深度)(符號(hào)表示取不大于x的最大整數(shù))是( )A. B. C. D.10、利用二叉鏈表存儲(chǔ)樹,則根結(jié)點(diǎn)的右指針是( )。A指向最左孩子 B指向最右孩子 C空 D非空11、已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為( )。ACBEFDA B FEDCBA C CBEDFA D不定 12、某二叉樹中序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E 則前序序列是:AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不
4、對 13、若前序遍歷二叉樹的結(jié)果為序列A、B、C,則有_棵不同的二叉樹可以得到這一結(jié)果。A. 3 B. 4 C. 5 D. 6 14、已知某二叉樹的后序遍歷序列是dabec, 中序遍歷序列是debac , 則它的前序遍歷是( )。 A. acbed B. decab C. deabc D. cedba 15、線索二叉樹是一種( )結(jié)構(gòu)。A邏輯 B邏輯和存儲(chǔ) C物理 D線性 二、填空題 1、對于任意一棵二叉樹,如果其葉子結(jié)點(diǎn)數(shù)為N0,度為1的結(jié)點(diǎn)數(shù)為N1,度為2的結(jié)點(diǎn)數(shù)為N2,則N0=_ N2 + 1_。2、具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_9_。3、一個(gè)深度為4的二叉樹,其結(jié)點(diǎn)至少有 4
5、個(gè),至多有 15 個(gè):4、深度為H 的完全二叉樹至少有_ 2H-1_個(gè)結(jié)點(diǎn);至多有 2H-1_個(gè)結(jié)點(diǎn);H和結(jié)點(diǎn)總數(shù)N之間的關(guān)系是 H=ëlog2Nû+1。5、若用鏈表存儲(chǔ)一棵二叉樹時(shí),每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外,還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中,N個(gè)結(jié)點(diǎn)的二叉樹共有_2N_個(gè)指針域,其中有_N-1_個(gè)指針域是存放了地址,有_N+1_個(gè)指針是空指針。6、設(shè)一棵赫夫曼樹有6個(gè)葉子結(jié)點(diǎn),權(quán)值分別為3、4、7、14、15、20,則根結(jié)點(diǎn)的權(quán)值是_63_7、已知二叉樹的先序遍歷次序是 abdcef,中序遍歷次序是 bdaecf,則它的后序遍歷次序是: dbefca 。8、對
6、一棵完全二叉樹,設(shè)一個(gè)結(jié)點(diǎn)的編號(hào)為i,若它的左孩子結(jié)點(diǎn)存在,則其編號(hào)為 2i ;若右孩子結(jié)點(diǎn)存在,則其編號(hào)為 2i+1 ;而雙親結(jié)點(diǎn)的編號(hào)為 ë û 。 9、赫夫曼樹是帶權(quán)路徑長度 最小的 二叉樹,又稱最優(yōu)二叉樹,路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。10、下面程序段的功能是建立二叉樹的算法,請?jiān)谙聞澗€處填上正確的內(nèi)容。typedef struct node int data; struct node *lchild;_ struct node *rchild _; BiTNode, *BiTree;void createBitree(BiTree &T) scanf(“%
7、c”, &ch);if(ch='#') T=NULL ;else T=( BiTNode *)malloc(sizeof(BiTNode); T->data=ch; createBitree(T->lchild);_createBitree(T->rchild);11、二叉樹由_根結(jié)點(diǎn)_,_左子樹_,_右子樹_三個(gè)基本單元組成。12、樹的鏈表存儲(chǔ)結(jié)構(gòu)常用的有三種,其中,雙親 表示法以一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn),在每個(gè)結(jié)點(diǎn)中設(shè)一個(gè)指示器指示雙親結(jié)點(diǎn)的位置。孩子 表示法每個(gè)結(jié)點(diǎn)的孩子以單鏈表的形式存儲(chǔ),n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表,n個(gè)頭指針又組成一個(gè)線性表,并以
8、順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。孩子兄弟 表示法以二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu),鏈表中的結(jié)點(diǎn)的兩個(gè)指針分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。/P135-13613、利用樹的孩子兄弟表示法存儲(chǔ),可以將一棵樹轉(zhuǎn)換為_二叉樹_。14、在二叉樹中,指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_ p->lchild=NULL && p->rchlid=NULL _。15、樹的孩子兄弟表示法和二叉樹的二叉鏈表表示法,本質(zhì)是一樣的,只是解釋不同,也就是說樹(樹是森林的特例,即森林中只有一棵樹的特殊情況)可用二叉樹唯一表示,并可使用二叉樹的一些算法去解決樹和森林中的問題。16、樹和二叉樹邏輯上都是樹形
9、結(jié)構(gòu),但是二叉樹不是樹的特例,二叉樹與樹是兩個(gè)不同的概念。二叉樹的度 至多為2,樹無此限制;二叉樹有左右子樹之分,即使在只有一個(gè)分枝的情況下, 也必須指出是 左子樹還是右子樹,樹無此限制。三、簡答題 1、已知一棵二叉樹的前序遍歷的結(jié)果是ABKCDFGHIJ,中序遍歷的結(jié)果是KBCDAFHIGJ, 試畫出這棵二叉樹,并寫出后序遍歷結(jié)果。 答案:當(dāng)前序序列為ABKCDFGHIJ,中序序列為KBCDAFHIGJ時(shí),逐步形成二叉樹的過程如下圖所示:這棵二叉樹的后序遍歷結(jié)果是:K D C B I H J G F A2、某通信電文由A、B、C、D、E、F六個(gè)字符組成,它們在電文中出現(xiàn)的次數(shù)(權(quán)值)分別是1
10、6,5,7,3,8,1。試畫出其哈夫曼樹,確定其對應(yīng)的哈夫曼編碼,并計(jì)算其帶權(quán)路徑長度。為使結(jié)果唯一,請將權(quán)值較小的結(jié)點(diǎn)作為其雙親的左孩子,而將權(quán)值較大的結(jié)點(diǎn)作為其雙親的右孩子。答案:哈夫曼樹如下:對應(yīng)的哈夫曼編碼如下:A: 0B: 101C: 110D: 1001E: 111F: 1000帶權(quán)路徑長度為: WPL=(1+3)*4+(5+7+8)*3+16*1=923、對下圖所示二叉樹分別按前序中序后序遍歷,給出相應(yīng)的結(jié)點(diǎn)序列,同時(shí)給二叉樹加上中序線索。答案:(1)前序序列:ABDEHCFG(2)中序序列:DHEBAFCG(3)后序序列:HEDBFGCA (4)中序線索見圖中虛線箭頭所示。四、
11、算法分析題1、已知二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表,閱讀下面算法,之后,對于如下所示的二叉樹:(1)畫出執(zhí)行下面算法后所建立的結(jié)構(gòu); (2)說明該算法的功能。typedef struct node DateType data; Struct node * next; ListNode; typedef ListNode * LinkList; LinkList Leafhead = NULL; void Inorder ( BinTree T ) LinkList s; If(T) Inorder(T>lchild); If (!T>lchild)&&(!T>rch
12、ild) s=(ListNode*)malloc(sizeof(ListNode); s>data=T>data; s>next=Leafhead; Leafhead=s; Inorder(T>rchild); 答案:2、已知二叉樹中的結(jié)點(diǎn)類型BinTreeNode定義為: struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data為結(jié)點(diǎn)值域,left和right分別為指向左、右孩子
13、結(jié)點(diǎn)的指針域。下面函數(shù)的功能是從二叉樹BT中查找值為x的結(jié)點(diǎn),若查找成功則返回結(jié)點(diǎn)地址,否則返回空。按標(biāo)號(hào)填寫空缺的內(nèi)容,要求統(tǒng)一填寫在算法后面的標(biāo)記處。 BinTreeNode* BTF(BinTreeNode* BT,ElemType x) if(BT=NULL) _ return NULL _; else if
14、(BT->data=x) _ return BT _; else BinTreeNode* t; if(t=BTF(BT->left, x) return t;
15、0; _ if(t=BTF(BT->right, x) return t _; return NULL;
16、; 3、由二叉樹的前序序列和中序序列能否唯一確定一棵二叉樹?由二叉樹的中序序列和后序序列能否唯一確定一棵二叉樹?由二叉樹的前序序列和后序序列能否唯一確定一棵二叉樹?請分別進(jìn)行論述。答案: (1)給定二叉樹結(jié)點(diǎn)的前序序列和中序序列,可以唯一確定該二叉樹。因?yàn)榍靶蛐蛄械牡谝粋€(gè)元素是根結(jié)點(diǎn),該元素將二叉樹中序序列分成兩部分,左邊(設(shè)l個(gè)元素)表示左子樹,若左邊無元素,則說明左子樹為空;右邊(設(shè)r個(gè)元素)是右子樹,若為空,則右子樹為空。根據(jù)前序遍
17、歷中“根左子樹右子樹”的順序,則由從第二元素開始的l個(gè)結(jié)點(diǎn)序列和中序序列根左邊的l個(gè)結(jié)點(diǎn)序列構(gòu)造左子樹,由前序序列最后r個(gè)元素序列與中序序列根右邊的r個(gè)元素序列構(gòu)造右子樹。(2)由二叉樹的中序序列和后序序列,也可以唯一確定一棵二叉樹。證明如下:當(dāng)n=1時(shí),只有一個(gè)根結(jié)點(diǎn),由中序序列和后序序列可以確定這棵二叉樹。設(shè)當(dāng)n=m-1時(shí)結(jié)論成立,現(xiàn)證明當(dāng)n=m時(shí)結(jié)論成立。設(shè)中序序列為S1,S2,Sm,后序序列是P1,P2,,Pm。因后序序列最后一個(gè)元素Pm是根,則在中序序列中可找到與Pm相等的結(jié)點(diǎn)(設(shè)二叉樹中各結(jié)點(diǎn)互不相同)Si(1im),因中序序列是由中序遍歷而得,所以Si是根結(jié)點(diǎn),S1,S2,Si-
18、1是左子樹的中序序列,而Si+1,Si+2,Sm是右子樹的中序序列。若i=1,則S1是根,這時(shí)二叉樹的左子樹為空,右子樹的結(jié)點(diǎn)數(shù)是m-1,則S2,S3,Sm和P1,P2,Pm-1可以唯一確定右子樹,從而也確定了二叉樹。若i=m,則Sm是根,這時(shí)二叉樹的右子樹為空,左子樹的結(jié)點(diǎn)數(shù)是m-1,則S1,S2,Sm-1和P1,P2,Pm-1唯一確定左子樹,從而也確定了二叉樹。最后,當(dāng)1<i<m時(shí),Si把中序序列分成S1,S2,Si-1和Si+1,Si+2,,Sm。由于后序遍歷是“左子樹右子樹根結(jié)點(diǎn)”,所以P1,P2,Pi-1和Pi,Pi+1,Pm-1是二叉樹的左子樹和右子樹的后序遍歷序列。因而由S1,S2,Si-1和P1,P2,Pi-1可唯一確定二叉樹的左子樹,由Si+1,Si+2,,Sm和Pi,Pi+1,,Pm-1可唯一確定二叉樹的右子樹 。(3)由二叉樹的前序序列和后序序列不能唯一確定一棵二叉樹。因?yàn)闊o法確定左右子樹兩部
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 科技浪潮下的職場技能升級(jí)與職業(yè)規(guī)劃
- 2025年桂林信息工程職業(yè)學(xué)院單招職業(yè)適應(yīng)性測試題庫完美版
- 電子化政府服務(wù)平臺(tái)的服務(wù)設(shè)計(jì)與實(shí)踐
- 2025年黑龍江林業(yè)職業(yè)技術(shù)學(xué)院單招職業(yè)傾向性測試題庫附答案
- 2025年貴州城市職業(yè)學(xué)院單招職業(yè)技能測試題庫匯編
- 2025年河北省張家口市單招職業(yè)傾向性測試題庫必考題
- 2025年廣西農(nóng)業(yè)工程職業(yè)技術(shù)學(xué)院單招職業(yè)適應(yīng)性測試題庫及答案一套
- 2025年黑龍江省大慶市單招職業(yè)傾向性測試題庫及答案1套
- 2025年阜新高等??茖W(xué)校單招職業(yè)傾向性測試題庫附答案
- 科技醫(yī)療的投資價(jià)值與發(fā)展趨勢
- 2024未來會(huì)議:AI與協(xié)作前沿趨勢白皮書
- 書畫同源 課件-2023-2024學(xué)年高中美術(shù)人教版(2019)選擇性必修2 中國書畫
- 2024年廣東普通專升本《公共英語》完整版真題
- 全飛秒激光近視手術(shù)
- 單原子催化劑的合成與應(yīng)用
- 電網(wǎng)調(diào)度運(yùn)行人員考試:電網(wǎng)調(diào)度調(diào)控考試試題及答案(最新版)
- 成都市深基坑管理規(guī)定課件
- 建立高效的員工溝通與反饋機(jī)制
- 促進(jìn)學(xué)習(xí)的課堂評(píng)價(jià):做得對
- 《語用學(xué)之指示語》課件
- 《對折剪紙》課件
評(píng)論
0/150
提交評(píng)論