• 2022-06-19
    设哈希函数H(K)= K mod 13,哈希地址空间为0~14,对关键字序列(36,13,49,24,38,21,4,12 , 40),按线性探测法解决冲突的方法构造哈希表,并求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。
  • 哈希表:(2分)ASL(succ)=(1+1+1+1+1+2+2+2+3)/9=14/9 (2分)ASL(unsucc)=(3+2+1+1+2+1+1+1+2+1+8+7+6+5+4)/15=3(2分)

    内容

    • 0

      设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77},采用哈希函数H(key)=key MOD 13,采用开放地址法的二次探测再散列方法解决冲突,试在0~12的散列空间中对关键字序列构造哈希表,画出哈希表,并求其查找成功时的平均查找长度。

    • 1

      有关键字序列{32,53,78,12,25,62,43},哈希函数H(K)=K mod 7,用线性探测再散列方法处理冲突,要求构造一个装填因子为0.7的哈希表,并计算查找成功时的平均查找长度

    • 2

      选取哈希函数H(k)=(k)%11。用二次探测法处理冲突,试在0-10的散列地址空间中对关键字序列(22,41,53,46,30,13,01)构造哈希表,并求等概率情况下查找成功时的平均查找长度。

    • 3

      已知关键字序列{11,2,15,26,5,18,13,9},设哈希表表长为16,哈希函数H(key)=key MOD 13,处理冲突的方法为线性探测法,请给出哈希表,并计算在等概率的条件下的平均查找长度。

    • 4

      设一组初始记录关键字集合为(18, 12, 11, 27, 22, 32, 54, 68), 哈希表的长度为 11, 哈希函数 H(k) = k mod 11, 要求:用线性探测 法作为解决冲突的方法设计哈希表, 在等概率的假设下计算:(1)查找成功时 的平均查找长度;(2)查找失败时的平均查找长度(小数点后保留2位);