若用二次探査法解决冲突,求“下一个空位”的探查序列为:
其中,H0是第一次求得的散列地址,Hi是第i次求得的散列地址,m是散列表的大小。
(1)相邻的地址Hi与Hi-1之间是什么关系?
(2)为保证散列地址序列的地址不会循而往复地重迭,m应设为什么数?装填因子α应如何取值?
(3)为保证在删除时不中断搜索链,可对被删记录做逻辑删除。为此,每个散列地址有3个状态,除了Active(正在使用)和Deleted(删除)状态外,还应有一个什么状态?
设散列表容量为11且初始为空,采用除余法确定散列地址,采用单向平方试探法排解冲突,采用懒惰策略实现删除操作。
a)若通过put()接口将关键码(2012,10,120,175,190,230)依次插入中,试给出此时各桶单元的内容;
b)若再执行remove(2012),试给出此时各桶单元的内容;
c)若继续执行get(2012),会出现什么问题?为什么?
d)为避免此类问题的出现,可以采取什么措施?试给出至少两种方案。
A、m+k
B、m×k-1
C、m×k+1
D、m×k
(1)k1的探查序列:___30___,________,________,________,
(2)k2的探查序列:___28___,________,________,________,
(3)k3的探查序列:________,________,________,________,
在地址空间为0~16的散列区中,对以下关键字序列构造两个散列表:
1)用线性探测开放定址法处理冲突;
2)用链地址法处理冲突。
并分别求这两个散列表在等概率情况下查找成功和不成功的平均查找长度。设散列函数为H(key)=i/2,其中i为关键字中第一个字母在字母表中的序号。
A、关键码值
B、元素值
C、散列地址
D、含义
散列表A[10]中,若采用线性探查方法解决冲突,则在该散列表上进行等概率成功搜索的平均搜索长度为()。
A、2.60
B、3.14
C、3.71
D、4.33
(h+q2),(h+(q-1)2),…,(h+1),h,(h-1),…,(h-q2*),其中,q=(m-1)/2。闪此在相继被探查的两个桶之间地址相减所得的差取模(%m)的结果为m-2,m-4,m-6.…,5,3,1,1,3,5,…,m-6,m-4,m-2,