假设一个散列表中已装人100个表项并采用线性探查法解决冲突,要求搜索到表中已有表项时的平均
设α是散列表的装载因子,则应用线性探查法解决冲突时的搜索成功的平均搜索长度和搜索不成功的平均搜索长度分别为:
请根据题意选择合用的公式。
设α是散列表的装载因子,则应用线性探查法解决冲突时的搜索成功的平均搜索长度和搜索不成功的平均搜索长度分别为:
请根据题意选择合用的公式。
(1)散列表的大小应该是多少?
(2)如果散列函数采用除留余数法,写出散列两数的定义;
(3)若已有的8个记录分别为(58,87,38,95,49,75,64,47),依次将它们存放到表中;
(4)计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
设α是散列表的装钱因子,则应用双散列法解决冲突时的搜索成功的平均搜索长度和搜索不成功的平均搜索长度分别为:(请根据题意选用合用的公式)
101003245581263292004000
(1)散列函数采用除留余数法,用%m(取模运算)将各关键码映像到表中。请指出每一个产生冲突的关键码可能产生多少次冲突。
(2)散列函数采用先将关键码各位数字折叠相加,再用%m将相加的结果映像到表中的办法。请指出每一个产生冲突的关键码可能产生多少次冲突。
设散列表为,即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为:
其中,函数Rev(x)表示颠倒10进制数x的各位,如Rev(37)=73,Rev(7)一7等。若插入的关键码值序列为(2,8,31,20,70,59,25,28)。
(1)试画出插人这8个关键码值后的散列表。
(2)计算搜索成功的平均搜索长度。
设散列表的地址空间为0到16,散列函数为h(k)=k mod 17,用线性探查法解决碰撞。现从空的散列表开始,依次插入关键码值190,89,217,208,75,177,则最后一个关键码177的地址为
A.6
B.7
C.8
D.9
A、数字分析法、除留余数法、平方取中法
B、数字分析法、除留余数法、线性探查法
C、数字分析法、线性探查法、双散列法
D、线性探查法、双散列法、开散列法
A、O(1)
B、O(n)
C、O(log2n)
D、O(n2)