假定对有序表: ( 3,4, 5,7,24 ,30,42,54 ,63,72,87,95)进行折半查找,试回答下列问题: 1、画出描述折半查找过程的判定树; 2、若查找元素54,需依次与哪些元素比较? 3、若查找元素90,需依次与哪些元素比较? 4、假定每个元素的查找概率相等,求查找成功时的平均查找长度。
1、
30
5 63
3 7 42 87
4 24 54 72 95
2、
30 63 42 54
3、
30 63 87 95
4、
37/12
2.42 72 54
3.42 72 87 95
4.(5*4+4*3+2*2+1)/12=37/12
为什么是取30 而不是42
17679377259 回复 17797964441: (low+high)/2,取商,余数舍去
1、画出判定树
2、查找...
用户登录可进行刷题及查看答案
2、查找元素54,需依次与30, 63, 42, 54 元素比较; 3、查找元素90,需依次与30, 63,87, 95 元素比较; 4、求ASL 之前,需要统计每个元素的查找次数。判定树的前3 层共查找1+ 2 × 2+ 4×3=17 次;最后一层只有5个元素,5× 4=20 次, 所以ASL = ( 17+ 20 )/12= 37/12
登录后提交答案