精华内容
下载资源
问答
  • 【哈尔滨工业大学2005 四、1(8分)】画出对长度为18的有序的顺序表进行折半查找时的判定树,并指出在等概率时查找成功的平均查找长度,以及查找失败时所需的最多的关键字比较次数。 判定树如下: 图1-1判定树 ...

    写在前边的话:你的支持是我写作的动力,有帮助到你的话麻烦点赞收藏呦。感激不尽!如有错误也请留言指正。

    考研数据结构练习,欢迎订阅我的专辑《考研数据结构题型分类讲解练习》


    【哈尔滨工业大学2005 四、1(8分)】画出对长度为18的有序的顺序表进行折半查找时的判定树,并指出在等概率时查找成功的平均查找长度,以及查找失败时所需的最多的关键字比较次数。

    判定树如下:

    图1-1判定树

     查找成功时的ASL=(1+4+12+32+15)/18=\frac{64}{18}


    查找失败时ASL=(52+30)/19=\frac{82}{19}

    图1-3

    以4*13=52为例,解释一下数字的含义。

    • 4:图中的□代表查找失败的节点,“4*13=52”这行的□需要查找四次。比如,对于16来说,查找到16需要四次,再往下找的时候判断它的左节点为空,而此时也就找到了□。
    • 13:这行一共有13个□需要查找四次
    • 52:这行查找失败的总次数是4*13次

    写在后边的话:你的支持是我写作的动力,有帮助到你的话麻烦点赞收藏呦。感激不尽!如有错误也请留言指正。

    考研数据结构练习,欢迎订阅我的专辑《考研数据结构题型分类讲解练习》

    展开全文
  • 平均查找长度

    千次阅读 2017-06-21 21:05:01
    平均查找长度ASL (Average Search Length)定义为:  ①n是结点的个数; ②Pi是查找第i个结点的概率。若不特别声明,认为每个结点的查找概率相等,即 pl=p2…=pn=1/n ③ci是找到第i个结点所需进行的比较次数。 ...


    平均查找长度ASL (Average Search Length)定义为:


              ①n是结点的个数; ②Pi是查找第i个结点的概率。若不特别声明,认为每个结点的查找概率相等,即  pl=p2…=pn=1/n         ③ci是找到第i个结点所需进行的比较次数。


    1、  顺序查找:逐个比较,顺序/链式存储  平均查找长度:((n+1)/2 )

    2、  折半/二分查找:有序表,确定中间位置,mid = ( left + right )/ 2;比较前后。类二叉树。折半查找成功时进行的比较次数最多不超过树的深度。等概率时,折半查找的平均长度为:当n很大时,ASLbin = log2(n+1)-1

    3、  分块查找:数据按块间有序,分块顺序查找,块内不一定有序. ASLbs = Lb + Lw  

    展开全文
  • 折半查找平均查找长度

    千次阅读 2019-12-23 18:15:08
    建完全二叉树 例如长度为12的有序线性表,构建完全二叉树,如下图: 平均查找长度为:3.1

    建完全二叉树

    例如长度为12的有序线性表,构建完全二叉树,如下图:
    在这里插入图片描述
    平均查找长度为:3.1

    展开全文
  • 散列表查找失败平均查找长度

    千次阅读 多人点赞 2020-11-01 21:04:40
    要想知道 散列表查找失败的平均查找长度,就要知道什么叫做查找失败!举个栗子:8个数字 key%11 如下算好了: 散列地址 0 1 2 3 4 5 6 7 8 9 10 关键字 33 1 13 12...

    如果你看了很多其他博客然后都看不懂看到了这篇,你一定可以容易懂的!我佛了,这么简单的东西死板地讲题目不讲原理鬼看得懂啊,这种风气真的不行,我忍不住想骂一声垃圾,啥玩意儿,误人子弟!原理懂了啥题不会做?

    要想知道 散列表查找失败的平均查找长度,就要知道什么叫做查找失败!举个栗子:8个数字  key%11  如下算好了:

    散列地址 0 1 2 3 4 5 6 7 8 9 10
    关键字 33 1 13 12 34 38 27 22      
    冲突次数 0 0 0 2 3 0 1 7      

    什么叫做查找失败?比如你要查55这个关键字,你必须%11,等于0,查地址0为33,不对,下一位1,不对,继续往下查找直到出现空的才知道这个关键字一定不存在,否则就放在空着的那个地址。所以以上表,计算地址为0的关键字查了9次才才知道没有这个关键字称为查找失败;计算地址为1的关键字只有探测完1-8号才能确定该元素不存在,以此类推。但是注意了,如果计算地址为8的或者9的、10的,只需要查找一次就知道该地址为空,失败了。因此查找一次就行。而且要知道如果查找成功是除以关键字个数,但是查找失败是除以你要模的数字本题是11,千万记住了,不是地址个数,不是关键字个数。综上所述,查找失败的平均查找长度为(9+8+7+6+5+4+3+2+1+1+1)/11=47/11。放心错不了,书上原题。

    还要注意,如下题型H(key)=key%7:

    散列地址 0 1 2 3 4 5 6 7 8
    关键字 98 22 30 87 11 40 6 20  

    千万注意,%7只能映射到0-6,散列函数不可能映射7,因此查找失败平均查找长度为(9+8+7+6+5+4+3)/7=6。看到这你可能想骂娘,啥玩意儿,别急。我会让你看懂,因为我最讨厌虾鸡吧写博客的傻逼玩意儿,写的不清楚又不解释,还误人子弟,low咖!!!好了回归正题。首先要知道,我们求平均查找长度其实在求概率,对于成功的平均查找长度,查找每个元素的概率是1/8,这个8就是关键字个数。就是说,查找成功你只能选择8个中的一个,否则成功不了,所以都是在等概率1/8情况下。查找失败也是一样,这里对每个位置的查找概率都是1/7,注意7是你要模的数字,就是说,你随便拿几个数,模7,只能是0、1、2、3、4、5、6,其中一种情况,不可能是7、8以后的数字,所以只需要计算地址在0-6中的概率。如果计算地址后为0,那么需要比较9次,以此类推,所以只能是上面的计算式子,别搞错了噢!还有要注意有些散列表不是完全填满,中间有空位,那相信你看完上面原理就不用我解释了,找到了空位还没有就说明不存在嘛,否则它就占位这个空位了。注意以上所讨论的全部是线性探测,如果是平方探测注意左右跳动,具体问题具体分析,就不展开了。相信你看到这个已经真正明白了什么叫做查找失败平均查找长度。对于垃圾博客需要狠狠骂,对于我也是,我写的烂的大家给我狠狠骂,这样才能少一些误人子弟的渣渣了,只讲怎么怎么操作不讲原理有什么狗屁用,换个方式描述不还是不会。知其然要知其所以然!!!以上如果有错误,还请大家狠狠指出来,谢谢大家!

    比如这篇博客,真佛了,一来就巴拉巴拉在那算算算,好像谁不会计算散列表似的,人家真正不懂的是查找失败的平均查找长度的计算,真正的标题党。垃圾文章!!!

     

     

     

     

     

     

    展开全文
  • 二分查找的平均查找长度 对二分查找的平均查找长度进行简单分析。 向作出假设:要查找的元素在数组内,数组长度为 nnn. 约定对长度为 nnn 的数组,平均查找长度为随机变量 CnC_nCn​,随机变量 InI_nIn​ 定义如下 ...
  • 查找——平均查找长度

    千次阅读 多人点赞 2017-06-19 11:14:36
    接下来整理一下上面每个方式的平均查找长度顺序表查找ASL如果每个关键字查找概率相同,则ASL = (n+1)/2。 一般都是概率相同。二分查找ASL举例说明:这是一个有序序列(下标和关键字相同): 0 1 2 3 4 初始化:low = ...
  • ASL 平均查找长度

    千次阅读 2018-09-04 08:40:12
    接下来整理一下上面每个方式的平均查找长度 顺序表查找ASL 如果每个关键字查找概率相同,则ASL = (n+1)/2。  一般都是概率相同。 二分查找ASL 举例说明: 这是一个有序序列(下标和关键字相同): 0 1 2 3 4 ...
  • 折半查找判定数及平均查找长度

    万次阅读 多人点赞 2016-07-06 13:28:31
    折半查找判定数及平均查找长度 折半查找的过程看,可用二叉树来描述,二叉树中的每个结点对应有序表中的一个记录,结点中的值为该记录在表中的位置。通常称这个描述折半查找二叉树的过程称为折半查找判定树。 ...
  • 常见的平均查找长度总结

    万次阅读 多人点赞 2019-10-01 15:29:37
    1. 平均查找长度(ASL) pi 是查找到某个元素的概率(probability) ci 是查找到这个元素时已经比较的次数,如,查找在 10 个数中查找第 5 个数,其比较的次数是多少(包括和第 5 个数比较的次数) 2. 顺序查找的...
  • 平均查找长度 ASL(Average Search Length),即平均查找长度,在查找运算中,由于所费时间在关键字的比较上,所以把平均需要和待查找值比较的关键字次数称为平均查找长度。 它的定义是这样的: 其中n为查找表中元素...
  • 平均查找长度详解

    万次阅读 多人点赞 2016-04-11 21:49:42
    平均查找长度:ASL = (n+....+2+1)/n= (n+1)/2。 2.二分法查找: 前提是线性表是有序表。假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值等于x,则查找成功;若x小于当前位置值,...
  • 哈希表平均查找长度

    万次阅读 多人点赞 2017-08-13 10:53:31
    题目:关键字序列为:{38,25,74,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。注:没给哈希表长度,给出装填因子时,可求哈希...
  • 数据结构几种平均查找长度

    千次阅读 2020-04-16 17:39:35
    数据结构几种平均查找长度 总结的有关数据结构中平均查找长度ASL的三种计算小技巧: 1.顺序查找法的平均查找长度为:(n+1)/2 2.散列表的查找成功和查找不成功的平均查找长度 技巧(线性探测法和链地址法): ...
  • 哈希表的平均查找长度

    千次阅读 2017-08-03 15:34:17
    查找成功时的平均查找长度 查找不成功时的平均查找长度 http://www.doc88.com/p-903238204265.html
  • 关于平均查找长度 ASL 可以建一颗二叉树,解决一些对数列进行二分查找的问题 eg: 对有序数组 5 13 19 21 37 56 64 75 88 92 100 进行二分查找,等概率的情况下,查找成功的**平均查找长度(平均比较次数)**是??? ...
  • 首先,推荐两个写的很好的关于哈希表查找——成功和不成功时的平均查找长度的博客,感谢分享! https://blog.csdn.net/longlovefilm/article/details/78009782 ... 尤其需要注意哈希表查找不成功时的平均查找长度。...
  • 散列表查找失败时的平均查找长度

    千次阅读 2021-01-14 20:54:40
    在利用线性探测再散列法处理冲突的散列表中,很多人对计算失败时的平均查找长度,作除数应该是散列表长,还是散列函数:mod后面的数不清楚,首先接下来我们先解决这一问题. 问题一:其除以的数是mod后面的数还是散列表长? ...
  • 哈希表的平均查找长度可以为0吗,老师上课说可以,说是不用比较,但我感觉至少也要1啊
  • Hash表的平均查找长度包括查找成功时的平均查找长度和查找失败时的平均查找长度。  查找成功时的平均查找长度=表中每个元素查找成功时的比较次数之和/表中元素个数; 查找不成功时的平均查找长度相当于在表中查找...
  • 一、链地址法在等概率下查找成功和查找不成功的平均查找长度:将关键字序列{1 13 12 34 38 33 27 22} 散列存储到散列表中。散列函数为:H(key)=key mod 11,处理冲突采用链地址法,求在等概率下查找成功和查找不成功...
  • 如何计算哈希表查找失败时的平均查找长度

    万次阅读 多人点赞 2020-04-30 18:20:01
    1.请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败时的平均查找长度如何计算? 例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为:H(key)=keyMOD13,哈希表长为m=15,设每个记录...
  • 散列表的平均查找长度

    万次阅读 多人点赞 2018-01-16 15:13:14
    等概率情况下查找成功平均查找长度 等概率情况下查找不成功的平均查找长度 题目要求 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列...
  • 求折半查找成功时的平均查找长度

    千次阅读 2019-02-14 09:30:30
    * 求折半查找成功时的平均查找长度 * 实验目的: * 深入掌握折半查找过程和折半查找算法分析 * 实验内容: * 设计程序,建立有序序列R[0...n-1]进行二分查找产生的判断树, * 在此基础上完成如下功能: * 1、输出n=11时...
  • 关于二叉排序树的平均查找长度的计算

    万次阅读 多人点赞 2020-02-10 14:41:29
    查找成功的情况下: 第一层结点:一个 查找了一次 第二层结点:二个 每个查找两次 第三层结点:四个 每个查找三...所以查找成功情况下的平均查找长度是: 查找失败的情况下: 查找失败情况下的平均查找长度是: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 93,563
精华内容 37,425
关键字:

平均查找长度最好