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