中南大学数据结构与算法第9讲查找课后作业答案.doc

第9章查找习题练习答案 1.对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较??答：　　设变量max和min用于存放最大元和最小元(的位置)，第一次取两个元素进行比较，大的放入max，小的放入min。从第2次开始，每次取一个元素先和max比较，如果大于max则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，一路比较下去都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元和最小元。 2.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：　(1)查找不成功，即表中无关键字等于给定值K的记录；　(2)查找成功，即表中有关键字等于给定值K的记录。答：　　查找不成功时，需进行n+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表和无序表是一样的。　　查找成功时，平均查找长度为(n+1)/2,有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。 3.画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。答：　　　　　　 　　等概率情况下，查找成功的平均查找长度为：　　　　ASL=(1+2*2+3*4+4*8+5*3)/18=3.556?　　查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5. 4.为什么有序的单链表不能进行折半查找?答：　　因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。 5.设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。 解：?　(1)查找b的过程如下(其中方括号表示当前查找区间，圆括号表示当前比较的关键字)　　　　　　下标：? 1? 2? 3? 4? 5? 6?? 7?? 8? 9 10 11 12 13?　　　第一次比较： [a? b? c? d? e? f? (g)? h? i? j? k? p? q]　　　第二次比较： [a? b (c) d? e? f]? g?? h? i? j? k? p? q　　　第三次比较： [a (b)]c? d? e? f?? g?? h? i? j? k? p? q　　　经过三次比较，查找成功。? (2)g的查找过程如下：??? 　 [a b c d e f (g) h i j k p q]??? 　一次比较成功。? (3)n的查找过程如下：? 　????? 下标：? 1? 2? 3? 4? 5? 6? 7?? 8? 9 10 11 12? 13???? 　第一次比较： [a? b? c? d? e? f (g)? h? i? j? k? p? q]?　 第二次比较：? a? b? c? d? e? f? g? [h? i (j) k? p? q]?　 第三次比较：? a? b? c? d? e? f? g?? h? i? j [k (p) q]? 　第四次比较：? a? b? c? d? e? f? g?? h? i? j [k] p? q]? 　经过四次比较，查找失败。 6.将(for, case, while, class, protected, virtual, public, private, do, template, const ,if, int)中的关键字依次插入初态为空的二叉排序树中，请画出所得到的树T。然后画出删去for之后的二叉排序树T,若再将for 插入T中得到的二叉排序树T是否与T相同?最后给出T的先序、中序和后序序列。答：　　二叉排序树T如下图：　　　　　　　　　 　 　　删去for后的二叉排序树如下图：　　 　　再插入结点for后的二叉排序树T：　　　? 　　　　　　　　　　 ? 二叉排序树T与T不同??? T的先序序列是：do case class const while protected private if for int virtual public template?　　T的中序序列是：case class const do for if int private protected public template virtual while　　T的后序序列是：const class case for int if private template public virtual prot