设有序列{10，12，15，19，22，25，100，130，150，200}画出对上述序列进行折半查找的判定树（以序列中的元素作为树的结点）。为了成功查找到100需要进行多少次元素间的比较？为了查找9，经过多少次元素间的比较可知道查找失败？

第1题：

正确答案：A
解析：利用逐点插入建立二叉排序树是从空树开始，通过查找将每个节点作为一个叶子插入。建立序列(52、43、73、88、76、18、 38、61、45、39)的二叉排序树如图3-14所示。
 
  根据图3-14所示的二叉排序树可知，查找元素61要进行3次元素间的比较。

第2题：

第3题：

第4题：

第5题：

设有一个整数序列{50，38，16，82，110，13，64}，依次取出序列中的数，构造一棵二叉排序树。利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到？为了查找15，经多少次元素间的比较可知道查找失败？
（1）

（2）三次；四次
略

第6题：

设查找表为（20，19，24，57，68，11）在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。（要求以数据元素作为树结点）

略

第7题：

依次插入序列（50，72，43，85，75，20，35，45，65，30）后建立的二叉搜索树中，查找元素35要进行（）元素间的比较。

• A、4次
• B、5次
• C、7次
• D、10次

第8题：

依次取a中各数据，构造一棵二叉排序树。 （1）对该二叉树进行查找，成功查找到38，和46各要进行多少次元素间的比较？ （2）给出按后序遍历该二叉排序树的序列。

第9题：

第10题：

第11题：

第12题：

第13题：

参考答案(1)3次
　　(2 )4次
　　(3)

第14题：

正确答案：A
解析：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左右子树也分别为二叉排序树。二叉排序树也叫二叉查找树。二叉排序树是一种动态树表。其特点是，树的结构通常不是一次生成的，而是在查找过程中逐步插入结点形成的，即当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或者右孩子(若给定值小于最后一个结点的关键字值，则插入成为其左孩子，否则便插入成为其右孩子)。此题中建立二叉排序树的过程如图13-38所示。

当查找元素35时，依次要跟49、43，21、35比较，因此要比较4次。

第15题：

第16题：

设有序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下标依次为1，2，……，12。画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）。

略

第17题：

设有序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下标依次为1，2，……，12。设查找元素5，需要进行多少次元素间的比较才能确定不能查到。
3次。
略

第18题：

画出对长度为10的有序表进行折半查找的判定树（以序号1，2，……10表示树结点），并对上述序列进行折半查找，求等概率条件下，成功查找的平均查找长度。
（1）

（2）ASL=（1x1+2x2+3x4+4x3）/10=29/10
略

第19题：

在序列（2，5，8，11，15，16，22，24，27，35，50）中采用折半查找（二分查找）方法查找元素24，需要进行（）次元素之间的比较。

第20题：

设查找表为（7，15，21，22，40，58，68，80，88，89，120），元素的下标依次为1，2，3，……，11。说明成功查找到元素40需要经过多少次比较？

第21题：

第22题：

第23题：