题目中的意思是:对于n个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为多少?
时间: 2024-03-07 10:51:34 浏览: 32
对于n个元素的表做顺序查找时,每个元素被查找到的概率是相同的,即1/n。平均查找长度(ASL)是指查找成功和查找失败的总次数与总关键字数的比值,也就是平均查找次数。在顺序查找中,当查找成功时需要比较的次数是1到n的等差数列和,即n(n+1)/2,当查找失败时需要比较n次。因此,ASL为:
ASL = [(1/n) * (n(n+1)/2) + ((n-1)/n) * n]/n = (n+1)/2
因此,对于n个元素的表做顺序查找时,平均查找长度为(n+1)/2。
相关问题
在长度为n的线性表中进行顺序查找,查找第i个数据元素的的概率为p i ,且分布如下1=
在长度为n的线性表中顺序查找第i个数据元素的概率可以通过以下方式计算得出。
首先,我们需要了解每个数据元素出现的概率分布。根据题目给出的信息,1 ≤ i ≤ n,且数据元素的概率分布如下:
p1 = 0.2
p2 = 0.15
p3 = 0.1
p4 = 0.1
p5 = 0.05
p6 = 0.2
p7 = 0.1
p8 = 0.05
p9 = 0.05
接下来,我们可以将这些概率值相加,得到总的概率值:
p1 + p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9 = 0.2 + 0.15 + 0.1 + 0.1 + 0.05 + 0.2 + 0.1 + 0.05 + 0.05 = 1.0
由于概率的总和等于1,我们可以确定这是一个有效的概率分布。
根据这个概率分布,我们可以计算出查找第i个数据元素的概率。例如,查找第3个数据元素的概率为p3,查找第7个数据元素的概率为p7,以此类推。
综上所述,在长度为n的线性表中进行顺序查找第i个数据元素的概率为pi(1 ≤ i ≤ n),其中pi表示该数据元素的概率。这些概率值可以通过给定的概率分布计算得出。
若有一个无序顺序表r1和递增有序顺序表r2,它们均含有n个元素,且可能存在相同关键字的元素。设计两个算法分别输出r1和r2中第一个关键字为k的元素位置,并分析成功查找的平均查找长度。
题目描述:给定两个无序顺序表r1和r2,它们均含有n个元素,并可能存在相同关键字的元素。设计两个算法分别输入r1和r2中第一个关键字为k的元素位置,并分析成本查找的平均查找长度。
答案:
该题考查的是查找算法。
算法一:顺序查找
该算法是从表的第一个元素开始顺序地对每一个元素进行比较,直到找到关键字等于k的元素为止。
该算法的成本是:
当查找到目标元素在待查找表的前面时,需要进行n次比较,查找成本为(n+1)/2。
当查找到目标元素在待查找表的后面时,需要进行n次比较,查找成本为n。
当目标元素不存在时,需要进行n次比较,查找成本为(n+1)/2。
因此平均查找长度为:
(n+(n+1)/2)/n= (3n+1)/4
算法二:折半查找
该算法是利用顺序表有序的特点,先将表分成两个部分,然后取中间位置的元素与关键字进行比较,如果相等,直接返回;如果中间位置的元素大于关键字,则在左半部分中继续查找;否则在右半部分中继续查找。
该算法的成本是:
当查找到目标元素时,需要进行k次比较,查找成本为log2n。
当目标元素不存在时,需要进行k次比较,查找成本为log2(n+1)
因此平均查找长度为:
[(log2n+1)/n ]+[(log2(n+1)+1)/n]
=([log2n+log2(n+1)+2]/n)
知识拓展:
平均查找长度是评价查找算法的一个重要指标,它反映了查找算法的效率。在某种意义上,它反映了查找数据所需的平均操作次数。它越小,则说明查找算法越优秀。