数据结构:哈希表平均长度,给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79) 哈希函数为:H(key)=key % 13, 哈希表长为m=15,设每个记录的查找_哈希函数h(key)=key%13 和线性探测法处理冲突构造哈希表,并求出在等概率情况下的-程序员宅基地

技术标签: 经验分享  数据结构and算法and日常问题  

目录

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

线性探测法例题

链地址法例题

网上一些博客错误的指正


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

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

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

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

ps:老师改题啦,原来和下面的那题是一样的,题目任你改做不出算我输,哈哈哈(低调低调)

由第一个H(19) = 19MOD 13 =  6以此类推

19 14 23 1 68 20 84 27 55 11 10 79
6 1 10 1 0 7 6 1 3 11 10 1

可以得到散列表为

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
65 14 1 21 55 79 19 78 84   23 11 10    

 

key 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
count 1 1 2 3 2 5 1 1 3   1 1 3    

查找成功的平均长度:(1+1+2+3+2+5+1+1+3+1+1+3)÷12 = 24/12 = 2; 

key 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
count 10 9 8 7 6 5 4 3 2 1 4 3 2    

查找失败得平均长度:(10+9+8+7+6+5+4+3+2+1+4+3+2)÷13 = 64/13;

(2)

链地址法:

查找成功的平均长度:(1×7+2×3+3×1+4×1)÷12 = 20/12=5/3;

查找失败的平均长度:(2+5+1+2+1+1+3+2+1+1+3+2+1)÷13 = 25/13; 

 

 

请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败时的平均查找长度如何计算?

例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)

       哈希函数为:H(key)=key MOD 13, 哈希表长为m=15,

       设每个记录的查找概率相等,采用以上两种方法处理冲突,查找失败时的平均查找长度各是多少

 

 这题可真得是出到点子上去啦,看视频,找资料,网上有得解释真的是有点误人子弟,随后加上问了老师一番才有了确定的结果

没错我们主要得难点还是查找失败得分母到底是什么呢,还有一个网上解释错得,但广为流传得,

但是还是全部体系得去写吧毕竟也许以后就忘了

线性探测

(1)

有第一个H(19) = 19MOD 13 =  6,后面得以此类推,

19 14 23 1 68 20 84 27 55 11 10 79
6 1 10 1 3 7 6 1 3 11 10 1

可以得到散列表为

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
  14 1 68 27 55 19 20 84 79 23 11 10    

 

key 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
count   1 2 1 4 3 1 1 3 9 1 1 3    

查找成功的平均长度:(1+2+1+4+3+1+1+3+9+1+1+3)÷12 = 30/12 = 2.5; 

 

key 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
count 1 13 12 11 10 9 8 7 6 5 4 3 2    

查找失败得平均长度:(1+13+12+11+10+9+8+7+6+5+4+3+2)÷13 = 7

 

 

ps:查找失败得平均长度分母是MOD后面得数也就是13

(2)

链地址法:

查找成功的平均长度:(1×6+2×4+3×1+4×1)÷12 = 21/12;

查找失败的平均长度:(1+5+1+3+1+1+3+2+1+1+3+2+1)÷13 = 25/13; 

ps:它的分母也是mod后面的数13 ,并且查的范围是0-12

 

线性探测法例题

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

当时由于老师让及时做出来,就有点匆忙,能懂哪个意思就行

链地址法例题

题目
将关键字序列{1 13 12 34 38 33 27 22} 散列存储到散列表中。散列函数为:H(key)=key mod 11,处理冲突采用链地址法,求在等概率下查找成功和查找不成功的平均查找长度

1mod11=1,所以数据1是属于地址1
13mod11=2,所以数据13是属于地址2
12mod11=1,所以数据12也是属于地址1(这个数据是数据1指针的另一个新数据)
34mod11=1,所以数据34是属于地址1(这个数据是数据12指针的另一个新数据)
38mod11=5,所以数据38是属于地址5
33mod11=0,所以数据33是属于地址0
27mod11=5,所以数据27是属于地址5,(这个数据是数据38指针的另一个新数据)
22mod11=0,所以数据22是属于地址0,(这个数据是数据33指针的另一个新数据)

链地址法处理冲突构造所得的哈希表如下:


查找成功时: ASL=(3×1+2×3+1×4)/8=13/8,

查找不成功时:ASL=(3+4+2+1+1+3+1+1+1+1+1)/11=19/11;或者 ASL=(7×1+1×2+2×3+1×4 )/11=19/11,


 

网上一些博客错误的指正

 这个里面的一个解释是错的

 

这个地址就是9

这个也是有错的

全部少加一个1

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43813140/article/details/106103101

智能推荐

容器三把斧之 | cgroup原理与实现_struct list_headtasks;-程序员宅基地

文章浏览阅读1.6k次,点赞5次,收藏12次。前面我们介绍了CGroup的使用与基本概念,接下来将通过分析源码(本文使用的 Linux2.6.25 版本)来介绍CGroup的实现原理。在分析源码前,我们先介绍几个重要的数据结构,因为CGroup就是通过这几个数据结构来控制进程组对各种资源的使用。cgroup结构体前面介绍过,cgroup是用来控制进程组对各种资源的使用,而在内核中,cgroup是通过cgroup结构体来描述的,我们来看看其定义:structcgroup{unsignedlongfla..._struct list_headtasks;

SpringMVC初认识_兔头程序员-程序员宅基地

文章浏览阅读164次。SpringMVCMVC1. 什么是MVC?MVC是一种框架模式,是Model View Controller(模型-视图-控制器)的缩写。Model 模型数据模型,提供要展示的数据,用于封装数据View 视图展示数据Controller 控制器控制模型的数据要在哪一个视图展示2. 作用MVC模式使展示与模型分离,流程控制逻辑、业务逻辑调用与展示分离。最终实现系统的职能分工。3. 优缺点优点耦合性低重用性高生命周期成本低部署快可维护性高有利于软件工程化管理_兔头程序员

Svchost.exe进程详解及Svchost.exe病毒清除方法_svchost.exe -k rpcss-程序员宅基地

文章浏览阅读2.3w次,点赞3次,收藏18次。这几天在宿舍上网的时候其他的舍友反映网络特别的卡。不知道是什么原因。然后我就发现自己的电脑有一个程序,自己走流量而且每秒能达100kb以上对于宿舍8个人共用的一个4M的网线来说已经算是占了好大一部分网速了。在金山流量监控上发现这个程序叫Svchost.exe。这是一个什么程序呢。然后我就尝试禁用。但我发现win7的任务管理器的进程中是找不到这个进程的。然后我通过上网了解了这个进程。 s_svchost.exe -k rpcss

java中修改对象类的数据_Java基础09 类数据与类方法-程序员宅基地

文章浏览阅读728次。我们一直是为了产生对象而定义类(class)的。对象是具有功能的实体,而类是对象的类型分类。这是面向对象的一个基本概念。在继承(inheritance)中,我们将类当做可以拓展的主体,这提高了我们对“类”的认识。类本身还有许多值得讨论的地方。我们将继续深入。static数据成员有一些数据用于表述类的状态。比如Human类,我们可以用“人口”来表示Human类的对象的总数。“人口”直接描述类的状态,..._java中如何用方法来改变一个类的值

hdu 2066:一个人的旅行_输入数据:每组的第一行是三个整数t,s和d,表示有t条路,和去往临近城市高铁站、火车-程序员宅基地

文章浏览阅读448次。草儿决定要在最短的时间去一个自己想去的地方,因为草儿的家在一个小镇上,没有火车经过,所以她只能去邻近的城市坐火车。多组输入数据,每组的第一行是三个整数T,S和D,表示有T条路,和草儿家相邻的城市的有S个,草儿想去的地方有D个;接着有T行,每行有三个整数a,b,time,表示a,b城市之间的车程是time小时;(1=接着的第T+1行有S个数,表示和草儿家相连的城市;接着的第T+2行有D个_输入数据:每组的第一行是三个整数t,s和d,表示有t条路,和去往临近城市高铁站、火车

java统计字符串中每个字符出现的次数_java string 统计某个字符出现的次数-程序员宅基地

文章浏览阅读6.3w次,点赞33次,收藏76次。例如String str = “abcaaaefdabbhg”; 统计该字符串中每个字符出现的次数,输出: a====5 b====3 c====1 d====1 e====1 f====1 g====1 h====1方法一: 采用HashMappublic static void count(String str){ //将字符串转化为字符数组_java string 统计某个字符出现的次数

随便推点

python 数据存储方式_数据存储是什么python-程序员宅基地

文章浏览阅读1.9k次。blog.csdn.net/ffblog/article/details/46558051一.序列1.用于存储一系列的数据2.在内存中,序列就是一块用于存放多个值的连续的内存空间如a=[10,20,30,40]存储示意:3.python中序列结构:str,list,tuple,dict,set..._数据存储是什么python

【语音去噪】IIR+FIR滤波器语音信号去噪(含滤波前后对比图)【含Matlab源码 4062期】-程序员宅基地

文章浏览阅读354次,点赞4次,收藏4次。IIR+FIR滤波器语音信号去噪(含滤波前后对比图)完整的代码,包运行;运行操作视频见CSDN资源!适合小白!

Tensorflow-hub[例子解析1]-程序员宅基地

文章浏览阅读364次。0. 引言Tensorflow于1.7之后推出了tensorflow hub,其是一个适合于迁移学习的部分,主要通过将tensorflow的训练好的模型进行模块划分,并可以再次加以利用。不过介于推出不久,目前只有图像的分类和文本的分类以及少量其他模型这里先通过几个简单的例子,来展示该hub的使用流程。1. 一个超简单例子1.1 创建一个Module#该文件名为half_plus_two..._tensorflow hub、py

Linux利用重定向三步搞定请求百度主页源代码_linux socket 访问百度-程序员宅基地

文章浏览阅读1.4k次。Linux利用重定向三步搞定请求百度主页源代码第一步:新建文件描述符,简历与百度通信的socket通道exec 8<> /dev/tcp/www.baidu.com/80命令解释:8:新建的文件描述符<>:既要发送请求,又要接收响应数据/dev/tcp:这个目录看不到,但内核确实有一旦执行该命令,就会新建一个socket连接删除文件描述符:..._linux socket 访问百度

C primer plus(第六版) 第七章答案_第七章单元测试提交作业6. 单选题(2分)下图中哪个点是最小方差点?( )。a点cb-程序员宅基地

文章浏览阅读7.1k次,点赞21次,收藏19次。C primer plus(第六版) 第七章答案/* 第一题 */#include<stdio.h>#define SPACE ' 'int main(void){ int count_space = 0; int count_line_break = 0; int count_others = 0; int ch; printf("Please pu..._第七章单元测试提交作业6. 单选题(2分)下图中哪个点是最小方差点?( )。a点cb

Ubuntu:显存占用及处理_ubuntu root图形界面占显存-程序员宅基地

文章浏览阅读2.7k次。问题在进行深度学习时,显存是一种非常宝贵的资源。但是即便在Ubuntu下,各种各样的系统配置都会不自觉的占用一些显存,导致深度学习难以为继。在本博客中,主要搬运一些查询显存占用原因及处理方法。翻译来源链接https://unix.stackexchange.com/questions/591393/how-to-shift-process-from-gpu-to-cpu-usagehttps://askubuntu.com/questions/1220144/can-somebody-explai_ubuntu root图形界面占显存

推荐文章

热门文章

相关标签