数据结构习题及答案（1）.pdf

数据结构习题及答案（1）

第八章查找

一、判断题

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)