首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
散列表是一种重要的存储方式,在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些,请举例说明(至少三个)。 (3)怎样用拉链法和开地址法处理碰撞?
散列表是一种重要的存储方式,在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些,请举例说明(至少三个)。 (3)怎样用拉链法和开地址法处理碰撞?
admin
2009-07-15
45
问题
散列表是一种重要的存储方式,在散列表里可快速进行检索。
(1)散列表的基本思想是什么?
(2)常用的散列函数有哪些,请举例说明(至少三个)。
(3)怎样用拉链法和开地址法处理碰撞?
选项
答案
(1)散列表的基本思想是;由结点的关键码值决定结点的存储地址。即以关键码值k为自变量,通过一定的函数关系H(称为散列函数),计算出对应的函数值H(k)来,把这个值解释为结点的存储地址,将结点存入该地址中去,检索时,按同样的方法计算出结点的地址,然后到相应的地址中取结点即可。 (2)常用的散列函数有: ①除余法:即选择一个适当的正整数p(通常选p为小散列表存储区域大小的最大素数),用p去除关键码值,取其余数作为地址。 ②折叠法:即将关键码值从某些地方断开,分为几段,折叠相加,作为地址。 ③中平方法:即将关键码值平方,取中间的几位数作为地址。 (3)用拉链法处理碰撞就是给散列表的每个结点增加一个link字段,当碰撞发生时利用link字段拉链,建立链接方式的同义词子表。每个同义词子表的第一个元素都在散列表基本区域中,同义词子表的其他元素的存储又有两种解决方法,一种是建立溢出区,存放各同义词子表的其他元素,另一种是不建立溢出区,同义词子表的其他元素就存放在散列表中没有占用的单元中, 用开地址法处理碰撞就是当碰撞发生时形成一个探查序列,沿着这个序列逐个地址探查,直到找到一个未被占用的地址,将发生碰撞的关键码值存入该地址中。最简单的探查序列是线性探查,即若发生碰撞的地址为d,则探查的地址序列为; d+1,d+2,…,m-1,0,1,…,d-1 其中,m是散列表存储区域的大小,另一种效果更好的探查序列是再散列探查,即用第二个散列函数H2来确定探查序列,若发生碰撞的地址为d,则探查的地址序列为: (d+H2(k))mod m,(d+2H2(k))mod m,(d+3H2(k))mod m,…
解析
转载请注明原文地址:https://kaotiyun.com/show/mRNZ777K
0
笔试
原NCRE全国计算机四级
NCRE全国计算机四级
相关试题推荐
在字长为16位、32位、64位或128位的计算机中,字长为_____________位的计算机数据运算精度最高。
Windows命令行输入()命令后得到下图所示的结果。
下图是在Linux系统中用ls命令查看文件信息的输出结果,可以判断命令行输入的完整命令是(42),当前目录的下级目录是(43),当前目录中的可执行文件是(44),当前用户是(45)。
用补码表示的8位二进制数11100000,其值为十进制数(1)。
阅读以下说明和Java代码,将应填入(n)处的字句写在对应栏内【说明】编写字符界面的Application程序,接收依次输入的10个整型数据,每个数据一行,将这些数据按升序排序后从系统的标准输出设备输出。【Java代码】import
阅读以下说明和C函数,将应填入(n)处的字句写在答题纸的对应栏内。【说明】计算机在处理算术表达式时,首先将其转换为后缀表达式。例如,表达式“46+5*(120-37)”的后缀表达式形式为“46512037-*+”。计算后缀表达式时,从
A firewall is a(1)system designed to(2)an organization’s network against threats.
(69)is permanently stored in the computer and provides a link between the hardware and other programs that run on the PC.
Software design is a(46) process. It requires a certain amount of fl air on the part of the(47). Design can not be learned from
Whichcommandisusedtocreateadatabasefilethatit’sstructureissameasanotherone’sinFoxProDBMS?()
随机试题
急性髓性白血病与慢性髓性白血病主要根据下列哪项鉴别
患者实感天旋地转,恶心欲吐,站立不稳,跌倒在地,神志清楚,数分钟后自行缓解。应诊断为()(2005年第70题)
并殖吸虫病患者一般常规检查及其他体液检查中明显升高的是
注册有效期届满需继续执业,且符合注册条件的,应在届满前()工作日内申请延续注册。
隧道钻爆法开挖时,炮眼根据围岩的好坏、施工方法的快慢来确定炮眼深度,一般在100~600cm范围内,每循环钻爆进尺一般是炮眼深度的()%。
下列说法中正确的是( )。
Forseveralyears,Americanshaveenjoyedteleshopping—watchingTVandbuyingthingsbyphone.NowteleshoppingisstartinginE
《史记》中《公仪休嗜鱼》说的是,公仪休在鲁国当丞相的时候特别喜欢吃鱼,有很多人投其所好送鱼给他,他一概不收。有人问:你为什么喜欢吃鱼却不收鱼?他说,我现在做丞相买得起鱼,自己可以买来吃。如果因接受了别人送的鱼而被免职,我从此就买不起鱼,也吃不起鱼了。这段文
(2013年单选9)某街道办事处主任陈某利用其掌握的城市居民低保资格复核权,收受申请人好处费,被上级机关撤销主任一职。陈某受到的法律制裁属于()。
HowdoesReevefeelinacrisis?
最新回复
(
0
)