数据结构第九章查找练习及答案

一、选择题

1、对线性表进行二分查找时，要求线性表必须（） A、以顺序方式存储 B、以链表方式存储

C、以顺序方式存储，且结点按关键字有序排列 D、以链表方式存储，且结点按关键字有序排列

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

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

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

A、n2 B、nlog2n C、n D、log2n

4、二分查找和二叉排序树的时间性能（） A、相同 B、不相同 C、有时相同 D、有时不相同

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

11、有100个元素，用折半查找法进行查找时，最小比较次数是（）

A、7 B、4 C、2 D、1

12、散列函数有一个共同性质，即函数值应当以（）取其值域的每个值。

A、同等概率 B、最大概率 C、最小概率 D、平均概率

13、散列地址空间为0到m-1，k为关键字，用p去除k，将所得的余数作为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、若有一棵二叉排序树，则按照中序遍历顺序将产生一个（有序）序列

2、顺序查找法的平均查找长度为（(N+1)/2）；二分查找法的平均查找长度为（LOG2N）；分

块查找法（以顺序查找确定块）的平均查找长度为（N/(2*S)+S/2+1）；分块查找法（以二分查找确定块）的平均查找长度为（LOG2(N/S+1)+S/2）。

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

4、二分查找的存储结构仅限于（顺序存储结构），而且是（有序的）。

5、在分块查找中首先查找（关键字所在的块），然后再查找相应的（块内关键字）。

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

7、在散列函数H（key）=key%p中，p应取（不大于m的最大素数）。

8、假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数为（1）；比较两次查找成功的结点数为（2）；比较三次查找成功的结点数为（4）；比较四次查找成功的结点数为（8）；比较五次查找成功的结点数为（5）；平均查找长度为（37/10）。

9、散列表存储的基本思想是由（关键字值）决定数据的存储地址。 10、当所有结点的值都相等时，用这些结点构造的二叉排序树的特点是只有（根结点）。

11、（中序）遍历二叉排序树的结点就可以得到排好序的结点序列。

12、对两棵具有相同关键字集合而形状不同的二叉排序树，（中

序）遍历它们得到的序列的顺序是一样的。