选择题

1．顺序查找法适合于存储结构为（ ）的线性表。
A.散列存储 B．顺序存储或链接存储 C．压缩存储 D．索引存储

2．对线性表进行折半查找时，要求线性表必须( )。
A．以顺序方式存储
B．以链接方式存储
C．以顺序方式存储，且结点按关键字有序排序
D．以链接方式存储，且结点接关键字有序排序

3．采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。
A . n B． n／2 C．（n＋ l）／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．采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。
A. 10 B．25 C．6 D．625
9.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用( )查找方法。
A. 分块 B．顺序 C．二分 D．散列

10.设有100个元素，用折半查找法进行查找时，最大比较次数是（ ）。
A. 25 B．50 C．10 D．7 （判定树的深度＝foor(log2n)+1）

11．设有100个元素，用折半查找法进行查找时，最小比较次数是（ ）。
A. 7 B．4 C．2 D．1

12．哈希函数有一个共同性质，即函数值应当以（ ）取其值域的每个值。
A. 同等概率 B．最大概率 C．最小概率 D．平均概率

13．设哈希地址空间为0…m-1，k为关键字，取哈希函数为H(k)=k % p，为了减少发生冲突的频率，一般取p为（ ）。
A. 小于m的最大奇数 B．小于m的最大偶数
C．小于m的最大质数 D．小于m的最大合数

14．某顺序存储的表格中有90000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值皆不同，用顺序查找法查找时，平均比较次数约为（ C ），最大比较次数约为（ D）。
A. 25000 B．30000 C．45000 D．90000

填空题

1．在各种查找方法中，平均查找长度与结点个数n无关的查法方法是（ 哈希表查找）。

2．折半查找的存储结构仅限于（ 有序表 ），且是（ 顺序存储）。

3．在分块查找方法中，首先查找（ 索引表 ），然后再查找相应的（ 块 ）。

4．长度为255的表，采用分块查找法，每块的最佳长度是（ 15 ）。

5．假设在有序线性表A[l．．20]上进行折半查找，则比较一次查找成功的结点数为（1），则比较二次查找成功的结点数为（ 2 ），则比较三次查找成功的结点数为（ 4 ），则比较四次查找成功的结点数为（ 8 ），则比较五次查找成功的结点数为（ 5 ），平均查找长度为（ 3.7 ）。

6．对于长度为n的线性表，若进行顺序查找，则时间复杂度为（ O(n ) ）；若采用折半法查找，则时间复杂度为（ (log2n) ）；若采用分块查找（假定总块数和每块长度均接近），则时间复杂度为（ O(n1/2 ) ）。

7．在散列存储中，装填因子а的值越大，则(发生冲突的可能越大，查找时关键字进行比较的次数越多)；а的值越小，则(发生冲突的可能越小，查找时关键字进行比较的次数越少)。

8.哈希查找的基本思想是按（关键字）决定数据的存储地址。

9．哈希表的查找效率主要取决于选取的（哈希函数），（处理冲突的方法）和（ 哈希表的装填因子 ）。

10.折半查找不成功时，出现（low>high）情况，程序终止。

简答题

1．设哈希表的长度为13，哈希函数为H(k)=k %13，给定的关键字序列为：19，14，23，01，68，20，84，27，55，11，10，79}，画出用线性探测法和链地址法解决冲突时所构成的散列表，并求等概率情况下这两种方法查找成功时的平均查找长度。

2．假定有n个关键字，它们具有相同的哈希函数值，用线性探测法把这n个关键字存入到散列地址中要做多少次探测？（n+1）*n/2

3．设有序表为{a,b,c,d,e,f,g,h,i}，请画出分别对给定值e和k进行折半查找的过程。

4．画出对长度为10的有序表进行折半查找的判定树，并求其等概论时查找成功的ASL.