首页
登录
从业资格
对于关键字序列(26,25,72,38,8,18,59),采用散列函数H(Key
对于关键字序列(26,25,72,38,8,18,59),采用散列函数H(Key
考试题库
2022-08-02
50
问题
对于关键字序列(26,25,72,38,8,18,59),采用散列函数H(Key)=Keymod13构造散列表(哈希表)。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元),则关键字59所在散列表中的地址为( )。A.6B.7C.8D.9
选项
A.6
B.7
C.8
D.9
答案
D
解析
根据题目给出的散列函数我们可以分别计算出关键字(26,25,72,38,8,18,59)对应的散列地址分别为(0,12,7,12,8,5,7)。
开放定址处理冲突的基本思路是为发生冲突的关键字在散列表中寻找另一个尚未占用的位置,其解决冲突能力的关键取决于探测序列,在本题中,题目告诉我们采用顺序探查法,即增量为1的线性探测法,在该线性探测法中,设Hi(1≤i<m)为第i次在散列表中探测的位置,其中增量序列为{1,2,3,4,5,…,m-1}则有:
Hi=(H(Key)+i)%m
其中H(Key)为散列函数,m为散列表长度,i为增量序列。而本题中m=13。因此本题的散列表构造过程如下:
(1)关键字26,25,72由散列函数H(key)得到没有冲突的散列地址而直接存入散列表中。
(2)计算关键38的散列地址为12,发生冲突(与关键字25冲突),其第一次线性探测地址为(12+1)%13=0,但仍然发生冲突(与关键字26冲突),因此需要进行第二次线性探测,其地址为(12+2)%13=1,这时没有发生冲突,即将38存入地址为1的空间。
(3)接着将关键字8,18计算其散列地址,由于没有冲突,即分别存入散列地址为8和5的空间中。
(4)计算关键59的散列地址为7,发生冲突(与关键字72冲突),其第一次线性探测地址(7+1)%13=8,但仍然发生冲突(与关键字8冲突),因此需要进行第二次线性探测,其地址为(7+2)%13=9,这时没有发生冲突,即将59存入地址为9的存储空间。
因此本题的答案选D。
转载请注明原文地址:https://tihaiku.com/congyezige/2410286.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
在数据库中新建存储过程的关键字是()。A.CREATEPROCEDURE
关系模式R(U,F)中,属性集U={A,B,C,D,E},函数依赖集F=(A→B
设有关系模式:选课(学号,课程号,课程名,成绩),其函数依赖集为{课程号+课程名
对分组查询结果进行筛选的是( ),其条件表达式中可以使用聚集函数。A.WHER
函数调用和返回控制是用( )实现的。A.哈希表 B.符号表 C.栈 D.
令序列X、Y、Z的每个元素都按顺序进栈,且每个元素进栈和出栈仅一次。则不可能得到
关系R(A1,A2,A3)上的函数依赖集F={A1A3→A2,A1A2→A3},
假设关系R(A1,A2,A3)上的函数依赖集F={A1→A2.A1→A3.A2→
数据挖掘的分析方法可以划分为关联分析、序列模式分析、分类分析和聚类分析四种。如果
下列关于函数依赖的叙述中,错误的是( )A.若A→B,B→C,则A→C B.
随机试题
Environmentliterallyis"thatwhichenvironsorsurrounds".Thetermisuse
It’sHardtoCleanBigDataA)KarimKeshayjee,aTorontophy
[originaltext](1)AskthemajorityofAmericansaboutthehighlightofatra
AlongwiththegrandviewoftheGreatWall,travelerstoBeijingshouldn’t
混凝土立方体抗压强度试验时的加荷速度对试验结果有较大影响,因此根据混凝土的强度等
心理学实验和相关研究证明,对理解的知识有复习的学生较无复习的学生保持效果好。如果
下列有关不良贷款拨备覆盖率的说法错误的是()。A.借贷损失准备金占不良贷款余
某投资者年初以10元/股的价格购买某股票1000股,年末该股票的价格上涨到11元
E企业为汽油、柴油、煤油生产经营企业。2012年实际用工2000人,其中有120
骨盆骨折最为重要的体征是A.局部肿痛 B.骨盆分离、挤压实验(+) C.反常
最新回复
(
0
)