深度为4的平衡二叉树至少有（）个结点。
A．9 B．8 C．7 D．6
在二叉排序树上查找关键码为28的结点（假设存在），则依次比较的关键码有可能是（ ）。
A．30, 36, 28 B．38, 48, 28
C．48, 18, 38, 28 D．60, 30, 50, 40, 38, 36
一棵深度为k的平衡二叉树，其每个分支结点的平衡因子均为0，则该平衡二叉树共有（ ）个结点。
A．2k-1-1 B．2k-1+1 C．2k-1 D．2k
在含有n个结点的二叉排序树中查找一个关键码，最多进行（ ）次比较。
A．n/2 B．log2n C．log2n + 1 D．n
已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为（ ）。
A．4 B．5 C．6 D．7
平衡二叉树上所有结点的平衡因子不可能为（）。
A．1 B．0 C．-1 D．2
具有5层的平衡二叉树至少有（ ）个结点。
A．10 B．12 C．15 D．17
已知10个数据元素（50，30，15，35，70，65，95，60，25，40），按照依次插入结点的方法生成一棵二叉排序树后，在查找成功的情况下，查找每个元素的平均查找长度为（ ）。
A．2.5 B．2.7 C．2.9 D．3.1
分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）。
A．（100，80， 90， 60， 120，110，130）
B．（100，120，110，130，80， 60， 90）
C．（100，60， 80， 90， 120，110，130）
D．(100，80， 60， 90， 120，130，110)
二叉排序树中，最小值结点的（ ）。
A．左指针一定为空 B．右指针一定为空
C．左、右指针均为空 D．左、右指针均不为空
下列二叉排序树中查找效率最高的是（ ）。
A．平衡二叉树 B．二叉查找树
C．没有左子树的二叉排序树 D．没有右子树的二叉排序树
如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用( )查找法。
A．顺序查找 B．折半查找
C．分块查找 D．哈希查找
在二叉排序树中插入一个结点的时间复杂度为（）。
A. O(1) B. O(n) C. O(log2n) D. O(n2)
对一棵二叉排序树按（）遍历，可得到一个有序序列。
A. 先序
B. 中序
C. 后序
D. 层次
在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插到集合中，这种方式主要适合于（ ）。
A. 静态查找表
B. 动态查找表
C. 两种表都适合
D. 两种表都不适合
对于一个线性表，若要求既能进行较快地插人和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该( )。 A.以顺序存储方式 B.以链接存储方式 C.以索引存储方式 D.以散列存储方式
设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为（ ）。
(A) O(1) (B) O(log2n) (C)O(n) (D) O(n*log2n)
如果要求一个线性表既能较快地查找，又能动态适应变化要求，可以采用（ ）。 A.顺序 B.分块 C.折半 D.散列
在一棵平衡二叉树中，每个结点的平衡因子的取值范围是（ ）。
A. -1~1 B. -2~2 C. 1~2 D. 0~1
分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()
(A)（55，33，77，22，44，66，88，11，99）
(B)（55，33，22，11，44，77，66，88，99）
(C)（55，77，33，88，66，44，22，99，11）
(D)（55，33，44，77，22，66，99，88，11)
一棵二叉树如图所示，该二叉树是（ ）。
A．平衡二叉树 B．二叉排序树 C．完全二叉树 D．以上都不是
对线性表进行顺序查找，要求线性表的存储结构为（ ）。
A．散列存储 B．顺序存储 C．链接存储 D．顺序存储或链接存储
有一棵二叉树如下图，该树是（ ）。
A．平衡二叉树 B．二叉排序树 C．完全二叉树 D．线索二叉树
从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为（ ）。
A. O(n) B. O(1) C. O(logn) D. O(n2)
关于二叉排序树，下面说法中正确的是（ ）。
A．二叉排序树是动态树表，在插入新结点时会引起树的重新分裂或组合
B．对二叉排序树进行层次遍历可得到有序序列
C．在构造二叉排序树时，若插入的关键码有序，则二叉排序树的深度最大
D．在二叉排序树中进行查找，关键码的比较次数不超过节点数的一半
在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（ ）
A. n B. log2n C. (h+1)/2 D. h
已知数据序列为（13, 8, 12, 15, 19, 21, 3, 14, 20, 4），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ ）。
现有{10, 20, 30, 40, 50, 60, 70}一共7个元素，用它们构成了一棵平衡二叉树，恰好每个枝结点的平衡因子都是 -1。请问前序遍历这棵树的第5个结点是（ ）。
A. 40 B. 50 C. 60 D. 7
C. 静态查找表和动态查找表
用n个键值构造一棵二叉排序树，其最低高度为（ ）。
A．n/2 B．n C．[log2n」 D．[log2n + 1」
不可能生成如图所示二叉排序树的关键码序列是（ ）。
A．{4, 2, 1, 3, 5} B．{4, 2, 5, 3, 1}
C．{4, 5, 2, 1, 3} D．{4, 5, 1, 2, 3}
从具有n个结点的线性表使用折半查找一个元素时，在最坏情况下的时间复杂度为（ ）。
已知10个元素（54, 28, 16, 73, 62, 95, 60, 26, 43），按照依次插入的方法生成一棵二叉排序树，查找值为62的结点所需比较次数为（ ）。
A．2 B．3 C．4 D．5
下列二叉树中，不平衡的二叉树是（ ）。
向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的插入，若元素的值大于根结点的值，则接着向根结点的插入。
下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。
struct node
{int key; struct node *lchild; struct node *rchild;};
struct node *bstsearch(struct node *t, int k)
{
if (t==0 ) return(0);
while (t!=0)
if (t->key==k)
;
else if (t->key>k)
t=t->lchild;
else
}
对一棵二叉排序树进行遍历，可以得到一个键值从小到大次序排列的有序序列。
对一棵二叉排序树进行中序遍历时，得到的结点序列是一个。
设一组初始记录关键字序列为(20，12，42，31，18，14，28)，根据这些记录关键字构造二叉排序树，则该树查找成功的平均查找长度是。
高度为6的平衡二叉排序树，其每个分支结点的平衡因子均为0，则该二叉树共有个结点。
在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定该结点的值，右子树上所有结点的值一定该结点的值。（填：大于/等于/小于）
在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过。
由序列{3,7,8,1,5,6,2,4}生成一棵二叉排序树，请写出生成的二叉排序树的前序遍历序列和后序遍历序列。
依次读入给定的整数序列{7,16,4,8,20,9,6,18,5}，构造一棵二叉排序树。
1.该二叉排序树深度？
2.该二叉排序树度为0-2的结点各几个？
3.计算在等概率情况下该二叉排序树查找成功的平均查找长度ASL。
若依次输入序列{62,68,30,61,25,14,53,47,90,84}中的元素，生成一棵二叉排序树。
1.写出第4层的元素
2.写出中序遍历序列
