第7章自测练习题参考答案

1第7章自测练习题参考答案1．有一个有序文件，其中各记录的关键字为：{3,4,5,6,7,8,10,17,19,20,27,32,43,54,65,76,87}，当用折半查找算法查找关键字为4,20,65时，其比较次数分别为多少?解：该有序文件长度为17，根据折半查找算法画出判定树如下图所示。从图中可得出：当关键字为4,20,65时，其比较次数分别为3，4，3。2.若对大小均为n的有序顺序表和无序顺序表分别进行顺序查找，试就下列三种情况分别讨论两者在等查找概率时的平均查找长度是否相同?(1)查找失败；(2)查找成功；(3)查找成功，表中有多个关键字等于给定值的记录，一次查找要求找出所有记录。解：(1)平均查找长度不相同。有序顺序表小于等于无序顺序表。(2)平均查找长度相同。(3)平均查找长度不相同，有序顺序表小于等于无序顺序表。3.试按下列次序将各关键字插入到二叉平衡树中，画出重新平衡的情况。关键字依次为：8、9、12、2、1、5、3、6、7、11解：生成并调整成平衡二叉排序树的过程如下图(a)～(j)所示。K=46571110128213151416491317K=20K=65判定树89128RR89(b)不调整1289(c)调整(a)初始91282(d)不调整912821LL912281(e)调整24.已知长度为12的表：（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）。(1)试按表中元素的顺序，依次插入一棵初始为空的二叉树；试画出插入完成之后的二叉排序树，并求其在等查找概率情况下查找成功的平均查找长度。(2)若对表中元素先进行排序构成有序表，试求在等查找概率情况下对此有序表进行二分查找时查找9122815LR9128251LL9825112(f)调整39825112(g)不调整39825112(h)不调整63982511267RR1985621273(i)调整RL111985621273RR1211985621173911185621273(j)调整JanonFebMarAugJulDecMayAprJunNovOctSep3成功的平均查找长度。解：(1)二叉排序树如下图所示。平均查找长度SAL=(1*1+2*2+3*3+3*4+2*5+1*6)/12=42/12=3.5(2)对有序表（Apr,Aug,Dec,Feb,Jan,Jul,Jun,Mar,May,Nov,Oct,Sep）进行二分查找时，其判定树如下图所示,所以平均查找长度SAL=(1*1+2*2+4*3+5*4)/12=37/12≈3.085.在题图7-1所示的3阶B-树中，删除关键字37，试画出删除过程。解：JulnonDecMayAugMarOctAprJunFebNovSepJan4511523761937810128题图7-145115261937810128(a)删除3745112852619378101(b)双亲28下移61112878529310145(c)向右兄弟借关键字6146.已知一个线性表(38，25，74，63，52，48)，采用的散列函数为H(Key)=Keymod7，将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为多少？若利用链地址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为多少？解：（1）用线性探测的开放定址法解决冲突的哈希表:H(38)=38%7=3比较1次H(25)=25%7=4比较1次H(74)=74%7=4(冲突)H1(74)=(H(74)+1)%7=(4+1)%7=5(成功)比较2次H(63)=63%7=0比较1次H(52)=52%7=3(冲突)H1(52)=(H(52)+1)%7=(3+1)%7=4(冲突)H2(52)=(H(52)+2)%7=(3+2)%7=5(冲突)H3(52)=(H(52)+3)%7=(3+3)%7=6(成功)比较4次H(48)=48%7=6(冲突)H1(48)=(H(48)+1)%7=(6+1)%7=0(冲突)H1(48)=(H(48)+2)%7=(6+2)%7=1(成功)比较3次地址01234567关键字634838257452比较次数131124(2)平均查找长度ASL=（3*1+1*2+1*3+1*4）/6=12/6=2（3）用链地址法解决冲突的哈希表:H(38)=38%7=3比较1次H(25)=25%7=4比较1次H(74)=74%7=4(冲突)比较2次H(63)=63%7=0比较1次H(52)=52%7=3(冲突)比较2次H(48)=48%7=6比较1次(4)平均查找长度ASL=（4*1+2*2）/6=8/6=4/37.设有关键字序列{22,41,53,46,30,13,01,67}，选取哈希函数H（k）=3k%11，试用下列两种处理冲突的方法分别在0~10的散列地址空间中构造哈希表。（1）线性探测法；（2）线性补偿探测法（取Q=5）。解：（1）线性探测法构造哈希表过程如下：H(22)=3*22%11=0比较1次H(41)=3*41%11=2比较1次H(53)=3*53%11=5比较1次∧∧∧0123456763∧382548∧52∧74∧5H(46)=3*46%11=6比较1次H(30)=3*30%11=2(冲突)H1(30)=(H(30)+1)%11=(2+1)%11=3(成功)比较2次H(13)=3*13%11=6(冲突)H1(13)=(H(13)+1)%11=(6+1)%11=7(成功)比较2次H(01)=3*1%11=3(冲突)H1(01)=(H(01)+1))%11=4(成功)比较2次H(67)=3*67%11=3(冲突)H1(67)=(H(67)+1))%11=(3+1)%11=4(冲突)H2(67)=(H(67)+2))%11=(3+2)%11=5(冲突)H3(67)=(H(67)+3))%11=(3+3)%11=6(冲突)H4(67)=(H(67)+4))%11=(3+4)%11=7(冲突)H5(67)=(H(67)+5))%11=(3+5)%11=8(成功)比较6次地址012345678910关键字2204130015346136700比较次数10122112600查找成功时的平均查找长度为：ASL=(4*1+3*2+1*6)/8=18/8=2.25（2）线性补偿探测法（取Q=3）构造哈希表过程如下：(1)H(22)=3*22%11=0比较1次(2)H(41)=3*41%11=2比较1次(3)H(53)=3*53%11=5比较1次(4)H(46)=3*46%11=6比较1次(5)H(30)=3*30%11=2(冲突)H1(30)=(H(30)+3)%11=(2+3)%11=5(冲突)H2(30)=(H(30)+6)%11=(2+6)%11=8(成功)比较3次(6)H(13)=3*13%11=6(冲突)H1(13)=(H(13)+3)%11=(6+3)%11=9(成功)比较2次(7)H(01)=3*1%11=3(成功)比较1次(8)H(67)=3*67%11=3(冲突)H1(67)=(H(67)+3))%11=(3+3)%11=6(冲突)H2(67)=(H(67)+6))%11=(3+6)%11=9(冲突)H3(67)=(H(67)+9))%11=(3+9)%11=1(成功)比较4次地址012345678910关键字22674101053463013比较次数141101132查找成功时的平均查找长度为：ASL=(5*1+1*2+1*3+1*4)/8=14/8=1.75