对于一个长度为m=41的散列表,采用双散列法解决冲突,对于关键码k1,k2,k3,若h(k1
(1)k1的探查序列:___30___,________,________,________,
(2)k2的探查序列:___28___,________,________,________,
(3)k3的探查序列:________,________,________,________,
(1)k1的探查序列:___30___,________,________,________,
(2)k2的探查序列:___28___,________,________,________,
(3)k3的探查序列:________,________,________,________,
20,03,78,31,15,36建立表。
(1)采用线性探查法寻找下一个空位,画出机应的散列表,并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
(2)采用双散列法寻找下一个空位,再散列函数为RH(key)=(7×key)%10+1,寻找下一个空位的公式为Hi=(Hi-1+RH(key))%13,H1=H(key)。画出相应的散列表,并计算等概率下搜索成功的平均搜索长度。
若设散列表的大小为m,利用散列函数计算出的散列地址为h-hash(x)。
(1)试说明确定m的原则。
(2)试证明:如果采用二次探查法解决冲突,表的大小是一个索数,若当表的装载因子α≤0.5,则新的元素总能被插入,且在插人过程中没有一个存储地址被探查2次。
设α是散列表的装钱因子,则应用双散列法解决冲突时的搜索成功的平均搜索长度和搜索不成功的平均搜索长度分别为:(请根据题意选用合用的公式)
101003245581263292004000
(1)散列函数采用除留余数法,用%m(取模运算)将各关键码映像到表中。请指出每一个产生冲突的关键码可能产生多少次冲突。
(2)散列函数采用先将关键码各位数字折叠相加,再用%m将相加的结果映像到表中的办法。请指出每一个产生冲突的关键码可能产生多少次冲突。
A、m
B、小于或等于m的最大素数
C、大于的最小素数
D、小于或等于m的最大合数
试证明,只要散列表长取作素数M=4k+3(k为非负整数),则:
a)任一关键码所对应的查找链中,前M个桶必然互异(即取遍整个散列表);
b)在装填因子尚未增至100%之前,插入操作必然成功(而不致因无法抵达空桶而失败)。