多做题,通过考试没问题!

数据结构

睦霖题库>大学试题(计算机科学)>数据结构

假定一个待散列存储的线性表为(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
答案解析:
进入题库查看解析

微信扫一扫手机做题