工学
填空题在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关，最好的情况是二叉排序树为（）树的时候。
题目
相似问题和答案
第1题：
在下列方法中，不用查找表中数据元素的关系进行查找的方法是______。
A．有序表查找
B．二叉排序树查找
C．平衡二叉树
D．散列查找
解析：线性表查找和树状查找都是利用了数据元素之间的关系进行查找，只有散列查找是利用关键词值与存储位置来进行查找。
第2题：
设二叉排序树中有n个结点，则二叉排序树的平均查找长度为()。
A.O(1)
B.O(log2n)
C.O(n)
D.(n2)
第3题：
A.所有结点的左子树都为空的二叉排序树
B.所有结点的右子树都为空的二叉排序树
C.平衡二叉树
D.没有左子树的二叉排序数
第4题：
第5题：
在关键字随机分布的情况下，在二叉排序树上进行查找的平均查找长度与(28)的量级相当。
A．顺序查找
B．二分查找
C．哈希查找
D．逆序查找
第6题：
最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度Σwl最小的树，其中对于最优二叉树，n表示(42)；对于最优查找树，n表示(43)；构造这两种树均(44)。
A．结点数
B．叶结点数
C．非叶结点数
D．度为二的结点数
第7题：
结点数目为n的二叉查找树（二叉排序树）的最小高度为（56）、最大高度为（57）。
A.A
B.B
C.C
D.D
本题考查二叉排序树的基本构造特点。若二叉树中有n个结点，则结点分布均匀、且高度最小的树的特点是除了最后一层，其余各层的结点数目都达到最大值（第i层上有2i-1个结点），此时树的高度为[log2(n+1)]。若每层只有一个结点，则树的高度为n。具有三个结点的二叉树的所有形态如下所示，每层只有一个结点时称为单枝树。二叉排序树是根据输入序列构造的，当序列呈现有序的特点时，就构造出一棵单枝树。
第8题：
A.形态和平均查找长度都不一定相同
B.形态不一定相同，但平均查找长度相同
C.形态和平均查找长度都相同
D.形态相同，但平均查找长度不一定相同
第9题：
在某个二叉查找树（即二叉排序树）中进行查找时，效率最差的情形是该二叉查找树是(59) 。
A.完全二叉树
B.平衡二叉树
C.单枝树
D.满二叉树
本题考查数据结构基础知识。非空二叉查找树中的结点分布特点是左子树中的结点均小于树根，右子树中的结点均大于树根。因此，在二叉查找树中进行查找时，走了一条从树根出发到所找到结点的路径，到达一个空的子树则表明查找失败。根据定义，高度为h的满二叉树中有2h-l个结点，每一层上的结点数都达到最大值。完全二叉树的最高层只要求结点先占据左边的位置。例如，高度为3的满二叉树如下图(a)所示，具有6个结点的完全二叉树如下图(b)所示。在平衡二叉树中，任何一个结点的左子树高度与右子树高度之差的绝对值不大于1。单枝树中给每个结点只有1个子树。例如，具有3个结点的单枝树如下图所示。显然，在结点数确定后，二叉查找树的形态为单枝树时查找效率最差。
第10题：
