设一组初始记录关键字集合为(18, 12, 11, 27, 22, 32, 54, 68), 哈希表的长度为 11, 哈希函数 H(k) = k mod 11, 要求:用线性探测 法作为解决冲突的方法设计哈希表, 在等概率的假设下计算:(1)查找成功时 的平均查找长度;(2)查找失败时的平均查找长度(小数点后保留2位);
举一反三
- 设哈希函数H(K)=3 K mod 11,哈希地址空间为0~10,对关键字序列(32,13,49,24,38,21,4,12),按下述两种解决冲突的方法构造哈希表,并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。① 线性探测法;② 链地址法。
- 设哈希函数H(K)= K mod 13,哈希地址空间为0~14,对关键字序列(36,13,49,24,38,21,4,12 , 40),按线性探测法解决冲突的方法构造哈希表,并求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。
- 设哈希表的长度m=11,哈希函数为H(K)=K mod m,采用链地址法解决冲突,待依次插入的关键码序列为{1,13,12,34,38,33,27,22}。根据构成的哈希表:在等概率的情况下,搜索成功时的平均查找长度为 ,在等概率的情况下,搜索失败时的平均查找长度为 。
- 设哈希函数H(K)=(3*K)%11,哈希地址空间为0~10,对关键字序列(32,13,49,24,38,21,4,12),采用链地址法解决冲突,试构造哈希表,并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。
- 对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8,采用线性探测再散列方法解决冲突。 (1)设计哈希函数; (2)画出哈希表; (3)计算查找成功和查找失败的平均查找长度;