5.1 静态查找法

二、综合应用题

　　1．综合应用题题目部分
　　● 习题1：已知一个有序表的表长为8N，并且表中没有关键字相同的记录。假设按如下方法查找一个关键字等于给定值K的记录：先在第8，16，24，…，8K，…，8N个记录中进行顺序查找，或者查找成功，或者由此确定出一个继续进行折半查找的范围。画出描述上述查找过程的判定树，并求等概率查找时查找成功的平均查找长度。
　　● 习题2：假定对有序表：（3,4,5,7,24,30,42,54,63,72,87,95）进行折半查找，试回答下列问题：
　　（1）画出描述折半查找过程的判定树。
　　（2）若查找元素54，需依次与哪些元素比较?
　　（3）若查找元素90，需依次与哪些元素比较?
　　（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
　　2．综合应用题的答案与分析
　　习题1分析：
　　解此类问题时要求读者对顺序查找和折半查找的算法，以及这两种算法的平均查找长度的计算方法非常熟悉。
　　（1）查找的判定树如图5-1所示。
　　（2）平均查找长度。
　　该算法的平均查找长度由在有序表内以8为间隔顺序查找ASL_seq和在（8i-7, 8i-1）区间内折半查找ASL_bi两部分组成。在等概率条件下，，而每次进行折半查找的区间内有8个元素，但实际上要进行折半查找的元素只有7个（8i-7,8i-1），其中1≤i≤N，因此。因此等概率查找时查找成功的平均查找长度为。
　　习题2分析：
　　（1）根据折半查找算法的思想，构造判定树如图5-2所示。

　　　　
　　　　　　　　　图5-1 判定树
　　
　　　　　　　　　　　　　　　　图5-2 判定树
　　（2）根据图5-2所示，查找元素54，需要依次与30、63、42、54进行比较。
　　（3）查找元素54，需要依次与30、63、87、95进行比较。
　　（4）在等概率下，查找成功时的
　　。
　　3．训练自测表（如表5-2所示）

表5-2 应用题练习自测表