第六章考研習(xí)題

本文格式為Word版，下載可任意編輯——第六章考研習(xí)題1．高度為K的二叉樹最大的結(jié)點(diǎn)數(shù)為（）。

kk-1kk-1

A．2B．2C．2-1D．2-12.利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是（）。

A．指向最左孩子B．指向最右孩子C．空D．非空3．若二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹的位置，利用()遍歷方法最適合。

A．前序B．中序C．后序D．按層次4、高度為h的滿二叉樹對(duì)應(yīng)的森林由（）棵樹構(gòu)成。

h

A．1B．log2C．h/2D．h

5某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E則前序序列是：(),二叉樹對(duì)應(yīng)的森林包括多少棵樹（）。

6一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）A．所有的結(jié)點(diǎn)均無左孩子B．所有的結(jié)點(diǎn)均無右孩子C．只有一個(gè)葉子結(jié)點(diǎn)D．是任意一棵二叉樹

7在二叉樹結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（）

A．都不一致B．完全一致C．先序和中序一致，而與后序不同D．中序和后序一致，而與先序不同

8某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A．空或只有一個(gè)結(jié)點(diǎn)B．任一結(jié)點(diǎn)無左子樹C．高度等于其結(jié)點(diǎn)數(shù)D．任一結(jié)點(diǎn)無右子樹9在完全二叉樹中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒（）。

A．左子結(jié)點(diǎn)B．右子結(jié)點(diǎn)C．左子結(jié)點(diǎn)和右子結(jié)點(diǎn)D．左子結(jié)點(diǎn)，右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)

10在以下狀況中，可稱為二叉樹的是（）

A．每個(gè)結(jié)點(diǎn)至多有兩棵子樹的樹B.哈夫曼樹C．每個(gè)結(jié)點(diǎn)至多有兩棵子樹的有序樹

D.每個(gè)結(jié)點(diǎn)只有一棵右子樹E．以上答案都不對(duì)

11設(shè)F是一個(gè)森林，B是由F變換得的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（）個(gè)。

A．n-1B．nC．n+1D．n+212由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的有向樹？（）

A．2B．3C．4D．513由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（）A．2B．3C．4D．514下述編碼中哪一個(gè)不是前綴碼（）。

A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）應(yīng)用題：

1．從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。

2已知完全二叉樹的第七層有10個(gè)葉子結(jié)點(diǎn)，則整個(gè)二叉樹的結(jié)點(diǎn)數(shù)最多是多少？

3已知一棵滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)為20到40之間的素?cái)?shù)，此二叉樹的葉子結(jié)點(diǎn)有多少個(gè)？

4．一棵共有n個(gè)結(jié)點(diǎn)的樹，其中所有分支結(jié)點(diǎn)的度均為K，求該樹中葉子結(jié)點(diǎn)的個(gè)數(shù)。

5、設(shè)T是一棵二叉樹，除葉子結(jié)點(diǎn)外，其它結(jié)點(diǎn)的度數(shù)皆為2，若T中有6個(gè)葉結(jié)點(diǎn)，試問：

（1）T樹的最大深度Kmax=?最小可能深度Kmin=?（2）T樹中共有多少非葉結(jié)點(diǎn)？

6．試寫出復(fù)制一棵二叉樹的算法。二叉樹采用標(biāo)準(zhǔn)鏈接結(jié)構(gòu)。

7、已知一棵二叉樹的中序序列和后序序列，寫一個(gè)建立該二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)的算法。

8．給定一組項(xiàng)及其權(quán)值，假定項(xiàng)都存放于二叉樹的樹葉結(jié)點(diǎn)，則具有最小帶權(quán)外部路徑長(zhǎng)度的樹稱為huffman樹。（1）給出構(gòu)造huffman樹的算法。

（2）給定項(xiàng)及相應(yīng)的權(quán)如下表：畫出執(zhí)行上述算法后得到的huffman樹。（3）用c語言編寫構(gòu)造huffman樹的程序.

序