[計算機(jī)軟件及應(yīng)用]棧的應(yīng)用和串圖-資料下載頁
2025-10-07 23:17本頁面
【正文】 0。 ② 二叉樹的度為 2； ③二叉樹的左右子樹可任意交換 。 ④ 深度為 K的完全二叉樹的結(jié)點(diǎn)個數(shù)小于或等于深度相同的滿二叉樹。 A．①②③ B．②③④ C．②④ D．①④ 8．若一棵二叉樹具有 10個度為 2的結(jié)點(diǎn)， 5個度為 1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個數(shù)是（ ） A． 9 B． 11 C． 15 D．不確定 9．在一棵三叉樹中度為 3的結(jié)點(diǎn)數(shù)為 2個，度為 2的結(jié)點(diǎn)數(shù)為 1個，度為 1的結(jié)點(diǎn)數(shù)為 2個，則度為 0的結(jié)點(diǎn)數(shù)為（ ）個 A． 4 B． 5 C． 6 D． 7 D B C 11．具有 10個葉結(jié)點(diǎn)的二叉樹中有（ ）個度為 2的結(jié)點(diǎn)， A． 8 B． 9 C． 10 D． ll 12．一棵完全二叉樹上有 1001個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是（ ） A． 250 B． 500 C． 254 D． 505 E．以上答案都不對 16. 有關(guān)二叉樹下列說法 正確 的是（ ） A．二叉樹的度為 2 B．一棵二叉樹的度可以小于 2 C．二叉樹中至少有一個結(jié)點(diǎn)的度為 2 D．二叉樹中任何一個結(jié)點(diǎn)的度都為 2 17．二叉樹的第 I層上最多含有結(jié)點(diǎn)數(shù)為（ ） A． 2I B． 2I11 C． 2 I1 D． 2I 1 B E B C 18. 一個具有 1025個結(jié)點(diǎn)的二叉樹的高 h為（ ） A． 11 B． 10 C． 11至 1025之間 D． 10至 1024之間 19．一棵二叉樹高度為 h,所有結(jié)點(diǎn)的度或為 0，或為 2，則這棵二叉樹最少有 ( )結(jié)點(diǎn) A． 2h B． 2h1 C． 2h+1 D． h+1 20．對于有 n 個結(jié)點(diǎn)的二叉樹 , 其高度為（ ） A． nlog2n B． log2n C． ?log2n?+1 D．不確定 21. 一棵具有 n個結(jié)點(diǎn)的完全二叉樹的樹高度 （ 深度 ） 是 （ ）A． ?log2n?+1 B． log2n+1 C． ?log2n? D． log2n1 22． 深度為 h的滿 m叉樹的第 k層有 （ ） 個結(jié)點(diǎn) 。 (1=k=h) A． mk1 B． mk1 C． mh1 D． mh1 C B D A A 23． 在一棵高度為 k的滿二叉樹中 ， 結(jié)點(diǎn)總數(shù)為 （ ） A． 2k1 B． 2k C． 2k1 D． ?log2k?+1 24．高度為 K的二叉樹最大的結(jié)點(diǎn)數(shù)為（ ）。 A． 2k B． 2k1 C． 2k 1 D． 2k11 25. 一棵樹高為 K的完全二叉樹至少有 （ ） 個結(jié)點(diǎn) A． 2k –1 B. 2k1 –1 C. 2k1 D. 2k 26. 將有關(guān)二叉樹的概念推廣到三叉樹 ， 則一棵有 244個結(jié)點(diǎn)的完全三叉樹的高度 （ ） A． 4 B． 5 C． 6 D． 7 C C C C 二 、 填空題 1．二叉樹由 _(1)__， __(2)_， _(3)__三個基本單元組成。 6．具有 256個結(jié)點(diǎn)的完全二叉樹的深度為 ______。 7． 已知一棵度為 3的樹有 2個度為 1的結(jié)點(diǎn) ， 3個度為 2的結(jié)點(diǎn) ， 4個度為 3的結(jié)點(diǎn) ， 則該樹有 ______個葉子結(jié)點(diǎn) 。 8． 深度為 k的完全二叉樹至少有 ___(1)____個結(jié)點(diǎn) ， 至多有___(2)____個結(jié)點(diǎn) 。 9．深度為 H 的完全二叉樹至少有 _(1)__個結(jié)點(diǎn)；至多有 _(2)__個結(jié)點(diǎn)； H和結(jié)點(diǎn)總數(shù) N之間的關(guān)系是 (3)__。 10．在順序存儲的二叉樹中，編號為 i和 j的兩個結(jié)點(diǎn)處在同一層的條件是 ______。 11．在完全二叉樹中，編號為 i和 j的兩個結(jié)點(diǎn)處于同一層的條件是 ______。 12． 一棵有 n個結(jié)點(diǎn)的滿二叉樹有 __(1)_個度為 1的結(jié)點(diǎn) 、 有 __(2)_個分支 （ 非 終端 ） 結(jié)點(diǎn)和 __(3)_個葉子 ， 該滿二叉樹的深度為_(4)__。 13． 假設(shè)根結(jié)點(diǎn)的層數(shù)為１ ， 具有ｎ個結(jié)點(diǎn)的二叉樹的最大高度是______。 14． 在一棵二叉樹中 ， 度為零的結(jié)點(diǎn)的個數(shù)為 N0,度為 2的結(jié)點(diǎn)的個數(shù)為 N2,則有 N0 =______ 15．設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為 0，則高度為 k的二叉樹的最大結(jié)點(diǎn)數(shù)為 ______,最小結(jié)點(diǎn)數(shù)為 ______。 17．高度為 K的完全二叉樹至少有 ______個葉子結(jié)點(diǎn)。 19．已知二叉樹有 50個葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少是 ______。 20．一個有 2021個結(jié)點(diǎn)的完全二叉樹的高度為 ______。 參考答案 1.(1)根結(jié)點(diǎn) (2)左子樹 (3)右子樹 ； 6. 9 7. 12 8.(1)2k1 (2)2k1 9.(1)2H1 (2)2H1 (3)H=?log2N?+1 10. 用順序存儲二叉樹時 ， 要按完全二叉樹的形式存儲 ， 非完全二叉樹存儲時 ， 要加 “ 虛結(jié)點(diǎn) ” 。 設(shè)編號為 i和 j的結(jié)點(diǎn)在順序存儲中的下標(biāo)為 s 和 t ,則結(jié)點(diǎn) i和 j在同一層上的條件是 ?log2s?=?log2t?。 11. ?log2i?=?log2j? 12.(1)0 (2)(n1)/2 (3)(n+1)/2 (4) ?log2n? +1 14. N2+1 15.(1) 2K+11 (2) k+1 17. 2k219. 99 20. 11
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1