• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    5年前 (2013-04-11)  笔试面试 |   5 条评论  17 
    文章评分 0 次,平均分 0.0

    为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(Average Search Length),ASL成功。
    对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL=∑PiCi (i=1,2,3,…,n),可以简单以数学上的期望来这么理解。其中:Pi 为查找表中第i个数据元素的概率,Ci为找到第i个数据元素时已经比较过的次数。
    在查找表中查找不到待查元素,但是找到待查元素应该在表中存在的位置的平均查找次数称为查找不成功时的平均查找长度,ASL不成功。

    比如:

    已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key) = key%7计算散列地址,并散列存储在散列表A【0....6】中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为(C

    A、1.5                  B、1.7                           C、2.0                       D、2.3

    依次进行取模运算求出哈希地址:

     

    A

    0

    1

    2

    3

    4

    5

    6

    记录

    63

    48

    38

    25

    74

    52

    查找次数

    1

    3

    1

    1

    2

    4

     

     

    74应该放在下标为4的位置,由于25已经放在这个地方,所以74往后移动,放在了下标为5的位置上了。

    由于是等概率查找,所以结果为:1/6*(1+3+1+1+2+4)= 2.0

     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/538.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享