|
一、下面是有關(guān)二叉樹的敘述，請判斷正誤（每小題1分，共10分） （ √ ）1. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點的二叉樹鏈表中只有n—1個非空指針域。 （ × ）2.二叉樹中每個結(jié)點的兩棵子樹的高度差等于1。 （ √ ）3.二叉樹中每個結(jié)點的兩棵子樹是有序的。 （ × ）4.二叉樹中每個結(jié)點有兩棵非空子樹或有兩棵空子樹。 （ ×）5.二叉樹中每個結(jié)點的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值。（應(yīng)當是二叉排序樹的特點） （ × ）6.二叉樹中所有結(jié)點個數(shù)是2k-1-1，其中k是樹的深度。（應(yīng)2i-1） （ × ）7.二叉樹中所有結(jié)點，如果不存在非空左子樹，則不存在非空右子樹。 （ × ）8.對于一棵非空二叉樹，它的根結(jié)點作為第一層，則它的第i層上最多能有2i—1個結(jié)點。（應(yīng)2i-1） （ √ ）9.用二叉鏈表法（link-rlink）存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個為空指針。 （正確。用二叉鏈表存儲包含n個結(jié)點的二叉樹，結(jié)點共有2n個鏈域。由于二叉樹中，除根結(jié)點外，每一個結(jié)點有且僅有一個雙親，所以只有n-1個結(jié)點的鏈域存放指向非空子女結(jié)點的指針，還有n+1個空指針。）即有后繼鏈接的指針僅n-1個。 （ √ ）10. 〖01年計算機系研題〗具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。 最快方法：用葉子數(shù)＝[n/2]＝6，再求n2=n0-1=5 二、填空（每空1分，共15分） 1． 由３個結(jié)點所構(gòu)成的二叉樹有 5 種形態(tài)。 2. 【計算機研2000】 一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n0-1=31 個分支結(jié)點和 26-1 =32個葉子。 注：滿二叉樹沒有度為1的結(jié)點，所以分支結(jié)點數(shù)就是二度結(jié)點數(shù)。 3． 一棵具有２５７個結(jié)點的完全二叉樹，它的深度為 9 。 （ 注：用? log2(n) ?+1= |
|
|
