2024年5月26日发(作者：)

第八章 查找

一、判断题

1.用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可

以是没有按键值排好序的。（ ）

2.哈希表的查找不用进行关键字的比较。（ ）

3.哈希表的定义函数H（key）=key%p(p<=m)这种方法是直接定址法。（ ）

4.装填因子α的值越大，就越不容易发生冲突。( )

5.选择hash函数的标准为：随机性好、均匀性好和尽量避免冲突。( )

参考答案：1、×2、×3、×4、×5、√

二、填空题

1.顺序查找法的平均查找长度为__________，二分查找法的平均查找长度为________，

分块查找法(以顺序查找确定块)的平均查找长度为__________，分块查找法(以二分查找确定

块〉的平均查找长度为_________，哈希表查找法采用链接法处理冲突时的平均查找长度为

_________。

(n+1)/2；((n+1)*log2(n+1))/n-1；(s2+2s+n)/2s；log2(n/s+1)+s/2；1+α

2.在各种查找方法中,平均查找长度与结点个数n无关的查法方法是_________

哈希表查找

3.二分查找的存储结构仅限于_________,且是__________。

顺序；有序的

4.在分块查找方法中,首先查找__________,然后再查找相应的___________。

索引；块

5.长度为255的表,采用分块查找法,每块的最佳长度是____________。

15

6.在散列函数H(key)=key%p中,p应取_______________。

小于表长的最大素数

7.假设在有序线性表A[1..20]上进行二分查找,则比较一次查找成功的结点数为

_________,则比较二次查找成功的结点数为__________,则比较三次查找成功的结点数为

_________,则比较四次查找成功的结点数为________,则比较五次查找成功的结点数为

_________,平均查找长度为_________。

①1 ②2 ③4 ④8 ⑤5 ⑥3.7

8.对于长度为n的线性表,若进行顺序查找,则时间复杂度为__________，若采用二分法

查找,则时间复杂度为_________。

①O(n) ② O(log2n)

9.己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98),当二分查找值为29和

90的元素时,分别需要________次和____________次比较才能查找成功；若采用顺序查找时,

分别需要___________次和_________次比较才能查找成功。

4、4、5、10

三、选择题

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

（A）散列存储（B）顺序存储或链接存储（C）压缩存储（D）索引存储

参考答案：B

2.对线性表进行二分查找时,要求线性表必须（ ）。

（A）以顺序方式存储（B）以链接方式存储

（C）以顺序方式存储,且结点按关键字有序排序

（D）以链接方式存储,且结点按关键字有序排序

参考答案：C

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

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

参考答案：C

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

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

参考答案：D

5.二分查找和二叉排序树的时间性能（ ）。

（A）相同 （B）不相同 （C）无法比较

参考答案：B

6.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点

时,（ ）次比较后查找成功。

（A）1（B）2（C）4（D）8

参考答案：C

7.设哈希表长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

参考答案：D

8.有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况

下查找成功所需的平均比较次数为（ ）

（A）35/12（B）37/12（C）39/12（D）43/12

参考答案：B

9.采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺

序查找来确定结点所在的块时,每块应分（ ）个结点最佳。

（A）10（B）25（C）6（D）625

参考答案：B

10.如果要求一个线性表既能较快地查找,又能适应动态变化的要求,可以采用（ ）查

找方法。

（A）分块（B）顺序（C）二分（D）散列

参考答案：A

四、问答题

1.已知一个线性表为(38,25,74,63,52,48),假定采用H(k)=k%7计算散列地址进行散列

存储,试分别求出利用线性探测的开放定址法处理冲突和利用链接法处理冲突,在该散列表

上进行查找的平均查找长度。

2.己知线性表的元素为(87,25,310,8,27,132,68,95,187,123,70,63,47),散列函数为

h(k)=k%13,采用链接法处理冲突。设计出这种链表结构,并求该表平均查找长度。

3.假定一个待散列存储的线性表为(32,75,63,48，94,25,36,18,70),散列地址空间为

[0...10],若采用除留余数法构造散列函数和线性探查法处理冲突,试给出它们对应的散列表,

并求出在等概率情况下的平均查找长度。

4.试用连线把右边是四种线性表的存储结构与左边对应的操作的特点连接起来。

(A）散列表 （1）查找和存取速度快,但插入和删除速度慢。

(B)顺序有序表 (2）查找、插入和删除速度快,但不能进行顺序存取。

(C)顺序表 (3）插入、删除和顺序存取速度快,但查找速度慢。

(D)链接表 (4)查找、插入和删除速度慢,但顺序存取和随机存取第i个元素速度

快。

五、应用题

设闭散列表容量为7，给定表（30，36，47，52，34），散列函数H（K）＝k mod 6，

采用线性探测解决冲突，要求：

（1）构造此散列表(散列地址为0~6)：

（2）求查找34需要进行比较的次数。

六、算法设计

哈希表的删除

hashtable del_hashtable (hashtable &hash, keytype K)

{t=h(k);

if ( hash[t]= = null) return ("infeasible");

else if (hash[t]= =K) hash[t]=hash[t]->next;

else { found=0;

q=hash[t];

p=hash[t]->next;

while ((!found)&&(p<> null))

if ( p->key= =K)

{found=1;

q->next=p->next;

}

else{q=p; p=p->next;}

if(!found) return ("infeasible");

}

return(hash);

}