第九章 答案分析和总结.docx

第9章 查找

1.C11.B

1.C

11.B

2.D

12.B

3D

4.A

5.B

6.1C

6.2C

15.D

7.1B

16.B

7.2A

17.D

18.D

9.C

19.D

10.C

20.C

二．判断题

1.√

1.√

2.√

3.×

4.√

5.√

6.×

7.√

8.×

9.×

10.

×

11.

√

12.

×

13.

√

14.

×

三．填空题

1．n n+1 2．6,9,11,12 3．5

4．26（第4层是叶子结点，每个结点两个关键字）

5．m-1,「m/2?-1 9．2,4,3

6．小于等于表长的最大素数或不包含小于20的质因子的合数

8．(n+1)/2 9．(n+1)/n*log(n+1)-1 10．结点的左子树的高度减去结点的右子树的高

2

度

11．(1)静态查找表(2)动态查找树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈希(7)

建立公共溢出区

n?1

12．log ( 2 )+1 ，(n+1)/2（最坏情况是每个结点只要一个孩子结点的情况，这时的

?m/2?

平均时间复杂度为（n+1）/2,而log?( 5(n?1))?2是通常情况下的ASL）13．31

主关键字

插入 删除

16(1)low=mid+1(2)high=mid-1 (3)high=low

四．应用题1．概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答略。

3．

散列地址

0

1

2

3

4

5

6

7

8

9

关键字

14

01

9

23

84

27

55

20

比较次数

1

1

1

2

3

4

1

2

查找成功平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8

以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）%10=7（冲突）H2=（6+22）%10=0（冲突） H3=（6+33）%10=5 所以比较了4次。

注意：计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i（0

≤i≤m-1）时的查找次数。如下例中m=10。对于关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，哈希函数为H（key）=key%7采用线性探测再散列方法解决冲突，则哈希表如下：

散列地址

0

1

2

3

4

5

6

7

8

9

关键字

21

15

30

36

25

40

26

37

比较次数

1

1

1

3

1

1

2

6

故查找失败时的平均查找长度为：ASLunsu=c（c4+8+7+6+5+4+3+2+1+1）/10=4.6

4.

ASL查找成功=18/13

7.如下图：

9．（1）当插入26后的树形为：

插入85后树形为：

（2）删除53后为：

删除37后：

10.

（1）构造的二叉排序树为： （4）删除结点66后;

(2)对于一个二叉排序树，想得到一个从大到小的序列只要先读右子树再读根结点，最后读左子树的遍历这颗二叉树就可以了。如果是要从小到大的序列，则只需中序遍历这颗二叉树就可。

该二叉树的平均查找长度为：ASL=（1*1+2*2+3*4+4*3）/10=2.911.

单向左旋

单向左旋

先右旋后左旋

先右旋后左旋

12.（1）二叉判定树为

（2）若要查找54，则需要查找：30，63，42，54

（3）若要查找90，则需查找：30，63，87，95，空

假定每个元素的查找概率相等，则查找成功时的平均查找长度为：

ASL=（1*1+2*2+4*3+5*4）/12=37/12