第 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 a b c d e f g
h i j [k (p) q] h i j [k] p
q]
经过四次比较，查找失败。
6.将(for, case, while, class, protected, virtual, public, private, do, template, const ,if, int)中的关键字依次插 入初态为空的二
叉排序树中，请画岀所得到的树 入T'中得到的二叉排序树 答：
二叉排序树T如下图：
T。然后画岀删去for之后的二叉排序树 T',若再将for插
T”是否与T相同？最后给岀T\的先序、中序和后序序列。
中南大学数据结构与算法第9章查找课后作业答案剖析
