散列表是一种重要的存储方式，在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些，请举例说明(至少三个)。 (3)怎样用拉链法和开地址法处理碰撞?

admin2009-07-15 68

问题散列表是一种重要的存储方式，在散列表里可快速进行检索。
(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)

散列表是一种重要的存储方式，在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些，请举例说明(至少三个)。 (3)怎样用拉链法和开地址法处理碰撞?

笔试

原NCRE全国计算机四级

NCRE全国计算机四级

两个网络21.1.193.0/24和21.1.194.0/24汇聚之后为()。

下面选项中，(56)不能实现安全邮件传输。

在Windows系统中，系统对用户组默认权限由高到低的顺序是(9)。如果希望某用户对系统具有完全控制权限，则应该将该用户添加到用户组(10)中。(9)

与八进制数：1706等值的十六进制数是__________________。

若[X]补=CCH，机器字长为8位，则[X/2]补=(17)。

The______has　several　major　components,　including　the　system　kernel,　a　memory　management　system,　the　file　system　manager,　device

In　C　program,　all　variables　must　be(70)before　use,　usually　at　the　beginning　of　the　function　before　any(71)statements.

The(71)　program　is　generally　translated　to　an　object　program,　which　is　in　a　form　directly　understandably　by　the　computer。

计算机中16位浮点数的表示格式如图1所示：某机器码为1110001010000000。若阶码为移码且尾数为反码，其十进制真值为(8)；若阶码为移码且尾数为原码，其十进制真值为(9)；若阶码为补码且尾数为反码，其十进制真值为

万女士是不孕门诊的新诊病人，医嘱测量基础体温。护士给万女士讲解测量方法，其中讲解不全的一项是

患者，女，23岁。风湿性心脏瓣膜病史3年，近1个月余不明原因持续低热，抗生素治疗无效，现收住入院。心脏彩超提示二尖瓣有一大小约为12mm×12mm赘生物。该患者首选用药

根据刑事诉讼法相关规定，下列应当由军事法院管辖的是：

该市居民各项活动占用时间最多的是()。

马克思主义诞生的标志是()。

某人动用资金24000元，按5:3的比例分别买入甲、乙两种股票，资金全部投入，第五天全部抛出，其投资的收益率可以算出．(1)甲种股票升值15%(2)乙种股票下跌10%

树是结点的集合，它的根结点数目是()

散列表是一种重要的存储方式，在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些，请举例说明(至少三个)。 (3)怎样用拉链法和开地址法处理碰撞?

笔试

原NCRE全国计算机四级

NCRE全国计算机四级

两个网络21.1.193.0/24和21.1.194.0/24汇聚之后为()。

下面选项中，(56)不能实现安全邮件传输。

在Windows系统中，系统对用户组默认权限由高到低的顺序是(9)。如果希望某用户对系统具有完全控制权限，则应该将该用户添加到用户组(10)中。(9)

与八进制数：1706等值的十六进制数是__________________。

若[X]补=CCH，机器字长为8位，则[X/2]补=(17)。

The______has several major components, including the system kernel, a memory management system, the file system manager, device

In C program, all variables must be(70)before use, usually at the beginning of the function before any(71)statements.

The(71) program is generally translated to an object program, which is in a form directly understandably by the computer。

计算机中16位浮点数的表示格式如图1所示：某机器码为1110001010000000。若阶码为移码且尾数为反码，其十进制真值为(8)；若阶码为移码且尾数为原码，其十进制真值为(9)；若阶码为补码且尾数为反码，其十进制真值为

万女士是不孕门诊的新诊病人，医嘱测量基础体温。护士给万女士讲解测量方法，其中讲解不全的一项是

患者，女，23岁。风湿性心脏瓣膜病史3年，近1个月余不明原因持续低热，抗生素治疗无效，现收住入院。心脏彩超提示二尖瓣有一大小约为12mm×12mm赘生物。该患者首选用药

根据刑事诉讼法相关规定，下列应当由军事法院管辖的是：

该市居民各项活动占用时间最多的是()。

马克思主义诞生的标志是()。

某人动用资金24000元，按5:3的比例分别买入甲、乙两种股票，资金全部投入，第五天全部抛出，其投资的收益率可以算出．(1)甲种股票升值15%(2)乙种股票下跌10%

树是结点的集合，它的根结点数目是()

The______has　several　major　components,　including　the　system　kernel,　a　memory　management　system,　the　file　system　manager,　device　

In　C　program,　all　variables　must　be(70)before　use,　usually　at　the　beginning　of　the　function　before　any(71)statements.

The(71)　program　is　generally　translated　to　an　object　program,　which　is　in　a　form　directly　understandably　by　the　computer。

　　　　该市居民各项活动占用时间最多的是()。