數(shù)據(jù)結(jié)構(gòu)題目

1、02一 選擇題：1、以下說法錯(cuò)誤的是 樹形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前趨線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼樹形結(jié)構(gòu)可以表達(dá)(組織)更復(fù)雜的數(shù)據(jù)樹(及一切樹形結(jié)構(gòu))是一種"分支層次"結(jié)構(gòu)任何只含一個(gè)結(jié)點(diǎn)的集合是一棵樹2深度為6的二叉樹最多有( )個(gè)結(jié)點(diǎn) 64 63 32 313 下列說法中正確的是 任何一棵二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2任何一棵二叉樹中每個(gè)結(jié)點(diǎn)的度都為2 二叉樹可空任何一棵二叉樹中的度肯定等于2 任何一棵二叉樹中的度可以小于24 設(shè)森林T中有4棵樹，第一、二、三、四棵樹的結(jié)點(diǎn)個(gè)數(shù)分別是n1,n2,n3,n4,那么當(dāng)把森林T轉(zhuǎn)換成一棵二叉樹后，且根

2、結(jié)點(diǎn)的右子樹上有（ ）個(gè)結(jié)點(diǎn)。n1-1 n1 n1+n2+n3 n2+n3+n4 二名詞解釋：1 結(jié)點(diǎn)的度 3。葉子 4。分支點(diǎn) 5。樹的度三 填空題 二叉樹第i(i>=1)層上至多有_個(gè)結(jié)點(diǎn)。1、 深度為k(k>=1)的二叉樹至多有_個(gè)結(jié)點(diǎn)。2、 如果將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，則對(duì)任一編號(hào)為i(1<=i<=n)的結(jié)點(diǎn)X有：若i=1,則結(jié)點(diǎn)X是_ _；若i1,則X的雙親PARENT(X)的編號(hào)為_ _。若2i>n，則結(jié)點(diǎn)X無_ _且無_ _；否則，X的左孩子LCHILD(X)的編號(hào)為_。若2i+1>n，則結(jié)點(diǎn)X無_ _；否則，X的右孩子RCHIL

3、D(X)的編號(hào)為_。4以下程序段采用先根遍歷方法求二叉樹的葉子數(shù)，請(qǐng)?jiān)跈M線處填充適當(dāng)?shù)恼Z句。Void countleaf(bitreptr t,int *count)/*根指針為t，假定葉子數(shù)count的初值為0*/ if(t!=NULL) if(t->lchild=NULL)&&(t->rchild=NULL)_ _; countleaf(t->lchild,&count); countleaf(t->rchild,&count); 5 先根遍歷樹和先根遍歷與該樹對(duì)應(yīng)的二叉樹，其結(jié)果_。6 由 _轉(zhuǎn)換成二叉樹時(shí)，其根結(jié)點(diǎn)的右子樹總是空的

4、。7 哈夫曼樹是帶權(quán)路徑度_ _的樹，通常權(quán)值較大的結(jié)點(diǎn)離根_ _。8 一棵樹的形狀如圖填空題33所示，它的根結(jié)點(diǎn)是_，葉子結(jié)點(diǎn)是_，結(jié)點(diǎn)H的度是_，這棵樹的度是_，這棵樹的深度是_，結(jié)點(diǎn)F的兒子結(jié)點(diǎn)是_，結(jié)點(diǎn)G的父結(jié)點(diǎn)是_。9任意一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，若它有m個(gè)葉子，則該二叉樹上度數(shù)為1的結(jié)點(diǎn)為_ _個(gè)。03一、填空1 由個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有 種形態(tài)。 2. 一棵深度為6的滿二叉樹有 個(gè)分支結(jié)點(diǎn)和 個(gè)葉子。3 一棵具有個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為 。4. 設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有(100-511)= 個(gè)葉子結(jié)點(diǎn)，有 個(gè)度為2的結(jié)點(diǎn)，有 個(gè)結(jié)點(diǎn)只有非空左子樹

5、，有 個(gè)結(jié)點(diǎn)只有非空右子樹。5. 二叉樹的基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按N L R次序），后序法（即按 次序）和中序法（也稱對(duì)稱序法，即按L N R次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是 。 6. 用5個(gè)權(quán)值3, 2, 4, 5, 1構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長(zhǎng)度是 。7.一個(gè)深度為h的二叉樹最多有 結(jié)點(diǎn)，最少有 結(jié)點(diǎn)。二、選擇題1二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以 。（）它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ); （）它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)

6、構(gòu)存儲(chǔ); （）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ); （）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用 2. 具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 。() élog2(n)ù () ë log2(n)û () ë log2(n) û+1 () élog2(n)+1ù3把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是 。（）唯一的 （）有2種（）有多種，但根結(jié)點(diǎn)都沒有左孩子 （）有多種，但根結(jié)點(diǎn)都沒有右孩子4. 樹是結(jié)點(diǎn)的有限集合，它 根結(jié)點(diǎn)，記為T。其余的結(jié)點(diǎn)分成為m（m0）個(gè) 的集合T1，T2，Tm，每個(gè)集合又都是樹

7、，此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)（1im）。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的 。供選擇的答案A： 有0個(gè)或1個(gè) 有0個(gè)或多個(gè) 有且只有1個(gè) 有1個(gè)或1個(gè)以上 B: 互不相交 允許相交 允許葉結(jié)點(diǎn)相交 允許樹枝結(jié)點(diǎn)相交C： 權(quán) 度 次數(shù) 序答案：A= B= C= 三、簡(jiǎn)答題1. 給定如圖所示二叉樹T，請(qǐng)畫出與其對(duì)應(yīng)的中序線索二叉樹。2825 3340 60 08 54 5504一、選擇題1、如圖所示的4棵二叉樹中，（ ）不是完全二叉樹。A、 B、 C、 D、 2、在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是（ ）。 A、t->left=NULL B、t->ltag

8、=1 C、t->ltag=1且t->left=NULL D、以上都不對(duì)3、已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（ ）A、acbed B、decab C、deabc D、cedba 4、如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的后序就是T2中結(jié)點(diǎn)的（ ）A、前序 B、中序 C、后序 D、層次序5、對(duì)一個(gè)滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h，則（ ）A、n=h+m B、h+m=2n C、m=h-1 D、n=2（h次方）-16、具有5層結(jié)點(diǎn)的二叉平衡樹至少有（ ）個(gè)結(jié)點(diǎn)。A、10 B、12 C、15 D、17 二、填空題1、結(jié)點(diǎn)

9、最少的樹為_，結(jié)點(diǎn)最少的二叉樹為_。2、從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是_。三、問答題1、假設(shè)二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，如圖（1）所示1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20eafdgcjhib (1)（1）畫出二叉樹表示； （2）寫出先序遍歷，中序遍歷和后序遍歷的結(jié)果；（3）寫出結(jié)點(diǎn)值c得雙親結(jié)點(diǎn)，其左、右孩子；（4）畫出把此二叉樹還原成森林的圖。05選擇題 在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是_。 A、t->left=NULL B、t->ltag=1 C、t->

10、ltag=1且t->left=NULL D、以上都不對(duì)1、 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為_。 A.2h B.2h-1 C.2h+1 D.h+12、 如圖所示的4棵二叉樹，_不是完全二叉樹。 3、 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這個(gè)數(shù)對(duì)應(yīng)的二叉樹。結(jié)論正確的是_。A、 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同B、 樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同C、 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同D、 以

11、上都不對(duì)5、 線索二叉樹是一種_結(jié)構(gòu) A、邏輯 B、邏輯與存儲(chǔ) C、物理 D、線性2、 簡(jiǎn)答題1、 指出樹和二叉樹的三個(gè)主要差別。2、假設(shè)二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，如圖所示。 （1） 畫出二叉樹表示（2） 寫出先序遍歷，中序遍歷，后序遍歷的結(jié)果（3） 寫出結(jié)點(diǎn)值c的雙親結(jié)點(diǎn)，其左、右孩子（4） 畫出把此二叉樹還原成森林的圖 06選擇題 1.討論樹、森林和二叉樹的關(guān)系，目的是為了（ ）A借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對(duì)樹的一些運(yùn)算B將樹、森林按二叉樹的存儲(chǔ)方式進(jìn)行存儲(chǔ)C將樹、森林轉(zhuǎn)換成二叉樹D體現(xiàn)一種技巧，沒有什么實(shí)際意義2樹最適合用來表示 ( )A有序數(shù)據(jù)元素 B無序數(shù)據(jù)元素C元素之間具有分支層次

12、關(guān)系的數(shù)據(jù) D元素之間無聯(lián)系的數(shù)據(jù)3若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（ ）A9 B11 C15 D不確定 4設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（ ）。AM1 BM1+M2 CM3 DM2+M35.利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空二填空題1.深度為k的完全二叉樹至少有_ _個(gè)結(jié)點(diǎn)，至多有_ _個(gè)結(jié)點(diǎn)2.具有n個(gè)結(jié)點(diǎn)的二叉樹中,一共有_個(gè)指針域,其中只有_個(gè)用來指向結(jié)點(diǎn)的左右孩子，其余的_個(gè)指針域?yàn)镹ULL。3.

13、樹的主要遍歷方法有_、_、_等三種。4二叉樹的先序序列和中序序列相同的條件是_ _。5一個(gè)無序序列可以通過構(gòu)造一棵_ _樹而變成一個(gè)有序序列，構(gòu)造樹的過程即為對(duì)無序序列進(jìn)行排序的過程。判斷題1. 一棵一般樹的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點(diǎn)前序遍歷和后序遍歷是一致的。( ) 2.二叉樹只能用二叉鏈表表示。（ ）3.用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。（ ）程序填空1.以下程序是二叉鏈表樹中序遍歷的非遞歸算法，請(qǐng)?zhí)羁帐怪晟?。二叉樹鏈表的結(jié)點(diǎn)類型的定義如下： typedef struct node /*C語言/ char data; struct node *lc

14、hild,*rchild;*bitree;void vst(bitree bt) /*bt為根結(jié)點(diǎn)的指針*/ bitree p; p=bt; initstack(s); /*初始化棧s為空棧*/while(p | !empty(s) /*棧s不為空*/ if(p) push (s,p); (1)_ ; /*P入棧*/else p=pop(s); printf(“%c”,p->data);(2)_ _; /*棧頂元素出棧*/2.二叉樹存儲(chǔ)結(jié)構(gòu)同上題，以下程序?yàn)榍蠖鏄渖疃鹊倪f歸算法，請(qǐng)?zhí)羁胀晟浦?int depth(bitree bt) /*bt為根結(jié)點(diǎn)的指針*/int hl,hr; i

15、f (bt=NULL) return(1)_ _); hl=depth(bt->lchild); hr=depth(bt->rchild); if(2)_ _) (3)_ _； return(hr+1); 07一、選擇題1 某二叉樹的先序和后序遍歷序列正好相反，則該二叉樹一定是（）。A ）空或只有一個(gè)結(jié)點(diǎn)B ）完全二叉樹 C ）二叉排序樹D ）2 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹，其中結(jié)論（）是正確的。 A ）樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同 B

16、 ）樹的后根遍歷序列與其對(duì)應(yīng)的二義樹的后序遍歷序列相同 c ）樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同 D ）以上都不對(duì) 3 按照二叉樹的定義，具有3 個(gè)結(jié)點(diǎn)的二叉樹有（）種。 A ) 3B ) 4C ) SD ) 6 4 深度為5 的二叉樹至多有（）個(gè)結(jié)點(diǎn)。 A ) 16B ) 32C ) 3lD ) 10 5. 二叉樹前序遍歷和中序遍歷序列如下： 前序遍歷序列：EFHIJK 中序遍歷序列：HFIEJK 則該二叉樹根結(jié)點(diǎn)的右子樹的根為：( ）。 A ) E B ) F C ) D ) H 6 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后

17、序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹，其中結(jié)論（）是正確的。 A ）樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同 B ）樹的后根遍歷序列與其對(duì)應(yīng)的二義樹的后序遍歷序列相同 c ）樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同 D ）以上都不對(duì)二、填空題1、由10000個(gè)結(jié)點(diǎn)構(gòu)成的二叉排序樹在等概率查找的假設(shè)下查找成功時(shí)的平均查找長(zhǎng)度的最大值可能達(dá)到_。2、深度為k的完全二叉樹至少有_個(gè)結(jié)點(diǎn)至多有_個(gè)結(jié)點(diǎn)若按自上而下從左到右次序給結(jié)點(diǎn)編號(hào)(從1開始)三、算法設(shè)計(jì)題（1） 假設(shè)二叉樹T采用如下定義的存儲(chǔ)結(jié)構(gòu) typedef struct node DataTyp

18、e data; struct node *lchild,*rchild,*parent; PBinTree;其中結(jié)點(diǎn)的lchild域和rchild域已分別填有指向其左右孩子的指針而parent域中的值為空指針擬作為指向雙親結(jié)點(diǎn)的指針域。請(qǐng)編寫一個(gè)遞歸算法將該存儲(chǔ)結(jié)構(gòu)中各結(jié)點(diǎn)的parent域的值修改成指向其雙親結(jié)點(diǎn)的指針081已知一算術(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/DE2. 在下述結(jié)論中，正確的是（ ）只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0; 二叉樹的度為2；

19、 二叉樹的左右子樹可任意交換;深度為K 的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。A B C D6. 設(shè)森林F 對(duì)應(yīng)的二叉樹為B，它有m 個(gè)結(jié)點(diǎn)，B 的根為p,p 的右子樹結(jié)點(diǎn)個(gè)數(shù)為n,森林F 中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（ ）Am-n Bm-n-1 Cn+1 D條件不足，無法確定3二叉樹的第I 層上最多含有結(jié)點(diǎn)數(shù)為（ ）A2I B 2I-1-1 C 2I-1 D2I -14一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（ ）ACABDEFG BABCDEFG CDACEFBG DADCFEG5下面的說法中正確的是（ ）.（1）任何一棵二叉樹的葉子結(jié)點(diǎn)在三種遍歷中的相對(duì)次

20、序不變；（2）按二叉樹定義，具有三個(gè)結(jié)點(diǎn)的二叉樹共有6 種。A(1)(2) B(1) C(2) D(1)、(2)都錯(cuò)6.由3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的有向樹？（ ）A2 B3 C4 D57從下列有關(guān)樹的敘述中,選出5 條正確的敘述 （ ）A二叉樹中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn),而樹無此限制,因此二叉樹是樹的特殊情況。B當(dāng)K1 時(shí)高度為K 的二叉樹至多有2k-1 個(gè)結(jié)點(diǎn)。C用樹的前序周游和中序周游可以導(dǎo)出樹的后序周游。D線索二叉樹的優(yōu)點(diǎn)是便于在中序下查找前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。E將一棵樹轉(zhuǎn)換成二叉樹后,根結(jié)點(diǎn)沒有左子樹。F一棵含有N 個(gè)結(jié)點(diǎn)的完全二叉樹,它的高度是LOG2N+1。G在二叉樹中插入結(jié)點(diǎn),該

21、二叉樹便不再是二叉樹。H采用二叉樹鏈表作樹的存儲(chǔ)結(jié)構(gòu),樹的前序周游和其相應(yīng)的二叉樹的前序周游的結(jié)果是一樣的。I哈夫曼樹是帶權(quán)路徑最短的樹,路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。J用一維數(shù)組存儲(chǔ)二叉樹時(shí),總是以前序周游存儲(chǔ)結(jié)點(diǎn)2.判斷題1任何二叉樹的后序線索樹進(jìn)行后序遍歷時(shí)都必須用棧。2由一棵二叉樹的前序序列和后序序列可以唯一確定它。3完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉。4. 二叉樹只能用二叉鏈表表示.5. 一棵有n 個(gè)結(jié)點(diǎn)的二叉樹，從上到下，從左到右用自然數(shù)依次給予編號(hào)，則編號(hào)為i 的結(jié)點(diǎn)的左兒子的編號(hào)為2i(2i< n)，右兒子是2i+1（2i+1<n）三、填空題1二叉樹由

22、_(1)_，_(2)_，_(3)_三個(gè)基本單元組成。2樹在計(jì)算機(jī)內(nèi)的表示方式有_(1)_，_(2)_，_(3)_。3在二叉樹中，指針p 所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_。4中綴式a+b*3+4*（c-d）對(duì)應(yīng)的前綴式為_(1)_，若a=1，b=2，c=3，d=4，則后綴式db/cc*a-b*+的運(yùn)算結(jié)果為_(2)_。5二叉樹中某一結(jié)點(diǎn)左子樹的深度減去右子樹的深度稱為該結(jié)點(diǎn)的_.6具有256 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_。7已知一棵度為3 的樹有2 個(gè)度為1 的結(jié)點(diǎn)，3 個(gè)度為2 的結(jié)點(diǎn)，4 個(gè)度為3 的結(jié)點(diǎn)，則該樹有_個(gè)葉子結(jié)點(diǎn)。8深度為k 的完全二叉樹至少有_(1)_個(gè)結(jié)點(diǎn)，至多有_(2)_個(gè)結(jié)

23、點(diǎn)9下面的類PASCAL 語言遞歸算法的功能是判斷一棵二叉樹（采用二叉鏈表存貯結(jié)構(gòu)）是否為完全二叉樹。請(qǐng)把空缺的兩部分補(bǔ)寫完整。（提示：利用完全二叉樹結(jié)點(diǎn)序號(hào)性質(zhì)）TYPE link=node;node=RECORD key:keytype; l,r:link; END;VAR all:boolean; n:integer; root:link;FUNC num(t:link):integer;BEGIN (1)_END;PROC chk(t:link;mt 所指結(jié)點(diǎn)應(yīng)有序號(hào):integer)BEGIN (2)_END;BEGIN 建二叉樹，其根由root 指出 n:=num(root);求結(jié)

24、點(diǎn)數(shù) all:=true; chk(root,1);IF all THEN writeln（該樹為完全二叉樹?。〦LSE writeln （該樹非完全二叉樹！）END； 10將二叉樹bt 中每一個(gè)結(jié)點(diǎn)的左右子樹互換的C 語言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進(jìn)隊(duì)，出隊(duì)和判別隊(duì)列是否為空的函數(shù)，請(qǐng)?zhí)顚懰惴ㄖ械每瞻滋?，完成其功能。typedef struct nodeint data ; struct node *lchild, *rchild; btnode;void EXCHANGE(btnode *bt)btnode *p, *q;if (bt)ADD

25、Q(Q,bt);while(!EMPTY(Q)p=DELQ(Q); q=(1)_; p->rchild=(2)_; (3)_=q;if(p->lchild) (4)_; if(p->rchild) (5)_;11下面使用類pascal 語言寫的對(duì)二叉樹進(jìn)行操作的算法，請(qǐng)仔細(xì)閱讀TYPE pointer=tnodetp;tnodetp=RECORD data: char; llink,rlink: pointer；END;linkstack=linknodet;linknodet=RECORD data:pointer； next;linkstack；END;PROC unkn

26、own (VAR t:pointer);VAR p,temp：pointer;BEGIN p:=t;IF p<> NIL THENtemp:=p.llink ；p.llink:=p.rlink;；p.rlink:=temp;unknown(p.llink); unknown(p.rlink); END; 指出該算法完成了什么功能 用棧將以上算法改為非遞歸算法unknown1,其中有若干語句或條件空缺請(qǐng)?jiān)诳杖碧幪顚懮线m當(dāng)?shù)恼Z句或條件PROC inistack(VAR s:linkstack);(1)_; s.next:=NIL;ENDP;FUNC empty (s:linkstack

27、):boolean;IF (2)_THEN empty:=true ELSE empty:=false;ENDF;FUNC gettop(s:linkstack):pointer;gettop:= (3)_;ENDF;FUNC pop(VAR s:linkstack)：pointer;VAR p:linkstack;pop:=s.next.data; p:=s.next; (4)_；(5)_;ENDF;PROC push (VAR s:linkstack;x:pointer);VAR p:linkstack;new(p); p.data:=x; (6)_; s.next:=p;ENDP;PRO

28、C unknown1(VAR t:pointer);VAR p,temp: pointer; finish: boolean;BEGINinistack(s); finish:=false; p:=t;REPEATWHILE p<> NIL DOtemp:=p.llink; p.llink:=p.rlink; p.rlink:=temp;(7)_; p:=p.llink; ;IF (8)_THEN p:=gettop(s);temp;=pop(s); ELSE (9)_UNTIL (10)_ENDP;091.若二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則前序序列遍

29、歷為（）。 A、acbed B、decab C、deabc D、cedba2. 具有35個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（） A、5 B、6 C、7 D、83. 在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充足條件是（）A、t-lchild=NULL B、t->ltag=1 C、t->ltag=1&&t->lchild=NULL D、以上都不對(duì)4. 設(shè)n,m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是（） A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孫5. 線索二叉樹是一種（）結(jié)構(gòu) A、邏輯 B、邏輯和存儲(chǔ) C、物理 D、線性 1、由一棵二叉

30、樹后序序列和（）可唯一確定這棵二叉樹。 2、含有n個(gè)結(jié)點(diǎn)的二叉樹用二叉鏈表表示時(shí)，有（）個(gè)空鏈域。 3、有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹有（）個(gè)結(jié)點(diǎn)。 4、前序?yàn)閍,b,c且后序c,b,a的二叉樹共有（）棵。 5、已知完全二叉樹的第4層有6個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是（）。一棵完全二叉樹有500個(gè)結(jié)點(diǎn)，請(qǐng)問該完全二叉樹有多少個(gè)葉子結(jié)點(diǎn)？有多少個(gè)度為1的結(jié)點(diǎn)？有多少個(gè)度為2的結(jié)點(diǎn)？如果完全二叉樹有501個(gè)結(jié)點(diǎn)，結(jié)果如何？請(qǐng)寫出推導(dǎo)過程。 1. 設(shè)二叉樹中每個(gè)結(jié)點(diǎn)均用一個(gè)字母表示，若一個(gè)結(jié)點(diǎn)的左子樹或右子樹為空，用#表示，現(xiàn)前序遍歷二叉樹，訪問的結(jié)點(diǎn)序列為ABD#C#E#F#，寫出中序和后序遍歷二叉樹時(shí)結(jié)點(diǎn)的

31、訪問序列。 10一、單項(xiàng)選擇題1若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（ ） A9 B11 C15 D不確定2二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為（ ）A2I B 2I-1-1 C 2I-1 D2I -13已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（ ）。 ACBEFDA B FEDCBA C CBEDFA D不定4下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（ ）。 A0,10,110,1111 B11,10,001,101,0001 C00,010,0110,1000 Db,c,aa,ac,aba,abb,abc

32、5. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對(duì)應(yīng)的二叉樹。結(jié)論（ ）是正確的。 A.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同 B.樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同 C.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同 D.以上都不對(duì)二、判斷1. 二叉樹中所有結(jié)點(diǎn)如果不存在非空左子樹則不存在非空右子樹。（ ）2. 用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。( )3. 二叉樹中序線索化后，不存在空指針域。（ ）三、填空1.深度為k的完全二叉樹至少有_個(gè)結(jié)點(diǎn)，

33、至多有_個(gè)結(jié)點(diǎn)2. 在二叉樹中，指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_3.設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有_個(gè)葉子結(jié)點(diǎn)。四、程序1試寫出復(fù)制一棵二叉樹的算法。二叉樹采用標(biāo)準(zhǔn)鏈接結(jié)構(gòu)2.將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹。（只要求給出轉(zhuǎn)換結(jié)果）111. 列出圖所示二叉樹的葉結(jié)點(diǎn)、分支結(jié)點(diǎn)和每個(gè)結(jié)點(diǎn)的層次。 2. 如果一棵樹有n1個(gè)度為1的結(jié)點(diǎn), 有n2個(gè)度為2的結(jié)點(diǎn), , nm個(gè)度為m的結(jié)點(diǎn), 試問有多少個(gè)度為0的結(jié)點(diǎn)? 試推導(dǎo)之。3. 試分別找出滿足以下條件的所有二叉樹: (1) 二叉樹的前序序列與中序序列相同; (2) 二叉樹的中序序列與后序序列相同; (3) 二叉樹的前序序列與后序序列

34、相同4. 請(qǐng)畫出右圖所示的樹所對(duì)應(yīng)的二叉樹。5. 已知一棵二叉樹的先序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫出這棵二叉樹。13一、選擇題1.由三個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹( ) 。A) 3 B) 4 C) 5 D) 62.在一棵深度為k的完全二叉樹中,所含結(jié)點(diǎn)個(gè)數(shù)不小于( )。A）2k B) 2k+1C) 2k-1 D) 2k-13.對(duì)于任何一棵二叉樹，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=（ ）。A. n2-1 B. n2+1 C. n2 D. n2-24.已知二叉樹的后序遍歷序列是d a b e c,中序序列是d e b a

35、 c,則它的前序遍歷是 ( )。A) c e d b a B) a c b e d C) d e c a b D) d e a b c二、填空題1如果結(jié)點(diǎn)A有 3個(gè)兄弟，而且B是A的雙親，則B的度是_。2若以4，5，6，7，8作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長(zhǎng)度是_。三、應(yīng)用題1要求二叉樹按二叉鏈表形式存儲(chǔ)，（1）寫一個(gè)建立二叉樹的算法。（2）寫一個(gè)判別給定的二叉樹是否是完全二叉樹的算法。完全二叉樹定義為：深度為K，具有N個(gè)結(jié)點(diǎn)的二叉樹的每個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至N的結(jié)點(diǎn)一一對(duì)應(yīng)。此題以此定義為準(zhǔn)。2將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹。（只要求給出轉(zhuǎn)換結(jié)果）NPG

36、HJMOLIKEDFBAC 17選擇題1.在一棵二叉樹上第4層的結(jié)點(diǎn)數(shù)最多為（）。A. 2B. 4 C. 6D. 82.用順序存儲(chǔ)的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R1.n，結(jié)點(diǎn)Ri若有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)（）。A. R2i+1B. R2iC. Ri/2D. R2i-13.已知一棵完全二叉樹的結(jié)點(diǎn)總數(shù)為9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為（）。A. 1 B. 2C. 3D. 44.對(duì)二叉排序樹進(jìn)行  ( )遍歷，可以得到該二叉樹所有結(jié)點(diǎn)構(gòu)成的排序序列。   A、前序      

37、;   B、中序       C、后序         D、按層次5.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹第i層上，最多具有  ( )  個(gè)結(jié)點(diǎn)。  A、2i           B、2i+1       C、2i-1  

38、0;       D、2n判斷題6.完全二叉樹的某結(jié)點(diǎn)若無左孩子，則它必是葉結(jié)點(diǎn)。   （  ）7.存在這樣的二叉樹，對(duì)它采用任何次序的遍歷，結(jié)果相同。（ ）8.二叉樹就是結(jié)點(diǎn)度為2的樹。（ ）9.二叉樹中不存在度大于2的結(jié)點(diǎn)，當(dāng)某個(gè)結(jié)點(diǎn)只有一棵子樹時(shí)無所謂左、右子樹。（   ）10.已知二叉樹的前序遍歷序列和后序遍歷序列并不能唯一地確定這棵樹，因?yàn)椴恢罉涞母Y(jié)點(diǎn)是哪一個(gè)。（）11.中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列。（）12.將一棵樹轉(zhuǎn)換成二叉

39、樹后，根結(jié)點(diǎn)沒有左子樹。（   ）13.用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷。（  ）14.哈夫曼樹是帶權(quán)路徑長(zhǎng)度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。（ ）15.不使用遞歸也能實(shí)現(xiàn)二叉樹前序、中序和后序遍歷。（ ）填空題16.一棵具有個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為 。17.若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是 。 18.用5個(gè)權(quán)值3, 2, 4, 5, 1構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長(zhǎng)度是 。解答題19.已知二叉樹的中序遍歷序列是DBGEAFHC，后序遍歷序列是DGE

40、BHFCA，請(qǐng)構(gòu)造一棵二叉樹,并給出前序遍歷序列。18一、單項(xiàng)選擇題 以下說法錯(cuò)誤的是 ( )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)的度為2 B任何一棵二叉樹中每個(gè)結(jié)點(diǎn)的度都為2C任何一棵二叉樹中的度肯定等于2 D任何一棵二叉樹中的度可以小于23討論樹、森林和二叉樹的關(guān)系，目的是為了（ ）A借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對(duì)樹的一些運(yùn)算B將樹、森林按二叉樹的存

41、儲(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ù)12已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（ ）。ACBEFDA B FEDCBA C CBEDFA D不定 13已知某二叉樹的后序遍歷序列是dabec, 中序遍歷序列是debac , 它的前序遍歷是（ ）。Aacbed Bdecab Cdeabc Dcedba 二、判斷題（在各題后填寫“”或“×”）1. 完全二叉樹一定存在度為1的結(jié)點(diǎn)。( )2對(duì)于有N

42、個(gè)結(jié)點(diǎn)的二叉樹，其高度為log2n。( )3. 二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序。( )4. 一棵一般樹的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點(diǎn)前序遍歷和后序遍歷是一致的。( )三、填空題1在二叉樹中，指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_ _。2深度為k的完全二叉樹至少有_個(gè)結(jié)點(diǎn)，至多有_ _個(gè)結(jié)點(diǎn)。3高度為8的完全二叉樹至少有_個(gè)葉子結(jié)點(diǎn)。4.具有n個(gè)結(jié)點(diǎn)的二叉樹中,一共有_個(gè)指針域,其中只有_個(gè)用來指向結(jié)點(diǎn)的左右孩子，其余的_個(gè)指針域?yàn)镹ULL。5樹的主要遍歷方法有_、_、_等三種。20一 選擇題1.如果T2是由數(shù)T轉(zhuǎn)換而來的二叉樹，那么對(duì)T中結(jié)點(diǎn)的后序遍歷就是對(duì)T2中

43、結(jié)點(diǎn)的_遍歷。A 先序 B 中序 C 后序 D 層次序2. 設(shè)數(shù)T的度是4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1，則T中的葉子數(shù)為_ A.5 B.6 C.7 D.83. 由4個(gè)結(jié)點(diǎn)可以構(gòu)造出_種不同的二叉樹。 A.10 B.12 C.14 D.164. 二叉樹在線索后，人不能有效求解的問題是_ A. 在先序線索二叉樹中求先序后繼 B. 在中序線索二叉樹中求中序后繼 C. 在中序線索二叉樹中求中序前驅(qū) D. 在后序線索二叉樹中求后序后繼5. 一顆二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是_ A.9 B.11 C.15 D.不確定6.設(shè)高度為h的二叉樹只有

44、度為0和2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為_個(gè) A. 2h B. 2h-1 C.2h+1 D. h+17.設(shè)給定權(quán)值的葉子總數(shù)為n 個(gè)，其哈夫曼數(shù)的結(jié)點(diǎn)總數(shù)為_ A. 不確定 B 2n C. 2n+1 D.2n-18. 某二叉樹的先序遍歷和后序遍歷正好相反，則此二叉樹一點(diǎn)是_ A. 空或只有一個(gè)結(jié)點(diǎn) B. 完全二叉樹 C. 單支數(shù) D. 高度等與結(jié)點(diǎn)數(shù)9. 在二叉樹的先序序列，中序遍歷和后序遍歷中，所有葉子結(jié)點(diǎn)的先后順序_- A 都不相同 B. 完全相同 C. 先序和中序相同，而與后序不同 D. 中序和后序相同，而與先序不同10. 根據(jù)使用頻率，為五個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能是_

45、A.111,110,10,01,00 B. 000,001,010,011,1 C. 100,11,10,1,0 D. 001,000,01,11,10二填空題 1.已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，則二叉樹的總結(jié)點(diǎn)數(shù)至少是_ 2.樹在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)有_._-和_ 3.在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)為N0,度為2的結(jié)點(diǎn)個(gè)數(shù)是N2,則有N0=_ 4.葉子權(quán)數(shù)（5，6，17，8，19）所構(gòu)造的哈夫曼數(shù)帶權(quán)路徑長(zhǎng)度為_ 5.設(shè)一棵完全二叉樹葉子結(jié)點(diǎn)數(shù)為k ，最后一層結(jié)點(diǎn)數(shù)為偶數(shù)時(shí)，則該二叉樹的高度為_,最后一層結(jié)點(diǎn)數(shù)為奇數(shù)時(shí)，則該二叉樹的高度為_ 6.有_種不同形態(tài)的二叉樹可以按照中序遍歷得到相同的

46、abc序列 7.已知二叉樹先序?yàn)锳BDEGCF，中序?yàn)镈BGEACF,則后序一定是_ 8.深度為k的完全二叉樹至少有_個(gè)結(jié)點(diǎn)，至多有_個(gè)節(jié)點(diǎn) 9.具有10個(gè)葉子的哈夫曼樹，其最大高度為_,最小高度為_ 10.設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非終端節(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有_個(gè)三判斷題 1.哈夫曼樹的結(jié)點(diǎn)個(gè)數(shù)不可能是偶數(shù) 2.二叉樹中序線索化后，不存在空指針域 3.二叉樹線索化后，任意一個(gè)結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線索 4.哈夫曼編碼是前綴編碼 5.非空的二叉樹一定滿足：某結(jié)點(diǎn)若有左孩子，則其中序前驅(qū)一定沒有右孩子 6.必須把一般數(shù)轉(zhuǎn)換成二叉樹以后才能進(jìn)行存儲(chǔ) 7.由先

47、序和后序遍歷序列不能唯一確定一棵二叉樹 8.一棵樹中的葉子數(shù)一定等于與其對(duì)應(yīng)的二叉樹的葉子數(shù) 9.一個(gè)樹的葉子數(shù)，在前序遍歷和后序遍歷下，皆以相同的相對(duì)位置出現(xiàn) 10在哈夫曼樹中權(quán)值相同的葉節(jié)點(diǎn)都在同一層上四綜合題 1.已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA,寫出其先序遍歷序列五程序填空 1.一棵以孩子兄弟表示法存儲(chǔ)，遞歸算法計(jì)算并返回根為r的數(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)（NULL代表空指針） Typedef struct tnode Struct tnode *firstson, *nextbrother; Tnode; Int numberofleaf(Tnode

48、*r) Int num; If(r=NULL) num=0; Else if(r->firstson=NULL) Num=_+numberrofleaf(r->nextbrother); Else_; Return(num); 2. 假設(shè)二叉樹t的結(jié)點(diǎn)有四個(gè)字段，它們分別是：data. Lchild .rchild.parent,，其中data存放結(jié)點(diǎn)值，lchild和rchild分別指向左子結(jié)點(diǎn)和右子結(jié)點(diǎn)，parent指向父結(jié)點(diǎn)。在下列程序中，非遞歸函數(shù)mid_order(t)實(shí)現(xiàn)了對(duì)二叉樹t的中序遍歷 Type struct node Int data; Struct node *ichild,*rchild; Struct node*parent; Node; Void mid_order(Node *t) Node *p,*q; P=NULL;q=t; Do While(q!=NULL) _(1)_; q=q->lchild; If( (2) ) printf(“%5d,p->data”); _