扫码加入训练营

牢记核心词

学习得礼盒

41.(10分)将关键字序列(7,8,30,11,18,9,14)散列存储到散列

2021-07-01 07:52:00来源:新东方在线

  【题目】

  41.(10分)将关键字序列(7,8,30,11,18,9,14)散列存储到散列表中,散列表的存储空间是一个下标从0开始的一维数组,散列函数为:H(key)=(key×3)MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。

  (1) 请画出所构造的散列表。

  (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。

  【答案要点】

  (1)由装载因子0.7,数据总数7个→存储空间长度为10→P=10。所以,构造的散列表为: H(7)=(7×3)MOD 7=0

  H(8)=(8×3)MOD 7=3

  H(11)=(11×3)MOD 7=5

  H(18)=(18×3)MOD 7=5

  H(9)=(9×3)MOD 7=6

  H(14)=(14×3)MOD 7=0

  H(30)=(30×3)MOD 7=6

  (2)查找成功的平均查找长度:ASL成功=(1+1+1+1+2+3+3)/7=12/7。

  查找不成功的平均查找长度:AsL不成功=(3+2+1+2+1+5+4)/7=18/7。



考研公开课小程序

限时免费
资料推荐
更多>>
更多内容

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】,识别上方二维码;
2.点击【关注公众号】,获取资料大礼包。

考研资料大礼包
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
获取验证码
收不到短信?点此接收语音验证码
电话拨打中...请留意来自125909888237的来电
60秒后可重新获取
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
账号密码登录 找回密码
国际手机登录
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
手机快速登录 找回密码
获取验证码
收不到短信?点此接收语音验证码
电话拨打中...请留意来自125909888237的来电
60秒后可重新获取
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
账号密码登录 找回密码
国际手机登录
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
手机快速登录 找回密码
获取验证码
收不到短信?点此接收语音验证码
电话拨打中...请留意来自125909888237的来电
60秒后可重新获取
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
账号密码登录 找回密码
国际手机登录
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
手机快速登录 找回密码