以下对二叉排序树的描述不正确的是（）。

A．左指针一定为空

B．右指针一定为空

C．左右指针均为空

D．左右指针均不为空

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

供选择的答案

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

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

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

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

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

③后序遍历 ④层次遍历

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

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

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

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

A.二叉排序树是动态树表，在插入新节点时会引起树的重新分裂和合并

B.对二叉排序树进行层次遍历可以得到一个有序序列

C.在二叉排序树中进行查找，关键字的比较次数不超过节点数的一半

D.在构造二叉排序树时，若关键字序列有序，则二叉排序树的高度最大

此题为判断题(对，错)。

（27）

A. 对二叉排序树进行中序遍历，必定得到结点关键字的有序序列

B. 依据关键字无序的序列建立二叉排序树，也可能构造出单支树

C. 若构造二叉排序树时进行平衡化处理，则根结点的左子树结点数与右子树结点数的差值一定不超过1

D. 若构造二叉排序树时进行平衡化处理，则根结点的左子树高度与右子树高度的差值一定不超过1

（27）

A. 对二叉排序树进行中序遍历，必定得到结点关键字的有序序列

B. 依据关键字无序的序列建立二叉排序树，也可能构造出单支树

C. 若构造二叉排序树时进行平衡化处理，则根结点的左子树结点数与右子树结点数的差值一定不超过1

D. 若构造二叉排序树时进行平衡化处理，则根结点的左子树高度与右子树高度的差值一定不超过1

（27）

A. 对二叉排序树进行中序遍历，必定得到结点关键字的有序序列

B. 依据关键字无序的序列建立二叉排序树，也可能构造出单支树

C. 若构造二叉排序树时进行平衡化处理，则根结点的左子树结点数与右子树结点数的差值一定不超过1

D. 若构造二叉排序树时进行平衡化处理，则根结点的左子树高度与右子树高度的差值一定不超过1

（59）

A. 对二叉排序树进行中序遍历，必定得到结点关键字的有序序列

B. 依据关键字无序的序列建立二叉排序树，也可能构造出单支树

C. 若构造二叉排序树时进行平衡化处理，则根结点的左子树结点数与右子树结点数的差值一定不超过1

D. 若构造二叉排序树时进行平衡化处理，则根结点的左子树高度与右子树高度的差值一定不超过1

A.左子树中所有结点的关键字小于根结点的关键字

B.根结点的关键字大于左、右子树中所有结点的关键字

C.右字树中所有结点的关键字大于根节点的关键字C.

D.关键字插入的顺序影响二叉排序树的形态

A．对二叉排序树进行中序遍历，必定得到节点关键字的有序序列

B．依据关键字无序的序列建立二叉排序树，也可能构造出单支树

C．若构造二叉排序树时进行平衡化处理，则根节点的左子树节点数与右子树节点数的差值一定不超过1

D．若构造二叉排序树时进行平衡化处理，则根节点的左子树高度与右子树高度的差值一定不超过1