国家开放大学
设有一个整数序列{50，38，16，82，110，13，64}，依次取出序列中的数，构造一棵二叉排序树。利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到？为了查找15，经多少次元素间的比较可知道查找失败？
题目
相似问题和答案
第1题：
对具有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是正确的。
第2题：
设查找表为(50,60,75,85,96,98,105,110,120,130)
(1)说出进行折半查找成功查找到元素120需要进行多少次元素间的比较?
(2)为了折半查找元素95，经过多少次元素间的比较才能确定不能查到?
(3)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点)。
(2 )4次
(3)
第3题：
(2)4次(3)ASL=(1+2*2+3*4+4*4)/11=3
第4题：
设有查找表{5，14，2，6，18，7，4，16，3}，依次取表中数据，构造一棵二叉排序树。并说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。
（1）
（2）中序遍历：中序2，3，4，5，6，7，14，16，18
略
第5题：
设有一个整数序列d{40，28，6，72，100，3，54}依次取出序列中的数，构造一棵二叉排序树。并对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度。
（1）
（2）ASL=（1×1+2×2+3×3+4）/7=18/7
略
第6题：
利用逐点插入建立序列(52,43,73,88,76,18,38,61,45,39)对应的二叉排序树之后，查找元素61要进行(57)次元素间的比较。
A．3
B．4
C．6
D．8
解析：利用逐点插入建立二叉排序树是从空树开始，通过查找将每个节点作为一个叶子插入。建立序列(52、43、73、88、76、18、 38、61、45、39)的二叉排序树如图3-14所示。
根据图3-14所示的二叉排序树可知，查找元素61要进行3次元素间的比较。
第7题：
利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉查找树后，查找元素35要进行(29)次元素间比较。
A．2
B．3
C．4
D．5
第8题：
利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素30要进行(42)次元素间的比较。
A．4
B．5
C．6
D．7
解析：利用逐点插入法建立二叉排序树是从空树开始，通过查找将每个结点作为一个叶子插入。按上述次序建立的二叉排序树如下图所示。
第9题：
设有序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下标依次为1，2，……，12。设查找元素5，需要进行多少次元素间的比较才能确定不能查到。
3次。
略
第10题：
设有序列{10，12，15，19，22，25，100，130，150，200}画出对上述序列进行折半查找的判定树（以序列中的元素作为树的结点）。为了成功查找到100需要进行多少次元素间的比较？为了查找9，经过多少次元素间的比较可知道查找失败？
（1）
（2）4次；3次
略