《软件技术基础》课件第8章

8.1线性表查找8.2散列技术习题8第8章查找8.1.1顺序查找

顺序查找(SequentialSearch)是一种最简单的查找方法，即从表头开始查找，直到找到为止。这种方法适用于较小的顺序表或链表。顺序查找的过程为：从表的一端开始，逐个将记录的关键字与给定值进行比较，若某个记录的关键字与给定值相等，则查找成功；反之，若直至最后一个记录，都没有找到与给定值相等的关键字，则表明表中没有所查的记录，查找失败。

算法8.1是以一维数组作为存储结构的顺序查找算法，该算法可以很容易地修改为基于链表结构的顺序查找算法。

算法8.1是以一维数组作为存储结构的顺序查找算法，该算法可以很容易地修改为基于链表结构的顺序查找算法。8.1线性表查找给定关键字序列(21，9，33，64，15，59，75，47)，现要查找的关键字为9，根据算法8.1，经过7次比较得到的查找结果为：要查的关键字在表中的下标为2。如果待查找的关键字为3，那么查找失败，返回i=0。

在算法8.1中，监视哨R[0]的作用是为了在for循环中省去下标i的判断条件i>0。这一改进可以减少约一半的比较次数，从而节省时间。同理，监视哨也可设在数组高端。

下面分析顺序查找的性能。查找算法的平均查找长度定义为：查找给定值所需进行的关键字比较次数的期望值。

在等概率情况下，顺序查找成功时的平均查找长度为

(8-1)

若待查找的关键字k不在表中，则必须进行n+1次比较才能确定查找失败。顺序查找的平均查找长度应当综合考虑查找成功时的平均查找长度和查找失败时的平均查找长度。

通常情况下，表中各记录被查找的可能性并不相等，例如汉字中常用字、词的使用频率就比较高，而一些偏僻字则使用极少。那么，为了减少平均查找长度，在事先知道查找概率或它们的分布情况下，可将表中记录按查找概率的大小顺序存放。若无法确定各记录的查找概率，则可对算法做如下修改：每当查找成功，就将找到的记录位置提前一位或若干位。这样，查找概率大的记录在查找过程中能不断向前移，在以后的查找过程中就能减少比较次数。常用的汉字输入法就是基于这个原理。

顺序查找的优点非常明显，其算法简单，并且对线性表的存储结构和关键字的有序性无任何要求，但是当n很大时，这种方法的查找效率较低。因此，顺序查找只适用于长度较小的线性表。8.1.2折半查找

折半查找(BinarySearch)又称为二分查找，它是一种效率较高的查找方法。查找的对象必须是顺序存储结构的有序表，即表中记录按关键字有序。假设有序的记录序列为{R1,R2,…,Rn}，其关键字值分别是k1,k2,

…,kn。利用折半查找算法查找关键字值k的过程是：每次将k先与表的中间记录相比较，如果未找到，则判断k是在表的左半部还是右半部，以缩小查找范围；逐步缩小查找区间，直至查找成功或查找区间不存在时结束。

折半查找的过程如算法8.2所示。

在算法8.2中，low和high分别表示当前查找区间的下界和上界，当前查找区间的中值设为mid= 

(low+high)/2

。如果关键字k与中值不相等，则将查找区间缩小为上一次的一半。那么在第i次比较时，最多只剩下

n/2i

个记录，故折半查找又称为二分查找。

下面举例说明。已知有序表中关键字序列为：9,15,21,33,47,59,64,77,84,91，现要查找关键字为15及80的记录，其查找过程如下：

再取mid=

(low+high)/2

=9，由于k=80<R[9].key，取high=mid

1=8，由于low>high，因此查找区间不存在，查找失败。

折半查找的性能分析可通过折半查找判定树来描述。

折半查找判定树定义如下：利用当前查找区间的中值记录作为根，将有序表的左子表和右子表的记录分别作为根的左子树和右子树，由此得到的二叉树称为折半查找判定树。上例有序表的折半查找判定树如图8.1所示。树中的圆形结点称为内部结点，结点内的数字表示该结点在有序表中的位置。所有内部结点的空指针域相当于指向一个方形结点，称为外部结点，可用于表示两个内部结点之间的有效关键字区间。

图8.1具有10个结点的折半查找判定树那么，折半查找的平均查找长度是多少呢？为讨论方便，不妨设结点总数n=2h

1，则判定树是满二叉树，其深度为h=lb(n+1)。在等概率条件下，折半查找的平均查找长度为

(8-2)

当n较大时，可以用近似公式：

(8-3)

对于有序表，折半查找的效率显然高于顺序查找。但是，为得到有序表，必须进行排序，而排序本身是一种很费时的运算，其时间复杂度至少是O(lb n)。因此，折半查找只适用于顺序存储结构，且表不易变动而又经常查找的情况。对那些查找少、经常进行插入或删除操作的线性表，宜采用链表作为存储结构。

8.1.3分块查找

分块查找(BlockingSearch)又称索引顺序查找，是顺序查找的一种改进方法。分块查找的对象是分块有序表及其索引表，如图8.2所示。其中线性表含有18个记录，被分为三个子表(R1,R2,

…,R6)、(R7,R8,…,R12)、(R13,R14,…,R18)。对每个子表(或称块)建立一个索引项，其中包含两项内容：关键字值项(为该子表内的最大关键字值)和指针项(指示该子表的第一个记录在表中的位置)。

“分块有序”是指对任意两个相邻子表，后面子表中所有记录的关键字值均大于前一个子表中的最大关键字值。由此得到的索引表是按关键字值有序的，而子表内的关键字不一定有序。

图8.2分块有序表及其索引表

因此，分块查找需分两步进行：首先可用顺序查找或折半查找索引表，确定待查记录所在的块，然后在块中顺序查找所需的记录。例如在图8.2所示的存储结构中，查找关键字值为k=44的结点，由于索引表小，因此可用顺序查找法查找索引表，直至找到第一个关键字大于等于k的结点，即关键字为48的结点。由于22<k<48，关键字为44的结点若存在的话，则必定在第二个子表中，因此根据同一索引项中的指针指示，从第二个子表中的第一个记录，也即分块有序表中的第7个记录起进行顺序查找，直到R[9].key=k为止。若此子表中没有关键字值等于k的记录，即在第7～12个记录这段区间没有关键字和k相等，则查找不成功。

当索引表较长时，亦可用折半查找来确定关键字所在的块。块中记录可以是任意排列的，因此在块中只能进行顺序查找。由此，分块查找的算法即为这两种算法的简单合成。

分块查找的平均查找长度为

ASLbs = Lb + Ls

(8-4)

其中：Lb为查找索引表确定所在块的平均查找长度；Ls为在块中查找元素的平均查找长度。

一般情况下，为进行分块查找，可将长度为n的表均匀地分成b块，每块含有s个记录，即b=n/s；又假定表中的每个记录的查找概率相等，则每块查找的概率为1/b，块中每个记录的查找概率为1/s。

若用顺序查找法确定所在块，则分块查找的平均查找长度为

(8-5)

若用折半查找确定所在块，则分块查找的平均查找长度为

(8-6)

在实际应用中，线性表不一定要均匀分块，而应该根据表的实际特征进行分块。例如学校的学生登记表，不同院系、班级的人数可能不一样。另外，所有子块的结点可以存放在一个向量中，也可单独存放，例如每一块用不同的向量或单链表来存放。

散列(Hash)是一种重要的存储方法。与前面讨论的各种结构相比，散列结构最大的特点是：记录在表中的存储位置与其关键字是相关的。换句话说，我们可以根据关键字直接计算得到该记录的存储地址。因此，在散列结构中进行查找可以省去大量的关键字比较操作，从而提高查找效率。

8.2散列技术8.2.1散列表的概念

散列表的理想情况是：不经过任何比较而一次就能直接存取所查的记录。其基本思想是：在记录的关键字k和结点的存储地址d之间，建立一个确定的函数映射关系H，即d=H(k)，那么查找时利用该函数H，就可以根据要查找的关键字直接计算记录所在的单元。因此，散列法又称为关键字—地址转换法。这个函数H就称为散列函数，H(k)则称为散列地址。用散列法存储的线性表叫散列表或哈希表。

下面举一个简单的例子。假设要建立一张30个地区民族人口统计表，每个地区为一个记录，记录的各数据项为：

如果以一维数组R[30]作为散列表的存储空间，那么散列地址就是数组的下标。假设以地区编号作为该记录的关键字，i＝0～29，则很容易得到散列函数为H(i)=i，由散列函数值可以唯一地确定记录R[i]，从而查找到编号为i的地区的人口情况。例如，要查看编号3的地区记录，利用散列函数可知，其数组单元的下标为3。

在很多情况下，散列函数并不容易得到。上例中，如果选取总人口、汉族人口等其他数据项作为关键字，或者将地区编号改为该地区的汉语拼音，则散列函数就会比较复杂。在8.2.2节中将介绍常用散列函数的构造方法。

从上面的例子可知：

(1)对任意数据类型的关键字，总可以灵活地设计散列函数将得到的散列地址控制在表长允许的范围内。设计散列函数时，应使其尽可能简单。

(2)若散列函数是一对一映射函数，则在查找时只需根据给定关键字计算散列地址，即可得到待查记录的存储位置，查找过程无须进行关键字比较。若该地址非空，则查找成功；否则该记录不存在。

(3)大多数情况下，散列函数并非一对一映射函数，即对于不相等的关键字k1和k2，有可能计算得到相同的散列地址。该现象称为冲突(Collision)，发生冲突的这两个关键字称为该散列函数的同义词(Synonym)。例如，对于关键字序列{at,as,be,can,cat,for,face,force}，如果取散列函数为H(key)=key[0]

'a'，其中key[0]存放关键字的第一个字母，可见关键字at、as互为同义词，它们的散列地址都是0，即产生冲突。

对于上例我们应重新构造一个散列函数。但在实际应用中，关键字的取值集合远远大于表空间的地址集，因此理想化的、不产生冲突的散列函数极少存在。例如，我们要为1000个人设置个人标识符，要求标识符的长度为8、以字母打头(区分大小写)的字母数字串，因此关键字(即标识符)取值的集合大小为

可见，设表长为1000即可满足需要。但是要将1.09388

1012个可能的标识符映射到这1000个地址上，难免产生冲突。因此，通常的散列函数是一个多对一的映射函数，散列法查找时的冲突现象也是不可避免的。一旦发生冲突，就必须采取相应措施及时予以解决。

发生冲突的频繁程度除了与散列函数H相关外，还与表的填满程度相关。为了减少冲突，散列表的空间一般大于所有记录所需的容量，此时虽然浪费了一定空间，但换取的是查找效率。设散列表空间大小为m，表中存储的记录个数是n，则称

=n/m为散列表的装填因子(LoadFactor)。

的取值区间一般设为[0.65,0.9]。

下面主要讨论散列法查找时的两个主要问题：

(1)设计一个计算简单且冲突尽量少的“均匀”的散列函数；

(2)寻求解决冲突的方法，即如何存储产生冲突的同义词。

8.2.2散列函数的构造方法

如何设计一个计算简单且冲突尽量少的“均匀”的散列函数呢？

前面已经介绍，散列函数的运算应尽可能简单，且任何关键字的散列函数值都出现在表长允许的范围内。这里要重点理解“均匀”的概念。所谓均匀，是指任意给定一个关键字，散列函数将其映射到任何一个存储地址的概率是相等的。换句话说，经散列函数映射得到的存储地址越随机越好。这样，一组不同的关键字就能够均匀地存储到表中，从而减少相互之间的冲突。为此有下面常用的构造散列函数的方法。

1．直接定址法

直接选取某个关键字或关键字的某个函数值作为散列地址，如下所示：

其中a和b为常数。当a=1,b=0时，散列函数值为关键字本身。

表8.1中给出了直接定址法的示例。取学号作为关键字k，散列函数H(k)=k+(

206000)。

若要查找学号是206056的记录，只需查第206056-206000=56项即可。直接定址法比较简单，而且所得到的地址集合与关键字集合的大小相同，所以不会发生冲突，但实际场合中适用的情况较少。

2．数字选择法

若关键字为数字且已知散列表中可能出现的关键字集合，则可选取其中数字分布比较均匀的若干位作为散列地址。

例如，有一组由7位数字组成的关键字，如表8.2第一列所示。

分析这8个关键字就会发现：第①②③位都是020，显然不均匀；第④⑤⑥⑦位的取值范围较大，有一定的均匀性。因此，可根据散列表的长度取其中几位或它们的组合作为散列地址。若表长为100(即地址为0～99)，则可取④⑤⑥⑦中的任意两位数字作为散列地址；若表长为1000(即地址为0～999)，则可取④⑤⑥⑦中的任意三位作为散列地址等。为了增加随机性，还可以取散列地址中的若干位分成多组，取其和并舍去进位作为散列地址。表8.2中给出了一种选取方式，散列函数的实现如下：

3．平方取中法

通常情况下，关键字的数字分布未知或很难准确估计，因此要找到若干位均匀分布的数字并不容易。平方取中法的思路是通过关键字的平方来扩大差别。因为一个数的平方值与关键字的每一位都相关，由此使得产生的散列地址随机性增加，从而较为均匀。然后，可以用数字选择法来选取散列地址。

例如，给定一组关键字如表8.3所示，可见无法直接选取三位数字作为散列地址。取平方后，关键字的差别扩大，当表长为1000时，可取其中间三位作为散列地址。相应的散列函数如下：

4．折叠法

折叠法是指将关键字分割成位数相同的几段(最后一段的位数可以不同)，将各段的叠加和(舍去进位)作为散列地址。其中段的长度取决于散列表的地址位数。当关键字位数较多且数字分布较均匀时，可采用此方法。

折叠法又分移位叠加和边界叠加两种。移位叠加是指将各段的最低位对齐，然后相加；边界叠加是指将相邻的段沿边界来回折叠，然后对齐相加。例如关键字key=35726，散列表长度为100，可将关键字每两位分成一段，两种叠加结果如下：

5．除留余数法

在除留余数法中，假设散列表长为m，选取适当的正整数p去除关键字，将所得余数作为散列地址，即

H(key)=key％p(p≤m)

这是一种最简单、最常用的散列函数构造方法。它可以直接对关键字取模，也可以对折叠、平方取中等运算的结果进行操作。该方法的关键是取适当的p。

举几个简单的例子。例如取p为偶数，则它奇数的关键字经转换后的地址仍为奇数，而偶数的关键字也只能转换到偶数地址，这当然不好。又如，取p为关键字的基数的幂次，若关键字是十进制整数，其基数为10，取p=100，则关键字159，259，359…均互为同义词。

一般情况下，p应该选为小于或等于散列表长度m的某个最大素数。下面给出一些常用取值：

m=8,16,32,64,128,256,512,1024

p=7,13,31,61,127,251,503,1019

除留余数法较为简单，我们无需将它定义为一个C的函数，而是将它直接写到相应的程序里。除留余数法也可以与其他散列方法组合在一起使用，例如设关键字是字符串，散列函数是通过将字符串的首、尾两个字符相加之和转换为整数，然后用除留余数法求散列地址。该散列函数的定义如下：

6．基数转换法

基数转换法的思路是把某一进制的关键字看成是另一个进制上的数，再把它转换成原来进制上的数，取其中的若干位作为散列地址。一般要求两个基数互素，其所取的基数大于原基数。进制转换后，关键字的随机性一般会增大，从而减少冲突。

例如，把一个十进制数的关键字(360495)10看做十六进制数(360495)16，再把它转换为十进制数，(360495)16＝(3540117)10，此时可根据散列表的长度选取若干位数字作为散列地址，也可应用其他方法。

7．随机数法

随机数法取决于随机函数random的构造，即

H(key)=random(key)

其中random为伪随机函数。若产生的是一个随机整数，则通常采用以下方法保证函数值在0～m -1之间：

H(key)=random(key)％m

实际上，上述各种方法都具有一定的随机性。随机性的强弱直接决定散列函数的均匀性。通常，当关键字长度不等时，采用随机数法构造散列函数较合适。

8.2.3处理冲突的方法

构造合适的散列函数只能够减少冲突，不可能避免冲突，因此，如何处理冲突问题是构造散列表的另一个重要方面。通常有两种方法处理冲突：开放地址法和拉链法。前者是将所有记录均匀地存放在散列表HT[m]中；后者是将互为同义词的记录链接成一个单链表，而把单链表的头指针存放在散列表HT[m]中。

1．开放地址法

开放地址法又称为开放定址法，其基本思路是：首先将表置空，并根据某种方法在散列表中定义一个探查序列，当发生冲突时，沿此序列逐个单元查找空单元，一旦找到，则将新记录放入。好的探查序列能够保证所有冲突的记录都能迅速地找到相应的空单元。

设表长为m，关键字个数为n，探查序列设为di,i=1~m

1，则开放地址的公式为

hi=(H(key) + di)％m

(8-7)

其中H(key)为散列函数。那么如何形成探查序列呢？

1)线性探查法

线性探查法的基本思想是：将散列表看成是一个环形表，若发生冲突的单元地址为d，则依次探查d+1,d+2,

…,m

1,0,1,…,d

1，直至找到一个空单元为止。

例如，已知一组关键字集(21,32,11,43,35,05,51,12,07)，用线性探查法解决冲突，试构造这组关键字的散列表。

通常令装填因子

<1，这里取

=0.75。由于关键字个数为n=9，可以确定散列表长m=

n/

=12，因此可以设置一维数组HT[12]为散列表。我们采用除留余数法构造散列函数，并选p=11，则开放地址为

hi = (H(key) + di)％m = (key％11 + i)％12

其中i=1～m

1。由此可以计算关键字的散列地址及开放地址。如果散列地址为空，则散列地址即为开放地址，记录可直接存入；否则根据di查找下一个开放地址。结果如表8.4所示。

插入第二个关键字32时，散列地址d=H(21)=10已被关键字21占用(即发生冲突)，利用探查序列得到h1=(10+1)%12=11为开放地址，因此可将32插入HT[11]中。与此类似，关键字43的散列地址也为10，经过三次探查后，找到开放地址h3=(10+3)%12=1。依次类推，可以插入所有关键字。表8.4中最末一行的数字表示查找该记录时所需进行的关键字比较

次数。

可见，只要散列表仍有空单元，线性探查法就总能找到一个不发生冲突的地址。表8.4中还出现了一种现象。虽然关键字12和43并非同义词，但是散列地址H(12)=1却被关键字43占用，也即发生了冲突。一般地，用线性探查法解决冲突时，当表中i,i+1,…,i+k位置上非空时，散列地址为i,i+1,…,i+k+1的记录都将插入在位置i+k+1上，我们把这种散列地址不同的结点争夺同一个后继散列地址的现象称为“堆积”。这种现象的后果是，不是同义词的结点处在同一个探查序列之中，从而增加了探查序列的长度。若装填因子过大或散列函数选择不当，都可能使堆积的机会增加。后面的两种方法可解决这一问题。

2)二次探查法

二次探查法的探查序列依次是：12,

12,22,

22,…。发生冲突时，求下一个开放地址的公式为

h2i

1 = (H(key) + i2)％m

h2i = (H(key) 

 i2)％m

(8-8)

其中1≤i≤(m

1)/2。分析式(8-8)可知，发生冲突时，同义词将来回在其散列地址H(key)的两端寻找开放地址。

二次探查法可以减少堆积现象，但是不容易探查到整个散列表空间。仅当表长m为4j+3(j为正整数)的素数时，才能探查到整个表空间。

3)随机探查法

随机探查法的探查序列将随机产生，求下一个开放地址的公式可以表示为

hi = (H(key) + Ri)%m

(8-9)

其中1≤i≤m

1，R1,R2，…,Rm－1是1,2,…，m

1的一个随机排列。随机排列的产生有很多种方法，实用中常用移位寄存器序列代替随机数序列。

2．拉链法

拉链法也称为链地址法，假设散列函数的值域为0～m

1，则可将散列表定义为一个指针数组HTP[m]，凡是散列地址为i的结点，均插入到以HTP[i]为头指针的单链表中。可见，拉链法解决冲突的思路是：将所有关键字为同义词的结点链接到同一个单链表中。

以表8.4中的关键字集(21,32,11,43,35,05,51,12,07)为例，用拉链法解决冲突以构造这组关键字的散列表。首先，这里设置散列函数为H(key)=key%11，其值域为0～10，则散列表为HTP[11]。对于所有散列地址为H(key)=i的关键字，都要接到第i个单链表中。我们采用尾插法建立单链表，则可得到如图8.3所示的散列表。

图8.3拉链法构造散列表示例当装填因子

较大时，开放地址法所需的探查次数比较多。虽然拉链法所用的空间比开放地址法多，但是不会产生堆积现象，其平均查找长度也较短。所以，拉链法所增加的空间开销是合算的。利用单链表结点的动态申请特点，拉链法还适合于无法确定表长的情况。

另一方面，对于用拉链法构造的散列表，简单地在链表上删除结点即可实现散列表的删除操作。而在开放地址法构造的散列表中，不能简单地将被删结点的空间置空来删除结点，因为空地址单元(即开放地址)都是查找失败的条件，这样做会截断在它之后填入散列表的同义词结点的查找路径。正确的做法是在被删结点上做删除标记，而不能真正删除结点。

8.2.4散列表的查找及分析

散列表的查找过程和建表过程基本一致。假设给定值为k，根据建表时设定的散列函数H可计算得到散列地址H(k)。若表中该地址空间未被占用，则查找失败；否则，进行关键字值的比较。若相等，则查找成功；否则，根据建表时处理冲突的方法查找下一个地址，直至某个地址空间为空(查找失败)或者关键字比较相等(查找成功)为止。

下面以线性探查法和拉链法为例，给出相应的散列表查找和插入算法。利用线性探查法解决冲突的有关说明及查找和插入操作如算法8.3及算法8.4所示，利用拉链法解决冲突的有关说明及查找和插入操作如算法8.5和算法8.6所示。

由于冲突和堆积现象的存在，在记录及其存储位置之间建立相应的映射关系仍然需要关键字的比较操作，这可以从散列表的查找和插入算法中看出。但是，散列表的平均查找长度比顺序查找要小，甚至比折半查找也要小。下面以表8.4和图8.3的散列表为例分析散列表的平均查找长度。

1)等概率情况下查找成功时的平均查找长度

线性探查法：

ASL=(1+4+1+3+1+1+2+1+2)/9=16/9≈1.78

拉链法：

ASL=(1×6+2×2+3×1)/9=13/9≈1.44

而当n=9时，顺序查找和折半查找的平均查找长度为

ASLsq(9)=(9+1)/2=5

ASLbn(9)=(1×1+2×2+3×4+4×2/9=25/9≈2.78

2)等概率情况下查找不成功时的平均查找长度

顺序查找和折半查找所需进行的关键字比较次数仅取决于表长，而散列表查找所需进行的关键字比较次数和待查结点有关，因此可将散列表在等概率情况下查找不成功时的平均查找长度定义为查找不成功时对关键字需要执行的平均比较次数。

线性探查法：假设待查关键字k不在表8.4中，若H(k)=0，则必须依次将HT[0]～HT[4]中的关键字与k进行比较，经过5次比较后才能发现HT[7]为空；若H(k)=1，则需比较4次才能确定查找不成功。依次类推，由于散列函数H(key)%11的值域为0～10，可得查找不成功时的平均查找长度为

ASLunsucc=(5+4+3+2+1+2+1+3+2+1+7)/11=31/11≈2.82

拉链法：设待查关键字k的散列地址为d=H(k)，在图8.3所示的链地址法中，若第d个链表上具有t个结点，则需经过t次关键字比较(不包括空指针判定)才能确定查找不成功。因此，查找不成功时的平均查找长度为

ASLunsucc=(1+1+1+0+0+1+0+2+0+0+3)/11=9/11≈0.82

综上可知，由同一个散列函数、不同解决冲突方法构成的散列表，其平均查找长度是不相同的。假设散列函数是均匀的，可以证明在一般情况下这一结论是成立的。表8.5给出了几种不同的冲突处理方法在等概率情况下得到的散列表的平均查找长度。

由表8.5可见，散列表的平均查找长度是装填因子

的函数，与记录个数n无关。因此，通过选择合适的

可以将散列表的查找长度限定于某个范围。显然，

越小产生冲突的机会就越小，但过小的

会造成较大的空间浪费。例如，当

=0.9时，对于成功的查找，线性探查法的平均查找长度是5.5，二次探查、随机探查及双散列函数探查法的平均查找长度是2.56，拉链法的平均查找长度为1.45。

一、名词解释

查找表，查找长度，有序表，散列表，散列函数，同义词，冲突，拉链法，堆积

二、填空题

1．查找表中主关键字指的是

，次关键字指的是

。

2．二分查找在查找成功时的查找长度不超过

，其平均查找长度为

，当n较大时约等于

。

3．在散列存储中，装填因子

的值越大，则

。

习题8

4．二分查找法仅适用于这样的表：表中的记录必须

，其存储结构必须是

。

5．静态查找表的三种不同实现各有优缺点。其中，

查找效率最低但限制最少，

查找效率最高但限制最强，而

查找则介于上述二者之间。

6．设有一个已按各元素的值排好序的线性表，长度为125，对给定的k值，用二分法查找与k相等的元素，若查找成功，则至少需比较

次，至多需比较

次。

7．在采用开放地址法解决冲突的散列表中删除一个记录，则对该元素所在存储单元的操作是

。

8．以下算法在散列表HP中查找键值等于K的结点，成功时返回指向该结点的指针，不成功时返回空指针。请分析程序，并在

上填充合适的语句。

pointerresearch_openhash(keytypeK,openhashHP)

{

i=H(K);//计算K的散列地址

p=HP[i];//i的同义词子表表头指针传给p

while(

)p=p->next;//未达表尾且未找到时，继续扫描

___________;

}

9．以下算法假定以线性探测法解决冲突，在散列表HL中查找键值为K的结点，成功时回送该位置，不成功时回送标志 -1。请分析程序，并在

上填充合适的语句。

intsearch_cloxehash(keytypeK,closehashHL)

{

d=H(K);//计算散列地址

i=d;

while(HL[i].key!=K&&(i!=d-1)i=

; //未成功且未查遍整个HL时继续扫描

if(

)reurn(i); //查找成功

elsereturn(-1); //查找失败

}

三、选择题

1．顺序查找法适合于()存储结构的查找表。

A.压缩

B.散列

C.索引

D.顺序或链式

2．对采用折半查找法进行查找运算的查找表，要求按()方式进行存储。

A.顺序存储

B.链式存储

C.顺序存储且结点按关键字有序

D.链式存储且结点按关键字有序

3．设顺序表的长为n，则其每个元素的平均查找长度是()。

A. n B. (n-1)/2 C. n/2 D. (n+1)/2

4．分块查找的时间性能()。

A.低于二分查找