第9章-综合应用题数据结构(共2页).doc

精选优质文档-倾情为你奉上应用题：1、采用哈希函数H(k) = 3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间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) = K MOD P，回答下列问题：（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