结构推理
在包含n个元素的字典里进行顺序检索,若查找第i个元素的概率为p
i
,p
i
如下分布:
p
1
=1/2,p
2
=1/4,…,p
n-1
=1/(2
n-1
),p
n
=1/2
n
求成功的检索的平均比较次数。
【正确答案】
平均比较次数ASL=p
1
×1+p
2
×2+…p
n
×n=1/2+2/4+3/8+…+n/2
n
=2-(n+2)/2
n
。
【答案解析】
提交答案
关闭