資源簡(jiǎn)介

(
.
) (
.
)
樹(shù)與二叉樹(shù)
一 、選擇題(每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求
的，不選、多選、錯(cuò)選均不得分)
1.一棵度為3,深度為4的樹(shù)，最多含有的節(jié)點(diǎn)個(gè)數(shù)是
A.31 B.32
C.40 D.42
2. 下列關(guān)于樹(shù)的說(shuō)法，不正確的是
A.樹(shù)形結(jié)構(gòu)的特點(diǎn)是一個(gè)節(jié)點(diǎn)可以有多個(gè)直接前驅(qū)
B.樹(shù)形結(jié)構(gòu)可以表達(dá)(組織)比線性結(jié)構(gòu)更復(fù)雜的數(shù)據(jù)
C.樹(shù)(及一切樹(shù)形結(jié)構(gòu))是一種分支層次結(jié)構(gòu)
D.只含一個(gè)節(jié)點(diǎn)的集合也是一棵樹(shù)
3. 某二叉樹(shù)如圖所示。
則使用數(shù)組表示該二叉樹(shù)的結(jié)果是
( )
( )
( )
4.現(xiàn)有一棵二叉樹(shù)的中序遍歷序列為b-e-c-f-a-d,后序遍歷序列為
c-f-c-b-d-a,則該二叉樹(shù)的前序遍歷序列是 ( )
A.a-b-c-d-e-f
B.b-d-a-e-f-c
C.a-b-c-e-f-d
D.a-b-c-f-e-d
5.現(xiàn)有一棵二叉樹(shù)的中序遍歷序列為B-A-C-D-F-E, 后序遍歷序列為
A-B-F-E-D-C, 則該二叉樹(shù)的前序遍歷序列是 ( )
A.C-B-A-F-E-D
(
D.C-B-A-D-E-F
)
B.C-B-A-D-F-E
C.C-B-A-E-F-D
6. 現(xiàn)有一棵二叉樹(shù)的前序遍歷序列為a-b-c-d-e-f-g-h-i-j-k,中序遍歷 序列為c-d-b-e-f-a-g-h-i-j-k,則該二叉樹(shù)的后序遍歷序列是( )
A.d-f-c-e-b-k-j-i-h-g-a
B.c-d-f-e-b-k-j-i-g-h-a
C.d-c-e-f-b-j-k-i-h-g-a
D.d-c-f-e-b-k-j-i-h-g-a
7. 下列關(guān)于二叉樹(shù)節(jié)點(diǎn)的說(shuō)法，不正確的是 ( ) A.具有12個(gè)節(jié)點(diǎn)的完全二叉樹(shù)有5個(gè)度為2的節(jié)點(diǎn)
B. 由3個(gè)節(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有6種形態(tài)
C.一棵深度為6的滿二叉樹(shù)有32個(gè)葉子節(jié)點(diǎn)
D.一棵具有257個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，它的深度為9
8. 某公司的內(nèi)部管理的組織關(guān)系如圖所示。通過(guò)觀察可知，該組織
(
形式是一種樹(shù)形結(jié)構(gòu)，下列說(shuō)法正確的是
總經(jīng)理
人事部
門(mén)店
2
門(mén)店
3
A.
該樹(shù)中共有
8
個(gè)葉子節(jié)點(diǎn)
售后部
零售部
運(yùn)維部
項(xiàng)目部
技術(shù)部
財(cái)務(wù)部
業(yè)務(wù)部
采購(gòu)部
(
)
門(mén)店
1
)
B.該樹(shù)的度為4,高度為4
C.“售后部”節(jié)點(diǎn)的父節(jié)點(diǎn)是“業(yè)務(wù)部”節(jié)點(diǎn)
D.“項(xiàng)目部”節(jié)點(diǎn)是“零售部”節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
9 .如果一棵二叉樹(shù)的中序遍歷序列是B-A-C,那么它的前序遍歷序列
不可能是 ( )
A.A-B-C B.C-B-A
C.A-C-B D.B-A-C
10. 將含100個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，按照從上層到下層，同層從左到右 的順序依次給它們編以從0開(kāi)始的連續(xù)自然數(shù)，則編號(hào)為40的節(jié) 點(diǎn)x的父節(jié)點(diǎn)的編號(hào)是 ( )
A.19 B.20
C.21 D.39
11.某二叉樹(shù)如圖所示。用list表示該二叉樹(shù)是 ( )
A.[5,2,1,3,4]
B.[5,[2,[1,None,None],None],[3,[4]]]
C.[5,[2,[1]],[3,[4,None,None]]]
D.[5,[2,[1,None,None]],[3,[4,None,None],None],None]
12. 已知某二叉樹(shù)如圖所示，則其對(duì)應(yīng)的一維數(shù)組(None 表示為空數(shù) 據(jù))表示為 ( )
A.bt-["A","B","C","D","E"]
B.bt=["A","B","C",None,"D",None,None,None,"E"]
C.bt=["A","B","C",None,"D",None,None,None,None,"E"]
D.bt=["A","B","C",None,"D",None,None,None,None,None,"E"]
13. 如圖所示， 一個(gè)數(shù)學(xué)表達(dá)式可以用一棵表達(dá)式樹(shù)來(lái)表示。下列關(guān)
于該表達(dá)式樹(shù)的描述，不正確的是 ( )
A.該表達(dá)式樹(shù)不是完全二叉樹(shù)
B.若表達(dá)式樹(shù)中只有四則運(yùn)算，則對(duì)應(yīng)的表達(dá)式樹(shù)的每個(gè)節(jié)點(diǎn)都
有兩個(gè)孩子節(jié)點(diǎn)
C.表達(dá)式樹(shù)的根節(jié)點(diǎn)左右子樹(shù)的深度差不會(huì)超過(guò)1
D.該表達(dá)式樹(shù)對(duì)應(yīng)的表達(dá)式為“(3+4)*6-8+4/(3*2)”
14. 已知某二叉樹(shù)可用嵌套列表表示為bt=["A",["B",["D",None,
None],["E",None,Nonel],["C",None,["F",None,Nonell],下列說(shuō)法正
確的是 ( )
A.該二叉樹(shù)的前序遍歷序列為A-B-C-D-E-F
B.該二叉樹(shù)的中序遍歷序列為D-B-E-A-C-F
C.該二叉樹(shù)的后序遍歷序列為B-F-C-D-E-A
D.該二叉樹(shù)的層序遍歷序列為A-B-D-E-C-F
15. 使用鏈表構(gòu)建如圖所示的二叉樹(shù)。
構(gòu)建此二叉樹(shù)的Python程序如下：
class Node:#創(chuàng)建Node類(lèi)
def ini (self,value=None,left=None,right=None):
self.value=value
Self. . left=left #左子樹(shù)
Self .right=right #右子樹(shù)
if name ==" main ":
root=
則劃線處應(yīng)填入的代碼是 ( )
A.Node("A",Node("B",Node("D"),Node("E"),Node("C"))
B.Node("A",Node("B",Node("D"),Node("E"),"C"))
C.Node("A",Node("B",Node("C"),Node("D"),Node("E")
D.Node("A",Node("B",Node("D"),Node("E"),Node("C"))
16. 某Python程序如下：
bt=["A","B","C","D","E",None,"F"]
result=[]
stack=[0]
while stack:
i=stack.pop()
result.append(bt[i]))
c=2*i+1
if cstack.append(c)
if c+1stack.append(c+1)
print("-".join(result[::- 1])
程序運(yùn)行后，輸出的結(jié)果為 ( )
A.A-B-C-D-E-F
B.D-B-E-F-C-A
C.D-E-B-F-C-A
D.A-B-D-E-C-F
二、非選擇題
17. 已知一棵二叉樹(shù)的中序遍歷序列是D-B-G-E-A-F-H-C, 后序遍歷 序列是D-G-E-B-H-F-C-A, 請(qǐng)畫(huà)出這棵二叉樹(shù)，并給出其前序遍
歷序列。
18. 已知一批數(shù)據(jù)如下：48,17,65,19,67,18,73,72,43,85。依據(jù)這 10個(gè)數(shù)據(jù)按照“小左大右”的二叉排序樹(shù)構(gòu)建規(guī)則，構(gòu)建一棵二叉 排序樹(shù)。請(qǐng)回答下列問(wèn)題：
(1)畫(huà)出該二叉樹(shù)。
(2)在該二叉排序樹(shù)上搜索某個(gè)值的自定義函數(shù)search(root,x)如
下，請(qǐng)?jiān)趧澗€處填入合適的代碼。
def search(root.x):
if root is None:
return "找不到!"
elif x==root.data:
return"找到!"
elif xprint("左",end="")
else:
print("右",end="")
return search(root.right,x)
19. 下列Python程序的功能是使用列表data 建立二叉樹(shù)，并輸出該二
叉樹(shù)的節(jié)點(diǎn)。請(qǐng)?jiān)趧澗€處填入合適的代碼。
def create tree(tree,data):
for i in range( ① ):
depth=0
if i==0:
②
else:
while tree[depth]!=0:
if data[i]>tree[depth]:
③
else:
depth=depth*2+1
tree[depth]=data[i]
btree=[0]*20
data=[20,30,15,18,7,25,22,13,35,12]
create tree(btree,data)
print("生成的二叉樹(shù)數(shù)組為：")
for iin range(len(btree)):
print(btree[i],end="")
參考答案
C 2 .A 3.C 4.C 5.D 6.D 7.B 8.C 9.C 10.A
11.D 12.C 13.C 14.B 15.A 16.C
前序遍歷序列是 A-B-D-E-G-C-F-H
(1)
return search(root.left,x)
len(data) ② tree[depth]=data[i]
③ depth=depth*2+2

展開(kāi)更多......

收起↑