數(shù)據(jù)結(jié)構(gòu)(樹)-供參考

1、數(shù)據(jù)結(jié)構(gòu)與算法上機(jī)作業(yè)第三章 樹一、選擇題1、在一棵樹中，如果結(jié)點(diǎn)A有3個(gè)兄弟，B是A的雙親，則B的度為 D A. 1B. 2C. 3D. 42、深度為h的完全二叉樹至少有 D 個(gè)結(jié)點(diǎn)，至多有 B 個(gè)結(jié)點(diǎn)A. 2hB. 2h-1C. 2h+1D. 2h-13、具有n個(gè)結(jié)點(diǎn)的滿二叉樹有 C 個(gè)葉結(jié)點(diǎn)。A. n/2B. (n-1)/2C. (n+1)/2D. n/2+14、一棵具有25個(gè)葉結(jié)點(diǎn)的完全二叉樹最多有 C 個(gè)結(jié)點(diǎn)。A. 48B. 49C. 50D. 515、已知二叉樹的先根遍歷序列是ABCDEF，中根遍歷序列是CBAEDF，則后根遍歷序列是 A 。A. CBEFDAB. FEDCBAC.

2、 CBEDFAD. 不定6、具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有 B 個(gè)度為2的結(jié)點(diǎn)。A. 8B. 9C. 10D. 117、一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足 B 。A. 所有非葉結(jié)點(diǎn)均無左孩子B. 所有非葉結(jié)點(diǎn)均無右孩子C. 只有一個(gè)葉子結(jié)點(diǎn)D. A和B同時(shí)成立8、在線索二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是 D 。A. t-left=NULLB. t-ltag=TRUEC. t-ltag=TRUE且t-left=NULLD. 以上都不對(duì)9、n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為 C 。A. 2nB. n-1C. n+1D. n10、二叉樹按照某種順序線索化后

3、，任一結(jié)點(diǎn)都有指向其前驅(qū)和后繼的線索，這種說法 B 。A. 正確B. 錯(cuò)誤C. 不確定D. 都有可能11、具有n(n1)個(gè)結(jié)點(diǎn)的完全二叉樹中，結(jié)點(diǎn)i(2in)的左孩子結(jié)點(diǎn)是 D 。A. 2i B. 2i+1C. 2i-1D. 不存在12、具有64個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 C 。A. 5B. 6C.7D. 813、將一顆有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下、從左到右一次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為45的結(jié)點(diǎn)的右孩子的編號(hào)為 D 。A. 46B. 47C. 90D. 9114、在結(jié)點(diǎn)數(shù)為n的堆中插入一個(gè)結(jié)點(diǎn)時(shí)，復(fù)雜度為 C 。A. O(n)B. O(n2)C. O(log2n)D.

4、O(logn2)15、兩個(gè)二叉樹是等價(jià)的，則它們滿足 D 。A. 它們都為空B. 它們的左右子樹都具有相同的結(jié)構(gòu)C. 它們對(duì)應(yīng)的結(jié)點(diǎn)包含相同的信息 D. A、B和C16、包含n個(gè)元素的堆的高度為 C 。（符號(hào)a表示取不小a最小整數(shù)）A. nB. log2nC. log2(n+1)D. n+117、以下說法錯(cuò)誤的是 B 。A. 存在這樣的二叉樹，對(duì)其采用任何次序的遍歷其結(jié)點(diǎn)訪問序列均相同B. 二叉樹是樹的特殊情形C. 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的D. 在二叉樹中只有一棵子樹的情形下，也要指出是左子樹還是右子樹18、設(shè)F是一個(gè)森林，B是由F變換得到的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則

5、B中沒有右孩子的結(jié)點(diǎn)有 C 個(gè)。A. n-1B. nC. n+1D. n+219、將一棵樹T轉(zhuǎn)換為二叉樹B，則T的后根序列是B的 B 。A. 先根序列B. 中根序列C. 后根序列D. 層次序列20、將一棵樹轉(zhuǎn)換為二叉樹后，這顆二叉樹的形態(tài)是 B 。A. 唯一的，根結(jié)點(diǎn)沒有左孩子B. 唯一的，根結(jié)點(diǎn)沒有右孩子C. 有多種，根結(jié)點(diǎn)都沒有左孩子D. 有多種，根結(jié)點(diǎn)都沒有右孩子21、設(shè)樹T的度為4，其中度為1, 2, 3, 4的結(jié)點(diǎn)個(gè)數(shù)分別為4, 2, 1, 1，則T中的葉結(jié)點(diǎn)的個(gè)數(shù)為 D 。A. 5B. 6C. 7D. 822、設(shè)森林F中有三棵樹，第一、第二、第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1, M2,

6、M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)為 D 。A. M1-1B. M1+M2C. M2D. M2+M323、若以二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹是 C 。A. 二叉排序樹B. 哈夫曼樹C. 堆D. 線索二叉樹24、用5個(gè)權(quán)值3, 2, 4, 5, 1構(gòu)造的哈夫曼樹的帶權(quán)路徑長度是 C 。A. 32B. 33C. 34D. 15二、填空題1、一棵二叉樹有67個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的度是0和2。問這棵二叉樹中度為2的結(jié)點(diǎn)有 33 個(gè)。2、含A, B, C三個(gè)結(jié)點(diǎn)的不同形態(tài)的二叉樹有 0 棵。3、含有4個(gè)度為2的結(jié)點(diǎn)和5個(gè)葉子結(jié)點(diǎn)的完全二叉樹，有 1

7、個(gè)度為1的結(jié)點(diǎn)。4、具有100個(gè)結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為 50 。5、在用左右鏈表示的具有n個(gè)結(jié)點(diǎn)的二叉樹中，共有 2n 個(gè)指針域，其中 n-1 個(gè)指針域用于指向其左右孩子，剩下的 n+1 個(gè)指針域是空的。 6、如果一顆完全二叉樹的任意一個(gè)非終結(jié)結(jié)點(diǎn)的元素都 大于等于 其左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)(如果有的話)的元素，則稱此完全二叉樹為最大堆。7、堆是一種特殊形式的 完全二叉樹 二叉樹，對(duì)于最大堆而言，其根結(jié)點(diǎn)的元素的值應(yīng)該是所有結(jié)點(diǎn)元素中 最大的 的。8、二叉樹的復(fù)制是指按照一棵已知的二叉樹復(fù)制一個(gè)副本，使兩者 等價(jià) 。復(fù)制二叉樹最長用的方法是 后根遍歷遞歸算法 。9、在定義堆時(shí)，通常采用

8、 數(shù)組 方式定義相應(yīng)的二叉樹，這樣可以很容易實(shí)現(xiàn)其相關(guān)操作。10、在構(gòu)建選擇樹時(shí)，根據(jù)孩子結(jié)點(diǎn)的獲勝者確定他們雙親結(jié)點(diǎn)所得到的選擇樹稱為 勝者樹 。根據(jù)孩子結(jié)點(diǎn)的失敗者確定他們雙親結(jié)點(diǎn)所得到的選擇樹稱為 敗者樹 。11、樹的表示方法包括 數(shù)組 、 鄰接表 和 左右鏈 。12、表達(dá)式(a+b*(c-d)-e/f的波蘭式(前綴式)是 -+a*b-cd/ef ，逆波蘭式(后綴式)是 abcd-*+e/f- 。13、設(shè)F是由T1、T2、T3三棵樹組成的森林，與F對(duì)應(yīng)的二叉樹為B。已知T1, T2, T3的結(jié)點(diǎn)數(shù)分別為n1, n2和n3，則二叉樹B的左子樹中有 n1-1 個(gè)結(jié)點(diǎn)，二叉樹B的右子樹中有 n

9、2+n3 個(gè)結(jié)點(diǎn)。14、設(shè)二叉樹的中根序列為ABCDEFG，后根序列為BDCAFGE。則該二叉樹的先根序列為EGCBDGF 。該二叉樹對(duì)應(yīng)的森林中包含 2 棵樹。15、先根次序遍歷森林等同于按 先根 遍歷對(duì)應(yīng)的二叉樹，后根次序遍歷森林等同與按 中根 遍歷對(duì)應(yīng)的二叉樹。16、一棵哈夫曼樹有19個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)的個(gè)數(shù)為 10 。17、設(shè)有數(shù)據(jù)WG=7, 19, 2, 6, 32, 3, 21, 10葉節(jié)點(diǎn)權(quán)重集合，則所構(gòu)建哈夫曼樹的高是 6 ，帶權(quán)路徑長度WPL為 261 。18、設(shè)有一份電文中共使用6個(gè)字符a, b, c, d, e, f，其中出現(xiàn)頻率依次為2，3，4，7，8，19，則字符c

10、的哈夫曼編碼是 001 ，電文編碼的總長度為 96 。20、在有n個(gè)結(jié)點(diǎn)的哈夫曼樹中，葉子結(jié)點(diǎn)總數(shù)為 （n+1）/2 ，非葉結(jié)點(diǎn)的總數(shù)為 (n-1)/2 。三、試分別畫出具有4個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。四、已知一棵二叉樹的中根序列和后根序列分別是BDCEAHFG和DECBHGFA，請(qǐng)畫出此二叉樹。五、已知非空二叉樹T，寫一個(gè)算法，求度為2的結(jié)點(diǎn)的個(gè)數(shù)。要求：1、定義二叉樹的抽象數(shù)據(jù)類型和型BTREE，并定義基本操作。2、編寫函數(shù)count2(BTREE T)，返回度為2的節(jié)點(diǎn)的個(gè)數(shù)。 3、在主函數(shù)中，構(gòu)建一個(gè)二叉樹，并驗(yàn)證所編寫的算法。六、用遞歸方法寫一個(gè)算法，求二叉樹的葉子結(jié)點(diǎn)數(shù)int

11、leafnum(BTREE T)。要求：定義二叉樹的抽象數(shù)據(jù)類型和型BTREE，并定義基本操作。編寫函數(shù)leafnum(BTREE T)，返回樹T的葉子節(jié)點(diǎn)的個(gè)數(shù)。在主函數(shù)中，構(gòu)建一個(gè)二叉樹，并驗(yàn)證所編寫的算法。七、畫出下圖所表示的二叉樹的中序線索二叉樹和先序線索二叉樹。 八、已知二叉樹的先根序列是AEFBGCDHIKJ，中根序列是EFAGBCHKIJD，畫出此二叉樹，并畫出后序線索二叉樹。九、在中序線索二叉樹中插入一個(gè)結(jié)點(diǎn)Q作為樹中某個(gè)結(jié)點(diǎn)P的左孩子，試給出相應(yīng)的算法。要求：定義中序線索二叉樹的型THTREE以及基本操作。定義函數(shù)void LInsert(THTREE P, THTREE Q

12、); 實(shí)現(xiàn)題目要求的操作。在主函數(shù)中，利用操作RInsert和LInsert構(gòu)造一個(gè)線索二叉樹，并中序輸出二叉樹的結(jié)點(diǎn)的元素，驗(yàn)證結(jié)果。十、假設(shè)現(xiàn)在有如下的元素：7、16、49、82、5、31、6、2、44。畫出將每一個(gè)元素插入堆中以后的最大堆。要求：利用基本操作Insert的基本原理，先用第一個(gè)元素7構(gòu)成一個(gè)二叉樹，然后將第二個(gè)元素16插入該二叉樹中，再將第三個(gè)元素49插入堆中，直到最后一個(gè)元素插入為止。上述過程要求畫圖完成。十一、編寫一個(gè)函數(shù)，在最大堆中查找任意元素，并分析其時(shí)間復(fù)雜度。要求：定義最大堆的型HEAP及其基本操作。定義函數(shù)int Find(HEAP H, Elementtyp

13、e e)，查找e是否為堆的元素，如果是，返回該元素在堆中的位置，如果不是，返回0。（提示：利用最大堆的元素特點(diǎn)進(jìn)行查找，可降低復(fù)雜度）在主函數(shù)中首先構(gòu)建一個(gè)二叉樹，然后驗(yàn)證所構(gòu)造的函數(shù)。十二、給定葉子結(jié)點(diǎn)的權(quán)值集合15, 3,14, 2, 6, 9, 16, 17，構(gòu)造相應(yīng)的哈夫曼樹，并計(jì)算其帶權(quán)路徑長度。十三、已知n=9和一組等價(jià)關(guān)系： 15、68、72、98、37、42、93 試應(yīng)用抽象數(shù)據(jù)類型MFSET設(shè)計(jì)一個(gè)算法，按輸入的等價(jià)關(guān)系進(jìn)行等價(jià)分類。十四、畫出下圖所示的森林經(jīng)轉(zhuǎn)換后所對(duì)應(yīng)的二叉樹，并指出在二叉樹中某結(jié)點(diǎn)為葉子結(jié)點(diǎn)時(shí)，所對(duì)應(yīng)的森林中結(jié)點(diǎn)應(yīng)滿足的條件。十五、已知森林F的先根序列為

14、：ABCDEFGHIJKL，后根序列為：CBEFDGAJIKLH，試畫出森林F。提示：先畫出森林F所對(duì)應(yīng)的二叉樹B，然后再將B轉(zhuǎn)換為森林。十六、畫出表達(dá)式(A+B*C/D)*E+F*G所對(duì)應(yīng)的樹結(jié)構(gòu)，并寫出該表達(dá)式的波蘭表示式和逆波蘭表示式。十七、利用逆波蘭表達(dá)式求一個(gè)四則混合元算的值。具體要求：定義二叉樹的型BTREE和位置的型position。實(shí)現(xiàn)二叉樹的基本操作。實(shí)現(xiàn)將一個(gè)四則混合運(yùn)算轉(zhuǎn)換成二叉樹的函數(shù)：BTREE convert(char *express)，其中參數(shù)express為四則混合運(yùn)算表達(dá)式，返回值為生成的樹。實(shí)現(xiàn)計(jì)算四則混合運(yùn)算的值的函數(shù)：double computer(B

15、TREE bt)，其中，參數(shù)bt為四則運(yùn)算所對(duì)應(yīng)的樹，返回值為計(jì)算結(jié)果。提示：先求樹的的波蘭表達(dá)式，然后利用棧結(jié)構(gòu)計(jì)算表達(dá)式的值。在主函數(shù)中進(jìn)行測(cè)試，求2+3*（5+8）/4-5的值。要求：1、上述作業(yè)要求在單獨(dú)完成；2、完成后，于規(guī)定期限內(nèi)提交到ftp服務(wù)器的相應(yīng)目錄中中，注意，在提交時(shí)將所編寫的程序統(tǒng)一拷貝到一個(gè)Word文件中，文件名格式為“學(xué)號(hào)+姓名”三ABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCD四BCAFEDGH五、六代碼#includeusing namespace std;typedef char datatype

16、;struct nodenode *lchild;datatype data;node *rchild;typedef node *BTREE;void CreateBTREE(BTREE &BT,char *&str)/先根輸入樹 char ch;ch=*str+;if(ch=#)BT=NULL;elseBT=new node;BT-data=ch;CreateBTREE(BT-lchild,str);CreateBTREE(BT-rchild,str);void Empty(BTREE BT)BT=NULL;bool IsEmpty(BTREE BT)/判斷是否為空 if(BT=NULL)

17、return true;elsereturn false;BTREE CreateBT(datatype v,BTREE ltree,BTREE rtree)/用左右子樹建立二叉樹 BTREE root;root=new node;root-data=v;root-lchild=ltree;root-rchild=rtree;return root;BTREE Lchild(BTREE BT)/返回左子樹 return BT-lchild;BTREE Rchild(BTREE BT)/返回右子樹 return BT-rchild;datatype Data(BTREE BT)/返回節(jié)點(diǎn)元素值

18、return BT-data;void visit(datatype dt)coutlchild)&(BT-rchild)return 1+count2(Lchild(BT)+count2(Rchild(BT);if(BT-lchild)&(BT-rchild=NULL)return count2(Lchild(BT);if(BT-lchild=NULL)&(BT-rchild)return count2(Rchild(BT);int leafnum(BTREE BT)static int count=0;if(BT-lchild=NULL&BT-rchild=NULL)return +cou

19、nt;elseleafnum(Lchild(BT);leafnum(Rchild(BT);int main()BTREE BT=NULL;char *str=abc#d#ef#g#;CreateBTREE(BT,str);cout度為2的節(jié)點(diǎn)的個(gè)數(shù):count2(BT)endl;cout葉子節(jié)點(diǎn)個(gè)數(shù)：leafnum(BT)endl;七h(yuǎn)ead中序線索二叉樹798653421先序線索二叉樹689735124head八二叉樹BGAEFCDHJIK后序線索二叉樹BGAEFCDHJIKHead九#includeusing namespace std;typedef char datatype;stru

20、ct nodenode *lchild;node *rchild;bool ltag;bool rtag;datatype data;typedef node *THTREE;THTREE InPre(THTREE P)/求中序前驅(qū)(右子樹的最左節(jié)點(diǎn))THTREE Q=P-lchild;if(P-ltag=true)while(Q-rtag=true)Q=Q-rchild;return Q;THTREE InNext(THTREE P)/求中序后繼(左子樹的最右節(jié)點(diǎn))THTREE Q=P-rchild;if(P-rtag=true)while(Q-ltag=true)Q=Q-lchild;re

21、turn Q;/二叉樹中插入一個(gè)結(jié)點(diǎn)Q作為樹中某個(gè)結(jié)點(diǎn)P的左孩子void LInsert(THTREE P,THTREE Q)THTREE W;Q-lchild=P-lchild;Q-ltag=P-ltag;Q-rchild=P;Q-rtag=false;P-lchild=Q;P-ltag=true;if(Q-ltag=true)/如果P節(jié)點(diǎn)有左孩子W=InPre(Q);W-rchild=Q;void RInsert(THTREE P,THTREE Q)THTREE W;Q-rchild=P-rchild;Q-rtag=P-rtag;Q-lchild=P;Q-ltag=false;P-rchi

22、ld=Q;P-rtag=true;if(Q-rtag=true)/如果P節(jié)點(diǎn)有右孩子W=InNext(Q);W-lchild=Q;void ThInOrder(THTREE HEAD)THTREE temp;temp=HEAD;dotemp=InNext(temp);if(temp!=HEAD)coutdata);while(temp!=HEAD); int main()node *HEAD=new node;node *A=new node;HEAD-data=!;A-data=A; HEAD-lchild=A;HEAD-rchild=HEAD;HEAD-ltag=true;HEAD-rta

23、g=true;A-lchild=HEAD;A-rchild=HEAD;A-ltag=false;A-rtag=false; node *B=new node;B-data=B;node *C=new node;C-data=C;node *D=new node;D-data=D;node *E=new node;E-data=E;node *F=new node;F-data=F;node *G=new node;G-data=G;LInsert(A,B);RInsert(A,C);LInsert(B,D);RInsert(B,E);LInsert(C,F);RInsert(C,G);ThIn

24、Order(HEAD);十16744263158249716263158249716631582497163158249716582497168249716491677十一#include#define MaxSize 200using namespace std;typedef structint data;Elementtype;typedef structElementtype elementsMaxSize;int n;HEAP;void MaxHeap(HEAP &heap)/創(chuàng)建一個(gè)空堆 heap.n=0;bool HeapEmpty(HEAP heap)/判斷是否為空堆 retu

25、rn (!heap.n); bool HeapFull(HEAP heap)/判斷是否滿堆 return(heap.n=MaxSize-1);void Insert(HEAP &heap,Elementtype element)/最大堆插入一個(gè)元素 int i;if(!HeapFull(heap)i=+heap.n;while(i!=1&(element.dataheap.elementsi/2.data)heap.elementsi=heap.elementsi/2;i/=2;heap.elementsi=element;Elementtype DeleteMax(HEAP &heap)/刪

26、除堆中的最大元素 int parent=1,child=2;Elementtype element,tmp;if(!HeapEmpty(heap)element=heap.elements1;tmp=heap.elementsheap.n-;while(child=heap.n)if(childheap.n)&(heap.elementschild.data=heap.elementschild.data) break;heap.elementsparent=heap.elementschild;parent=child;child*=2;heap.elementsparent=tmp;ret

27、urn element;int Find(HEAP &H,Elementtype e)/查找e是否為堆中元素 int i=H.n,j;if(e.data=H.elements1.data)return 1;if(i!=0)if(e.data=H.elementsi.data)return i;else if(e.dataH.elementsi/2.data)&(e.dataH.elementsi/4.data)j=i/4+1;while(ji)if(e.data=H.elementsj.data)return j;j+;return 0;elsei/=4;int main()HEAP H;H.n=0;Elementtype element;int data=7,16,49,82,5,31,6,2,44;for(int i=0;i9;i+)element.data=datai;Insert(H,element);cout最大堆元素為：endl;for(int i=1;i=9;i+)coutH.elementsi.datat;coutendl;cout請(qǐng)輸入要查找的元素element.data;cout該元素在堆中的位置為Find(H,element)endl;2923651191415161733208249十二WPL=(16+