首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
散列表是一种重要的存储方式,在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些,请举例说明(至少三个)。 (3)怎样用拉链法和开地址法处理碰撞?
散列表是一种重要的存储方式,在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些,请举例说明(至少三个)。 (3)怎样用拉链法和开地址法处理碰撞?
admin
2009-07-15
90
问题
散列表是一种重要的存储方式,在散列表里可快速进行检索。
(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全国计算机四级
相关试题推荐
在HTML语言中,______可用来为图像定义一串预备的可替换的文本。
RIP协议通过路由器之间的()计算通信代价。
话筒是向计算机提供(10)的设备。
(13)属于标记语言。
CPU执行算术运算或者逻辑运算时,算术逻辑运算部件(ALU)将计算结果保存在(5)中。
线性表采用顺序存储结构,若表长为m,且在任何一个合法插入位置上进行插入操作的概率相同,则插入一个元素平均移动(15)个元素。
在IPv6地址无状态自动配置过程中,主机将其________附加在地址前缀1111111010之后,产生一个链路本地地址。
阅读以下说明和Java代码,将解答写入对应栏内。【说明】下面是一个Applet程序,其功能是输出已定义好的两个变量x和chr。请改正程序中的错误(有下划线的语句),使程序能输出正确的结果。注意:不改动程序的结构,不得增行或删行。i
用ASCII码表示的大写英文字母B(42H)加偶校验后的二进制编码为(20)。
假设某计算机有IMB的内存,并按字节编址,为了能存取其中的内容,其地址寄存器至少需要(9)位。为使4B组成的字能从存储器中一次读出,要求存放在存储器中的字边界对齐,一个字的地址码应(10)。若存储周期为200ns,且每个周期访问4B,则该存储器按bit存储
随机试题
BoththebluepinkandthebluedressesareprettybutIlikethe_________better.
纤维素样坏死物质可见于下列哪些病变
A.雷洛昔芬B.乳酸钙C.雌二醇D.阿法骨化醇E.帕米膦酸二钠属于钙剂的有()
大肠癌术前肠道准备内容是
[2013年第12题]不属于工程量清单编制依据的是:
雇主所能支付的最高工资水平的估算因素不包括()。
20×4年1月1日,甲公司为乙公司的800万元债务提供50%担保。20×4年6月1日,乙公司因无力偿还该笔到期债务被债权人起诉。至20×4年12月31日,法院尚未判决,但经咨询律师,甲公司认为有55%的可能性需要承担全部保证责任,赔偿400万元,并预计承担
A、24B、19C、25D、21A窗户和屋顶上的数字个位数和十位数相加后等于门上的数字,1+1+4+0+2+3+1+6+5+1=24→?=5+0+2+1+3+3+1+0+2+7=24,故本题正确答案为A。
幂级数的收敛域是___________.
下列工作中()都属于管理信息系统实施阶段的内容。
最新回复
(
0
)