第9章-综合应用题数据结构

应用题：1、采用哈希函数H(k)=3*kmod13并用线性探测开放地址法处理冲突，在数列地址空间[0..12]中对关键字序列22，41，53，46，30，13，1，67，51；（1）构造哈希表（画示意图）；（2）装填因子；（3）等概率下成功的平均查找长度；（4）等概率情况下查找失败的平均查找长度2、已知一组关键字为（26，36，41，38，44，15，68，12，6，51，25），用链地址法解决冲突。假设装填因子α=0.75，哈希函数的形式为H(K)=KMODP，回答下列问题：（1）构造哈希函数（2）画出哈希表（3）计算出等概率情况下查找成功的平均查找长度。（4）计算出等概率情况下查找失败的平均查找长度。答：（1）（2）装填因子=9/13≈0.7（3）ASLsucc=11/9（4）ASLunsucc=(3+2+1+3+2+1+4+3+2+1+2+1+4)/13=29/13答：由α=0.75，得表长m=11/0.75=15.（1）哈希函数H(K)=K/13（2）哈希表（3）等概率情况下查找成功的平均查找长度：ASL=18/11（4）等概率情况下查找失败的平均查找长度：ASL=11/13012345678910111226Λ4115Λ68Λ44Λ6Λ36Λ381251ΛΛΛΛΛΛ25Λ