資源簡介

(共23張PPT)
第四章　樹
驗收卷(三)　樹
(考試時間40分鐘　滿分50分)
一、選擇題(本題共14小題，每小題2分，共28分)
1.樹中所有節(jié)點的度等于(　　)
C
解析　本題主要考查的是節(jié)點的度。樹中節(jié)點的度是指該節(jié)點的后繼節(jié)點數(shù)，兩個節(jié)點間有一條邊，即節(jié)點的度是從該節(jié)點出發(fā)的邊數(shù)。因此，所有節(jié)點的度等于所有節(jié)點數(shù)減1，故答案為C。
A.所有節(jié)點數(shù) B.所有節(jié)點數(shù)加1
C.所有節(jié)點數(shù)減1 D.所有節(jié)點數(shù)加2
C
2.一棵高度為6的滿二叉樹中的節(jié)點數(shù)為(　　)
解析　本題主要考查的是滿二叉樹的特點。一棵高度為6的滿二叉樹中的節(jié)點數(shù)為26－1個，即63個，因此，答案為C。
A.31個 B.32個 C.63個 D.64個
B
3.某樹的結(jié)構(gòu)如下，下列說法正確的是(　　)
解析　本題考查樹的性質(zhì)。A選項數(shù)的度取決于節(jié)點的最大度數(shù)，因此該樹的度為3。
A.該樹的度為4
B.該樹的高度為4
C.該樹的葉子節(jié)點為3個
D.節(jié)點F和G是兄弟節(jié)點
A
4.一棵有n(n>0)個節(jié)點的二叉樹，其節(jié)點為0度或2度，則此樹的最大高度是(　　)
解析　本題考查二叉樹基本性質(zhì)。該二叉樹的節(jié)點的度都為0或2，即除根節(jié)點外，其每個節(jié)點都有一個兄弟節(jié)點。題目要求樹的最大高度，每層就只有2個節(jié)點(除了根節(jié)點)，若總節(jié)點數(shù)加上1，相當(dāng)于令第1層也變成兩個節(jié)點，那么總層數(shù)就是(n＋1)∥2。
A.(n＋1)∥2 B.n∥2 C.(n－1)∥2 D.int(log2n＋1)
C
5.已知一棵完全二叉樹有8個葉子節(jié)點，下列說法正確的是(　　)
解析　本題考查樹的性質(zhì)。根據(jù)樹的性質(zhì)，2度節(jié)點個數(shù)為葉子節(jié)點個數(shù)減1，因此2度節(jié)點有7個。由于是完全二叉樹，1度節(jié)點的個數(shù)為0或1，因此總共節(jié)點數(shù)為15或16個。A選項根據(jù)總共節(jié)點數(shù)，可知該樹可能是3層，也可以是4層。B選項當(dāng)總節(jié)點是3層時，是一棵滿二叉樹，當(dāng)節(jié)點為16時，在4層下有一個節(jié)點。C選項當(dāng)總節(jié)點為16時，有一個1度節(jié)點。D選項2度節(jié)點個數(shù)為7個。
A.該完全二叉樹的高度可能為3
B.該完全二叉樹的形態(tài)只有一種
C.該完全二叉樹可能有1個度為1的節(jié)點
D.該完全二叉樹有9個度為2的節(jié)點
C
6.如圖所示，將二叉樹A的根節(jié)點與二叉樹B的根節(jié)點連接，使得二叉樹A成為二叉樹B的左子樹，合并為一棵新的二叉樹C。下列說法中正確的是 (　　)
解析　本題考查二叉樹的性質(zhì)和遍歷。新二叉樹高度為4；葉子節(jié)點數(shù)量為4，是一棵完全二叉樹；中序遍歷的結(jié)果為84251637，不是一個有序序列。
A.二叉樹C的高度為3
B.二叉樹C的葉子節(jié)點數(shù)量為3
C.二叉樹C是一棵完全二叉樹
D.二叉樹C中序遍歷的結(jié)果是一個有序序列
D
A.二叉樹的數(shù)據(jù)元素之間呈非線性關(guān)系
B.二叉樹的第 k 層上最多有2k－1(k≥1)個節(jié)點
C.由前序遍歷和中序遍歷序列能唯一確定一棵二叉樹
D.具有 100 個節(jié)點的完全二叉樹有 50 個度為 2 的節(jié)點
解析　本題考查樹的性質(zhì)。A選項樹表現(xiàn)一種層次性的非線性關(guān)系。D選項設(shè)二叉樹0度、1度和2度的節(jié)點個數(shù)分別為t0，t1，t2，有等式t0＋t1＋t2＝100和t0＝t2＋1成立，代入可得t2＋1＋t1＋t2＝100，且完全二叉樹1度節(jié)點個數(shù)為0或1，因此t2值為49。
A
8.某二叉樹如圖所示，該二叉樹的中序遍歷序列是(　　)
解析　中序遍歷的每棵子樹均為左根右。
A.BIGDHAECF B.IGHDBEFCA
C.ABDGIHCEF D.BDGHIACEF
C
9.對于如圖所示的二叉樹，下列說法正確的是 (　　)
解析　本題考查二叉樹相關(guān)知識。A選項葉子節(jié)點有7，9，15，共3個。B選項完全二叉樹要求葉子節(jié)點從右開始，且最多只出現(xiàn)在最下面 2 層。C 正確，前序遍歷時 2－5－7－8－9－10－13－15，是一個遞增序列。D選項用數(shù)組表示是[2，5，10，7，8，None，13，None，None，9，None，None，None，None，15].
A.葉子節(jié)點有 4 個
B.是完全二叉樹，樹的高度為 4
C.前序遍歷的結(jié)果是一個遞增序列
D.可以使用數(shù)組[2，5，10，7，8，13，9，15]存儲
B
10.某二叉樹的樹形結(jié)構(gòu)如圖所示，其后序遍歷結(jié)果為“物技化數(shù)英語”，則中序遍歷結(jié)果為(　　)
解析　本題考查二叉樹遍歷。后序遍歷是“物技化數(shù)英語”可知，根節(jié)點為語，數(shù)英分別是語節(jié)點的左右孩子。物為數(shù)的左孩子，技為最高層的左孩子，化為數(shù)的右孩子。
A.語數(shù)英物化技 B.物數(shù)技化語英
C.語數(shù)物化技英 D.化物技英數(shù)語
B
11.已知一棵二叉樹如圖所示，下列說法正確的是(　　)
解析　A選項B和E也是葉子節(jié)點。B選項F是D的左子樹，在中序、后序遍歷中，F(xiàn)先于D，D和E分別是C的左右子樹，D肯定先于E。
A.樹的高度是 4，節(jié)點F 是唯一的葉子節(jié)點
B.中序、后序的遍歷方式，節(jié)點 F 先于節(jié)點 D、E 訪問
C.前序遍歷的結(jié)果為A－B－C－D－E－F
D.使用數(shù)組可以表示為[‘A’，‘B’，‘C’，‘ ’，‘ ’，‘D’， ‘E’，‘F’]
D
A.該表達式樹是一棵二叉樹，樹的度是2，高度是5
B.該樹的葉子節(jié)點數(shù)比度為2的節(jié)點數(shù)多1個
C.若采用完全二叉樹數(shù)組從 0 號位開始存儲，則節(jié)點b存儲在6號位
D.該表達式樹的前序遍歷序列是×d＋/fc－ab
解析　本題考查樹與二叉樹相關(guān)知識。樹的度是最大的節(jié)點的度，樹的高度是節(jié)點最大的層數(shù)，A選項在任意一棵二叉樹中都有n0＝n2＋1的性質(zhì)，即葉子節(jié)點數(shù)等于度為2的節(jié)點數(shù)多一個；非完全二叉樹若用完全二叉樹保存時需將樹補成完全二叉樹，即第3層需補全d節(jié)點的兩個孩子節(jié)點，此時節(jié)點b存儲在第6號位置上。D選項該表達式樹的前序遍歷序列是×d＋/f－cab，對節(jié)點“－”而言先于其子節(jié)點c。
C
13.二叉樹的中序遍歷為 BAEDFC，后序遍歷為 BEFDCA，其前序遍歷為(　　)
解析　本題考查二叉樹的相關(guān)知識。后序遍歷確定根節(jié)點，中序遍歷區(qū)分左右子樹。根據(jù)二叉樹的中序遍歷和后序遍歷可知，該二叉樹的形狀如圖所示，前序遍歷為：ABCDEF。
A.ABDEFC B.ABDCEF C.ABCDEF D.ABCDFE
B
14.已知一棵二叉樹的前序遍歷序列為ABCDEFG，則該二叉樹中序遍歷序列可能為(　　)
A.CABDEFG B.ABCDEFG C.DACEFBG D.ADBCFEG
解析　本題考查二叉樹的相關(guān)知識。前序遍歷找出根A，中序遍歷根據(jù)根的位置，區(qū)別左右子樹。A選項左子樹為C，但C在前序遍歷中后于B訪問，不正確。C選項同A選項。D選項該樹沒有左子樹，在右子樹中，B為根，D為B的左孩子，但在前序中D后于C訪問，不正確。B選項前序遍歷為根左右，中序遍歷為左根右，當(dāng)樹缺失左孩子時，前中序遍歷是一樣的。
二、非選擇題(本題共4小題，共22分)
答案　12　2011　(評分規(guī)則：寫對一個得4分)
解析　總共有2011個葉子節(jié)點，所以第n層的葉子節(jié)點可能是1到2n－1，n＝12，這是完全二叉樹的情況；如果二叉樹的每層只有一個右子樹，則到2011層共有2011個葉節(jié)點，因此答案為12或2011。
15.(6分)如果根節(jié)點的深度記為1，有一棵恰有2011個葉子節(jié)點的二叉樹，則該二叉樹的深度可能是____________或________。
16.(3分)設(shè)有一棵k叉樹，其中只有度為0和k兩種節(jié)點，設(shè)n0、nk分別表示度為0和度為k的節(jié)點個數(shù)，求出n0 和nk之間的關(guān)系(形式如n0＝數(shù)學(xué)表達式，數(shù)學(xué)表達式僅含nk 、k和數(shù)字)。關(guān)系式為________________________。
答案　n0和nk之間的關(guān)系為：n0＝(k－1) nk＋1
解析　設(shè)k叉樹中共有x個節(jié)點，則有n0＋nk＝x，度為k的節(jié)點，表示每個節(jié)點均有k個子節(jié)點，即有k*nk條邊，k叉樹的總邊數(shù)為x－1條，即k*nk＝x－1，因此可得到n0＋nk＝k*nk＋1，求得n0＝(k－1) nk＋1。
17.(7分)3個節(jié)點數(shù)的不同形態(tài)的二叉樹一共有__________種；5個節(jié)點數(shù)的不同形態(tài)的二叉樹一共有________種。
答案　5　42
解析　本題主要考查的是二叉樹的形態(tài)。本題可以分三種情況討論：只有左子樹、左右子樹均存在、只有右子樹，也可以直接用catalan數(shù)的公式來計算，h(n)＝(2n)！/(n！*(n＋1)！)。3個節(jié)點數(shù)的不同形態(tài)的二叉樹比較簡單，可直接畫樹來求，共有5種，而5個節(jié)點數(shù)的不同形態(tài)的二叉樹比較多，可用catalan數(shù)的公式來計算，共有42種。
18.(6分)二叉查找樹。所謂的二叉查找樹是指每一個樹根的值大于左子樹的值，但小于右子樹的值，左右子樹也是二叉查找樹，樹的每一個節(jié)點的值都不相同。
已知節(jié)點信息順序存儲在數(shù)組中，編寫程序創(chuàng)建一棵二叉查找樹，并輸出該二叉樹的數(shù)組表示。程序運行效果如圖所示。
原始數(shù)組為：
[11，6，8，15，12，16，9，7]
二叉樹內(nèi)容：
[11][6][15][None][8][12][16][None][None][7][9]
實現(xiàn)上述功能的程序如下，請回答下列問題。
def Bt_build (btree，data，length)：
global x
x＝0
for i in range(length)：
level＝0
while btree[level]！＝None：
　　　　 if data[i]>btree[level]：
　　　　　　 ①________________
　　　　else：
　　　　　　level＝level*2＋1
②________________
if x　　　x＝level
data＝[11，6，8，15，12，16，9，7]
length＝len(data)
btree＝[None]*100
print('原始數(shù)組為：')
print(data)
print(' ')
③________________
print('二叉樹內(nèi)容：')
for i in range(x＋1)：
print('[{}]'.format(btree[i])，end＝' ')
print()
(1)若data列表中元素依次為“15，10，8，18，20，9，11”，則輸出的二叉樹內(nèi)容為______________。
(2)請在程序劃線處填入合適的代碼。
劃線①處應(yīng)填入的代碼：
______________；
劃線②處應(yīng)填入的代碼：
______________；
劃線③處應(yīng)填入的代碼：
______________。
答案　(1)[15] [10] [18] [8] [11] [None] [20] [None] [9]　(2)①level＝level*2＋2?、赽tree[level]＝data[i]　③Bt_build (btree，data，length)
解析　(1)本題主要考查的是二叉樹的數(shù)組表示。首先構(gòu)建好查找二叉樹，然后將該二叉樹補全為完全二叉樹，最后用數(shù)組來表示。表示方法為由第1層開始，依次到下一層，在每一層中按照從左到右的順序創(chuàng)建節(jié)點，補充的節(jié)點用None表示。(2)左子樹的索引值是父節(jié)點的索引值×2＋1，右子樹的索引值是父節(jié)點的索引值×2＋2，if 中的條件為data[i]>btree[level]，可知data[i]為btree[level]節(jié)點的右孩子節(jié)點，因此右孩子的位置為①level＝level*2＋2；確定好子節(jié)點的索引位置level后，將數(shù)據(jù)元素data[i]存儲在btree[level]中，因此，劃線②處代碼為btree[level]＝data[i]；劃線③處代碼的功能是調(diào)用Bt_build函數(shù)，三個參數(shù)分別為btree(存儲查找二叉樹節(jié)點的數(shù)組)、data(生成二叉樹的各節(jié)點列表)、length(節(jié)點個數(shù))，因此，③處代碼為Bt_build (btree，data，length)。驗收卷(三)　樹
(考試時間40分鐘　滿分50分)
一、選擇題(本題共14小題，每小題2分，共28分)
1.樹中所有節(jié)點的度等于(　　)
A.所有節(jié)點數(shù) B.所有節(jié)點數(shù)加1
C.所有節(jié)點數(shù)減1 D.所有節(jié)點數(shù)加2
2.一棵高度為6的滿二叉樹中的節(jié)點數(shù)為(　　)
A.31個 B.32個 C.63個 D.64個
3.某樹的結(jié)構(gòu)如下，下列說法正確的是(　　)
A.該樹的度為4
B.該樹的高度為4
C.該樹的葉子節(jié)點為3個
D.節(jié)點F和G是兄弟節(jié)點
4.一棵有n(n>0)個節(jié)點的二叉樹，其節(jié)點為0度或2度，則此樹的最大高度是(　　)
A.(n＋1)∥2 B.n∥2 C.(n－1)∥2 D.int(log2n＋1)
5.已知一棵完全二叉樹有8個葉子節(jié)點，下列說法正確的是(　　)
A.該完全二叉樹的高度可能為3
B.該完全二叉樹的形態(tài)只有一種
C.該完全二叉樹可能有1個度為1的節(jié)點
D.該完全二叉樹有9個度為2的節(jié)點
6.如圖所示，將二叉樹A的根節(jié)點與二叉樹B的根節(jié)點連接，使得二叉樹A成為二叉樹B的左子樹，合并為一棵新的二叉樹C。下列說法中正確的是 (　　)
A.二叉樹C的高度為3
B.二叉樹C的葉子節(jié)點數(shù)量為3
C.二叉樹C是一棵完全二叉樹
D.二叉樹C中序遍歷的結(jié)果是一個有序序列
7.下列關(guān)于二叉樹的說法，不正確的是 (　　)
A.二叉樹的數(shù)據(jù)元素之間呈非線性關(guān)系
B.二叉樹的第 k 層上最多有2k－1(k≥1)個節(jié)點
C.由前序遍歷和中序遍歷序列能唯一確定一棵二叉樹
D.具有 100 個節(jié)點的完全二叉樹有 50 個度為 2 的節(jié)點
8.某二叉樹如圖所示，該二叉樹的中序遍歷序列是(　　)
A.BIGDHAECF B.IGHDBEFCA
C.ABDGIHCEF D.BDGHIACEF
9.對于如圖所示的二叉樹，下列說法正確的是 (　　)
A.葉子節(jié)點有 4 個
B.是完全二叉樹，樹的高度為 4
C.前序遍歷的結(jié)果是一個遞增序列
D.可以使用數(shù)組[2，5，10，7，8，13，9，15]存儲
10.某二叉樹的樹形結(jié)構(gòu)如圖所示，其后序遍歷結(jié)果為“物技化數(shù)英語”，則中序遍歷結(jié)果為(　　)
A.語數(shù)英物化技 B.物數(shù)技化語英
C.語數(shù)物化技英 D.化物技英數(shù)語
11.已知一棵二叉樹如圖所示，下列說法正確的是(　　)
A.樹的高度是 4，節(jié)點F 是唯一的葉子節(jié)點
B.中序、后序的遍歷方式，節(jié)點 F 先于節(jié)點 D、E 訪問
C.前序遍歷的結(jié)果為A－B－C－D－E－F
D.使用數(shù)組可以表示為[‘A’，‘B’，‘C’，‘ ’，‘ ’，‘D’， ‘E’，‘F’]
12.某表達式樹如下圖所示，下列說法錯誤的是(　　)
A.該表達式樹是一棵二叉樹，樹的度是2，高度是5
B.該樹的葉子節(jié)點數(shù)比度為2的節(jié)點數(shù)多1個
C.若采用完全二叉樹數(shù)組從 0 號位開始存儲，則節(jié)點b存儲在6號位
D.該表達式樹的前序遍歷序列是×d＋/fc－ab
13.二叉樹的中序遍歷為 BAEDFC，后序遍歷為 BEFDCA，其前序遍歷為(　　)
A.ABDEFC B.ABDCEF C.ABCDEF D.ABCDFE
14.已知一棵二叉樹的前序遍歷序列為ABCDEFG，則該二叉樹中序遍歷序列可能為(　　)
A.CABDEFG B.ABCDEFG C.DACEFBG D.ADBCFEG
二、非選擇題(本題共4小題，共22分)
15.(6分)如果根節(jié)點的深度記為1，有一棵恰有2011個葉子節(jié)點的二叉樹，則該二叉樹的深度可能是____________或________。
16.(3分)設(shè)有一棵k叉樹，其中只有度為0和k兩種節(jié)點，設(shè)n0、nk分別表示度為0和度為k的節(jié)點個數(shù)，求出n0 和nk之間的關(guān)系(形式如n0＝數(shù)學(xué)表達式，數(shù)學(xué)表達式僅含nk 、k和數(shù)字)。關(guān)系式為________________________。
17.(7分)3個節(jié)點數(shù)的不同形態(tài)的二叉樹一共有__________種；5個節(jié)點數(shù)的不同形態(tài)的二叉樹一共有________種。
18.(6分)二叉查找樹。所謂的二叉查找樹是指每一個樹根的值大于左子樹的值，但小于右子樹的值，左右子樹也是二叉查找樹，樹的每一個節(jié)點的值都不相同。
已知節(jié)點信息順序存儲在數(shù)組中，編寫程序創(chuàng)建一棵二叉查找樹，并輸出該二叉樹的數(shù)組表示。程序運行效果如圖所示。
原始數(shù)組為： [11，6，8，15，12，16，9，7] 二叉樹內(nèi)容： [11][6][15][None][8][12][16][None][None][7][9]
實現(xiàn)上述功能的程序如下，請回答下列問題。
def Bt_build (btree，data，length)：
global x
x＝0
for i in range(length)：
level＝0
while btree[level]！＝None：
　　　　 if data[i]>btree[level]：
　　　　　　 ①________________
　　　　else：
　　　　　　level＝level*2＋1
②________________
if x　　　x＝level
data＝[11，6，8，15，12，16，9，7]
length＝len(data)
btree＝[None]*100
print('原始數(shù)組為：')
print(data)
print(' ')
③________________
print('二叉樹內(nèi)容：')
for i in range(x＋1)：
print('[{}]'.format(btree[i])，end＝' ')
print()
(1)若data列表中元素依次為“15，10，8，18，20，9，11”，則輸出的二叉樹內(nèi)容為______________。
(2)請在程序劃線處填入合適的代碼。
劃線①處應(yīng)填入的代碼：
______________；
劃線②處應(yīng)填入的代碼：
______________；
劃線③處應(yīng)填入的代碼：
______________。
驗收卷(三)　樹
1.C　[本題主要考查的是節(jié)點的度。樹中節(jié)點的度是指該節(jié)點的后繼節(jié)點數(shù)，兩個節(jié)點間有一條邊，即節(jié)點的度是從該節(jié)點出發(fā)的邊數(shù)。因此，所有節(jié)點的度等于所有節(jié)點數(shù)減1，故答案為C。]
2.C　[本題主要考查的是滿二叉樹的特點。一棵高度為6的滿二叉樹中的節(jié)點數(shù)為26－1個，即63個，因此，答案為C。]
3.B　[本題考查樹的性質(zhì)。A選項數(shù)的度取決于節(jié)點的最大度數(shù)，因此該樹的度為3。]
4.A　[本題考查二叉樹基本性質(zhì)。該二叉樹的節(jié)點的度都為0或2，即除根節(jié)點外，其每個節(jié)點都有一個兄弟節(jié)點。題目要求樹的最大高度，每層就只有2個節(jié)點(除了根節(jié)點)，若總節(jié)點數(shù)加上1，相當(dāng)于令第1層也變成兩個節(jié)點，那么總層數(shù)就是(n＋1)∥2。]
5.C　[本題考查樹的性質(zhì)。根據(jù)樹的性質(zhì)，2度節(jié)點個數(shù)為葉子節(jié)點個數(shù)減1，因此2度節(jié)點有7個。由于是完全二叉樹，1度節(jié)點的個數(shù)為0或1，因此總共節(jié)點數(shù)為15或16個。A選項根據(jù)總共節(jié)點數(shù)，可知該樹可能是3層，也可以是4層。B選項當(dāng)總節(jié)點是3層時，是一棵滿二叉樹，當(dāng)節(jié)點為16時，在4層下有一個節(jié)點。C選項當(dāng)總節(jié)點為16時，有一個1度節(jié)點。D選項2度節(jié)點個數(shù)為7個。]
6.C　[本題考查二叉樹的性質(zhì)和遍歷。新二叉樹高度為4；葉子節(jié)點數(shù)量為4，是一棵完全二叉樹；中序遍歷的結(jié)果為84251637，不是一個有序序列。]
7. D　[本題考查樹的性質(zhì)。A選項樹表現(xiàn)一種層次性的非線性關(guān)系。D選項設(shè)二叉樹0度、1度和2度的節(jié)點個數(shù)分別為t0，t1，t2，有等式t0＋t1＋t2＝100和t0＝t2＋1成立，代入可得t2＋1＋t1＋t2＝100，且完全二叉樹1度節(jié)點個數(shù)為0或1，因此t2值為49。 ]
8.A　[中序遍歷的每棵子樹均為左根右。]
9.C　[本題考查二叉樹相關(guān)知識。A選項葉子節(jié)點有7，9，15，共3個。B選項完全二叉樹要求葉子節(jié)點從右開始，且最多只出現(xiàn)在最下面 2 層。C 正確，前序遍歷時 2－5－7－8－9－10－13－15，是一個遞增序列。D選項用數(shù)組表示是[2，5，10，7，8，None，13，None，None，9，None，None，None，None，15].]
10.B　[本題考查二叉樹遍歷。后序遍歷是“物技化數(shù)英語”可知，根節(jié)點為語，數(shù)英分別是語節(jié)點的左右孩子。物為數(shù)的左孩子，技為最高層的左孩子，化為數(shù)的右孩子。]
11.B　[A選項B和E也是葉子節(jié)點。B選項F是D的左子樹，在中序、后序遍歷中，F(xiàn)先于D，D和E分別是C的左右子樹，D肯定先于E。]
12.D　[本題考查樹與二叉樹相關(guān)知識。樹的度是最大的節(jié)點的度，樹的高度是節(jié)點最大的層數(shù)，A選項在任意一棵二叉樹中都有n0＝n2＋1的性質(zhì)，即葉子節(jié)點數(shù)等于度為2的節(jié)點數(shù)多一個；非完全二叉樹若用完全二叉樹保存時需將樹補成完全二叉樹，即第3層需補全d節(jié)點的兩個孩子節(jié)點，此時節(jié)點b存儲在第6號位置上。D選項該表達式樹的前序遍歷序列是×d＋/f－cab，對節(jié)點“－”而言先于其子節(jié)點c。]
13.C　[本題考查二叉樹的相關(guān)知識。后序遍歷確定根節(jié)點，中序遍歷區(qū)分左右子樹。根據(jù)二叉樹的中序遍歷和后序遍歷可知，該二叉樹的形狀如圖所示，前序遍歷為：ABCDEF。]
14.B　[本題考查二叉樹的相關(guān)知識。前序遍歷找出根A，中序遍歷根據(jù)根的位置，區(qū)別左右子樹。A選項左子樹為C，但C在前序遍歷中后于B訪問，不正確。C選項同A選項。D選項該樹沒有左子樹，在右子樹中，B為根，D為B的左孩子，但在前序中D后于C訪問，不正確。B選項前序遍歷為根左右，中序遍歷為左根右，當(dāng)樹缺失左孩子時，前中序遍歷是一樣的。]
15.12　2011　(評分規(guī)則：寫對一個得4分)
解析　總共有2011個葉子節(jié)點，所以第n層的葉子節(jié)點可能是1到2n－1，n＝12，這是完全二叉樹的情況；如果二叉樹的每層只有一個右子樹，則到2011層共有2011個葉節(jié)點，因此答案為12或2011。
16.n0和nk之間的關(guān)系為：n0＝(k－1) nk＋1
解析　設(shè)k叉樹中共有x個節(jié)點，則有n0＋nk＝x，度為k的節(jié)點，表示每個節(jié)點均有k個子節(jié)點，即有k*nk條邊，k叉樹的總邊數(shù)為x－1條，即k*nk＝x－1，因此可得到n0＋nk＝k*nk＋1，求得n0＝(k－1) nk＋1。
17.5　42
解析　本題主要考查的是二叉樹的形態(tài)。本題可以分三種情況討論：只有左子樹、左右子樹均存在、只有右子樹，也可以直接用catalan數(shù)的公式來計算，h(n)＝(2n)！/(n！*(n＋1)！)。3個節(jié)點數(shù)的不同形態(tài)的二叉樹比較簡單，可直接畫樹來求，共有5種，而5個節(jié)點數(shù)的不同形態(tài)的二叉樹比較多，可用catalan數(shù)的公式來計算，共有42種。
18.(1)[15] [10] [18] [8] [11] [None] [20] [None] [9]
(2)①level＝level*2＋2　②btree[level]＝data[i]
③Bt_build (btree，data，length)
解析　(1)本題主要考查的是二叉樹的數(shù)組表示。首先構(gòu)建好查找二叉樹，然后將該二叉樹補全為完全二叉樹，最后用數(shù)組來表示。表示方法為由第1層開始，依次到下一層，在每一層中按照從左到右的順序創(chuàng)建節(jié)點，補充的節(jié)點用None表示。(2)左子樹的索引值是父節(jié)點的索引值×2＋1，右子樹的索引值是父節(jié)點的索引值×2＋2，if 中的條件為data[i]>btree[level]，可知data[i]為btree[level]節(jié)點的右孩子節(jié)點，因此右孩子的位置為①level＝level*2＋2；確定好子節(jié)點的索引位置level后，將數(shù)據(jù)元素data[i]存儲在btree[level]中，因此，劃線②處代碼為btree[level]＝data[i]；劃線③處代碼的功能是調(diào)用Bt_build函數(shù)，三個參數(shù)分別為btree(存儲查找二叉樹節(jié)點的數(shù)組)、data(生成二叉樹的各節(jié)點列表)、length(節(jié)點個數(shù))，因此，③處代碼為Bt_build (btree，data，length)。

展開更多......

收起↑