内容摘要

--------------------------------------------------正文内容开始----------------------------------------------------------

精品文档

精品文档

PAGE

PAGE10

精品文档

PAGE

第八章 查找

一、填空题

1.线性有序表（a1，a2，a3，，a256)是从小到大排列的，对一个给定的值 k，用二分法检索

表中与k相等的元素，在查找不成功的情况下，最多需要检索 次。

设有100个结点，用二分法查找时，最大比较次数是 。

2．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素 20，它

将依次与表中元素 比较大小。

3. 在各种查找方法中，平均查找长度与结点个数 n无关的查找方法是 。

4、对线性表进行二分查找时，要求线性表必须以 方式存储，且结点按关键字

排列。

5．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为 _ __次；当

使用监视哨时，若查找失败，则比较关键字的次数为 __ 。

6．在有序表A[1..12] 中，采用二分查找算法查等于 A[12]的元素，所比较的元素下标依次为

____ _____。

7. 在有序表A[1..20] 中，按二分查找方法进行查找，查找长度为 5的元素个数是_

已知二叉排序树的左右子树均不为空，则_______上所有结点的值均小于它的根结点值，

________上所有结点的值均大于它的根结点的值。

9、中序遍历二叉排序树得到的序列是 序列（填有序或无序）。

10、从有序表(10，16，25，40，61，28，80，93)中依次二分查找 40和61元素时，其查找

长度分别为 和 。

1

二、单项选择题

（ ）1．在表长为ｎ的链表中进行顺序查找，它的平均查找长度为

Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２ ;

Ｃ. ＡＳＬ＝ n＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１

（ ）2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元

素58，则它将依次与表中 比较大小，查找结果是失败。

A．20，70，30，50 B ．30，88，70，50

C．20，50 D ．30，88，50

（ ）3．对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关

键字。

A．3 B ．4 C ．5 D ．6

（ ）4. 链表适用于 查找

A．顺序 B ．二分法 C ．顺序，也能二分法 D ．随机

（ ）5. 折半搜索与二叉搜索树的时间性能 。

A. 相同 B. 完全不同

C.有时不相同 D. 数量级都是O（log2n）

（ ）6．散列表的地址区间为 0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，

并将关键字序列 26，25，72，38，8，18，59依次存储到散列表中。元素 59存放在散列表中

的地址是 。

A．8 B. 9 C.10 D.11

( )7. 当采用分快查找时，数据的组织方式为

A．数据分成若干块，每块内数据有序

2

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）

的数据组成索引块

数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

数据分成若干块，每块（除最后一块外）中数据个数需相同

(

)8.

散列函数有一个共同的性质，即函数值应当以

取其值域的每个值。

A.最大概率B.

最小概率C.

平均概率

D.同等概率

(

)9.

假定有k个关键字互为同义词，若用线性探测法把这

k个关键字存入散列表中，

至少要进行 次探测？

A．k-1次 B.k 次 C.k+1 次 D.k （k+1）/2次

( )10 、二叉查找树的查找效率与二叉树的 有关, 在 时其查找效率最低

(1):A. 高度 B. 结点的多少 C. 树型 D. 结点的位置

(2):A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

( )11 、在顺序表(3,6,8,10,12,15,16,18,21,25,30) 中，用折半法查找

关键码值11，所需的关键码比较次数为

A)2 B)3 C)4 D)5

( )12 、对包含n个元素的哈希表进行查找，平均查找长度为

A)O(log2n) B)O(n) C)O(nlog 2n) D) 不直接依赖于n

( )13 、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找

法查找一个记录，其平均查找长度 ASL为( ) 。

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

( )14. 下面关于二分查找的叙述正确的是 ( )

表必须有序，表可以顺序方式存储，也可以链表方式存储

3

表必须有序且表中数据必须是整型，实型或字符型

表必须有序，而且只能从小到大排列

表必须有序，且表只能以顺序方式存储

( )15. 对线性表进行二分查找时，要求线性表必须（ ）

A.以顺序方式存储 B. 以顺序方式存储,且数据元素有序

C.以链接方式存储 D. 以链接方式存储,且数据元素有序

( )16 ．适用于折半查找的表的存储方式及元素排列要求为 ( )

A ．链接方式存储，元素无序 B ．链接方式存储，元素有序

C．顺序方式存储，元素无序 D ．顺序方式存储，元素有序

( )17 ．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序

查找，但前者比后者的查找速度 ( )

A．必定快 B. 不一定

C. 在大部分情况下要快 D. 取决于表递增还是递减

(

)18.

具有12个关键字的有序表，折半查找的平均查找长度（

）

A.3.1

B.4

C.2.5

D.5

(

)19.

折半查找的时间复杂性为（

）

A.O（n2）B.O

（n）

C.O

（nlog2n）

D.O

（log2n）

(

)20．设顺序线性表的长度为

30，分成5块，每块

6个元素，如果采用分块查找，则

其平均查找长度为（ ）。

(A)6 (B)11 (C)5 (D)6.5

( )21 ．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是

( )

4

A．（100，80，90，60，120，110，130）

（100，120，110，130，80，60，90）

C.（100，60，80，90，120，110，130）

D.(100，80，60，90，120，130，110)

( )22 、下列二叉排序树中，满足平衡二叉树定义的是（ ）

A、 B、 C、

D、

( )23 、设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择（ B）。

(A)小于等于m的最大奇数 (B)小于等于m的最大素数

(C)小于等于m的最大偶数 (D)小于等于m的最大合数

三、判断题

1、查找相同结点的效率折半查找总比顺序查找高。 ( )

2、索引顺序表的特点是块内可无序，块间要有序。 （ ）

3、 在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。 ( )

4、在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过 1。( )

5、若查找表的长度为 n，则顺序查找法的平均查找长度为（ n+1）/2。（ ）

6、折半搜索适用于有序表，包括有序的顺序表和有序的链表。 ( )

5

7．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在

位置置空，因为这会影响以后的查找。（ ）

8．负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。（ ）

散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。（）

若散列表的负载因子α 上一篇：数据结构宿舍管理系统实验 下一篇：数据结构的试卷学习试题及答案