首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
散列表是一种重要的存储方式,在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些,请举例说明(至少三个)。 (3)怎样用拉链法和开地址法处理碰撞?
散列表是一种重要的存储方式,在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些,请举例说明(至少三个)。 (3)怎样用拉链法和开地址法处理碰撞?
admin
2009-07-15
43
问题
散列表是一种重要的存储方式,在散列表里可快速进行检索。
(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全国计算机四级
相关试题推荐
与netstat-r具有同等功能的命令是__________。
(13)属于标记语言。
在SNMP的网络管理者——网管代理模型中,(59)负责管理指令的执行。
关于IPv6,下面的论述中正确的是(29)。
在IPv6地址无状态自动配置过程中,主机将其________附加在地址前缀1111111010之后,产生一个链路本地地址。
阅读以下说明和Java代码,填充程序中的空缺,将解答填入答题纸的对应栏内。【说明】某应急交通控制系统(TraficControlSystem)在红灯时控制各类车辆(Vehicle)的通行,其类图如图6—1所示,在紧急状态下应急车辆在红
阅读下列说明和C++代码,填补代码中的空缺,将解答填入答题纸的对应栏内。【说明】以下C++代码实现一个简单的聊天室系统(ChatRoomSystem),多个用户(User)可以向聊天室(ChatRoom)发送消息,聊天室将消息展示给所有用户。类图如图6
The(71) program is generally translated to an object program, which is in a form directly understandably by the computer。
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
AWeb(73)isoneofmanysoftwareapplicationsthatfunctionastheinterfacebetweenauserandtheInternet
随机试题
新民主主义革命的三大法宝及其相互关系是什么?
患者,男,52岁。间歇性右上腹痛2个月,实验室检查:甲胎蛋白320μ/L。为了进一步明确诊断,应该做的检查是
手三阳经的走向为()
优化的生产计划必须具备的特征有()。
注册会计师与被审验单位在注册资本的实收或变更的确认方面存在异议,且无法协商一致时,注册会计师应当拒绝出具验资报告。( )如果发现出资者以尚在诉讼中的有产权纠纷的房屋出资,则注册会计师一般不能认定其产权归属,不能对房屋的出资进行审验确认。( )
学校如何实施对家庭教育的指导?
A、 B、 C、 D、 D多次方数列。底数依次是102、(92)、82、72、62;指数可以依次写为的等比数列。
军队讲政治是根本,是顾大局、守纪律的基础和前提。如果不紧绷讲政治这根弦,就可能在错综复杂的政治斗争面前迷欠方向。由此可知:
在Windows98环境下,下列有关磁盘存储结构和管理的叙述中,正确的是______。
Somepeoplearefriendlydrunks,whereasothersarehostile,potentiallyposingadangertothemselvesandothers.Thedifferenc
最新回复
(
0
)