数据结构第七章参考答案

习题71.填空题（1）由10000个结点构成的二叉排序树，在等概率查找的条件下，查找成功时的平均查找长度的最大值可能达到（___________）。答案：5000.5（2）长度为11的有序序列：1，12，13，24，35，36，47，58，59，69，71进行等概率查找，如果采用顺序查找，则平均查找长度为（___________），如果采用二分查找，则平均查找长度为（___________），如果采用哈希查找，哈希表长为15，哈希函数为H（key）＝key%13，采用线性探测解决地址冲突，即di=(H(key)+i)%15，则平均查找长度为（保留1位小数）（___________）。答案：6，3，1.6（3）在折半查找中，查找终止的条件为（___________）。答案：找到匹配元素或者lowhigh?（4）某索引顺序表共有元素275个，平均分成5块。若先对索引表采用顺序查找，再对块元素进行顺序查找，则等概率情况下，分块查找成功的平均查找长度是（___________）。答案：31（5）高度为8的平衡二叉树的结点数至少是（___________）。答案：54计算公式：F(n)=F(n-1)+F(n-2)+1（6）对于这个序列{25，43，62，31，48，56}，采用的散列函数为H(k)=k%7，则元素48的同义词是（___________）。答案：62（7）在各种查找方法中，平均查找长度与结点个数无关的查找方法是（___________）。答案：散列查找（8）一个按元素值排好的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，平均比较次数分别是s和b，在查找成功的情况下，s和b的关系是（___________）；在查找不成功的情况下，s和b的关系是（___________）。答案：(1)(2s-1)b=2s([log2(2s-1)]+1)-2[log2(2s-1)]+1+1(2)分两种情况考虑，见解答。解：(1)设所有元素的个数为n，显然有s=n*(n+1)/(2n),则n=2s-1设折半查找树高度为k，则前k-1层是满二叉树，最后一层的节点数为n-(2k-1-1）因此，总比较次数nb=20*1+21*2+22*3+…+2k-2*(k-1)+(n-(2k-1-1))*k,而20*1+21*2+22*3+…+2k-2*(k-1)=2k-1*k-2k+1因此nb=2k-1*k-2k+1+(n-(2k-1-1))*k=(n+1)k-2k+1又k=[log2n]+1,n=2s-1,所以有(2s-1)b=2s([log2(2s-1)]+1)-2[log2(2s-1)]+1+1(2)查找不成功，对于顺序查找有：s=n。对于折半查找，找不到的情况有n+1种,查找到每个叶子节点或度为1的节点后就不再查找，设折半查找树高度为k，则第k-1层的节点数x=2k-2，第k层的节点数y=n-(2k-1-1）（a）当第k层的节点数y小于等于第k-1层的节点数x时，则第k-1层有y结点度为1，其余x-y个结点度为0。则查找次数为：(n+1)b=2yk+2(x-y)(k-1)+y(k-1)=2x(k-1)+yk(n+1)b=2k-1*(k-1)+(n-(2k-1-1))*k（b）当第k层的节点数y大于第k-1层的节点数x时，则第k-1层不存在度为0的结点，有2x-y个结点度为1，其余y-x个结点度为2则查找次数为：(n+1)b=2yk+(2x-y)(k-1)=2x(k-1)+y(k+1)(n+1)b=2k-1*(k-1)+(n-(2k-1-1))*(k+1)将k=[log2n]+1，n=s分别代入（a）（b）两个等式即得。2.选择题（1）从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个结点。A.nB.n/2C.(n-1)/2D.(n+1)/2（2）对一个长度为50的有序表进行折半查找，最多比较（）次就能查找出结果。A.6B.7C.8D.9（3）对有18个元素的有序表做折半查找，则查找A[3]（下标从1开始）的比较序列的下标依次为（）。A.1-2-3B.9-5-2-3C.9-5-3D.9-4-2-3（4）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为－1，右孩子的平衡因子为0，则做（）型调整以使其平衡。A.LLB.LRC.RLD.RR（5）理论上，散列表的平均比较次数为（）次。A.1B.2C.4D.n（6）二叉排序树中，最小值结点的（）。A.左指针一定为空B.右指针一定为空C.左、右指针均为空D.左、右指针均不为空（7）散列技术中的冲突指的是（）。A.两个元素具有相同的序号B.两个元素的键值不同，而其他属性相同C.数据元素过多D.不同键值的元素对应于相同的存储地址（8）散列表表长m=14，散列函数H(k)=k%11。表中已有15，38，61，84四个元素，如果用线性探测法处理冲突，则元素49的存储地址是（）。A.8B.3C.5D.9（9）采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（）。A.一定都是同词义词B.一定都不是同义词C.不一定都是同义词D.都相同（10）静态查找与动态查找的根本区别在于（）。A.它们的逻辑结构不一样B.施加在其上的操作不同C.所包含的数据元素的类型不一样D.存储实现不一样3．设一个散列表包含hashSize=13个表项，其下标从0到12，采用线性探查法解决冲突，请按以下要求，将关键码{10，100，32，45，58，126，3，29，200，400，0}散列到表中。（1）散列函数采用除留余数法，用%hashSize(取余运算)将各关键码映像到表中，请指出每一个产生冲突的关键码可能产生多少次冲突。答案：如下表，H(key)0123456789101112key032920032455810010126400产生冲突的关键码有：29－1次，45－1次，58－2次，126－2次，400－2次（2）散列函数采用先将关键码各位数字折叠相加，再用%hashSize将相加的结果映像到表中的办法，请指出每一个产生冲突的关键码可能产生多少次冲突。答案：如下表，H(key)0123456789101112key581010032003240004512629产生冲突的关键码有：100－1次，200－2次，400－2次，0－7次，126－1次4．试编写一个函数，完成拉链法解决冲突的散列表上删除一个指定结点的算法。5．设散列表的长度为13，散列函数为H(k)=k%13，给定的关键字序列为：19，14，23，01，68，20，84，27，55，11，10，79。试画出分别用拉链法和线性探测查找解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法的查找成功和查找不成功的平均查找长度。答案：拉链法：1367101119142316820842755111079平均查找次数：成功时是21/12=1.75次，不成功时是(4+2+2+2+1+2+1)/13=12/13=0.92次（在这里查找比较是指元素值的比较。如果指针为空，则不进行查找比较，此时不算查找）。线性探测法：H(key)0123456789101112key140168275519208479231110冲突次数010320028002成功时的比较121431139113次数不成功时的比较次数0121110987654321平均查找次数：成功时是2.5次，不成功时ASL=（0+12+11+10+9+8+7+6+5+4+3+2+1）/13=6次。