15[填空題]對右圖二叉樹進(jìn)行中序遍歷的結(jié)果為( )。
參考解析：ACBDFEHGP
【分析】中序遍歷的原則是先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。因此本題中遍歷結(jié)果是ACBDFEHGP。
16[填空題]在深度為7的滿二叉樹中，度為2的結(jié)點(diǎn)個數(shù)為( )。
參考解析：63
【分析】滿二叉樹的定義是除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)(即每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值)。第l層(根結(jié)點(diǎn)在第l層)擁有的結(jié)點(diǎn)數(shù)是20=1，第2層擁有的結(jié)點(diǎn)數(shù)是21=2，第3層擁有的結(jié)點(diǎn)數(shù)是22=4，……，第n層擁有的結(jié)點(diǎn)數(shù)是2n-1。在深度為7的滿二叉樹中，葉子結(jié)點(diǎn)全部在第7層，其余結(jié)點(diǎn)都是2度結(jié)點(diǎn)。在滿二叉樹中，第7層擁有的結(jié)點(diǎn)數(shù)是27-1=64。二叉樹具有這樣一個性質(zhì)：在任意一棵二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個。所以度為2的結(jié)點(diǎn)個數(shù)為64—1=63。
17[單選題]對右下圖二叉樹進(jìn)行后序遍歷的結(jié)果為( )。
參考答案：D
參考解析：后序遍歷的方法是：若二叉樹為空，則結(jié)束返回。否則先后序遍歷左子樹，再后序遍歷右子樹，最后訪問根結(jié)點(diǎn)。本題后序遍歷左子樹的結(jié)果是DEB，后續(xù)遍歷右子樹的結(jié)果是FC，最后根是A，所以后續(xù)遍歷的結(jié)果是DEBFCA。因此本題的正確答案是D。
18[單選題]在深度為7的滿二叉樹中，葉子結(jié)點(diǎn)的個數(shù)為( )。
參考答案：C
參考解析：在滿二叉樹中每層的結(jié)點(diǎn)數(shù)都達(dá)到最大值， 而且葉子結(jié)點(diǎn)全部出現(xiàn)在最底層。第l層(根結(jié)點(diǎn)所在的層)有20個結(jié)點(diǎn)，第2層有21個結(jié)點(diǎn)，……第n層有2n-1個結(jié)點(diǎn)。在深度為7的滿二叉樹中，第7層有2 7-l=64個結(jié)點(diǎn)(全部是葉子結(jié)點(diǎn))、在深度為7的滿二叉樹中，共有27—1=127個結(jié)點(diǎn)、因此本題的正確答案是C
19[填空題]在深度為7的滿二又樹中，度為2的結(jié)點(diǎn)個數(shù)為________。
參考解析：63
【分析】滿二叉樹的定義是除最后-層外，每-層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)(即每-層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值)。第l層(根結(jié)點(diǎn)在第l層)擁有的結(jié)點(diǎn)數(shù)是20=1，第2層擁有的結(jié)點(diǎn)數(shù)是21=2，第3層擁有的結(jié)點(diǎn)數(shù)是22=4，……，第n層擁有的結(jié)點(diǎn)數(shù)是2n-1。在深度為7的滿二叉樹中，葉子結(jié)點(diǎn)全部在第7層，其余結(jié)點(diǎn)都是2度結(jié)點(diǎn)。在滿二叉樹中，第7層擁有的結(jié)點(diǎn)數(shù)是27-1=64。二叉樹具有這樣一個性質(zhì)：在任意一棵二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個。所以度為2的結(jié)點(diǎn)個數(shù)為64—1=63。
20[單選題]一棵二叉樹中共有70個葉子結(jié)點(diǎn)與80個度為1的結(jié)點(diǎn)，該二叉樹中的總結(jié)點(diǎn)數(shù)為( )
A.219B.221C.229D.231
參考答案：A
參考解析：二叉樹具有這樣一個性質(zhì)：在任意-顆二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個。本題告知，葉子結(jié)點(diǎn)有70個，那度為2的結(jié)點(diǎn)就有69個，度為l的結(jié)點(diǎn)有80個，這顆二叉樹共有70+69+80=219個結(jié)點(diǎn)。因此本題的正確答案是A。
21[單選題]對右圖二叉樹進(jìn)行前序遍歷的結(jié)果為( )
A.DYBEAFCZX
B.YDEBFZXCA
C.ABDYECFXZ
D.ABCDEFXYZ
參考答案：C
參考解析：前序遍歷(DLR)的基本思想是：先訪問根結(jié)點(diǎn)，后前序遍歷dzq-樹，再前序遍歷右子樹。本題根結(jié)點(diǎn)是A，前序遍歷左子樹得到的序列為BDYE，前序遍歷右子樹得到的序列為CFXZ，所以對本題二叉樹進(jìn)行前序遍歷的結(jié)果為ABDYECFXZ。因此本題的正確答案是C。
22[單選題]一棵度數(shù)為4的樹，它的4度結(jié)點(diǎn)有l(wèi)個，3度結(jié)點(diǎn)有2個，2度結(jié)點(diǎn)有3個，l度結(jié)點(diǎn)4個，問它的葉子結(jié)點(diǎn)有多少個?( )。
參考答案：D
參考解析：
23[填空題]設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEACF，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為________。
參考解析：
DEBFCA【分析】我們可以根據(jù)前序遍歷的結(jié)果ABDECF，確定第l個元素A是根結(jié)點(diǎn)，再看中序遍歷的結(jié)果DBEACF，A前面的DBE應(yīng)該在左子樹，A后面的FC應(yīng)該在右子樹。根據(jù)前序遍歷的結(jié)果和中序遍歷的結(jié)果，我們可以推導(dǎo)出：A是根結(jié)點(diǎn)，B是A的左結(jié)點(diǎn)，D是B的左結(jié)點(diǎn)，E是B的右結(jié)點(diǎn).C是A的右結(jié)點(diǎn)，F(xiàn)是C的右結(jié)點(diǎn)，畫出的二叉樹如圖1.17所示。對圖進(jìn)行后序遍歷的結(jié)果為DEBFCA。
總結(jié)：先根據(jù)前序遍歷或后序遍歷的結(jié)果，確定根結(jié)點(diǎn)，根據(jù)根結(jié)點(diǎn)確定左右予樹上的結(jié)點(diǎn)，再根據(jù)兩種遍歷畫出對應(yīng)的二叉樹，最后遍歷二叉樹得到第三種遍歷結(jié)果。
24[填空題]樹是-種簡單的________(線性月)線性)結(jié)構(gòu)，在樹中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的________特性。
參考解析：非線性
25[填空題]一棵二叉樹第六層(根結(jié)點(diǎn)為第-層)的結(jié)點(diǎn)數(shù)最多為________個。
參考解析：
32【分析】根據(jù)二叉樹的性質(zhì)，我們可以得出一棵二又樹第n層(根結(jié)點(diǎn)為第-層)的結(jié)點(diǎn)數(shù)最多為2n-1個，因此第6層的結(jié)點(diǎn)數(shù)最多為25=32個，總結(jié)：二叉樹第1層只有一個根結(jié)點(diǎn)(20)，第2層最多只有兩個結(jié)點(diǎn)(21)，第3層最多只有4個結(jié)點(diǎn)(22)，……，第n層最多為有2n-1個結(jié)點(diǎn)(不是2n個)�？忌�需要了解一棵深度(高度)為n的二叉樹最多擁有的結(jié)點(diǎn)總數(shù)是2n-1(20+21+22+…+2n-1=2n-l).這種類型的試題不要死記硬背，有時是2n-1，有時是2n-l，所以考生最好采用我們介紹的方法來推導(dǎo)。
26[單選題]在表示樹的多重鏈表中，除了要存儲結(jié)點(diǎn)的值和多個指針之外，還必須需要存儲( )。
參考答案：A
27[單選題]具有8個結(jié)點(diǎn)的完全二：叉樹中編號為4的結(jié)點(diǎn)的右子結(jié)點(diǎn)的編號為( )。
參考答案：C
28[填空題]擁有奇數(shù)個結(jié)點(diǎn)的完全二叉樹中有4個內(nèi)部結(jié)點(diǎn)(非葉子結(jié)點(diǎn))，請問它的葉子結(jié)點(diǎn)數(shù)是________。
參考解析：5
【分析】由于完全二叉樹是自上而下、自左而右的從l開始連續(xù)編碼的，因此完全二又樹要么不存在-度結(jié)點(diǎn)(當(dāng)結(jié)點(diǎn)個數(shù)為奇數(shù)個時)，要么存在一個-度結(jié)點(diǎn)，而且唯-的一個-度結(jié)點(diǎn)就是最后編號為n(n為偶數(shù))的葉子結(jié)點(diǎn)的父結(jié)點(diǎn)。而在二叉樹中零度結(jié)點(diǎn)個數(shù)總比二度結(jié)點(diǎn)個數(shù)多l(xiāng)，因此擁有4個二度結(jié)點(diǎn)的二叉樹的葉子結(jié)點(diǎn)的個數(shù)是4+1=5。
總結(jié)，設(shè)n為完全二叉樹的結(jié)點(diǎn)數(shù)，n0為葉子結(jié)點(diǎn)數(shù)，nl為度為1的結(jié)點(diǎn)數(shù)，n2為度2的結(jié)點(diǎn)數(shù)，則n=n0+nl+n2,n0=n2+1。若n為奇數(shù)，則nI=0;若n為偶數(shù)，則nl=l(注意-定要是完全二又樹)。
29[填空題]一棵二又樹第六層(根結(jié)點(diǎn)為第一層)的結(jié)點(diǎn)數(shù)最多為( )個。
參考解析：32
30[填空題]某--y.樹中度為2的結(jié)點(diǎn)有l(wèi)8個，則該--y.樹中有( )個葉子結(jié)點(diǎn)。
參考解析：19
【分析】在任意一棵二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個。
31[填空題]擁有奇數(shù)個結(jié)點(diǎn)的完全二叉樹中有4個內(nèi)部結(jié)點(diǎn)(非葉子結(jié)點(diǎn))，請問它的葉子結(jié)點(diǎn)數(shù)是( )。
參考解析：5
32[填空題]設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEACF，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為( )。
參考解析：DEBFCA
圖1.17
33[填空題]樹是一種簡單的( )(線性月}線性)結(jié)構(gòu)，在樹中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的( )特性。
參考解析：非線性、層次
[填空題]設(shè)一棵完全二叉樹共有700個結(jié)點(diǎn)，則在該二叉樹中有( )個葉子結(jié)點(diǎn)。
參考解析：350
相關(guān)推薦：
2015計算機(jī)二級公共基礎(chǔ)知識考前沖刺練試題匯總
| 北京 | 天津 | 上海 | 江蘇 | 山東 |
| 安徽 | 浙江 | 江西 | 福建 | 深圳 |
| 廣東 | 河北 | 湖南 | 廣西 | 河南 |
| 海南 | 湖北 | 四川 | 重慶 | 云南 |
| 貴州 | 西藏 | 新疆 | 陜西 | 山西 |
| 寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
| 黑龍江 | 內(nèi)蒙古 |
