首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
散列表是一种重要的存储方式,在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些,请举例说明(至少三个)。 (3)怎样用拉链法和开地址法处理碰撞?
散列表是一种重要的存储方式,在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些,请举例说明(至少三个)。 (3)怎样用拉链法和开地址法处理碰撞?
admin
2009-07-15
101
问题
散列表是一种重要的存储方式,在散列表里可快速进行检索。
(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全国计算机四级
相关试题推荐
设有下面4条路由:192.168.129.0/24、192.168.130.0/24、192.168.132.0/24和192.168.133.0/24,如果进行路由汇聚,能覆盖这4条路由的地址是__________________。
以下关于VLAN配置的描述中,正确的是(55)________________。①通过创建VLAN,会同时进入VLAN视图②通过umdoVLAN,VLAN会处于停用状态③可以对VLAN配置描述字符串,字符串长度不限④通过displayVLAN命
如果客户机收到网络上多台DHCP服务器的响应,它将(68)DHCP服务器发送IP地址租用请求。在没有得到DHCP服务器最后确认之前,客户机使用(69)作为源IP地址。(68)
程序计数器(PC)包含在______中。
程序计数器(PC)是用来指出下一条待执行指令地址的,它属于(3)________________中的部件。
使用Windows操作系统,在“我的电脑”中选择某磁盘中的文件,再选择“查看”菜单中的“(4)”,可查看该文件建立(或最近修改)的时间和文件大小。
阅读以下说明和流程图,回答问题。[说明]从键盘输入一个高精度正整数n,去掉其中s个数字后按原左右次序再组成一个新的正整数。对给定的n,要寻找一种方案,使得余下的数字组成的新数最小。算法分析:每次删除一个数字,选择一个使余下的数最小
阅读以下程序说明和C程序,将程序段中(1)~(7)空缺处的语句填写完整。【说明】【C程序1】用回溯算法来产生由0或1组成的2m个二进位串,使该串满足以下要求。视串为首尾相连的环,则由m位二进制数字组成的2m个子序列,每个可能的子序
阅读以下程序说明和C++程序,将程序段中(1)~(5)空缺处的语句填写完整。【说明】以下【C++程序】实现一个简单的小型复数类MiniComplex,该复数类能进行输入、输出、复数的加法、减法、乘法和除法运算,还可以进行复数的相等比较。
Very long,complex expressions in program are difficult to write correctly and difficultto(68).
随机试题
以下哪一项是密钥托管技术?()
嗜碱性粒细胞减少可见于
生殖细胞肿瘤不包括
胆管结石引起感染性休克时应采取的处理措施为
某产品的实际成本为10000元,它由多个零部件组成,其中一个零部件的实际成本为880元,功能评价系数为0.140,则该零部件的价值指数为()。
李某户籍在A市,居住在B市,在C市某水泥厂工作,因长期接触粉尘,需要进行职业病诊断。根据《职业病防治法》,下列关于职业病诊断的说法中,正确的是()。
申请行政许可,行政机关拒绝或者在法定期限内不予答复,或者对行政机关作出的有关行政许可的其他决定不服的,公民、法人或者其他组织可以向人民法院提起行政诉讼。()
使用宏设计器,不能创建的宏是
InarecentSundayschoolclassinachurchintheNortheast,agroupofeight-toten-year-oldswereinadeepdiscussionwith
Sportingactivitiesareessentiallymodifiedformsofsomeoldstylehuntingbehavior.Viewed【B1】______,themodernfootballpl
最新回复
(
0
)