精华内容
下载资源
问答
  • 二分查找平均查找长度求解示例

    问题描述

    对于长度为 9 9 9 的顺序存储的有序表 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 {1, 2, 3, 4, 5, 6, 7, 8, 9}

    展开全文
  • 哈希表查找——成功和不成功时的平均查找长度

    万次阅读 多人点赞 2017-09-17 13:27:21
    哈希表查找——成功和不成功时的平均查找长度 以下求解过程是按照“计算机统考的计算方法”,不同的老师、教材在“处理冲突”上可能会有不同的方法,所以最主要的是掌握原理即可,对于考研的朋友最好掌握统考...

    哈希表查找——成功和不成功时的平均查找长度


    以下求解过程是按照“计算机统考的计算方法”,不同的老师、教材在“处理冲突”上可能会有不同的方法,所以最主要的是掌握原理即可,对于考研的朋友最好掌握统考真题的解题方法。

    题目

    例子:(2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题第一题

    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。
    (1) 请画出所构造的散列表;
    (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。

    1.散列表:

              α = 表中填入的记录数/哈希表长度    ==>  哈希表长度 = 7/0.7 = 10
                H(7) = (7x3) MOD 7 = 0           H(8) = (8x3) MOD 7 = 3           H(30) = (30x3) MOD 7 = 6
                H(11) = (11x3) MOD 7 = 5       H(18) = (18x3) MOD 7 = 5       H(9) = (9x3) MOD 7 = 6
                H(14) = (14x3) MOD 7 = 0
               按关键字序列顺序依次向哈希表中填入,发生冲突后按照“线性探测”探测到第一个空位置填入。

      
    0123456789
    71481130189

    2.查找长度:

            2.1 查找成功的平均查找长度

           (待查找的数字肯定在散列表中才会查找成功)

            查找数字A的长度 = 需要和散列表中的数比较的次数;
           步骤:
                    比如 查找数字:8
                    则  H(8) = (8x3) MOD 7 = 3
                    哈希表中地址3处的数字为8,进行了第一次比较:8 = 8,则查找成功,查找长度为1;
                    比如查找数字:14
                    则 H(14) = (14x3) MOD 7 = 0
                    哈希表中地址0处的数字为7,进行第一次比较:7≠14
                    哈希表中地址1处的数字为14,进行第二次比较:14=14 ,则查找成功,查找长度为2。                             
    由此可得到如下数据:【2016年12月26日修改,多谢@一楼的朋友指正】

         
    0123456789
    71481130189
    1211133
    所以总的查找成功的平均查找长度= (1+1+1+1+3+3+2)/7 = 12/7

    2.2查找不成功的平均查找长度

    (待查找的数字肯定不在散列表中)

    【解题的关键之处】根据哈希函数地址为MOD7,因此任何一个数经散列函数计算以后的初始地址只可能在0~6的位置
                    查找0~6位置查找失败的查找次数为:
    
                地址0,到第一个关键字为空的地址2需要比较3次,因此查找不成功的次数为3.      
                地址1,到第一个关键字为空的地址2需要比较2次,因此查找不成功的次数为2.
                地址2,到第一个关键字为空的地址2需要比较1次,因此查找不成功的次数为1.
      地址3,到第一个关键字为空的地址4需要比较2次,因此查找不成功的次数为2.
      地址4,到第一个关键字为空的地址4需要比较1次,因此查找不成功的次数为1.
      地址5,到第一个关键字为空的地址2(比较到地址6,再循环回去)需要比较5次,因此查找不成功的次数为5.
      地址6,到第一个关键字为空的地址2(比较到地址6,再循环回去)需要比较4次,因此查找不成功的次数为4.
    于是得到如下数据:
        
    0123456789
    71481130189
    3212154
    则查找不成功的平均查找长度 = (3+2+1+2+1+5+4)/7 = 18/7

    哈希表——线性探测法、链地址法、查找成功、查找不成功的平均长度

    四、哈希表的装填因子

    装填因子 = (哈希表中的记录数) /  (哈希表的长度)

    装填因子是哈希表装满程度的标记因子。值越大,填入表中的数据元素越多,产生冲突的可能性越大。

    五、不同处理冲突的平均查找长度

    技术分享

     

    例:

    假设散列表的长度是13,三列函数为H(K) = k % 13,给定的关键字序列为{32, 14, 23, 01, 42, 20, 45, 27, 55, 24, 10, 53}。分别画出用线性探测法和拉链法解决冲突时构造的哈希表,并求出在等概率情况下,这两种方法的查找成功和查找不成功的平均查找长度。

    (1)线性探测法:

    技术分享

    查找成功时的查找次数等于插入元素时的比较次数, 查找成功的平均查找长度为:

    ASL = (1+2+1+4+3+1+1+3+9+1+1+3)/12 = 2.5

    查找成功时的查找次数:第n个位置不成功时的比较次数为:第n个位置到第1个没有数据位置的距离如第0个位置取值为1,第11个位置取值为3,第12个位置取值2

    查找不成功的平均查找次数为:

    ASL = (1+13+12+11+10+9+8+7+6+5+4+3 + 2)/ 13 = 91/13

    哈希表查找不成功怎么计算? 解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数

    例如:散列函数为hash(x)=x MOD 11,用线性探测,建立了哈希表之后,如何求查找不成功时的平均查找长度!?

           地址:0     1    2    3    4    5    6    7    8    9    10       数据:33     1    13   12  34    38   27   22   -   -   -    成功次数:1     1    1    3    4    1    2    8  不成功次数:9     8    7    6    5    4    3    2    1    1    1

    查找成功时的平均查找长度:ASL=(1+1+1+3+4+1+2+8)/8 =47/8 查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+1)/11

    说明

    第n个位置不成功时的比较次数为,第n个位置到第1个没有数据位置的距离。

      如:第0个位置到第1个没有数据位置(8)的距离为9!

    (1) 开放定址法
    地址: 0    1    2    3    4    5    6    7    8    9    10    11    12        
    数据: 39   12   28   15   42   44    6   25   -   -    36    -    38    
    成功次数: 1    3    1    2    2    1    1    9                        1           
    不成功次数: 9    8    7    6    5    4    3    2    1    1      2    1      10 
    查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2 
    查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54

    (2)链地址法

    java中的hashMap就是这样一种链表+数组的数据结构,查找方法很简单,先利用散列函数(一般是取余数的方法)定位数组具体哪个点,比如1就是余数为1的点的链表中,然后再遍历链表查找具体数值的位置,如,果是53,那就在链表的第四位置,需要查找四次;同理,27就需要查找3次!

    技术分享

    查找成功时的平均查找长度:

    ASL = (1*6+2*4+3*1+4*1)/12 = 7/4

    查找不成功时的平均查找长度:

    ASL = (4+2+2+1+2+1)/13

    注意:查找成功时,分母为哈希表元素个数,查找不成功时,分母为哈希表长度。

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

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

    题目要求

    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。
    (1) 请画出所构造的散列表。
    (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。

    解题分析

    (1).首先明确一个概念装载因子,装载因子是指所有关键子填充哈希表后饱和的程度,它等于 关键字总数/哈希表的长度。 根据题意,我们可以确定哈希表的长度为 L = 7/0.7 = 10;因此此题需要构建的哈希表是下标为0~9的一维数组。根据散列函数可以得到如下散列函数值表

    这里写图片描述

    下面对散列表的构造方式加以说明,注意表1中的关键字7和14,30和9, 11和18,这三组关键子的H(Key)值相同,这在构建散列表时就会产生冲突,因为他们的地址相同,所以要通过一定的冲突处理方法来解决这个问题。依题,采用线性探测再散列法处理冲突。下面详细介绍如何构建散列表:

    第一个key 7,它的地址是0,因此放到散列表的数组下表为0的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

    第二个key 8,它的地址是3,因此放到散列表的数组下表为3的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

    第三个key 30,它的地址是6,因此放到散列表的数组下表为6的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

    第四个key 11,它的地址是5,因此放到散列表的数组下表为5的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

    第五个key 18,它的地址是5,因此放到散列表的数组下表为5的位置,但这个位置上已经有关键字11,遇到了冲突,此时我们根据线性探测再散列法来处理这个冲突,探测下一个位置6, 6这个位置上已经存在关键字30则继续增加步长1,因此现在的新地址应为7,位置7上没有关键字,放入即可,到此冲突已经解决;

    第六个key 9,它的地址是6,因此放到散列表的数组下表为6的位置,但这个位置上已经有关键字30,遇到了冲突,探测下一个位置7, 7这个位置上已经存在关键字18则继续增加步长1,因此现在的新地址应为8,位置8上没有关键字,放入即可;

    第七个key 14,它的地址是0,因此放到散列表的数组下表为0的位置,但这个位置上已经有关键字7,遇到了冲突,探测下一个位置1, 位置1上没有关键字,放入即可;

    等概率情况下查找成功平均查找长度:

    这一问可以根据第一问的构造过程求解:

    key7一次就填入了表中,因此查找次数为1,同理8, 30, 11查找次数均为1; key18 进行了3次放入操作,探测位置分别是5,6,7 ,因此查找次数为3;key9也是3次;key14 进行了两次探测,因此查找次数为2。

    次数表如表3所示
    这里写图片描述(成功除以关键字个数)

    等概率情况下查找不成功的平均查找长度:

    接下来讨论不成功的情况, 看表2,
    计算查找不成功的次数就直接找关键字到出现的第一个地址上关键字为空的距离即可, 但根据哈希函数地址为MOD7,因此初始只可能在0~6的位置。等概率情况下,查找0~6位置查找失败的查找次数为:(算本身)

    看地址0,到第一个关键字为空的地址2的距离为3,因此查找不成功的次数为3.

    地址1, 到第一个关键为空的地址2的距离为2,因此查找不成功的次数为2.

    地址2, 到第一个关键为空的地址2的距离为1,因此查找不成功的次数为1.

    地址3,到第一个关键为空的地址4的距离为2,因此查找不成功的次数为2.

    地址4,到第一个关键为空的地址4的距离为1,因此查找不成功的次数为1.

    地址5,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为5,因此查找不成功的次数为5.

    地址6,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为4,因此查找不成功的次数为4.

    这里写图片描述(不成功除以的是模数)

    展开全文
  • 设散列表的长度为8,散列函数H(k)=k mod 7,初始记录关键字序列为(25,31,8,27,13,68),要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。 答案分别为7/6 和 4/3 但是链地址法算出来觉得也...
  • 最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。 例题: 将关键字序列(7、8、30、11、...

    最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。

     

    例题:

    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。

    (1)请画出所构造的散列表。

    (2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。

     

    (1)首先明确一个概念:装载因子。装载因子是指所有关键子填充哈希表后饱和的程度,它等于 填入表中的关键字总数/哈希表的长度

    根据题意,我们可以确定哈希表的长度为 L = 7/0.7 = 10;因此此题需要构建的哈希表是下标为0~9的一维数组。

     

    这里采用线性探测再散列法处理冲突,构造散列表。

           H(7) = (7x3) MOD 7 = 0,地址为0,因此放到散列表的数组下表为0的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

           H(8) = (8x3) MOD 7 = 3,地址是3,因此放到散列表的数组下表为3的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

           H(30) = (30x3) MOD 7 = 6,地址是6,因此放到散列表的数组下表为6的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

           H(11) = (11x3) MOD 7 = 5,地址是5,因此放到散列表的数组下表为5的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

           H(18) = (18x3) MOD 7 = 5,地址是5,因此放到散列表的数组下表为5的位置,但这个位置上已经有关键字11,遇到了冲突,此时我们根据线性探测再散列法来处理这个冲突,探测下一个位置6,6这个位置上已经存在关键字30则继续增加1,因此现在的新地址应为7,位置7上没有关键字,放入即可,到此冲突已经解决;

           H(9) = (9x3) MOD 7 = 6,地址是6,因此放到散列表的数组下表为6的位置,但这个位置上已经有关键字30,遇到了冲突,探测下一个位置7,7这个位置上已经存在关键字18则继续增加1,因此现在的新地址应为8,位置8上没有关键字,放入即可;   

           H(14) = (14x3) MOD 7 = 0,地址是0,因此放到散列表的数组下表为0的位置,但这个位置上已经有关键字7,遇到了冲突,探测下一个位置1,位置1上没有关键字,放入即可;   

           到这一步所有关键字均已填入,散列表已经构造完成,如下表所示。

    地址0123456789
    关键字714 8 1130189 

     

    (2)等概率情况下查找成功平均查找长度:

            这一问可以根据第一问的构造过程求解:

            key7 一次就填入了表中,因此查找次数为1,同理8, 30, 11查找次数均为1;

            key18 进行了三次探测操作,探测位置分别是5,6,7 ,因此查找次数为3;

            key9 也是三次;

            key14 进行了两次探测,因此查找次数为2。次数如下表所示:

    地址0123456789
    关键字714 8 1130189

     

    成功次数12 1 1133 

       

            所以ASLsuccess= (1+2+1+1+1+3+3)/ 7 = 12/7。  

           

            接下来讨论不成功的情况,计算查找不成功的次数就直接找关键字到下一个地址关键字为空的距离即可,但根据散列函数地址为MOD7,因此初始只可能在0~6的位置。

            等概率情况下,0~6位置查找失败的查找次数为:

            地址0,到第一个关键字为空的地址2的距离为3,因此查找不成功的次数为3;

            地址1,到第一个关键字为空的地址2的距离为2,因此查找不成功的次数为2;

            地址2,到第一个关键字为空的地址2的距离为1,因此查找不成功的次数为1;

            地址3,到第二个关键字为空的地址4的距离为2,因此查找不成功的次数为2;

            地址4,到第二个关键字为空的地址4的距离为1,因此查找不成功的次数为1;

            地址5,到第三个关键字为空的地址9的距离为5,因此查找不成功的次数为5;

            地址6,到第三个关键字为空的地址9的距离为4,因此查找不成功的次数为4;

            注意地址7、8、9不用看。

            因此查找不成功的次数表如下表所示:

    地址0123456789
    关键字714 8 1130189

     

    失败次数3212154   


           所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。

    展开全文
  • 哈希算法的平均查找长度计算

    万次阅读 多人点赞 2017-07-29 23:21:54
    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。  Ans:  (1).首先明确一个概念装载因子,装载因
  • 哈希表等概率情况下查找成功和查找不成功的平均查找长度的计算 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅...
  • 比较次数如何求阿 求解
  • 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。 下面看下2010年...
  • (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 Ans: (1).首先明确一个概念装载因子,装载因子是指所有关键子填充哈希表后饱和的程度,它等于 关键字总数/哈希表的长度。 根据题意,我们可以确定...
  • Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 Ans: (1).首先明
  • 查找不成功的平均查找次数为: ASL = (1+2+3+4+5+6+7+8+9+10+11+12)/ 13 = 91/13 (2)链地址法 查找成功时的平均查找长度: ASL = (16+24+31+41)/12 = 7/4 查找不成功时的平均查找长度: ASL = (4+2+2+1+2+1)/13...
  • (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 Ans: (1).首先明确一个概念装载因子,装载因子是指所有关键子填充哈希表后饱和的程度,它等于 关键字总数/哈希表的长度。 根据题意,...
  • ⑵分别计算等概率情况下查找成功和查找不成功的平均查找长度。   1) H(Key) = (keyx3) MOD 7, 例如key=7时, H(7) = (7x3)%7 = 21%7=0,其他关键字同理。 Key 7 8 30 11 18...
  • 学习目录介绍C语言回顾学习-N1概述具体实例实例分析功能分析各功能实现方式全局变量定义以及预编译代码数据录入功能数组元素的查询和删减和打印功能数组元素的平均值求取动态分配数组元素大小(malloc、free)代码...
  • 设排好序的数组长度n,计算二分法查找的最好时间复杂度,最坏时间复杂度以及平均时间复杂度。
  • 分治法求解查找问题

    千次阅读 2020-03-14 10:22:14
    分治法求解查找问题查找最大和次大元素问题描述问题求解代码算法分析折半查找基本思路代码算法分析寻找一个序列中第k小元素问题描述问题求解代码算法分析寻找两个等长有序序列的中位数问题描述问题求解代码算法分析 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,277
精华内容 2,510
关键字:

平均查找长度的求解