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

第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 protected while do

7.对给定的关键字集合,以不同的次序插入初始为空的树中,是否有可能得到同一棵二叉排序树? 答:

有可能。如有两个序列: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.设二叉排序树中关键字互不相同,则其中最小元必无左孩子,最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗? 答:

此命题正确。假设最小元有左孩子,则根据二叉排序树性质,此左孩子应比最小元更小,如此一来就产生矛盾了,因此最小元不可能有左孩子,对于最大元也是这个道理。

但最大元和最小元不一定是叶子,它也可以是根、内部结点(分支结点)等,这得根据插入结点时的次序而定。

新结点总是作为叶子插入在二叉排序树中的。

11.在一棵m阶的B-树中,当将一关键字插入某结点而引起该结点的分裂时,此结点原有多少个关键字?若删去某结点中的一个关键字,而导致结点合并时,该结点中原有几个关键字? 答:

在一棵m阶的B-树中,若由于一关键字的插入某结点而引起该结点的分裂时,则该结点原有m-1个关键字。

若删去某结点中一个关键字而导致结点合并时,该结点中原有┌m/2┐-1个关键字。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4