假定对有序表：(3,4,5,7,24,30,42,54,63

[问答题]

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

(1). 画出描述折半查找过程的判定树；

(2). 若查找元素54，需依次与那些元素比较?

(3). 若查找元素90，需依次与那些元素比较?

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

扯吧

①先画出判定树如下（注：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

发表于 2019-06-25 22:26:14 回复(0)