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

    问题描述

    对于长度为 99 的顺序存储的有序表 1,2,3,4,5,6,7,8,9{1, 2, 3, 4, 5, 6, 7, 8, 9} ,若采用二分查找,求平均查找长度。

    分析

    值得注意的是,每次减治缩范围后新的 leftleftrightright 不等于 midmid,下面简单分析一下:

    • 第一步,left=1,right=9,mid=(1+9)/2=5left=1, right=9, mid=(1+9)/2=5
      • 第二步,left=1,right=51=4,mid=(1+4)/2=2left=1, right=5-1=4, mid=(1+4)/2=2
        • 第三步,left=1,right=21=1,mid=(1+1)/2=1left=1, right=2-1=1, mid=(1+1)/2=1
        • 第三步,left=2+1=3,right=4,mid=(3+4)/2=3left=2+1=3, right=4, mid=(3+4)/2=3
          • 第四步,left=3+1=4,right=4,mid=(4+4)/2=4left=3+1=4, right=4, mid=(4+4)/2=4
      • 第二步,left=5+1=6,right=9,mid=(6+9)/2=7left=5+1=6, right=9, mid=(6+9)/2=7
        • 第三步,left=6,right=71=6,mid=(6+6)/2=6left=6, right=7-1=6, mid=(6+6)/2=6
        • 第三步,left=7+1=8,right=9,mid=(8+9)/2=8left=7+1=8, right=9, mid=(8+9)/2=8
          • 第四步,left=8+1=9,right=9,mid=(9+9)/2=9left=8+1=9, right=9, mid=(9+9)/2=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        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

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

    展开全文
  • 设散列表长度为8,散列函数H(k)=k mod 7,初始记录关键字序列为(25,31,8,27,13,68),要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。 答案分别为7/6 和 4/3 但是链地址法算出来觉得也...
  • 请画出按照线性探测再散列处理冲突得到哈希表(给出求解过程),并计算查找成功和查找失败时的平均查找长度各是多少。 请画出按照链地址法处理冲突得到哈希表,并计算查找成功和查找失败时的平均查找长度各是...

    给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79)

    1. 题目要求

    哈希函数为:H(key)=key % 13, 哈希表长为m=15,设每个记录的查找概率相等。

    1. 请画出按照线性探测再散列处理冲突得到的哈希表(给出求解过程),并计算查找成功和查找失败时的平均查找长度各是多少。

    2. 请画出按照链地址法处理冲突得到的哈希表,并计算查找成功和查找失败时的平均查找长度各是多少。

    1. 解题思路

    2.1 线性探测

    哈希表长为m=15;
    分别得到的结果进行线性探测散列排列:
    

    在这里插入图片描述
    冲突的关键字按照关键字的原始排序进行向后的推移
    图中的冲突的关键字“1”他的现地址为1,但这个位置上已经被关键字“14”所占领,遇到了冲突,探测下一个位置2,位置2上没有关键字,放入即可;
    在这里插入图片描述
    关键字“84”在原始的关键字中排列在前,他现在的地址为6,但这个位置已经被关键字“19”占领,遇到了冲突,探测下一个地址7,但这个位置上也已经被关键字“20”占领,继续探测下一个地址8,位置8上没有关键字,放入即可;
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述在这里插入图片描述
    循环执行,到了这一步所有的关键字都已经填入哈希表,散列表的构造已经完成
    在这里插入图片描述
    注:散列表的比较次数与关键字在哈希表中插入位置的次数有关,
    查找成功的平均查找长度为:
    ASL=(1+1+2+1+3+4+1+1+2+1+1+2)/12
    在这里插入图片描述
    查找不成功的平均查找长度为:
    ASL=(10+9+8+7+6+5+4+3+2+1+2+3+4)/13

    注意:
    区别概念平均成功查找次数和平均不成功查找次数。
    平均成功查找次数=每个关键词比较次数之和÷关键词的个数
    平均不成功查找次数=每个位置不成功时的比较次数之和÷表长(所谓每个位置不成功时的比较次数就是在除余位置内,每个位置到第一个为空的比较次数。

    2.2链式地址法:

    在这里插入图片描述
    成功时平均查找次数:(1X5+2X4+3X1+4X1)/12=5/3
    失败时平均查找次数:(4+2+2+1+2+1)/11 =1

    注意:链地址法成功时查找次数的分母是哈希表元素的个数,分子为纵向比较;
    失败时,分母为哈希表的长度,分子为横向比较(几个);

    展开全文
  • 请画出按照线性探测再散列处理冲突得到哈希表(给出求解过程),并计算查找成功和查找失败时的平均查找长度各是多少。 请画出按照链地址法处理冲突得到哈希表,并计算查找成功和查找失败时的平均查找长度各是...

    给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79)

    哈希函数为:H(key)=key % 13, 哈希表长为m=15,设每个记录的查找概率相等。

    1. 请画出按照线性探测再散列处理冲突得到的哈希表(给出求解过程),并计算查找成功和查找失败时的平均查找长度各是多少。

    2. 请画出按照链地址法处理冲突得到的哈希表,并计算查找成功和查找失败时的平均查找长度各是多少。

    关键字除以13取余后分别得到:6,1,10,1,0,7,6,1,3,11,10,1

    线性探测:

    在这里插入图片描述

    成功时的平均查找次数:(1+1+2+3+2+4+1+1+3+1+1+3)/12 = 23/12

    在这里插入图片描述

    失败时的平均查找次数:(10+9+8+7+6+5+4+3+2+1+4+3+2)/ 13 = 64/13

    链地址法:

    0—>65

    1—>14,1,27,79

    2

    3—>55

    4

    5

    6—>19, 84

    7—>20

    8

    9

    10—>23,10

    11—>11

    总查找次数: 1+1+2+3+4+1+1+2+1+1+2+1=20

    成功时的平均查找次数:20/12=5/3

    失败时的平均查找次数:(4+1+2+1+2+1)/ 11 = 1

    展开全文
  • 请画出按照线性探测再散列处理冲突得到哈希表(给出求解过程),并计算查找成功和查找失败时的平均查找长度各是多少。 请画出按照链地址法处理冲突得到哈希表,并计算查找成功和查找失败时的平均查找长度各是...
  • 数据结构总结.docx

    2020-05-12 21:25:48
    二叉树遍历赫夫曼编码问题二叉树线索化可能会画图图遍历深度广度B树插入删除哈希表处理冲突方法开放定址法三种以及计算平均查找长度二...求解拓扑排序各种排序算法性能比较二分查找赫顺序查找的平均查找长度...
  • 最优二叉检索树

    2017-10-01 22:09:26
    定义:平均查找长度最小二叉检索树,又叫最优二分检索树。 动态规划求解,递推式证明如下: 一个实例:
  • 这道题让我们求两个有序数组中位数,而且限制了时间复杂度为O(log (m+n)),看到这个时间复杂度,自然而然想到了应该使用二分查找法来求解。那么回顾一下中位数定义,如果某个有序数组长度是奇数,那么其中位数...
  • 75,63,48,94,25,36,18},哈希地址空间为[0…10],采用哈希函数H(key)=key MOD 11,用二次探测再散列法处理冲突,试给出对应哈希表(给出求解过程),并计算在等概率情况下查找成功时的平均查找长度 ...
  • 这道题让我们求两个有序数组中位数,而且限制了时间复杂度为O(log (m+n)),看到这个时间复杂度,自然而然想到了应该使用二分查找法来求解。那么回顾一下中位数定义,如果某个有序数组长度是奇数,那么其中位数...
  • LINGO软件学习

    2009-08-08 22:36:50
    LINGO内置了一种建立最优化模型的语言,可以简便地表达大规模问题,利用LINGO高效的求解器可快速求解并分析结果。 §1 LINGO快速入门 当你在windows下开始运行LINGO系统时,会得到类似下面的一个窗口: ...
  • 本书特色有二,旨在提高读者问题求解能力,使读者能够理解算法设计过程和思想:一是强调算法设计创造性过程,注重算法设计背后创造性思想,而不拘泥于某个具体算法详细讨论;二是将算法设计类比于定理...
  • 实例159 创建长度可变数组 实例160 利用反射重写toString()方法 实例161 反射与动态代理 7.3 常见未检查型异常 实例162 算数异常 实例163 数组存值异常 实例164 数组下标越界异常 实例165 空指针异常 ...
  • 实例159 创建长度可变数组 实例160 利用反射重写toString()方法 实例161 反射与动态代理 7.3 常见未检查型异常 实例162 算数异常 实例163 数组存值异常 实例164 数组下标越界异常 实例165 空指针异常 ...
  • 数据结构课设

    2013-01-03 02:51:25
    利用直接插入排序、希尔排序,冒泡排序、快速排序、选择排序、堆排序,归并排序(递归和非递归),基数排序八种排序方法进行排序(结果为由小到大顺序),并统计每一种排序所耗费的平均时间 二、选做题。 1、 ...
  • 用例20:计算单元格区域数据开三次方后的平均值(POWER) 源文件:光盘\源文件\03\032.xlsx 用例21:求不同单价下利润(MMULT) 源文件:光盘\源文件\03\033.xlsx 用例22:设计工资条(MOD) 源文件:光盘\...
  • 实例159 创建长度可变数组 206 实例160 利用反射重写toString()方法 208 实例161 反射与动态代理 209 7.3 常见未检查型异常 210 实例162 算数异常 210 实例163 数组存值异常 211 实例164 数组下标越界异常 212 ...
  • 实例159 创建长度可变数组 206 实例160 利用反射重写toString()方法 208 实例161 反射与动态代理 209 7.3 常见未检查型异常 210 实例162 算数异常 210 实例163 数组存值异常 211 实例164 数组下标越界异常 212 ...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    问题求解步骤描述 C.要满足五个基本特性 D.A和 C. 5. 下面关于算法说法错误是(D )【南京理工大学 2000 一、1(1.5分)】 A.算法最终必须由计算机程序实现 B.为解决某问题算法同为该问题编写程序含义...
  • 9.8 查找表 240 9.9 空值 242 9.10 使用Model子句进行性能调优 243 9.10.1 执行计划 243 9.10.2 谓语前推 246 9.10.3 物化视图 247 9.10.4 并行 249 9.10.5 Model子句执行中分区 250 9.10.6 索引 251 ...
  • 9.8 查找表 240 9.9 空值 242 9.10 使用Model子句进行性能调优 243 9.10.1 执行计划 243 9.10.2 谓语前推 246 9.10.3 物化视图 247 9.10.4 并行 249 9.10.5 Model子句执行中分区 250 9.10.6 索引 251 ...

空空如也

空空如也

1 2
收藏数 24
精华内容 9
关键字:

平均查找长度的求解