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

第1题：

第2题：

第3题：

第4题：

第5题：

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

略

第6题：

对于长度为n的线性表，若进行顺序查找，则时间复杂度为（）；若采用折半法查找，则时间复杂度为（）

正确答案:O（n）；O（log₂n）

第7题：

假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找。假定每个元素的查找概率相等，求查找成功时的平均查找长度。

正确答案:求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；
但最后一层未满，不能用8×4，只能用5×4=20次，
所以ASL＝1/12（17＋20）＝37/12≈3.08

第8题：

假定在索引查找中，查找表长度为n，每个子表的长度相等，设为s，则进行成功查找的平均查找长度为（）。

正确答案:(n/s+s)/2+1

第9题：

采用二分检索方法检索长度为n的有序表，检索每个元素时的平均比较次数与对应的判定树高度（设高度≥2相比较为（）。

• A、小于
• B、大于
• C、等于
• D、大于等于

正确答案:C

第10题：

第11题：

第12题：

第13题：

第14题：

第15题：

第16题：

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

略

第17题：

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

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

第18题：

长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。

正确答案:4

第19题：

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

正确答案:6；19

第20题：

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

正确答案:6；31；19

第21题：

第22题：

第23题：

第24题：