求上述问题查找失败时候的平均查找长度
时间: 2023-12-22 16:29:39 浏览: 114
根据引用[1]中的计算方法,查找失败的平均查找长度可以通过依次减少层数来计算。假设原先有12层,每层的结点数分别为1、2、4、5、6、7、8、9、10、11、12、13。那么计算过程如下:
第一层:12x1 = 12
第二层:11x2 = 22
第三层:10x4 = 40
第四层:9x5 = 45
第五层:8x6 = 48
第六层:7x7 = 49
第七层:6x8 = 48
第八层:5x9 = 45
第九层:4x10 = 40
第十层:3x11 = 33
第十一层:2x12 = 24
第十二层:1x13 = 13
总共的查找失败次数为12+22+40+45+48+49+48+45+40+33+24+13 = 419
总共的层数为12
所以,查找失败的平均查找长度为419/12 = 34.92
相关问题
上述例子查找失败的平均查找长度
根据引用[1]和引用的内容,我们可以得出以下计算查找失败的平均查找长度的公式:
查找失败的平均查找长度 = P0*0 + P1 * 1 + P2 * 2 + P3 *2 + … + Pn * n
其中,P0表示查找失败的概率,即在哈希表中没有找到待查元素的概率;P1表示查找失败后需要查找的次数为1的概率,以此类推,Pn表示查找失败后需要查找的次数为n的概率。
根据引用中的描述,我们可以得出P0、P1、P2、...、Pn的计算公式:
P0 = (1 / 查找失败可能落在的位置总个数) * 第0层的查找失败可能落在的位置个数
P1 = (1 / 查找失败可能落在的位置总个数) * 第1层的查找失败可能落在的位置个数
P2 = (1 / 查找失败可能落在的位置总个数) * 第2层的查找失败可能落在的位置个数
...
Pn = (1 / 查找失败可能落在的位置总个数) * 第n层的查找失败可能落在的位置个数
因此,我们需要先计算出查找失败可能落在的位置总个数,以及每一层查找失败可能落在的位置个数。然后,根据上述公式,计算出查找失败的平均查找长度。
具体的计算方法可以参考引用和引用中的内容。
数据结构散列表查找失败的平均查找长度
散列表的查找失败的平均查找长度是指在查找一个不存在的关键字时,需要比较的平均次数。在散列表中采用线性探查法解决冲突的情况下,查找失败的平均查找长度可以通过以下公式计算:
(L / 2) * (1 + (1 / (1 - L)))
其中,L是装载因子,表示填入散列表的元素个数与散列表长度的比值。
根据引用中给出的信息,关键字序列87,40,30,6,11,22,98,20依次插入散列表HT后,可以计算出装载因子L为8/11。将L带入上述公式,可以得出查找失败的平均查找长度为11/3。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)