首页 > 试题广场 > 假定对有序表:(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)