首页 > 试题广场 >

设散列表(也称哈希表)为 HT[0..12],表长为 m=1

[问答题]
设散列表(也称哈希表)为 HT[0..12],表长为 m=13。现采用双散列法解决冲突。
散列函数为:H 0 =key%13,其中%表示求余数运算(=MOD);冲突后采用再散列函数解
决冲突,再散列函数为:H i =(H i­1 +REV(key+1)%11+1)%13,(i=1,2,3, …... , m­1),其中,
函数 REV(x)表示颠倒 10 进制数 x 的各位,例如 REV(37)=73,REV(7)=7 等。若插入
关键字序列为{2,8,31,20,19,18,53,27}。求:(1)画出插入这 8 个关键字后的散列表;(2)
计算查找成功的平均查找长度。
解:
散列表如下:
0      1     2      3     4     5     6     7     8     9      10     11
12
比较次数:
3      1     1                   1    1      1     1     2
ASL 成功=(1×6+3+2)/8=11/8
发表于 2017-05-14 22:27:13 回复(0)