试题详情
简答题假定一个待散列存储的线性表为（32，75，29，63，48，94，25，46，18，70），散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探查法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。
  • 散列函数：H（K）=k%m其中依题意得m=13
    H（32）=32%13=6
    H（5）=75%13=10
    H（29）=29%13=3
    H（63）=63%13=11
    H（8）=48%13=9
    H（94）=94%13=3（冲突）
    设d0=H（K）=H（94）=3
    d1=（d0+1）%m=（3+1）%13=4
    H（25）=25%13=12
    H（46）=46%13=7
    H（18）=18%13=5
    H（70）=70%13=5（冲突）
    设d0=H（K）=H（70）=5
    d1=（d0+1）%m=（5+1）%13=6（冲突）
    d2=（d1+1）%m=（6+1）%13=7（冲突）
    d3=（d2+1）%m=（7+1）%13=8
    ASL=（8*1+1*2+1*4）/10=1.4

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

热门试题