数据结构
在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（）。A、NB、log2nC、（h+1）/2D、h
题目
在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（）。
- A、N
- B、log2n
- C、（h+1）/2
- D、h
相似问题和答案
第1题：
对于静态表的顺序查找法，若在表头设置监视哨，则正确的查找方式为()
A.从第0个元素往后查找该数据元素
B.从第1个元素往后查找该数据元素
C.从第n个元素往开始前查找该数据元素
D.与查找顺序无关
第2题：
在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为()
A.(n+1)/2
B.n
C.3n/4
D.n/4
第3题：
第4题：
顺序查找一个具有n个元素的线性表，二分查找一个具有n个元素的有序表，其时间复杂性为______。
A．O(n)
B．O(log2n)
C．O(n2)
D．O(nlog2n)
第5题：
● 对 n 个元素的有序表 A[1..n]进行二分（折半）查找，则成功查找到表中的任意一个元素时，最多与A 中的 （39） 个元素进行比较。
（39）
第6题：
查找n个元素的有序表时,最有效的查找方法是()
A.顺序查找
B.分块查找
C.折半查找
D.二叉排序树
第7题：
An
Bn/2
C(n+1)/2
D(n-1)/2
第8题：
对具有n个元素的有序序列进行二分查找时，(61)。
A．元素位置越靠近序列前端，查找该元素所需的比较次数越少
B．查找序列中任何一个元素所需要的比较次数不超过[log2(n+1)]
C．查找元素所需的比较次数与元素的位置无关
D．元素位置越靠近序列后端，查找该元素所需的比较次数越少
解析：二分查找过程是：以处于中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或查找区间的大小为零时(表明查找不成功)为止。对于有11个元素的有序表进行二分查找的过程可用一个二叉树表示，如图6-12所示(结点中的数字表示元素在序列中的序号)。
图6-12所示二叉树表明，若需要查找序列中的第6个元素，则仅需一次元素间的比较。若需查找第3个或第9个元素，则分别需要两次比较。依此类推，查找第1、4、7、10个元素时，分别需要三次比较，查找第2、5、 8、11个元素时，分别需要四次比较。因此，查找元素所需的比较次数与元素在序列中的位置是有关的。显然，选项A或D的说法也是错误的。若序列中有n个元素，则根据二分查找法构造的二叉树的高度不会超过[log2(n+1)]，因此选项B是正确的。
第9题：
在具有n个结点的二叉排序树上插入一个新结点时，根据n个数据元素生成一棵二叉排序树时，其时间复杂性大致为______。
A．O(n)
B．O(n2)
C．O(log2n)
D．O(nlog2n)
第10题：
设有一个整数序列{50，38，16，82，110，13，64}，依次取出序列中的数，构造一棵二叉排序树。利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到？为了查找15，经多少次元素间的比较可知道查找失败？
（1）
（2）三次；四次
略