算法与数据结构练习

第七章 查找

一、选择题

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

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

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

A 以链式方式存储 B 以顺序方式存储

C以链式方式存储且结点按关键字排序

D以顺序方式存储且结点必须按关键字排序

3.已知一个有序顺序表为（11，15，23，35，45，56，66，85，89，106，127），当二分查找值为89的元素时，需要（ B ）次比较即可查找成功。

A 1 B 2 C 3 D 4

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

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

二、填空题

1. 采用二分查找的算法，当n较大时，其平均查找长度ASL近乎为_____

log2n +1_______.

2. 长度为255的表，采用分块查找法，每块的最佳长度是____25_________.

3. 若有序顺序表中有1000个元素，用折半法查找时，最大的比较次数是

______10__________.

4. 假设在有序顺序表A[1..20]上进行二分查找，比较一次查找成功的结点数

为_______ A[10]_______,比较两次查找成功的结点数为___ A[5]_,__ A[15]_____,,比较三次查找成功的结点数为__ A[2],_ A[7], A[12],___ A[18]_____,,比较四找成功的结点数为___ A[1], A[3], A[6], A[8], A[11], A[13], A[16], A[19], ________,,比较五次查找成功的结点数为___ A[4], A[9], A[14], A[17], A[20],________,

1