高中信息技术浙教版（2019）选修1 第四章　验收卷(三)　树 课件.pptxVIP

第四章树;一、选择题(本题共14小题，每小题2分，共28分)

1.树中所有节点的度等于();C;B;A;C;C;D;A;C;B;B;D;C;B;二、非选择题(本题共4小题，共22分);16.(3分)设有一棵k叉树，其中只有度为0和k两种节点，设n0、nk分别表示度为0和度为k的节点个数，求出n0和nk之间的关系(形式如n0＝数学表达式，数学表达式仅含nk、k和数字)。关系式为________________________。;17.(7分)3个节点数的不同形态的二叉树一共有__________种；5个节点数的不同形态的二叉树一共有________种。;18.(6分)二叉查找树。所谓的二叉查找树是指每一个树根的值大于左子树的值，但小于右子树的值，左右子树也是二叉查找树，树的每一个节点的值都不相同。

已知节点信息顺序存储在数组中，编写程序创建一棵二叉查找树，并输出该二叉树的数组表示。程序运行效果如图所示。;实现上述功能的程序如下，请回答下列问题。

defBt_build(btree，data，length)：

globalx

x＝0

foriinrange(length)：

level＝0

whilebtree[level]！＝None：

ifdata[i]btree[level]：

①________________

else：

level＝level*2＋1

②________________;ifxlevel：

x＝level

data＝[11，6，8，15，12，16，9，7]

length＝len(data)

btree＝[None]*100

print(原始数组为：)

print(data)

print()

③________________

print(二叉树内容：)

foriinrange(x＋1)：

print([{}].format(btree[i])，end＝)

print();(1)若data列表中元素依次为“15，10，8，18，20，9，11”，则输出的二叉树内容为______________。

(2)请在程序划线处填入合适的代码。

划线①处应填入的代码：

______________；

划线②处应填入的代码：

______________；

划线③处应填入的代码：

______________。;