判断题在一棵B树中，所有叶结点都处在同一层上，所有叶结点中空指针数等于所有关键码的总数加1。A 对B 错

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

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

A、21

B、22

C、10

D、9

A、树中每个结点最多有 m个关键字

B、树中叶子结点的个数为 n+1

C、在B树上进行查找的过程是顺指针找结点和在结点内找关键字交叉进行的过程。

D、树中所有叶子结点都在同一层，并且不带任何信息

E、树中每个结点最多有 m-1个关键字

F、树中每个结点最多有 m+1个关键字

下面关于二叉排序树叙述中，正确的是

A．右结点的度大于左结点的度

B．右子树的度大于左子树的度

C．左子树中所有的结点的关键码值都小于该结点的关键码值

D．右子树中所有的结点的关键码值都小于该结点的关键码值

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

A.叶结点

B.空结点

C.树根结点

D.分支结点

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

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

供选择的答案

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

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

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

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

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

③后序遍历 ④层次遍历

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

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

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

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

下列有关树的说法错误的是（ ）。

A)一棵树中只有一个无前驱的结点

B)一棵树的度为树中各个结点的度数之和

C)一棵树中每个结点的度数之和与边的条数相等

D)一棵树中，每个结点的度数之和等于结点总数减1

下列有关树的概念错误的是

A．一棵树中只有一个无前驱的结点

B．一棵树的度为树中各个结点的度数之和

C．一棵树中，每个结点的度数之和等于结点总数减1

D．一棵树中每个结点的度数之和与边的条数相等

●非空二叉排序树的定义是：若根结点具有左子树，则左子树中所有结点的关键码均小于根结点的关键码；若根结点具有右子树，则右子树中所有结点的关键码均大于根结点的关键码；左、右子树也是二叉排序树。由此可知，在一个二叉排序树中,(40)。

(40)

A．从根结点到任何一个叶子结点的路径上，结点的关键码序列呈递增排列

B．从根结点到任何一个叶子结点的路径上，结点的关键码序列呈递减排列

C．同层次结点从左向右排列，结点的关键码序列呈递增排列

D．同层次结点从左向右排列，结点的关键码序列呈递减排列