資源簡介

2023-2024學年高二上學期浙教版(2019)選修一4.1樹與二叉樹
一、選擇題
1．某二叉樹使用一維數組存儲結構進行存儲
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F
則該二叉樹的中序遍歷結果為（ ）
A．BAEDFC B．ECFDAB C．BFDEAC D．EDFCBA
2．已知一棵二叉樹如圖所示，下列說法正確的是（ ）
A．樹的高度是4，節點F是唯一的葉子節點
B．中序、后序的遍歷方式，節點F先于節點D、E訪問
C．前序遍歷的結果為A—B—C—D—E—F
D．使用數組可以表示為［’A’，’B’，’C’，’，’’，’D’，’E'，’F’]
3．一棵包含10個節點的完全二叉樹，其葉子節點的個數為（　　）
A．3 B．4 C．5 D．6
4．已知一棵二叉樹的中序遍歷序列為9–4+2*3/1+4，后序遍歷序列為94–23*+14+/，以下說法正確的是（ ）
A．這棵樹葉子結點比非葉子結點數多1 B．這是一棵滿二叉樹
C．其前序遍歷序列為/+-94*231+4 D．這棵樹有5層
5．某完全二叉樹，中序遍歷結果為“甲乙丙丁”，則后序遍歷結果是（ ）
A．甲乙丁丙 B．丙乙甲丁 C．甲丁丙乙 D．乙丁丙甲
6．已知某二叉樹的前序遍歷序列為ABCDEF，中序遍歷序列為BCAEFD，則該二叉樹的后序遍歷序列為（ ）
A．CBFEDA B．BCDEFA C．CBEFDA D．BCFEDA
7．有一棵二叉樹，如圖所示,下列說法正確的是（ ）
A．此二叉樹是完全二叉樹
B．此二叉樹的深度是3
C．此二叉樹的中序遍歷為H-D-B-E-A-C-F
D．此二叉樹用一維數組表示為['A','B',' ','C','D','E',' ','F',' ','H']
8．諸葛亮家族的部分家譜如圖所示。和家譜圖結構相似的數據結構是（ ）
A．樹 B．棧 C．隊列 D．鏈表
9．下列二叉樹中，中序遍歷結果為BAEDFC的是（ ）
A． B． C． D．
10．某二叉樹對應的一維數組表示如下圖所示：
下列關于該二叉樹的說法正確的是（ ）
A．這是一棵完全二叉樹 B．節點F是節點D的孩子節點
C．該二叉樹有1個葉子結點 D．該二叉樹中序遍歷的結果是DBEACF
11．某二叉樹前序遍歷的結果為“ABCDEF”，后序遍歷的結果為“BEFDCA”，則中序遍歷的結果可能是（ ）
A．CBDAEF B．CBAEDF C．BAEDFC D．BADCEF
12．樹的葉子節點個數與度為2的節點數的關系是（ ）
A．相等 B．多1 C．少1 D．無直接關系
13．一棵有n(n>0）個結點的二叉樹，其結點為0度或2度，則此樹的最大高度是（ ）
A．（n+1）//2 B．n//2 C．（n-1）//2 D． log2n+1
14．有二叉樹的前序遍歷序列為A-B-C-E-F-G-D，中序遍歷序列為A-E-C-F-G-B-D，則關于該二叉樹的說法正確的是（ ）
A．該二叉樹根節點的度為1 B．該二叉樹的高度為4
C．該二叉樹中節點G是節點C的左孩子 D．該二叉樹中葉子節點的個數為4
15．有如圖所示的樹。下列說法正確的是（ ）
A．該樹中共有3個葉子節點 B．該樹的度和深度均為3
C．該樹中度為2的子節點有1個，度為1的子節點有2個 D．節點e是節點f的兄弟節點
二、填空題
16．二叉樹是一種每個節點最多有 個子節點的樹結構。
17．由a，b，c3個不同的數字組成一個N位數，要求不出現兩個a相鄰，也不出現兩個b相鄰，這樣的N位數的個數為AN，用AN-1和AN-2表示AN的關系式為:AN= 。
18．設樹T有17條邊，12片樹葉，4個4度內部節點，1個3度內部節點。則T的樹根的度數為 。
三、操作題
19．什么是二叉樹？請簡述其特點。
四、簡答題
20．描述什么是二叉樹，并解釋二叉搜索樹的特點。
21．解釋什么是二叉樹的遍歷，并簡述其常見的遍歷方法。
參考答案：
1．A
2．B
3．C
4．A
5．A
6．A
7．C
8．A
9．C
10．D
11．C
12．B
13．A
14．A
15．C
16．兩
17．AN=2AN-1+AN-2（N>=2），且A0=1，A1=3
18．3
19．二叉樹是一種特殊的樹形數據結構，其中每個節點最多有兩個子節點，通常稱為左子節點和右子節點。其特點是每個節點都有序，左子節點的值小于或等于父節點的值，右子節點的值大于或等于父節點的值。
20．二叉樹是一種特殊的樹形數據結構，其中每個節點最多有兩個子節點，通常被稱為左子節點和右子節點。二叉搜索樹是一種特殊的二叉樹，其中每個節點的值都大于或等于其左子樹中所有節點的值，并且小于或等于其右子樹中所有節點的值。
21．二叉樹的遍歷是指按照某種順序訪問樹中的所有節點。常見的遍歷方法包括前序遍歷（Pre-order）、中序遍歷（In-order）、后序遍歷（Post-order）和層序遍歷（Level-order）。

展開更多......

收起↑