資源簡(jiǎn)介 (.) (.)樹(shù)與二叉樹(shù)一 、選擇題(每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的,不選、多選、錯(cuò)選均不得分)1.一棵度為3,深度為4的樹(shù),最多含有的節(jié)點(diǎn)個(gè)數(shù)是A.31 B.32C.40 D.422. 下列關(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-fB.b-d-a-e-f-cC.a-b-c-e-f-dD.a-b-c-f-e-d5.現(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-EC.C-B-A-E-F-D6. 現(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-aB.c-d-f-e-b-k-j-i-g-h-aC.d-c-e-f-b-j-k-i-h-g-aD.d-c-f-e-b-k-j-i-h-g-a7. 下列關(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ù),它的深度為98. 某公司的內(nèi)部管理的組織關(guān)系如圖所示。通過(guò)觀察可知,該組織(形式是一種樹(shù)形結(jié)構(gòu),下列說(shuō)法正確的是總經(jīng)理人事部門(mén)店2門(mén)店3A.該樹(shù)中共有8個(gè)葉子節(jié)點(diǎn)售后部零售部運(yùn)維部項(xiàng)目部技術(shù)部財(cái)務(wù)部業(yè)務(wù)部采購(gòu)部()門(mén)店1)B.該樹(shù)的度為4,高度為4C.“售后部”節(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-AC.A-C-B D.B-A-C10. 將含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.20C.21 D.3911.某二叉樹(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ò)1D.該表達(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-FB.該二叉樹(shù)的中序遍歷序列為D-B-E-A-C-FC.該二叉樹(shù)的后序遍歷序列為B-F-C-D-E-AD.該二叉樹(shù)的層序遍歷序列為A-B-D-E-C-F15. 使用鏈表構(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=valueSelf. . 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+1if cstack.append(c)if c+1stack.append(c+1)print("-".join(result[::- 1])程序運(yùn)行后,輸出的結(jié)果為 ( )A.A-B-C-D-E-FB.D-B-E-F-C-AC.D-E-B-F-C-AD.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=0if i==0:②else:while tree[depth]!=0:if data[i]>tree[depth]:③else:depth=depth*2+1tree[depth]=data[i]btree=[0]*20data=[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.A11.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)更多...... 收起↑ 資源預(yù)覽 縮略圖、資源來(lái)源于二一教育資源庫(kù)