在一棵B树中，所有叶结点都处在同一层上，所有叶结点中空指针数等于所有关键码的总数加1。（)

【 】树的所有关键码都出现在叶结点上,上面各层结点中的关键码均是下层相应结点中最大关键码的复写。

一棵哈夫曼树的带权(外部)路径长度等于其中所有分支结点的权值之和。()

(1)以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树(要求每个结点的左子树根结点的权小于等于右子树根结点的权)，给出相应权重值叶结点的哈夫曼编码。

(2)一棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由。

树中的结点数等于所有结点的度数加1。()

A、21

B、22

C、10

D、9

设二叉树中所有非叶结点的左、右子树都不为空。试证明对此类二叉树满足：

(1)含有n个叶结点的二叉树中共有2n-1个结点。

(2)，其中，n为叶结点个数，1.表示第i个叶结点所在的层次(设根结点所在的层次为1).

一棵共有n个结点的树，其中所有分支结点的度为k，则该树中叶子结点的个数为(18)。

A．

B．

C．

D．

从供选择的答案中选出应填入下列叙述中()内的正确答案：

在二叉排序树中，每个结点的关键码值(A)，(B)一棵二叉排序树，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称做最佳二叉排序树，最佳二叉排序树在结构上的特点是(C)。

供选择的答案

A：①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小

②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大

③比左右子树的所有结点的关键码值大

④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系

B：①前序遍历 ②中序(对称)遍历

③后序遍历 ④层次遍历

C：①除最下二层可以不满外，其余都是充满的

②除最下一层可以不满外，其余都是充满的

③每个结点的左右子树的高度之差的绝对值不大于1

④最下层的叶子必须在左边