若设散列表的大小为m,利用散列函数计算出的散列地址为h-hash(x)。(1)试说明确定m的原则。(2)试
若设散列表的大小为m,利用散列函数计算出的散列地址为h-hash(x)。
(1)试说明确定m的原则。
(2)试证明:如果采用二次探查法解决冲突,表的大小是一个索数,若当表的装载因子α≤0.5,则新的元素总能被插入,且在插人过程中没有一个存储地址被探查2次。
若设散列表的大小为m,利用散列函数计算出的散列地址为h-hash(x)。
(1)试说明确定m的原则。
(2)试证明:如果采用二次探查法解决冲突,表的大小是一个索数,若当表的装载因子α≤0.5,则新的元素总能被插入,且在插人过程中没有一个存储地址被探查2次。
(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,
设散列表为,即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为:
其中,函数Rev(x)表示颠倒10进制数x的各位,如Rev(37)=73,Rev(7)一7等。若插入的关键码值序列为(2,8,31,20,70,59,25,28)。
(1)试画出插人这8个关键码值后的散列表。
(2)计算搜索成功的平均搜索长度。
若散列表长度为m,散列函数为H(key)=key MOD p,则P应取(53)。
A.小于m的最大素数
B.小于m的最大奇数
C.小于/n的最大偶数
D.小于m的任意整数
设散列表的地址空间为0到16,散列函数为h(k)=k mod 17,用线性探查法解决碰撞。现从空的散列表开始,依次插入关键码值190,89,217,208,75,177,则最后一个关键码177的地址为
A.6
B.7
C.8
D.9
设散列表中m个存储单元,散列函数为H(key)=key%p,p是最好选择()。
A.小于等于m的最大奇数
B.小于等于m的最大素数
C.小于等于m的最大偶数
D.小于等于m的最大合数
设散列表的长度为8,散列函数H(k)=k mod 7,初始记录关键字序列为(25,31,8,27,13,68),要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。
设某散列表的长度为100,散列函数H(k)=k % P,则P通常情况下最好选择()。
A.99
B.97
C.91
D.93
已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0…6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为(50)。
A.1.5
B.1.7
C.2
D.2.3
●对于关键字序列(26,25,72,38,8,18,59),采用散列函数 H(Key)=Key mod 13 构造散列表(哈希表)。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元),则关键字59 所在散列表中的地址为 (61) 。
(61)
A.6
B.7
C.8
D.9
已知一个线性表为(38,25,74,63,52,48),假定采用H(K)=K mod 7计算散列地址进行散列存储,若利用线性探测的开放定址法处理冲突,则在该散列表上进行查找的平均查找长度为();若利用链地址法处理冲突,则在该散列上进行查找的平均查找长度为()。
A.1.5,1
B.1.7,3/2
C.2,4/3
D.2.3,7/6