请教关于数据结构的一个问题!在查找这一张中有一个概念叫做平均查找长度,以顺序查找为例,求法ASL=np1+(n-1)

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/05/22 02:03:28

请教关于数据结构的一个问题!在查找这一张中有一个概念叫做平均查找长度,以顺序查找为例,求法ASL=n*p1+(n-1)*p2+…+2*pn-1+pn,为什么这么算?每一次查找后总的顶点数目会减一,所以n的数目会减一,但是概率为什么没有变,我知道如果概率每次也增大的话最终结果会是n,但是ASL为什么需要这样多次相加得出呢?这似乎和抽奖的问题一样,放回与不放回的概率是不一样的,为什么却说先抽奖和后抽奖的概率一样呢?这个ASL算法似乎是不放回吧,而且也只是一次比较!

是和概率有关,但是与放回与不放回的概率不同.查找第几个数,是随机的,所以查找的次数也是随机的,即查找次数是随机变量,随机变量的平均值就是随机变量的数学期望,是随机变量值与取这个值的概率的乘积之和.
　　一般来说,顺序查找采用由后向前逐个比较的方法（由前向后雷同）,n个元素查找第1个需要查找n次,查找第2个需要查找n-1次,……,查找第n个需要查找1次,所以
　　ASL=n*p1+(n-1)*p2+…+2*pn-1+pn
　　这里p1=P(X=1),……,pn=P(X=n).是从n个元素中,查找第几个的概率.要查找第几个,都是等概的,不变的,所以都是1/n,因此
　　ASL=n*p1+(n-1)*p2+…+2*pn-1+pn =1/n(1+2+3+……+n)=(n+1)/2.
　　关键在搞清pi的涵义,它是表示从n个元素中,查找第i个的概率,总体元素个数始终是n,所以概率是不变的,也可以说相当于（不等同于）放回的情况；如果是每次查找一个元素,后一次在前一次剩余的元素中查找,pi表示第i次找到的概率,总体元素个数始终改变,概率就是变动的了,相当于（不等同于）不放回的情况.但是,这里是前者.

在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时平均查找长度为多少数据结构题目：才用折半查找算法在长度为12的有序表中查找一个元素时,查找成功的平均查找长度为多少?... 在一个长度为n顺序线性表中顺序查找值为x的元素时,查找的平均长度为顺序表长度为n的折半查找算法的平均查找长度关于数据结构二分法查找成功的平均查找长度和失败的查找长度数据结构有一个长度为12的有序表,按二分查找法对该表进行查找,在表内个元素等概率情况下,查找成功所需关于数据结构查找定一个集合,查找元素是否在集合中出现.输入每个测试用例由多行组成,第一行是两个整数n和m,两个数范围在算平均查找长度长度为12的按关键字有序的查找表采用顺序组织方式,若用二分法查找,则在等概率情况下,查找不成功的平均查找长关于哈希表查找不成功时的平均查找长度有一个长度为12的有序表,按折半查找法对表进行查找,在表内各元素等概率的情况下查找成功所需的平均比较次计算各种查找方法在等概率情况下查找成功时的平均查找长度数据结构折半查找的二叉查找树的问题