设散列表中已有8个记录,用二次探查再散列解决冲突,要求插人新记录的平均探查次数不超过1.5。设
(1)散列表的大小应该是多少?
(2)如果散列函数采用除留余数法,写出散列两数的定义;
(3)若已有的8个记录分别为(58,87,38,95,49,75,64,47),依次将它们存放到表中;
(4)计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
(1)散列表的大小应该是多少?
(2)如果散列函数采用除留余数法,写出散列两数的定义;
(3)若已有的8个记录分别为(58,87,38,95,49,75,64,47),依次将它们存放到表中;
(4)计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
第1题
设α是散列表的装钱因子,则应用双散列法解决冲突时的搜索成功的平均搜索长度和搜索不成功的平均搜索长度分别为:(请根据题意选用合用的公式)
第2题
设α是散列表的装载因子,则应用线性探查法解决冲突时的搜索成功的平均搜索长度和搜索不成功的平均搜索长度分别为:
请根据题意选择合用的公式。
第3题
第4题
设散列表为,即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为:
其中,函数Rev(x)表示颠倒10进制数x的各位,如Rev(37)=73,Rev(7)一7等。若插入的关键码值序列为(2,8,31,20,70,59,25,28)。
(1)试画出插人这8个关键码值后的散列表。
(2)计算搜索成功的平均搜索长度。
第5题
若设散列表的大小为m,利用散列函数计算出的散列地址为h-hash(x)。
(1)试说明确定m的原则。
(2)试证明:如果采用二次探查法解决冲突,表的大小是一个索数,若当表的装载因子α≤0.5,则新的元素总能被插入,且在插人过程中没有一个存储地址被探查2次。
第6题
设散列表的长度为8,散列函数H(k)=k mod 7,初始记录关键字序列为(25,31,8,27,13,68),要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。
第7题
(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,
第8题
(1)k1的探查序列:___30___,________,________,________,
(2)k2的探查序列:___28___,________,________,________,
(3)k3的探查序列:________,________,________,________,
第9题
A.8
B.3
C.5
D.9
第10题
●对于关键字序列(26,25,72,38,8,18,59),采用散列函数 H(Key)=Key mod 13 构造散列表(哈希表)。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元),则关键字59 所在散列表中的地址为 (61) 。
(61)
A.6
B.7
C.8
D.9