2. 从业资格
  3. 对于关键字序列（26，25，72，38，8，18，59），采用散列函数H（Key

对于关键字序列（26，25，72，38，8，18，59），采用散列函数H（Key

考试题库2022-08-02  20
问题 对于关键字序列（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
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)