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