资源描述：
《散列习题课复习课程.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、散列习题课二、填空1.常用的处理冲突的方法有两种：开放地址法和链地址法。2.发生了第i次冲突，试探的下一个地址将增加di，基本公式是：hi(key)=(h(key)+di)modTableSize,其中di取决于不同的解决冲突方案：线性探测时di＝i、平方探测时di＝±i2、双散列时di＝i*h2(key)。3.在开放地址散列表中，删除操作通常只能“懒惰删除”，即需要增加一个“删除标记(Deleted)”，而并不是真正删除它。4.当装填因子过大时，解决的方法是加倍扩大散列表，这样α可以减小一半，这个过程叫做“再散列”。5.可能将不同的关键字映射到同一个散列地址上，即h(keyi)=h(
2、keyj)（当keyi≠keyj），这种现象称为“冲突”，keyi和keyj称为“同义词”。三、选择题1.散列法存储的基本思想是根据A来决定B，碰撞（冲突）指的是C，处理碰撞的两类主要方法是D。供选择的答案A，B：①存储地址②元素的符号③元素个数④关键码值⑤非码属性⑥平均检索长度⑦负载因子⑧散列表空间C:①两个元素具有相同序号②两个元素的关键码值不同，而非码属性相同③不同关键码值对应到相同的存储地址④负载因子过大⑤数据元素过多D：①线性探查法和双散列函数法②建溢出区法和不建溢出区法③除余法和折叠法④拉链法和开地址法答案：A＝B＝C＝D＝１.④①③④四、简答题1.简述为手机号码建立一个散
3、列表的方法。2.简述影响产生冲突的三个因素。五、分析题1.设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝KMOD16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，试回答下列问题：画出哈希表的示意图；若查找关键字63，需要依次与哪些关键字进行比较？若查找关键字60，需要依次与哪些关键字比较？假定每个关键字的查找概率相等，求查找成功时的平均查找长度。（1）画表如下：（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47
4、,32,17,63相比，一共比较了6次！（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。（4）对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，ASL=1/11（6＋2＋3×3）＝17/11≈1.552.选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31
5、，66}。则(22*3)%11=6……0(41*3)%11=11……2(53*3)%11=14……5(08*3)%11=2……2(46*3)%11=12……6(30*3)%11=8……2(01*3)%11=0……3(31*3)%11=8……5(66*3)%11=9……03.已知散列函数为H(K)=Kmod12,健值序列为25，37，52，43，84，99，120，15，26，11，70，82，采用分离链接法处理冲突，试构造散列表，并计算查找成功的平均查找长度。查找成功的平均查找长度为：（4*2+8）/12=4/35.3设有一组关键字{29,01,13,15,56,20,87,27,69
6、,9,10,74}，散列函数为H(key)=key%17,采用线性探测法解决冲突。试在0~18的散列地址空间中对该关键字序列构造散列表，并计算成功查找的平均查找长度。5.4题目同上，采用平方探测法解决冲突。5.5设有一组关键字{92,81,58,21,57,45,161,38,117}，散列函数为H(key)=key%13,采用双散列探测法解决第i次冲突：H(key)=(H(key)+i*H2(key))%13,其中，H2(key)=(key%11)+1。试在0~12的散列地址空间中对该关键字序列构造散列表。5.6已知线性表关键字集合{21,11,13,25,48,6,39,83,30
7、,96,108}，散列函数为H(key)=K%11采用分离链接法处理冲突，试构造散列表，并计算查找成功的平均查找长度。5.7将关键字序列{7,8,30,11,18,9,14}散列存储到散列表中散列表的存储空间是一个下标从0开始的一个一维数组散列函数维：H（key）=（key×3）%p，处理冲突采用线性探测再散列法，要求装填因子为0.7。（1）请画出所构造的散列表；（2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。解：表长为10,p
