第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的过程如下(其中方括号表示当前查找区间，圆括号表示当前比较的关键字)下标：12345678910111213第一次比较：[abcdef(g)hijkpq]第二次比较：[ab(c)def]ghijkpq第三次比较：[a(b)]cdefghijkpq经过三次比较，查找成功。(2)g的查找过程如下：[abcdef(g)hijkpq]一次比较成功。(3)n的查找过程如下：下标：12345678910111213第一次比较：[abcdef(g)hijkpq]第二次比较：abcdefg[hi(j)kpq]第三次比较：abcdefghij[k(p)q]第四次比较：abcdefghij[k]pq]经过四次比较，查找失败。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"的先序序列是：docaseclassconstwhileprotectedprivateifforintvirtualpublictemplateT"的中序序列是：caseclassconstdoforifintprivateprotectedpublictemplatevirtualwhileT"的后序序列是：constclasscaseforintifprivatetemplatepublicvirtualprotectedwhiledo7.对给定的关键字集合，以不同的次序插入初始为空的树中，是否有可能得到同一棵二叉排序树?答：有可能。如有两个序列：3，1，2，4和3，4，1，2，它们插入空树所得的二叉排序树是相同的。8.将二叉排序树T的先序序列中的关键字依次插入一空树中，所得和二叉排序树T'与T否相同?为什么?答：这两棵二叉树完全相同。9.设二叉排序树中关键字由1至1000的整数构成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树上查找到的序列?(a)2，252，401，398，330,344，397，363；(b)924,220,911,244,898,258,362,363;(c)925,202,911,240,912,245,363;(d)2,399,387,219,266,382,381,278,363.答：(c)是不可能查找到的序列。把这四个序列各插入到一个初始为空的二叉排序树中，结果可以发现，(c)序列所形成的不是一条路径，而是有分支的，可见它是不可能在查找过程中访问到的序列。10.设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插...
