第七章应用题

（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

① 画出描述折半查找过程的判定树；

② 若查找元素54，需依次与哪些元素比较？

③ 若查找元素90，需依次与哪些元素比较？

④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。

答案：

①先画出判定树如下（注：mid=ë(1+12)/2û=6）：

②查找元素54，需依次与30, 63, 42, 54 元素比较；

③查找元素90，需依次与30, 63,87, 95元素比较；

④求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；

但最后一层未满，不能用8×4，只能用5×4=20次，

所以ASL＝1/12（17＋20）＝37/12≈3.08

（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。

        答案：

验算方法：  用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17,21

（3）已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）

① 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

② 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

③ 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

4）对图7.31所示的3阶B-树，依次执行下列操作，画出各步操作的结果。

① 插入90    ②  插入25   ③  插入45   ④ 删除60 

（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：

① 画出哈希表的示意图；

② 若查找关键字63，需要依次与哪些关键字进行比较？

③ 若查找关键字60，需要依次与哪些关键字比较？

④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

答案：①画表如下：

、

②查找63,首先要与H(63)=63%16=15号单元内容比较，即63与31比较 ,不匹配;

然后顺移，与46,47,32,17,63相比，一共比较了6次！

③查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

④对于黑色数据元素，各比较1次；共6次；

对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，

所以ASL=1/11（6＋2＋3×3+6）＝23/11

6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

答案：

平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8

以关键字27为例：H（27）=27%7=6（冲突）   H1=（6+1）%10=7（冲突）

H2=（6+22）%10=0（冲突）   H3=（6+33）%10=5   所以比较了4次。

（7）设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。

① 线性探测法；

② 链地址法。

答案：①

ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8

ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11

 ②

ASLsucc =（1*5+2*3）/8=11/8

ASLunsucc=（1+2+1+2+3+1+3+1+3+1+1）/11=19/11