Question

查找的平均长度

对长度为4的顺序表进行查找,若第一个元素的概率为1/8,第二个元素的概率为1/4,第三个元素的概率为3/8,第四个元素的概率为1/4,则查找任一元素的平均长度为____.
A:11/8
B:7/4
C:9/4
D:11/4

详细说明,帮帮小弟..

Answer 1

为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(Average Search Length)。
对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL=∑PiCi (i=1,2,3,…,n)。其中：Pi 为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数。

这题目应该选C

Answer 2

ASL=1/8*4+1/4*3+3/8*2+1/4*1=9/4
选C