樹和二叉樹習(xí)題

1、文檔收集于互聯(lián)網(wǎng)，已重新整理排版.word版本可編輯歡迎下載支持. 1文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編借. ZrAr 、 寸 第六早 樹和二叉樹 一、選擇題 1. 算術(shù)表達(dá)式a+b* （c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（B ） A. ab+cde/* B. abcde/+*+C. abcde/*+ D. abcde*/卄 2. 設(shè)有一表示算術(shù)表達(dá)式的二叉樹（見卜一圖），廠丿 它所表示的算術(shù)表達(dá)式是（c ）QT _X+ A. A*B+C/（D*E） + （F-G） B. （A*B+C） / （D*E） + （F-G）Q Q GY C. （A*B+）/（D*E+ （F-G） ） D. A

2、*B-C/D*E+F-G 3. 設(shè)樹T的度為4,其中度為1, 2, 3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4, 2,Q19T翩I胃 數(shù)為（D ） A. 5B. 6C. 7D. 8 4. 在下述結(jié)論中，正確的是（D ） 只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0;二叉樹的度為2；二叉樹的左右子樹可任意 交換； 深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。 A.B. C.D. 5. 設(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ù)是（A ） A. m-n B. m-n-1 C. n+1 D.條件不足，無法確泄 6. 若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5

3、個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（B ） A. 9B. 11C. 15D.不確定 7. 設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為Ml, M2和M3。與森林F 對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（D ）。 A. MlB. M1+M2C. M3D. M2+M3 8. 一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（E ） A. 250 B. 500 C. 254 D. 505 E.以上答案都不對(duì) 9. 有關(guān)二叉樹下列說法正確的是（B ） A.二叉樹的度為2B. 一棵二叉樹的度可以小于2 C.二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2 10.

4、二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為（C ） A. 21B. 2:_1-1C. 2I_1D. 21 -1 11. 一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高11為（C ） A. 11B. 10C. 11 至 1025 之間 D. 10 至 1024 之間 12. 一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?,或?yàn)?,則這棵二叉樹最少有（B ）結(jié)點(diǎn) D. h+1 ）個(gè)結(jié)點(diǎn) A. 2h B. 2h-lC. 2h+l 13. 一棵樹高為K的完全二叉樹至少有（C A. 2k -1B. 2戸-1 14. 對(duì)二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于英左、右孩子的編號(hào), 同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小

5、于其右孩子的編號(hào)，可采用（C ）次序的遍歷 實(shí)現(xiàn)編號(hào)。 A.先序B.中序C.后序D.從根開始按層次遍歷 15. 棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（B ） A. CABDEFGB. ABCDEFGC. DACEFBGD. ADCFEG 16. 已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果 為(A )。 A. CBEFDAB. FEDCBAC. CBEDFAD.不泄 17. 對(duì)于前序遍歷與中序遍歷結(jié)果相同的二叉樹為(1F); 對(duì)于前序遍歷和后序遍歷結(jié)果相同的二叉樹為(2B)。 A. 一般二叉樹B.只有根結(jié)點(diǎn)的二叉樹C.根結(jié)點(diǎn)

6、無左孩子的二叉樹 D.根結(jié)點(diǎn)無右孩子的二叉樹E.所有結(jié)點(diǎn)只有左子數(shù)的二叉樹F.所有結(jié)點(diǎn)只有右子 樹的二叉樹 18. 在下列情況中，可稱為二叉樹的是(B ) A.每個(gè)結(jié)點(diǎn)至多有兩棵子樹的樹B.哈夫曼樹 C.每個(gè)結(jié)點(diǎn)至多有兩棵子 樹的有序樹 D.每個(gè)結(jié)點(diǎn)只有一棵右子樹E.以上答案都不對(duì) 19. n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為(C ) A 2n B nlC n+1D n 20. 由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？ (D ) A. 2B. 3C. 4D. 5 21. 當(dāng)一棵有n個(gè)結(jié)點(diǎn)的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在一維數(shù)組 Al.n中時(shí)，數(shù)組中第i個(gè)結(jié)點(diǎn)的左孩子為(D )

7、 A. A2i (2i=n) B. A2i+1 (2i+l= n) C. Ai/2D.無法確定 二、填空題 1. 二叉樹由_(3)_三個(gè)基本單元組成。 2. 中綴式a+b*3+4* (c-d)對(duì)應(yīng)的前綴式為若a二1, b二2, c二3, d二4,則后綴式 db/cc*a-b*+的運(yùn)算結(jié)果為_(2)_。 3. 具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 4. 已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該 樹有個(gè)葉子結(jié)點(diǎn)。 5. 深度為k的完全二叉樹至少有_(1)_個(gè)結(jié)點(diǎn),至多有_(2)_ 個(gè)結(jié)點(diǎn)。 6. 設(shè)有N個(gè)結(jié)點(diǎn)的完全二叉樹順序存放在向量A1:N中，其下標(biāo)值最大的

8、分支結(jié)點(diǎn)為 7. 一個(gè)深度為k的，具有最少結(jié)點(diǎn)數(shù)的完全二叉樹按層次，(同層次從左到右)用自然數(shù)依 此對(duì)結(jié)點(diǎn)編號(hào)，則編號(hào)最小的葉子的序號(hào)是_(1)_：編號(hào)是i的結(jié)點(diǎn)所在的層次號(hào)是_(2)_ (根所在的層次號(hào)規(guī)定為1層)。 8. 具有N個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲(chǔ)，共有個(gè)空鏈域。 三、應(yīng)用題 1. 將算術(shù)表達(dá)式(a+b) +c*(d+e)+f) *(g+h)轉(zhuǎn)化為二叉樹。 2. 已知一棵滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)為20到40之間的素?cái)?shù)，此二叉樹的葉子結(jié)點(diǎn)有多少 個(gè)？ AEDGHFI：試畫 3. 將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹。(只要求給出轉(zhuǎn)換結(jié)果) 4. 弼二叉樹的前序嚴(yán)序列為:ABCDEFGHI,中用刪 序、后序序列如下，其 C D E H I _ K _FA_JKIG 出該卷咂華 峽出該二叉樹。 d) 5. 一涼上叉樹的先序內(nèi) 先序序列： 中序序列:C B 后序序列:_EFDB_JIH_A 6.