數(shù)據(jù)結(jié)構(gòu)期末試題及答案樣卷

1、-. z2020學(xué)年數(shù)據(jù)構(gòu)造期末試題及答案六一、選擇題1、二叉樹的深度為k，則二叉樹最多有 C 個結(jié)點(diǎn)。A. 2k B. 2k-1 C. 2k-1 D. 2k-12、用順序存儲的方法，將完全二叉樹中所有結(jié)點(diǎn)按層逐個從左到右的順序存放在一維數(shù)組R1.N中，假設(shè)結(jié)點(diǎn)Ri有右孩子，則其右孩子是 B 。A. R2i-1 B. R2i+1C. R2i D. R2/i3、設(shè)a,b為一棵二叉樹上的兩個結(jié)點(diǎn)，在中序遍歷時，a在b前面的條件是 B 。A. a在b的右方 B. a在b的左方C. a是b的祖先D. a是b的子4、設(shè)一棵二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹先序遍歷序列為

2、。A. adbce B. decab C. debac D. abcde5、在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為A。 A. 31 B. 32 C. 33 D. 166、由二叉樹的前序和后序遍歷序列 B 惟一確定這棵二叉樹。A. 能 B. 不能7、*二叉樹的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點(diǎn)數(shù)目為 C 。A. 3B. 2C. 4D. 58、假設(shè)以4,5,6,7,8作為權(quán)值構(gòu)造哈夫曼樹，則該樹的帶權(quán)路徑長度為 C 。A. 67B. 68C. 69D. 709、將一棵有100個結(jié)點(diǎn)的完全二叉樹從根這一層開場，每一層上從左到右依次對結(jié)點(diǎn)進(jìn)展編號，根結(jié)點(diǎn)的編號為1，則編

3、號為49的結(jié)點(diǎn)的左孩子編號為A 。A. 98B. 99C. 50D. 4810、表達(dá)式a*(b+c)-d的后綴表達(dá)式是 B 。A. abcd+-B. abc+*d-C. abc*+d- D. -+*abcd11、對*二叉樹進(jìn)展先序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果是 B 。A. DBFEACB. DFEBCAC. BDFECAD. BDEFAC12、樹最適合用來表示 C 。A. 有序數(shù)據(jù)元素 B. 無序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無聯(lián)系的數(shù)據(jù)13、表達(dá)式A*(B+C)/(D-E+F)的后綴表達(dá)式是 C 。A. A*B+C/

4、D-E+FB. AB*C+D/E-F+C. ABC+*DE-F+/D. ABCDED*+/-+14、在線索二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是。A. t-left=NULLB. t-ltag=1C. t-ltag=1&t-left=NULLD. 以上都不對15、任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序。A. 不發(fā)生改變B. 發(fā)生改變C. 不能確定D. 以上都不對16、假定在一棵二叉樹中，度為2的結(jié)點(diǎn)數(shù)為15，度為1的結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為個。A. 15B. 16C. 17D. 4717、在以下情況中，可稱為二叉樹的是 B 。A. 每個結(jié)點(diǎn)至多有兩棵子樹的樹B.

5、哈夫曼樹C. 每個結(jié)點(diǎn)至多有兩棵子樹的有序樹D. 每個結(jié)點(diǎn)只有一棵子樹18、用順序存儲的方法，將完全二叉樹中所有結(jié)點(diǎn)按層逐個從左到右的順序存放在一維數(shù)組R1.n中，假設(shè)結(jié)點(diǎn)Ri有左孩子，則其左孩子是。A. R2i-1 B. R2i+1C. R2i D. R2/i19、下面說法中正確的選項是。A. 度為2的樹是二叉樹 B. 度為2的有序樹是二叉樹C. 子樹有嚴(yán)格左右之分的樹是二叉樹D. 子樹有嚴(yán)格左右之分，且度不超過2的樹是二叉樹20、樹的先根序列等同于與該樹對應(yīng)的二叉樹的。A. 先序序列 B. 中序序列 C. 后序序列 D. 層序序列21、按照二叉樹的定義，具有3個結(jié)點(diǎn)的二叉樹有 C 種。A.

6、 3B. 4C. 5D. 622、由權(quán)值為3，6，7，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為 A 。A. 51B. 23C. 53 D. 74二、判斷題1、存在這樣的二叉樹，對它采用任何次序的遍歷，結(jié)果一樣。2、中序遍歷一棵二叉排序樹的結(jié)點(diǎn)，可得到排好序的結(jié)點(diǎn)序列。3、對于任意非空二叉樹，要設(shè)計其后序遍歷的非遞歸算法而不使用堆棧構(gòu)造，最適合的方法是對該二叉樹采用三叉鏈表。4、在哈夫曼編碼中，當(dāng)兩個字符出現(xiàn)的頻率一樣時，其編碼也一樣，對于這種情況應(yīng)做特殊處理。5、一個含有n個結(jié)點(diǎn)的完全二叉樹，它的高度是log2n1。6、完全二叉樹的*結(jié)點(diǎn)假設(shè)無左孩子，則它必是葉結(jié)點(diǎn)。三、填空題1、

7、具有n個結(jié)點(diǎn)的完全二叉樹的深度是log2n+1。2、哈夫曼樹是其樹的帶權(quán)路徑長度最小的二叉樹。3、在一棵二叉樹中，度為0的結(jié)點(diǎn)的個數(shù)是n0，度為2的結(jié)點(diǎn)的個數(shù)為n2，則有n0=N2+1。4、樹各結(jié)點(diǎn)度的最大值稱為樹的度。四、代碼填空題1、函數(shù)InOrderTraverse(Bitree bt)實(shí)現(xiàn)二叉樹的中序遍歷，請在空格處將算法補(bǔ)充完整。void InOrderTraverse(BiTree bt)if()InOrderTraverse(bt-lchild);printf(%c,bt-data);2、函數(shù)depth實(shí)現(xiàn)返回二叉樹的高度，請在空格處將算法補(bǔ)充完整。int depth(Bitre

8、e *t)if(t=NULL)return 0;elsehl=depth(t-lchild);hr=depth(t-rchild);if(hlhr)return hl+1;elsereturn hr+1;3、寫出下面算法的功能。Bitree *function(Bitree *bt)Bitree *t,*t1,*t2;if(bt=NULL)t=NULL;elset=(Bitree *)malloc(sizeof(Bitree);t-data=bt-data;t1=function(bt-left);t2=function(bt-right);t-left=t2;t-right=t1;retur

9、n(t);答案：交換二叉樹結(jié)點(diǎn)左右子樹的遞歸算法4、寫出下面算法的功能。void function(Bitree *t)if(p!=NULL)function(p-lchild);function(p-rchild);printf(%d,p-data);答案：二叉樹后序遍歷遞歸算法五、綜合題1、假設(shè)以有序?qū)Ρ硎緩碾p親結(jié)點(diǎn)到孩子結(jié)點(diǎn)的一條邊，假設(shè)樹中邊的集合為,請答復(fù)以下問題：1哪個結(jié)點(diǎn)是根結(jié)點(diǎn)？2哪些結(jié)點(diǎn)是葉子結(jié)點(diǎn)？3哪些結(jié)點(diǎn)是k的祖先？4哪些結(jié)點(diǎn)是j的兄弟？5樹的深度是多少？。2、假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請畫出該二叉樹。3、假設(shè)用于

10、通訊的電文僅由8個字母A、B、C、D、E、F、G、H組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。請為這8個字母設(shè)計哈夫曼編碼。答案：4、二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。答案：二叉樹形態(tài)5、試用權(quán)集合12,4,5,6,1,2構(gòu)造哈夫曼樹，并計算哈夫曼樹的帶權(quán)路徑長度。答案：WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=696、權(quán)值集合為5,7,2,3,6,9，要求給出哈夫曼樹，并計算帶權(quán)路徑長度WPL。答案：(1)樹形態(tài)：(2)帶權(quán)路徑長度：WPL

11、=(6+7+9)*2+5*3+(2+3)*4=44+15+20=797、一棵二叉樹的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。畫出二叉樹的形態(tài)。答案：8、一份電文中有6種字符：A,B,C,D,E,F，它們的出現(xiàn)頻率依次為16，5，9，3，30，1，完成問題：1設(shè)計一棵哈夫曼樹；畫出其樹構(gòu)造2計算其帶權(quán)路徑長度WPL；答案：(1)樹形態(tài)： (2)帶權(quán)路徑長度：WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=1299、*森林的二叉樹如下所示，試畫出它所表示的森林。答案：10、有一分電文共使用5個字符;a,b,c,d,e，它們的出現(xiàn)頻率依次為4、7、5、2、9，試構(gòu)造哈夫曼樹，并給出每個字符的哈夫曼編碼。11、畫出與以下圖所示的森林相對應(yīng)的二叉樹，并指出森林中的葉子結(jié)點(diǎn)在二叉樹中具有什么特點(diǎn)。12、如下所示的二叉樹，請寫出先序、中序、后序遍歷的序列。答案：先