习题七和上机答案.doc

《习题七和上机答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题七7.1画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。解：依题意，假设长度为10的有序表为a，进行二分查找的判定树如图10.3所示。查找成功的平均查找长度：ASL=(1×1+2×2+3×4+4×3)/10=2.97.2假设按下述递归方法进行顺序表的查找：若表长≤10，则进行顺序查找，否则进行折半查找。试画出对表长n＝50的顺序表进行上述查找时，描述该查找的判定树，并求出在等概率情况下查找成功的平均查找长度。解：查找的判定树如下（结点从0开始，升序顺序查找）：结点所在

2、树深度即为查找次数，由此可计算平均查找长度为ASL=(1×1+2×2+4×3+8×4+8×5+8×6+8×7+8×8+3×9)/50=5.687.3一组有序的关键字如下：15，17，22，28，33，41，51，67，90。设法画出一棵具有平衡性的二叉排序树。如果对每一个关键字的查找概率相等，计算平均查找长度ASL。进一步写出解决该问题的算法。（提示：以中间位置元素为根）。ASL=（1×1＋2×2＋3×4＋4×2）/9=2.787.4已知下列关键字和它们对应的哈希函数值(哈希表长度未知,α无法求解)KeyZ

3、haoSunLiWangChenLiuZhangH(Key)6574164由此构造哈希表，用线性探测法解决冲突，计算该哈希表的装填系数α和平均查找长度ASL。若用拉链法解决冲突情况又如何？解：线性探测法(哈希表长度大于8时)ASL(7)=(1×5＋3＋6)/7=2哈希表长度等于8时ASL(7)=(1×5＋3＋7)/7=2.14α=表中填入的记录数/哈希表的长度拉链法ASL(7)=(1×5＋2×2)/7=1.287.5已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要

4、求它在等概率情况下查找成功的平均查找长度不超过3。解：将姓氏中的每一个字母换成字母表中的位置，将所有位置两两相乘再相加的和作为key值如周zhou,字母位置为26,8,15,21则key=(26×8＋15×21)%1000＝5237.6试编写一个开放地址法解决冲突的哈希表删除算法。解：/************************************************************************************//*基本思想*//*将哈希表中最后一个与删除关键字ke

5、y相同的关键字覆盖删除关键字*//*例如123451535,删除5后，12343515*//************************************************************************************/#include"stdio.h"#defineSIZE10/*最大表长度*/#defineM10/*冲突处理函数*//*****************************************************************

6、************/voidcreat_hash(int*);/*建立哈希表*/voiddel_hash(int*,int);/*删除元素*/voidoutput(int*);/*显示哈希表*//*****************************************************************************/voidmain(void){inthash[SIZE]={0};/*哈希表，初始化为0，表示没有元素*/intk;/*删除的元素*/printf("

7、=====================DelHashList=====================");creat_hash(hash);output(hash);printf("Inputthedelkey:");scanf("%d",&k);del_hash(hash,k);output(hash);getch();}/*****************************************************************************/voidcre

8、at_hash(int*hash)/*建立哈希表*/{intm,n,i;printf("Inputdata(most%d,-1isend):",SIZE);for(i=0;i