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

第1题：

第2题：

第3题：

第4题：

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

第5题：

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

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

第6题：

假定对长度n=50的有序表进行折半查找，则对应的判定树高度为（），最后一层的结点数为（）。

正确答案:6；19

第7题：

在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为（）。

正确答案:6，9，11，12

第8题：

假定对长度n=50的有序表进行二分查找，则对应的判定树高度为（），判定树中前5层的结点数为（），最后一层的结点数为（）。

正确答案:6；31；19

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

第15题：

用折半查找法，对长度为12的有序的线性表进行查找，最坏情况下要进行（）次元素间的比较。

A4

B3

C5

D6

A
略

第16题：

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

略

第17题：

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

（2）4次；3次
略

第18题：

对有18个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标为（）。

• A、 1、2、3
• B、 9、5、2、3
• C、 9、5、3
• D、 9、4、2、3

正确答案:D

第19题：

假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为（）；比较四次查找成功的结点数为（），其下标从小到大依次是（），平均查找长度为（）。

正确答案:2；8；1，3，6，8，11，13，16，19；3.7

第20题：

设有序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下标依次为1，2，……，12。说出有哪几个元素需要经过3次元素间的比较才能成功查到。

正确答案:13，36，63，135。

第21题：

第22题：

第23题：