資源簡介

一．選擇題（共30小題）
1．已知二叉樹T節點的前序遍歷序列為A﹣B﹣D﹣E﹣F﹣G﹣C，中序遍歷序列是D﹣B﹣F﹣E﹣G﹣A﹣C，則其后序遍歷序列是（　　）
A．F﹣D﹣G﹣E﹣B﹣C﹣A B．D﹣F﹣G﹣E﹣B﹣C﹣A
C．B﹣F﹣D﹣G﹣B﹣C﹣A D．C﹣G﹣F﹣E﹣D﹣B﹣A
2．數學表達式（7﹣5）*（1+2）可用二叉樹表示，如圖所示。則下列說法錯誤的是（　　）
A．該二叉樹是滿二叉樹
B．該二叉樹的高度為3
C．通過后序遍歷可求出該表達式的逆波蘭式為7512﹣+*
D．用列表方式存儲該二叉樹的具體結構為：浙考神墻750[’*’，[’﹣’，[7，None，None]，[5，None，None]]，[’+’，[1，None，None]，[2，None，None]]]
3．有二叉樹用數組表示為：[“A”，“B”，“C”，None，“D”，“E”，“F”，None，None，None，“G”]，則下列關于該二叉樹的說法 正確的是（　　）
A．該二叉樹度為1的節點有2個
B．該二叉樹一共有3層
C．該二叉樹中的葉子節點有4個
D．該二叉樹的中序遍歷序列是B﹣G﹣D﹣A﹣E﹣C﹣F
4．用一維數組表示二叉樹，如表所示：
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G
下列有關該二叉樹的說法正確的是（　　）
A．該樹中共有 4 個葉子節點
B．該樹是完全二叉樹，其深度為4
C．該樹的中序遍歷為 B﹣F﹣D﹣G﹣A﹣C﹣E
D．該二叉樹的結構圖為（如圖所示）
5．某二叉樹前序遍歷為ABDCE，后序遍歷為DBECA，則該二叉樹可能情況有多少種？（　　）
A．1 B．2 C．4 D．6
6．關于二叉樹，下列說法正確的是（　　）
A．二叉樹的度肯定為2
B．在含有n個節點的二叉樹中，邊數為n﹣1
C．二叉樹的前序遍歷序列與中序遍歷序列肯定不同
D．在二叉樹的前序序列中，若節點u在節點v之前，則u一定是v的祖先
7．有二叉樹的前序遍歷序列為A﹣B﹣C﹣E﹣F﹣G﹣D，中序遍歷序列為A﹣E﹣C﹣F﹣G﹣B﹣D，則關于該二叉樹的說法正確的是（　　）
A．該二叉樹根節點的度為1
B．該二叉樹的高度為4
C．該二叉樹中節點G是節點C的左孩子
D．該二叉樹中葉子節點的個數為4
8．對于如圖所示的一義樹，下列說法正確的是（　　）
A．樹的高度是4，是一棵完全二叉樹
B．度為2的節點數比葉子節點數多1
C．若采用數組存儲法，需要6個存儲空間
D．該二叉樹的后序遍歷序列是fdebca
9．下列二叉樹中，中序遍歷結果為BAEDFC的是（　　）
A． B．
C． D．
10．若一棵二叉樹的中序遍歷序列為BIGDHAECF，后序遍歷序列為IGHDBEFCA，則該二叉樹的前序遍歷序列為（　　）
A．ABCDEFGHI B．ABDGHICEF C．ABDHGICEF D．ABDG IHCEF
11．現有一顆二叉樹的前序遍歷為ABCDEF，中序遍歷為BCADFE，則該二叉樹的后序遍歷為（　　）
A．CBFEDA B．BCFEDA C．CBDFEA D．BCEFDA
12．某二叉樹的后序遍歷序列為F一？—？—C一A一D，中序遍歷序列為F一B一D一E一A一C，則其前序遍歷序列為（　　）
A．D一B一A一F一E—C B．D一B一F一A一E一C
C．D一E一F一A一B一C D．D一E一A一F一B一C
13．如果將數學表達式中的運算數和運算符視同為二叉樹的每個節點，那么我們可以構造出各種表達式二叉樹，如圖所示的是一棵表達式二叉樹。如果對該之叉樹進行中序遍歷，并加上括號后，就可以得到中綴表達式：（ 9﹣4/2）*5+3。如果對該二叉樹實行前序遍歷，則可以得到的表達式為（　　）
A．+*﹣9/4253 B．+*﹣/42953 C．942/﹣*53+ D．942/﹣5*3+
14．如圖所示，有如下二叉樹，關于此二叉樹的說法中，描述正確的是（　　）
A．該二叉樹的前序遍歷為ABDGJCEFHI
B．該樹中共有3個葉子節點
C．若有前序遍歷和后序遍歷可以推導出唯一的二叉樹
D．該樹的深度為4
15．一棵包含10個節點的完全二叉樹，其葉子節點的個數為（　　）
A．3 B．4 C．5 D．6
16．已知二叉樹中序遍歷序列是BEDAFHCIG，前序遍歷序列是ABDECFHGI，它的后序遍歷序列是（　　）
A．BDEFHCIGA B．IGHFEDCBA C．EDBFHIGCA D．EDBHFIGCA
17．已知二叉樹T2的后序遍歷序列為G﹣D﹣H﹣E﹣B﹣I﹣F﹣C﹣A，中序遍歷序列是D﹣G﹣B﹣E﹣H﹣A﹣C﹣I﹣F，則二叉樹T2的前序遍歷序列為（　　）
A．A﹣B﹣D﹣G﹣E﹣H﹣C﹣I﹣F
B．A﹣B﹣D﹣G﹣E﹣H﹣C﹣F﹣I
C．A﹣B﹣D﹣G﹣E﹣H﹣F﹣C﹣I
D．該二叉樹形態不唯一，無法確定
18．已知一棵完全二叉樹，其第 4 層有 3 個葉子節點，這棵二叉樹的節點數量不可能是（　　）
A．25 B．24 C．11 D．10
19．已知一棵二叉樹的前序遍歷序列為：A﹣B﹣D﹣C﹣E，后序遍歷序列為：D﹣B﹣E﹣C﹣A，則該二叉樹是否能唯一確定？中序遍歷序列是（　　）
A．能唯一確定，中序遍歷序列為：B﹣D﹣A﹣E﹣C
B．不能唯一確定，中序遍歷序列可能為：B﹣D﹣A﹣E﹣C
C．能唯一確定，中序遍歷序列為：D﹣C﹣B﹣A﹣E
D．不能唯一確定，中序遍歷序列可能為：D﹣C﹣B﹣A﹣E
20．如圖所示的二叉樹，其節點的中序遍歷的序列為（　　）
A．ABCDEFG B．GDBEACF C．GDEBFCA D．ABDGECF
21．如圖a 為一棵二叉樹，其數組實現示意圖（部分）如圖b 所示。
下列說法正確的是（　　）
A．該二叉樹的前序遍歷為 ABCDEFG
B．該二叉樹的高度為 3
C．該二叉樹是完全二叉樹
D．節點 G 存儲在數組下標為 11 的位置
22．有一棵二叉樹如圖所示，該二叉樹的后序遍歷結果正確的是（　　）
A．XBCDAYEF B．FEYADCBX C．DBEAFXCY D．DEFABYCX
23．設一棵二叉樹的中序遍歷序列：becfad，后序遍歷序列：efcbda，則二叉樹前序遍歷序列為（　　）
A．abcdef B．bdaefc C．abcefd D．abcfed
24．一棵具有124個葉子結點的完全二叉樹，最多有（　　）個結點。
A．247 B．248 C．249 D．250
25．用順序存儲的方法，將完全二叉樹中所有結點按層逐個從左到右的順序存放在一維數組R[1..N]中，若結點R[i]有右孩子，則其右孩子是（　　）
A．R[2i﹣1] B．R[2i+1] C．R[2i] D．R[2/i]
26．設一棵二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹先序遍歷序列為（　　）
A．adbce B．decab C．debac D．abcde
27．有一種元素除首元素沒有前驅元素、尾元素沒有后繼元素外，其它元素都只有一個前驅元素和一個后繼元素。具有以上特點的數據結構是（　　）
A．樹結構 B．選擇結構 C．線性結構 D．網狀結構
28．在樹形結構中，沒有的是（　　）？
A．根的父節點 B．父節點 C．根 D．子樹
29．VB語言中，下列各種基本數據類型說明符中表示整型數的是（　　）
A．Integer B．Boolean C．Single D．String
30．在VB中，要定義一個存儲整型數值的變量，其合適的數據類型是（　　）
A．Boolean B．String C．Date D．Integer
參考答案與試題解析
一．選擇題（共30小題）
1．【解答】解：二叉樹的先序遍歷中第一個為根節點，中序遍歷中根節點位置的左右分別為左右子樹，根據這個關系，我們可以還原出這個二叉樹的結構，然后寫出后序遍歷為D﹣F﹣G﹣E﹣B﹣C﹣A。
故選：B。
2．【解答】解：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，所以該二叉樹為滿二叉樹；二叉樹的高度是垂直方向上樹的長度的量度，所以該二叉樹的高度為3；通過后序遍歷可求出該表達式的逆波蘭式為75﹣12+*；用列表方式存儲該二叉樹的具體結構為：浙考神墻750[’*’，[’﹣’，[7，None，None]，[5，None，None]]，[’+’，[1，None，None]，[2，None，None]]]，所以選項C說法錯誤。
故選：C。
3．【解答】解：如果父節點的下標是i那么左子節點的下標i*2+1右子節點的下標的i*2+2，根據此規律可以畫出該二叉樹，得到該二叉樹度為1的節點有2個，該二叉樹一共有4層，該二叉樹中的葉子節點有3個，該二叉樹的中序遍歷序列是D﹣B﹣A﹣E﹣G﹣F﹣C，所以選項A符合題意。
故選：A。
4．【解答】解：觀察圖形可知，中序遍歷的規則是：左子樹﹣﹣﹣＞根結點﹣﹣﹣＞右子樹所以該樹的中序遍歷為 B﹣F﹣D﹣G﹣A﹣C﹣E，選項C說法正確。
故選：C。
5．【解答】解：根據該二叉樹的前序遍歷為ABDCE，后序遍歷為DBECA，可知根節點為A，畫圖可得二叉樹可能情況有4種。
故選：C。
6．【解答】解：二叉樹每個結點最多兩個孩子，即結點的度最大為2，但也可能所有結點的度都不為2，如只有1個結點，或單枝樹等，所以二叉樹的度并不一定是2；在含有n個節點的二叉樹中，邊數為n﹣1；二叉樹的前序遍歷序列與中序遍歷序列有可能相同。
故選：B。
7．【解答】解：根據前序和中序遍歷可知，該二叉樹的根節點為A，根節點沒有左子樹，只有右子樹，所以根節點的度為1，所以選項A說法正確。
故選：A。
8．【解答】解：二叉樹的高度是二叉樹結點層次的最大值，也就是其左右子樹的最大高度+1。樹的高度是4，是一棵不完全二叉樹；后序遍歷就是左子樹﹣﹣﹣＞右子樹﹣﹣﹣＞根結點，所以該二叉樹的后序遍歷序列是fdebca；所以選項D說法正確。
故選：D。
9．【解答】二叉樹的中序遍歷順序為左子樹﹣＞根﹣＞右子樹，題目中四個二叉樹遍歷的結果：A：EDFBAC，B：BEDFAC，C：BAEDFC，D：BACEDF。
故選：C。
10．【解答】后序遍歷為IGHDBEFCA可以得到根節點為A；中序遍歷可知左子樹為BIGDH，右子樹為ECF，依次類推可以得到該二叉樹的前序遍歷為ABDG IHCEF。
故選：D。
11．【解答】有先序遍歷可得根節點為A，有中序遍歷可知左半部分的遍歷為BC，結合先序遍歷可得后序遍歷為CB，在觀察左子樹中先序和中序得到其后序遍歷為EFD，所以該二叉樹的后序遍歷為CBEFDA。
故選：A。
12．【解答】題干提供了后序遍歷可以得到根節點，在通過中序遍歷得到FB為左子樹，ACE為右子樹，結合中序和后序遍歷可知，左子樹中B為根節點，右子樹中，A為根節點，E為左節點由此可以得到前序遍歷為D一B一F一A一E一C。
故選：B。
13．【解答】如圖所示，前序遍歷的順序為根節點，左節點然后是右節點，所以該二叉樹的前序遍歷為：+*﹣9/4253。
故選：A。
14．【解答】如圖所示該二叉樹的前序遍歷為ABDGJCEFHI；該樹中共有4個葉子節點；給定先序和中序 或者給定 后序加中序 可以唯一確定一顆二叉樹二叉樹；從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度，所以該二叉樹深度為5.
故選：A。
15．【解答】一棵包含10個節點的完全二叉樹，其葉子節點的個數為10/2＝5.故選：C。
16．【解答】根據二叉樹的前序與中序，可畫出二叉樹如下圖，再寫出后序遍歷序列是 EDBHFIGCA。
故選：D。
17．【解答】由后序遍歷可知根節點為A，由中序遍歷可知左子樹為D﹣G﹣B﹣E﹣H，右子樹為C﹣I﹣F。所以前序遍歷為A﹣B﹣D﹣G﹣E﹣H﹣C﹣F﹣I。
故選：B。
18．【解答】完全二叉樹除了最后一層，是一棵滿二叉樹，其節點數為2^k﹣1，k是層數，所以為2^3﹣1＝7，然后加上第四層最少3個葉子為7+3＝10，故最少給10個節點，由于是完成二叉樹，每增加一個根節點則下面增加兩個子節點，所以不可能是11個節點。
故選：C。
19．【解答】已知一棵二叉樹的前序遍歷序列為：A﹣B﹣D﹣C﹣E可以確定根節點為A，已知后序遍歷序列為：D﹣B﹣E﹣C﹣A可以確定左子樹的起點為B，無法確定左子樹到哪里結束，同樣無法確定右子樹的開始節點。所以無法確定唯一性，中序遍歷序列可能為：B﹣D﹣A﹣E﹣C故選項B符合題意。
故選：B。
20．【解答】中序遍歷（中根）是先遍歷左子樹，再訪問當前節點，最后是右子樹。按照這個規則遍歷序列是GDBEACF。故選B。
21．【解答】該二叉樹的前序遍歷為 ABDCEGF；該二叉樹的高度為 4；該二叉樹是不完全二叉樹；節點 G 存儲在數組下標為 11 的位置。
故選：D。
22．【解答】根據后序遍歷的定義及方法可以該二叉樹后序遍歷為：DEFABYCX。故選：D。
23．【解答】根據后序可以確定根為a，那么結合中序遍歷的順序becf為左子樹，d為右子樹。那么可以確定前序遍歷順序根左右為abcefd故選：C。
24．【解答】一顆124個葉子結點的完全二叉樹，最多有248個結點。當完全二叉樹的最右非終結結點子樹個數為一時，非葉節點數目＝葉節點；當完全二叉樹的最右非終結結點子樹個數為二時，非葉節點數目＝葉節點+1。最右非終結結點子樹個數為一時，非葉結點數等于124+124＝248。二叉樹結點總數等于124+124＝248＝248。
故選：B。
25．【解答】根據完全二叉樹的性質，如果2i+1＞n，則結點i無右孩子，否則其右孩子rchild （i） 是結點2i+1。故選：B。
26．【解答】后序遍歷知道a是根結點，中序遍歷左根右知道b是左子樹。故選：D。
27．【解答】解析：有一種元素除首元素沒有前驅元素、尾元素沒有后繼元素外，其它元素都只有一個前驅元素和一個后繼元素。具有以上特點的數據結構是線性結構，故選：C。
28．【解答】解析：在樹形結構中，沒有的是根的父節點，故選：A。
29．【解答】Integer表示整型數；Boolean是布爾型；Single是單精度的浮點型；string是字符串類型。故選：A。
30．【解答】題干要求定義一個用來存儲整型數值的變量，應選擇Integer類型。
故選：D

展開更多......

收起↑