最优二叉搜索树一定是平衡的二叉搜索树。()

在所有结点的权值都相等的情况下，具有平衡特性的二叉搜索树一定是最优二叉搜索树。（)

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

最优二叉树（IIuffman树)和最优二叉搜索树均为平均搜索路径长度为最小的树，其中对最优二叉树。n

最优二叉树(IIuffman树)和最优二叉搜索树均为平均搜索路径长度为最小的树，其中对最优二叉树。n表示(①)，对最优二叉搜索树，n表示(②)，构造这两种树均(③)，

A、结点数

B、叶结点数

C、非叶结点数

D、度为2的结点数

最佳二叉搜索树是(36)。

A．关键码个数最少的二叉搜索树

B．搜索时平均比较次数最少的二叉搜索树

C．所有结点的左子树都为空的二叉搜索树

D．所有结点的右子树都为空的二叉搜索树

在所有结点的权值都相等的情况下，只有最下面两层结点的度数可以小下2，其他结点的度数必须等于2的二叉搜索树才是最优二叉搜索树。（)

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

图7-28（a)给出一棵二叉搜索树，对应的二叉判定树如图7-28（b)所示，它的搜索成功的平均搜索长度是

()，搜索不成功的平均搜索长度是()。

A、21/7

B、28/7

C、15/6

D、16/6

将二叉搜索树T的前序序列中的关键码依次插入到一棵空的二叉搜索树中，所得到的二叉搜索树T'与T是否相同？为什么？

设有一个关键码的输入序列（55，31，11，37，46，73，63，02，07)：（1)从空树开始构造平衡二叉搜索树，画

设有一个关键码的输入序列(55，31，11，37，46，73，63，02，07)：

(1)从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需进行的平衡旋转的类型及平衡旋转的结果

(2)计算该平衡二叉搜索树在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。

对二叉搜索树的搜索都是从根结点开始的，如果搜索失败，则搜索指针一定落在叶结点上。（)

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

设二叉搜索树中的关键码互不相同，则其中的最小元素必无左子女，最大元素必无右子女，此命题是否正确？最小元素和最大元素一定是叶结点？一个新元素总是作为叶结点插入二叉搜索树吗？