41.（10分）将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组，散列函数为 H（key）=（key×3）MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。 （1）请画出所构造的散列表。 （2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。
【参考答案及解析】
（1）由装载因子0.7，数据总数为7，得一维数组大小为7/0.7=10，数组下标为0~9。所构造的散列函数值如下所示： key |7 |8 |30 |11 |18 |9 |14 H(key) |0 |3 |6 |5 |5 |6 |0 采用线性探测再散列法处理冲突，所构造的散列表为： 地址 |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 关键字 |7 |14 | |8 |11 |30 |18 |9 | （2）查找成功时，是根据每个元素查找次数来计算平均长度，在等概率的情况下，各关键字的查找次数为 key |7 |8 |30 |11 |18 |9 |14 次数 |1 |1 |1 |1 |3 |3 |2 故，ASL成功 = 查找次数/元素个数 =（1+2+1+1+1+3+3）/7=12/7 这里要特别防止惯性思维。查找失败时，是根据查找失败位置计算平均次数，根据散列函数 MOD7，初始只可能在0~6的位置。等概率情况下，查找0~6位置查找失败的查找次数为： H(key) |0 |1 |2 |3 |4 |5 |6 次数 |3 |2 |1 |2 |1 |5 |4 故，ASL不成功= 查找次数 /散列后的地址个数 =（3+2+1+2+1+5+4）/7=18/7
正在整理中,欢迎在文下评论区提供答案解析,谢谢！
（1）由装载因子0.7，数据总数为7，得一维数组大小为7/0.7=10，数组下标为0~9。所构造的散列函数值如下所示： key |7 |8 |30 |11 |18 |9 |14 H(key) |0 |3 |6 |5 |5 |6 |0 采用线性探测再散列法处理冲突，所构造的散列表为： 地址 |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 关键字 |7 |14 | |8 |11 |30 |18 |9 | （2）查找成功时，是根据每个元素查找次数来计算平均长度，在等概率的情况下，各关键字的查找次数为 key |7 |8 |30 |11 |18 |9 |14 次数 |1 |1 |1 |1 |3 |3 |2 故，ASL成功 = 查找次数/元素个数 =（1+2+1+1+1+3+3）/7=12/7 这里要特别防止惯性思维。查找失败时，是根据查找失败位置计算平均次数，根据散列函数 MOD7，初始只可能在0~6的位置。等概率情况下，查找0~6位置查找失败的查找次数为： H(key) |0 |1 |2 |3 |4 |5 |6 次数 |3 |2 |1 |2 |1 |5 |4 故，ASL不成功= 查找次数 /散列后的地址个数 =（3+2+1+2+1+5+4）/7=18/7
正在整理中,欢迎在文下评论区提供答案解析,谢谢！