资源简介

(
.
) (
.
)
树与二叉树
一 、选择题(每小题列出的四个备选项中只有一个是符合题目要求
的，不选、多选、错选均不得分)
1.一棵度为3,深度为4的树，最多含有的节点个数是
A.31 B.32
C.40 D.42
2. 下列关于树的说法，不正确的是
A.树形结构的特点是一个节点可以有多个直接前驱
B.树形结构可以表达(组织)比线性结构更复杂的数据
C.树(及一切树形结构)是一种分支层次结构
D.只含一个节点的集合也是一棵树
3. 某二叉树如图所示。
则使用数组表示该二叉树的结果是
( )
( )
( )
4.现有一棵二叉树的中序遍历序列为b-e-c-f-a-d,后序遍历序列为
c-f-c-b-d-a,则该二叉树的前序遍历序列是 ( )
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.现有一棵二叉树的中序遍历序列为B-A-C-D-F-E, 后序遍历序列为
A-B-F-E-D-C, 则该二叉树的前序遍历序列是 ( )
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. 现有一棵二叉树的前序遍历序列为a-b-c-d-e-f-g-h-i-j-k,中序遍历 序列为c-d-b-e-f-a-g-h-i-j-k,则该二叉树的后序遍历序列是( )
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. 下列关于二叉树节点的说法，不正确的是 ( ) A.具有12个节点的完全二叉树有5个度为2的节点
B. 由3个节点所构成的二叉树有6种形态
C.一棵深度为6的满二叉树有32个叶子节点
D.一棵具有257个节点的完全二叉树，它的深度为9
8. 某公司的内部管理的组织关系如图所示。通过观察可知，该组织
(
形式是一种树形结构，下列说法正确的是
总经理
人事部
门店
2
门店
3
A.
该树中共有
8
个叶子节点
售后部
零售部
运维部
项目部
技术部
财务部
业务部
采购部
(
)
门店
1
)
B.该树的度为4,高度为4
C.“售后部”节点的父节点是“业务部”节点
D.“项目部”节点是“零售部”节点的兄弟节点
9 .如果一棵二叉树的中序遍历序列是B-A-C,那么它的前序遍历序列
不可能是 ( )
A.A-B-C B.C-B-A
C.A-C-B D.B-A-C
10. 将含100个节点的完全二叉树，按照从上层到下层，同层从左到右 的顺序依次给它们编以从0开始的连续自然数，则编号为40的节 点x的父节点的编号是 ( )
A.19 B.20
C.21 D.39
11.某二叉树如图所示。用list表示该二叉树是 ( )
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. 已知某二叉树如图所示，则其对应的一维数组(None 表示为空数 据)表示为 ( )
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. 如图所示， 一个数学表达式可以用一棵表达式树来表示。下列关
于该表达式树的描述，不正确的是 ( )
A.该表达式树不是完全二叉树
B.若表达式树中只有四则运算，则对应的表达式树的每个节点都
有两个孩子节点
C.表达式树的根节点左右子树的深度差不会超过1
D.该表达式树对应的表达式为“(3+4)*6-8+4/(3*2)”
14. 已知某二叉树可用嵌套列表表示为bt=["A",["B",["D",None,
None],["E",None,Nonel],["C",None,["F",None,Nonell],下列说法正
确的是 ( )
A.该二叉树的前序遍历序列为A-B-C-D-E-F
B.该二叉树的中序遍历序列为D-B-E-A-C-F
C.该二叉树的后序遍历序列为B-F-C-D-E-A
D.该二叉树的层序遍历序列为A-B-D-E-C-F
15. 使用链表构建如图所示的二叉树。
构建此二叉树的Python程序如下：
class Node:#创建Node类
def ini (self,value=None,left=None,right=None):
self.value=value
Self. . left=left #左子树
Self .right=right #右子树
if name ==" main ":
root=
则划线处应填入的代码是 ( )
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])
程序运行后，输出的结果为 ( )
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. 已知一棵二叉树的中序遍历序列是D-B-G-E-A-F-H-C, 后序遍历 序列是D-G-E-B-H-F-C-A, 请画出这棵二叉树，并给出其前序遍
历序列。
18. 已知一批数据如下：48,17,65,19,67,18,73,72,43,85。依据这 10个数据按照“小左大右”的二叉排序树构建规则，构建一棵二叉 排序树。请回答下列问题：
(1)画出该二叉树。
(2)在该二叉排序树上搜索某个值的自定义函数search(root,x)如
下，请在划线处填入合适的代码。
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 建立二叉树，并输出该二
叉树的节点。请在划线处填入合适的代码。
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("生成的二叉树数组为：")
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

展开更多......

收起↑