数据结构第9章查找习题

《数据结构第9章查找习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章习题课1.对于A[0..10]有序表,采用二分查找法时,求成功和不成功时的平均查找长度.并对有序表{12,18,24,35,47,50,62,83,90,115,134},当用二分查找法查找90时,需进行多少次查找可确定成功;查找47时需进行多少次查找可确定成功;查找100时,需进行多少次查找才能确定不成功.解首先构造有序表A[0..10]的二分查找判定树解首先构造有序表A[0..10]的二分查找判定树528012345678910013467910ASLsucc=(1*1+2*2+4*3+4*4)/11=3ASLunsucc=(4*3+8

2、*4)/12=3.67对于有序表528012345678910121824354750628390115134013467910对于有序表5028012345678910121824354750628390115134013467910对于有序表50248012345678910121824354750628390115134013467910对于有序表502490012345678910121824354750628390115134121835476283115134查找90时,需进行2次查找查找47时,需进行4次查找查找100时,需进行3次

3、查找9.2将整数序列{4,5,7,2,1,3,6}中的数依次插入到一颗空的二叉排序树中,度构造相应的二叉排序树,要求用图形给出构造过程,不需要编写程序.插入44插入545插入74574572插入2插入145721插入3457213插入64572136设哈希表长m=14,哈希函数H(keyy)=keymod11。表中已有4个结点addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,基余地址均为空，如用平方探查法处理冲突，求关键字49的结点地址。解h(49)=49mod11=5有冲突d1=(d0+12)mod11=6

4、仍有冲突d2=(d0+22)mod11=9无冲突答关键字49的结点地址为9