《第9章-综合应用题数据结构(共2页).doc》由会员分享，可在线阅读，更多相关《第9章-综合应用题数据结构(共2页).doc（2页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
精选优质文档-倾情为你奉上应用题：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答：由=0.75，得表长m=11/0.75=15.（1）哈希函数H(K) = K/13（2）哈希表0123456789101112261541512512383644668（3）等概率情况下查找成功的平均查找长度：ASL=18/11（4）等概率情况下查找失败的平均查找长度：ASL=11/13专心-专注-专业