數(shù)據(jù)結(jié)構(gòu) 第六章 考試題目

1、1一選擇1一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）A250B500C254D505E以上答案都不對以上答案都不對2.有關(guān)二叉樹下列說法正確的是（）A二叉樹的度為2B一棵二叉樹的度可以小于2C二叉樹中至少有一個結(jié)點的度為2D二叉樹中任何一個結(jié)點的度都為23二叉樹的第I層上最多含有結(jié)點數(shù)為（）A2IB2I11C2I1D2I14.一棵樹高為K的完全二叉樹至少有（）個結(jié)點A2k1B.2k11C.2k1D.2k5對二叉樹的結(jié)點從

2、1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用()次序的遍歷實現(xiàn)編號。A先序B.中序C.后序后序D.從根開始按層次遍歷6在下列存儲形式中，哪一個不是樹的存儲形式？（）A雙親表示法B孩子鏈表表示法C孩子兄弟表示法D順序存儲表示法順序存儲表示法7已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF中序遍歷結(jié)果為CBAEDF則后序遍歷的結(jié)果為（）。ACBEFDABFEDCBA

3、CCBEDFAD不定8.某二叉樹中序序列為ABCDEFG，后序序列為BDCAFGE則前序序列是：AEGFACDBBEACBDGFCEAGCFBDD上面的都不對9二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是：A、EB、FC、GD、H二判斷1.二叉樹是度為2的有序樹。2.完全二叉樹一定存在度為1的結(jié)點。3.對于有N個結(jié)點的二叉樹，其高度為log2n。4.二叉樹的遍歷結(jié)果不是唯一

4、的.√31___最小結(jié)點數(shù)為__k1____。9已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少是__99____。10一個有2001個結(jié)點的完全二叉樹的高度為__11____。11一個深度為k的，具有最少結(jié)點數(shù)的完全二叉樹按層次，（同層次從左到右）用自然數(shù)依此對結(jié)點編號，則編號最小的葉子的序號是__2k21_12如某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)為__69____。13對于一個具有n個結(jié)點的

5、二元樹，當(dāng)它為一棵_完全二叉樹完全二叉樹_二元樹時具有最小高度，當(dāng)它為一棵_單支樹單支樹_時，具有最大高度。14具有N個結(jié)點的二叉樹，采用二叉鏈表存儲，共有__n1____個空鏈域。158層完全二叉樹至少有__128____個結(jié)點，擁有100個結(jié)點的完全二叉樹的最大層數(shù)為___7___。16n（n大于1）個結(jié)點的各棵樹中，其深度最小的那棵樹的深度是_2__。它共有_n1__個葉子結(jié)點和_1__個非葉子結(jié)點，其中深度最大的那棵樹的深度是_

6、n__，它共有_1__個葉子結(jié)點和_n1__個非葉子結(jié)點。17已知一棵二叉樹的前序序列為abdecfhg中序序列為dbeahfcg，則該二叉樹的根為_a_，左子樹中有_dbe__，右子樹中有_hfcg_。18已知二叉樹前序為ABDEGCF，中序為DBGEACF，則后序一定是_DGEBFCA_。四應(yīng)用題1.有一份電文中共使用五個字符：a、b、c、d、e它們的出現(xiàn)頻率依次為8、14、10、4、18，請構(gòu)造相應(yīng)的哈夫曼樹，求出每個字符的哈夫曼