第9章 查找

第九章查找

一、基本概念

1、静态查找表、动态查找表的概念

2、静态查找表

（1）顺序查找、折半查找、分块查找的基本方法

（2）给定查找表，查找某元素的比较次数计算

（3）平均查找长度的计算

3、动态查找表

（1）二叉排序树的构造及平均查找长度计算

（2）平衡二叉树的旋转平衡方法

4、哈希表

（1）哈希表、哈希函数、散列、冲突、同义词、装填因子的概念

（2）哈希函数的常用构造方法

（3）冲突的解决方法（重点掌握开放地址法和链地址法）

（4）哈希表的构造和平均查找长度计算

二、练习题

1.顺序查找法适合于存储结构为____的线性表。

A. 散列存储

B. 顺序存储或链接存储

C. 压缩存储

D. 索引存储

2.对线性表进行二分查找时，要求线性表必须____。

A. 以顺序方式存储

B. 以链接方式存储

C. 以顺序方式存储，且结点按关键字有序排序

D. 以链接方式存储，且结点按关键字有序排序

3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____.

A. n

B. n/2

C. (n+1)/2

D. (n-1)/2

4.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为____。

A．O（n2） B. O(nlog2n) C. O(n) D. O(log2n)

5.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，____次比较后查找成功。

A. 1

B. 2

C. 4

D. 8

6.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：

addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7

如用二次探测再散列处理冲突，关键字为49的结点的地址是____。

A. 8

B. 3

C. 5

D. 9

7.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为____。

A. 35/12

B. 37/12

C. 39/12

D. 43/12

8．解决散列法中出现的冲突问题常采用的方法是。

A.数字分析法、除余法、平方取中法

B.数字分析法、除余法、线性探测法

C.数字分析法、线性探测法、多重散列法

D.线性探测法、多重散列法、链地址法

9．采用线性探测法解决冲突问题，所产生的一系列后继散列地址。

A.必须大于等于原散列地址

B.必须小于等于原散列地址

C.可以大于或小于但不能等于原散列地址

D.地址大小没有具体限制

11．对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于。

A.静态查找表

B.动态查找表

C.静态查找表与动态查找表D两种表都不适合

12.散列表的平均查找长度。

A.与处理冲突方法有关而与表的长度无关

B.与处理冲突方法无关而与表的长度有关

C.与处理冲突方法有关而与表的长度有关

D.与处理冲突方法无关而与表的长度无关

13．平衡二叉排序树上任一结点的平衡因子只可能是、或。

14．在散列函数H(key)=key%p中，p应取____。

15．在散列存储中，装填因子α的值越大，则____；α的值越小，则____。

综合题类型：

16. 选取哈稀函数H（k）=（3k）MOD 11。用开放定址法处理冲突，di=i（（7k）MOD 10+1）（I=1，2，3，…）.试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。

17.已知一组关键字{49，38，65，97，76，13，27，44，82，35，50}，画出由此生成的二叉排序树，注意边插入边平衡，并计算等概率下查找成功的平均查找长度。（要求按插入和调整步骤画出生成过程）

讲课提要

【主要内容】

1．基本概念和术语

2．线性表的查找

3．树表的查找

【教学目标】

1．熟练掌握顺序表和有序表的查找方法。

2．熟悉静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系。

3．熟练掌握二叉排序树的构造和查找方法。

4．了解二叉平衡树维护平衡的方法。

5．熟练掌握哈希表的构造方法，深刻理解哈希表与其他结构的表的实质性的差别。 6．掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。

学习指导

1．查找的基本概念

? 查找也称为检索。进行查找运算的数据元素通常是同一数据类型的数据元素或记录，由它们构成的集合又称为查找表。查找表分为静态查找表和动态查找表。

? 静态查找表：仅对查找表进行查找操作，即查找关键字等于给定值的数据元素是否在查找表中或检索其属性，查找前后不能改变表。

? 动态查找表：对查找表除进行查找操作外，可能还要向表中插入数据元素，或删除表中数据元素的表。

? 关键字、主关键字和次关键字：查找表中区别不同记录的数据项的数据元素称为关键字。若此关键字可以惟一的标识一个记录，则称此关键字为主关键字（Primary Key ）。反之，称用以识别若干记录的关键字为次关键字（Secondary Key ）。

? 查找（Searching ）是根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在一个这样的记录，则称查找成功，反之，查找不成功。

注意：不同的查找方法，不同的查找表存储结构，具有不同的查找效率。

? 平均查找长度，即在查找成功情况下的平均比较次数。平均查找长度的计算公式为：

ASL=

∑=n

i PiCi 1

其中，n 表示查找表的长度，即表中所包含的数据元素的个数，P i 是查找第i 个元素的概率，一般认为查找每个元素的概率相等。C i 是查找第i 个元素时，同给定值K 的比较次数。在查找每个元素等概率的情况下，则平均查找长度的计算公式变为：

ASL =2

12)1(1)121(1)1(1111+=

+=++-+-+=+-=∑∑==n n n n n n n n i n n Ci n n i n i 其对应的时间复杂度为：O （n ）。 2．线性表查找

线性表查找是指进行查找运算的查找表所采用的存储结构是线性的。 （1）顺序查找

最简单的查找技术是顺序查找（Sequential Search ），这种查找技术适用于基本线性表结构文件，如顺序存储或链式存储的基本线性表结构文件。

顺序查找的算法思想是：从表的末端开始，依次将记录的关键字与给定值K 进行比较，若出现相等情况，则查找成功；若直至第一个记录仍未发现相等，则查找失败。

在顺序存储和链式存储两种方法中，由于每个元素在查找表中位置不同，查找成功时的比较次数也不同。在不等概率的条件下，为了减少整个算法查找的次数，可以把查找概率大的数据元素放在查找表的靠前的位置。

（2）折半查找

折半查找（Binary Search ）也叫二分查找。算法思想为：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，则在中间元素的右

半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，则查找失败。

从折半查找过程看，可用二叉树来描述，称这个描述查找过程的二叉树为判定树。 以树高为k 的满二叉树（n=2k +1）为例。假设表中每个元素的查找是等概率的，即P i =1/n ，则树的第i 层有2i-1个结点，因此，折半查找的平均查找长度为：

1)1(log 21

-+≈=∑=n PiCi ASL n

i

【例7-1】有序表按关键字排列如下：7，14，18，21，23，29，31，35，38，42，46，49，52，在表中查找关键字为14和22的数据元素，并画出折半查找过程的判定树。

解：折半查找的过程描述如下：

① low=1；high=length ； //设置初始区间 ② 当low>high 时，返回查找失败信息 //表空，查找失败 ③ low ≤high ，mid=(low+high)/2; //取中点

a. 若kx

b. 若kx>tbl.elem[mid].key ，low=mid+1；转② //查找在右半区进行

c. 若kx=tbl.elem[mid].key ，返回数据元素在表中位置 //查找成功 ● 查找关键字为14的过程如下：

low=1 ①设置初始区间 high=13 ─────────────────────────── ↑ ②表空测试，非空；

mid=7 ③得到中点，比较测试为a 情形 ↑ ↑

low=1 high=6 high=mid-1，调整到左半区 ──────────────────────────── ↑ ②表空测试，非空；

mid=3 ③得到中点，比较测试为a 情形 ↑ ↑

low=1 high=2 high=mid-1，调整到左半区

──────────────────────────── ↑ ②表空测试，非空；

mid=1 ③得到中点，比较测试为b 情形 ↑↑

low=2 high=2 low=mid+1，调整到右半区

──────────────────────────── ↑ ②表空测试，非空；

mid=2 ③得到中点，比较测试为c 情形 查找成功，返回找到的数据元素位置为2

● 查找关键字为22的过程如下：

low=1 ①设置初始区间 high=13 ──────────────────────────── ↑ ②表空测试，非空；

mid=7 ③得到中点，比较测试为a 情形 ↑ ↑

low=1 high=6 high=mid-1，调整到左半区 ─────────────────────────── ↑ ②表空测试，非空；

mid=3 ③得到中点，比较测试为b 情形

↑ ↑

low=4 high=6 low=mid+1，调整到右半区

────────────────────────────

↑ ②表空测试，非空；

mid=5 ③得到中点，比较测试为a 情形

↑↑

low=4 high=4 high=mid-1，调整到左半区

────────────────────────────

↑ ②表空测试，非空；

mid=4 ③得到中点，比较测试为b 情形

↑ ↑

high=4 low=5 low=mid+1，调整到右半区

────────────────────────────

②表空测试，为空；查找失败，返回查找失败信息为0

● 查找过程的判定树如图7-1所示。

（3）索引查找

索引查找又称为分块查找，是对顺序查找的一种改进。算法思想是：将查找表分成若干个子表，并对子表建立索引表，查找表的每一个子表由索引表中的索引项确定。索引项包括两个字段：关键字字段（存放对应子表中的最大关键字值）；指针字段（存放指向对应子表的指针），并且要求索引项按关键字字段有序。查找时，先用给定值k 在索引表中检测索引项，以确定所要进行的查找在查找表中的查找分块（由于索引项按关键字字段有序，可用顺序查找或折半查找），然后，再对该分块进行顺序查找。

索引查找（分块查找）由索引表和子表查找两步完成。设n 个数据元素的查找表分为s 子表，且每个子表均为m 个元素，则s=n/m 。这样，索引查找的平均查找长度为：

ASL=ASL 索引表+ASL 子表=1)(2121211111++=+++=+∑∑==m m

n

m s j m i s m j s i

3．树表查找

（1）二叉排序树

二叉排序树（Binary Sort Tree ）又称二叉查找树（Binary Search Tree ），它或者是一棵空树，或者是一棵具有如下性质的非空二叉树：

? 若它的左子树非空，则左子树上的所有结点的关键字的值均小于根结点的值。 ? 若它的右子树非空，则右子树上的所有结点的关键字的值均大于根结点的值。 ? 左右子树本身又各是一棵二叉排序树。 二叉排序树的查找过程为：

（i ）若查找树为空，查找失败。

（ii ）查找树非空，将给定值k 与查找树的根结点关键字比较。

（iii ）若相等，查找成功，结束查找过程，否则，继续查找。

（iv ）当给定值k 小于根结点关键字，查找将在左子树上继续进行，转（i ）。 （v ）当给定值k 大于根结点关键字，查找将在右子树上继续进行，转（i ）。 ②算法实现

以二叉链表作为二叉排序树的存储结构来实现。 ③二叉排序树的运算 （i ）二叉排序树的创建

（ii ）二叉排序树的插入算法 （iii ）二叉排序树的删除运算 ④算法分析

在二叉排序树上查找关键字等于给定值k 的过程，正好经过了一条从树根到该结点的路径。与关键字k 比较的次数试该路径的长度加1。因此，查找的次数不会超过树的深度。由于二叉排序树的形状取决于输入的关键字序列，因此，对于同一组关键字，如果输入顺序不一样，所得到的二叉排序树也不一样。最好的情况是二叉排序树的形态和折半查找的判定树相同。

【例7-2】记录的关键字序列为：63，90，70，55，67，42，98，83，10，45，58，则画出构造一棵二叉排序树的过程。

解：构造二叉排序树的过程如图7-2所示。

（2）平衡二叉树 ①平衡二叉树的定义

平衡二叉树（Balanced Binary Tree 或 Height-Balanced Tree ）又称A VL 树。它或者是一棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过1。

②平衡二叉树的调整

（i ）左单旋转（又称RR 型）

（ii ）右单旋转（又称LL 型）

（iii ）左后右双向旋转（又称LR 型） （iv ）先右后左双向旋转（又称RL 型） ③平衡二叉树的算法 4．哈希表查找 （1）哈希表的定义

63

63 90 98 70 67 55 42

63 90 70 67

55 42

63 90 70 67

55 63 90 70

55 63 90 70

63 90

63 58 55

90

42 98 70 45 10 67 83

63 55 90 42

98

70 45 10 67 83

63 90 98 70 67 83

55 42 10

63 90 98 70 67 83

55 42

图7-2 二叉排序树的构造过程

把关键字与存储位置之间的对应关系，称之为哈希函数。每个关键字通过哈希函数得到一个存储位置，这个存储位置称为哈希地址。一组关键字通过哈希函数得到一段有限的连续地址，这段地址是所有关键字的一个映像，称为哈希表。哈希表又称为散列表或杂凑表。

（2）哈希函数的构造

常用的构造哈希函数的方法有：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。

实际工作中需视不同的情况采用不同的哈希函数。通常，考虑的因素有：

①计算哈希函数所需时间（包括硬件指令的因素）；

②关键字的长度；

③哈希表的大小；

④关键字的分布情况；

⑤记录的查找频率。

（3）冲突处理方法

假设哈希表的地址集为0～（n-1），冲突是指由关键字得到的哈希地址为j（0≤j≤n-1）的位置上已存有记录，则“处理冲突”就是为该关键字的记录找到另一个“空”的哈希地址。通常的处理冲突的方法有下列几种：

①开放定址法：线性探测法和二次探测法

②再哈希法

③拉链法

④建立一个公共溢出区

（4）查找及分析

在哈希表上进行查找的过程和哈希造表的过程基本一致。给定值k，根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找“下一个地址”，直至哈希表中某个位置为“空”或者表中所填记录的关键字等于给定值时为止。

在一般情况下，处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。哈希表的装填因子定义为：

α = 表中填入的记录数/哈希表的长度

α表示哈希表的装满程度。α越小，发生冲突的可能性就越小，平均查找长度也小，但空间的浪费加大；反之，α越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。

【例7-3】关键字集为（47，7，29，11，16，92，22，8，3），哈希表表长为11。H（key）= key MOD 11，用线性探测法处理冲突。

解：建表如下：

分析：47、7、11、16、92均是由哈希函数得到的没有冲突的哈希地址而直接存入的。

H（29）= 7，哈希地址上冲突，需寻找下一个空的哈希地址：

由H i =（H（29）+1）MOD 11 = 8 ，哈希地址8为空，将29存入。另外，22、8同样在哈希地址上有冲突，也是由H i找到空的哈希地址的。

而H（3）= 3，哈希地址上冲突，由：H1=（H（3）+1）MOD 11 = 4，仍然冲突。

H2=（H（3）+2）MOD 11 = 5，仍然冲突。H3=（H（3）+3）MOD 11 = 6，找到空的哈希地址，存入。

【例7-4】关键字序列为（47，7，29，11，16，92，22，8，3，50，37，89，94，21），哈希函数为：Hash(key)=key mod 11，用拉链表处理冲突。

解：建表如下：

14，55，20，84，27，68，11，10，77），采用哈希函数：H（key）= key % 13，若用开放定址法的线性探测法解决冲突，试在0～13的哈希地址空间中对该关键字序列构造哈希表并求其成功查找时的ASL。

解：依题意，m=13，线性探测法的下一个地址计算公式为：

d i = H（key）

d i+1 = （d i+1）% m ；i=1，2，…

其计算函数如下：

H（19）= 19 % 13 = 6

H（01）= 01 % 13 = 1

H（23）= 23 % 13 = 10

H（14）= 14 % 13 = 1 （冲突）

H（14）=（1+1）% 14 = 2

H（55）= 55 % 13 = 3

H（20）= 20 % 13 = 7

H（84）= 84 % 13 = 6 （冲突）

H（84）=（6+1）% 14 = 7 （仍冲突）

H（84）=（7+1）% 14 = 8

H（27）= 27 % 13 = 1 （冲突）

H（27）=（1+1）% 14 = 2 （仍冲突）

H（27）=（2+1）% 14 = 3 （仍冲突）

H（27）=（3+1）% 14 = 4

H（68）= 68 % 13 = 3 （冲突）

H（68）=（3+1）% 14 = 4 （仍冲突）

H（68）=（4+1）% 14 = 5

H（11）= 11 % 13 = 11

H（10）= 10 % 13 = 10 （冲突）

H（10）=（10+1）% 14 = 11 （仍冲突）

H（10）=（11+1）% 14 = 12

H（77）= 77 % 13 = 12 （冲突）

H（77）=（12+1）% 14 = 13

ASL=（1+2+1+4+3+1+1+3+1+1+3+2）/12=23/12≈1.9

一、选择题

1、已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（ A ）次。

A. 1

B. 2

C. 3

D. 4

2、有一组关键字序列{13,16,6,34,32,98,73,1,27}，哈希表的表长为13，哈希函数为H(key)=key MOD 13,冲突解决的办法为链地址法，请构造哈希表（用图表示）。

3、解决哈希冲突的主要方法有（）。

A. 数字分析法、除余法、平方取中法

B. 数字分析法、除余法、线性探测法

C. 数字分析法、线性探测法、再哈希法

D. 线性探测法、再哈希法、链地址法

4、在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（）。

n C. (h+1)/2 D. h

A. n

B. log

2

5、已知表长为25的哈希表，用除留取余法，按公式H(key)=key MOD p 建立哈希表，则p应取（）为宜。

A. 23

B. 24

C. 25

D. 26

6、设哈希表长m=14,哈希函数H(key)=key MOD 11。表中已有4个结点：

addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为（ A ）。

A.8

B. 3

C. 5

D. 9

7、在散列查找中，平均查找长度主要与（ C ）有关。

A. 散列表长度

B. 散列元素个数

C. 装填因子

D. 处理冲突方法

8、根据一组记录（56，42，50，64，48）依次插入结点生成一棵AVL树，当插入到值为的结点时需要进行旋转调整。

9、m阶B-树中的m是指（）。

A. 每个结点至少具有m棵子树

B. 每个结点最多具有m棵子树

C. 分支结点中包含的关键字的个数

D. m阶B-树的深度

10、一个待散列的线性表为k={18,25,63,50,42,32,9}，散列函数为H(k)=k MOD 9，与18发生冲突的元素有（）个。

A. 1

B. 2

C. 3

D. 4

11、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插到集合中，这种方式主要适合于（）。

A. 静态查找表

B. 动态查找表

C. 静态查找表和动态查找表

D. 两种表都不适合

12、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值为82的结点时，（ B ）次比较后查找成功。

A. 1

B. 4

C. 2

D. 8

13、在各种查找方法中，平均查找承担与结点个数n无关的查找方法是（ C ）。

A. 顺序查找

B. 折半查找

C. 哈希查找

D. 分块查找

14、下列二叉树中，不．平衡的二叉树是（ C ）。

15、对一棵二叉排序树按（ B ）遍历，可得到结点值从小到大的排列序列。

A. 先序

B. 中序

C. 后序

D. 层次

16、解决散列法中出现的冲突问题常采用的方法是（ D ）。

A. 数字分析法、除余法、平方取中法

B. 数字分析法、除余法、线性探测法

C. 数字分析法、线性探测法、多重散列法

D. 线性探测法、多重散列法、链地址法

17、对线性表进行折半查找时，要求线性表必须（ C ）。

A. 以顺序方式存储

B. 以链接方式存储

C.以顺序方式存储，且结点按关键字有序排序

D. 以链接方式存储，且结点按关键字有序排序

二、填空题

、具有相同函数值的关键字对哈希函数来说称为。

（×）1、折半查找只适用于有序表，包括有序的顺序表和链表。

（）2、二叉排序树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。

（）3、哈希表的查找效率主要取决于哈希表造表时所选取的哈希函数和处理冲突的方法。

（）4、平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。（√）5、AVL是一棵二叉树，其树上任一结点的平衡因子的绝对值不大于1。

四、综合题

1、选取哈希函数H （k ）=（k ）MOD 11。用二次探测再散列处理冲突，试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。 答案：(1)表形态：

010

9876

5

4

321413053221346013

1

1

1

2

1

1

(2)ASL ：ASL(7)=(1*5+2*1+3*1)/7=(5+2+3)/7=10/7

2、设哈希表HT 表长m 为13，哈希函数为H(k)=k MOD m ，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL 。 答案：(1)表形态：

1211109

8765

4321111023842019556827142

2

1

3

1

1

2

1

2

1

(2)平均查找长度：ASL(10)=(1*5+2*4+3*1)/10=1.6

3、设散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34）,散列函数H （K ）=K mod 6，采用线性探测法解决冲突，要求： （1）构造散列表；

（2）求查找数34需要比较的次数。 答案：(1)表形态：

06543

2

134524730261

3

1

2

1

(2)查找34 的比较次数：3

4、已知下面二叉排序树的各结点的值依次为1－9，请标出各结点的值。

答案：

5

26

9

618

317

5、若依次输入序列{62,68,30,61,25,14,53,47,90,84}中的元素，生成一棵二叉排序树。画出生成后的二叉排序树（不需画出生成过程）。

6、设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77},采用哈希函数H(key)=key MOD 13,采用开放地址法的二次探测再散列方法解决冲突，试在0－18的散列空间中对关键字序列构造哈希表，画出哈希表，并求其查找成功时的平均查找长度。

7、已知关键字序列{11,2,13,26,5,18,4,9}，设哈希表表长为16，哈希函数H(key)=key MOD 13，处理冲突的方法为线性探测法，请给出哈希表，并计算在等概率的条件下的平均查找长度。

8、设散列表的长度为m=13，散列函数为H(k)=k MOD m ，给定的关键码序列为19，14，23，1，68，20，84，27，55，11，13，7，试写出用线性探查法解决冲突时所构造的散列表。 答案：表形态：

012

111098765432113112384201927681141

1

1

3

1

1

4

1

2

1

553

73

9、依次读入给定的整数序列{7,16,4,8,20,9,6,18,5}，构造一棵二叉排序树,并计算在等概率情况下该二叉排序树的平均查找长度ASL 。（要求给出构造过程） 10、设有一组关键字（19，1，23，14，55，20，84，27，68，11，10，77），采用哈希函数H(key)=key%13，采用二次探测再散列的方法解决冲突，试在0-18的散列地址空间中对该关键字序列构造哈希表。 答案：

012111098

765432177112310201968551411

1

1

3

1

1

2

1

2

1

18

17

16

15

14

13

273

843

一、单项选择题

1. 若查找每个元素的概率相等，则在长度为n 的顺序表上查找任一元素的平均查找长度为( )。

A. n

B. n+1

C. (n-1)/2

D. (n+1)/2

2. 对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为( )的9分之一。

A. 20

B. 18

C. 25

D. 22

3. 对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为( )。

A. 3

B. 4

C. 5

D. 6

4. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为( )。

A. 2

B. 3

C. 4

D. 5

5. 对具有n 个元素的有序表采用折半查找，则算法的时间复杂度为( )。

A. O(n)

B. O(n 2

) C. O(1) D. O(log 2n)

6. 在索引查找中，若用于保存数据元素的主表的长度为n ，它被均分为k 个子表，每个子表的长度均为n/k ，则索引查找的平均查找长度为( )。

A. n+k

B. k+n/k

C. (k+n/k)/2

D. (k+n/k)/2+1

7. 在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。

A. 13

B. 24

C. 12

D. 79

8. 从具有n 个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为( )。

A. O(n)

B. O(1)

C. O(log 2n)

D. O(n 2

)

9. 从具有n 个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为( )。

A. O(n)

B. O(1)

C. O(log 2n)

D. O(n 2

)

10. 在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是( )。

A. -1~1

B. -2~2

C. 1~2

D. 0~1

11. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为( )。

A. 4

B. 8

C. 12

D. 13 12. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地址等于3的元素个数( )。

A. 1

B. 2

C. 3

D. 4

13. 若根据查找表建立长度为m 的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d ，则下一次的哈希地址为( )。

A. d

B. d+1

C. (d+1)/m

D. (d+1)%m

二、填空题

1. 以顺序查找方法从长度为n 的顺序表或单链表中查找一个元素时，平均查找长度为_ (n+1)/2_______，时间复杂度为O(n)________。

2. 对长度为n 的查找表进行查找时，假定查找第i 个元素的概率为p i ,查找长度（即在查找过程中依次同有关元素比较的总次数）为c i ，则在查找成功情况下的平均查找长度的计算公式为___

∑=n

i i i c p 1

_____。

3. 假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度_ 20.5 _______，在查找不成功情况下的平均查找长度__41 ______。

4. 以折半查找方法从长度为n的有序表中查找一个元素时，平均查找长度约等于__?log2(n+1)?___的向上取整减1，时间复杂度为___ O(log2n)_____。

5. 以折半查找方法在一个查找表上进行查找时，该查找表必须组织成___顺序_____存储的__有序______表。

6. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时，其比较次数分别为___1_____和___3 _____。

7. 假定对长度n=50的有序表进行折半查找，则对应的判定树高度为_6 _______，最后一层的结点数为__19 ______。

8. 假定在索引查找中，查找表长度为n，每个子表的长度相等，设为s，则进行成功查找的平均查找长度为__ (n/s+s)/2+1 __________。

9.在索引查找中，假定查找表（即主表）的长度为96，被等分为8个子表，则进行索引查找的平均查找长度为__ 11 ______。

10. 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定_小于 _______该结点的值，右子树上所有结点的值一定___大于_____该结点的值。

11. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个__有序序列______。

12. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明_查找成功 ______，若元素的值小于根结点的值，则继续向_左子树_______查找，若元素的值大于根结点的值，则继续向___，右子树_____查找。

13. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的__左子树______插入，若元素的值大于根结点的值，则接着向根结点的_，右子树_______插入。

14. 根据n个元素建立一棵二叉排序树的时间复杂度大致为_ O(n log2n) _______。

15. 在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过____1____。

16. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K %7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到_5_______次存储冲突。

17. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K %7作为哈希函数，采用线性探测法处理冲突，则平均查找长度为__2______。

18. 在线性表的哈希存储中，装填因子α又称为装填系数，若用m表示哈希表的长度，n表示线性表中的元素的个数，则α等于___ n/m _____。

19. 对线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用H(K)=K % 9作为哈希函数，则哈希地址为0的元素有___3_____个，哈希地址为5的元素有_2_______个。

三、应用题

1. 已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，试画出对应的折半查找判定树，求出其平均查找长度。

2.假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。

4. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,36,18,70,49,80)，哈希地址空间为HT [12]，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。

四、算法设计题

1. 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作为存储结构，且树中结点的关键字均不同。

2. 试将折半查找的算法改写成递归算法。

一、单项选择题

1. D

2. A

3. B

4. C

5. D

6. D

7. A

8. C

9. A 10. A 11. C 12. B 13. D

二、填空题

1. (n+1)/2, O (n)

2.

∑=n

i i i c p 1

3. 20.5, 41

4. ?log 2(n+1)?，O (log 2n )

5. 顺序 有序

6. 1，3

7. 6， 19 8. (n/s+s)/2+1 9. 11 10. 小于，大于

11. 有序序列 12. 查找成功，左子树，右子树 13. 左子树，右子树 14. O (n log 2n ) 15. 1 16. 5 17. 2 18. n/m 19. 3， 2

三、应用题

1. 折半查找判定树如图7-3所示，平均查找长度等于29/10。图7-3中的结点与有序表中元素的对应关系如下表所示。

2. 二叉排序树如图7-4所示，平均查找长度等于32/10。

图7-3

4. H(K)=K % 11，哈希表如图7-5所示，平均查找长度17/12。

∧

图7-5

四、算法设计题

1. 设计思路：进入判别算法之前，pre取初值为min(小于树中任一结点值)，fail=FALSE,即认为bt是二叉排序树。按中序遍历bt，并在沿向根结点，与前趋比较，若逆序，则fail 为TRUE,则bt不是二叉排序树。

void bisorttree(bitree bt,keytype pre, bool &fail)

{ //fail初值为FALSE，若非二叉序树，则fail值TRUE

if (!fail)

{ if (bt)

{ bisosrttree(bt->lchild,pre,fail); //判断左子树

if (bt->data_key

else

{ pre=bt->data_key;

bisorttree(bt->rchild,pre,fail); //判断右子树

}

}

}

} //bisorttree

说明：较为直观的方法，可套用中序遍历非递归算法。

2.int search_bin(SeqTable st , keytype k , int low , int high)

{ if (low

else

{ mid=(low+high)/2;

if (k= =st.elem[mid].key) return (mid) ; //成功

else

if (k

else return(st,k,mid+1,high);

}

} //search-bin