试题详情
简答题已知关键码序列为（Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec），散列表的地址空间为0~16，设散列函数为H（x）=，其中i为关键码中第一个字母在字母表中的序号，采用线性探测法和链地址法处理冲突，试分别构造散列表，并求等概率情况下查找成功的平均查找长度。
  • H.Jan）=10/2=5，H（Feb）=6/2=3，H（Mar）=13/2=6，H（Apr）=1/2=0
    H.May）=13/2=6，H（Jun）=10/25，H（Jul）=10/25，H（Aug）=1/2=0
    H.Sep）=19/2=8，H（Oct）=15/2=7，H（Nov）=14/2=7，H（Dec）=4/2=2
    采用线性探测法处理冲突，得到的闭散列表如下：

    平均查找长度=（1+1+1+1+2+4+5+2+3+5+6+1）/12=32/12
    采用链地址法处理冲突，得到的开散列表如下：
    平均查找长度=（1×7+2×4+3×1）/12=18/12

  • 关注下方微信公众号，在线模考后查看

热门试题