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

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

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

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

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

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

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