计算机等级考试三级数据结构第9章集合例题与答案.pdf

第九章集合

一、选择题

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一

个记录，其平均查找长度asl为()。【北京航空航天大学2000一、8（2分）】

a．(n-1)/2b.n/2c.(n+1)/2d.n

2.对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为()【南

京理工大学1998一、7（2分）】

a．（n+1）/2b.n/2c.nd.[（1+n）*n]/2

3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法

查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。在此假定n为线性表中结

点数，且每次查找都是成功的。【长沙铁道学院1997四、3(4分)】

a.n+1b.2log2nc.lognd.n/2e.nlog2nf.n2

4.下面关于二分查找的叙述正确的是()【南京理工大学1996一、3（2分）】

a.表必须有序，表可以顺序方式存储，也可以链表方式存储c.表必须有序，而且只能从

小到大排列

b.表必须有序且表中数据必须是整型，实型或字符型d.表必须有序，且表只能以

顺序方式存储

5.对线性表进行二分查找时，要求线性表必须（）【燕山大学2001一、5（2分）】

a.以顺序方式存储b.以顺序方式存储,且数据元素有序c.以链接方式存储d.以链接方式存

储,且数据元素有序

6．适用于折半查找的表的存储方式及元素排列要求为()【南京理工大学1997一、6（2

分）】

a．链接方式存储，元素无序b．链接方式存储，元素有序

c．顺序方式存储，元素无序d．顺序方式存储，元素有序

7.用二分（对半）查找表的元素的速度比用顺序法()【南京理工大学1998一、11（2

分）】

a．必然快b.必然慢c.相等d.不能确定

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

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

a．必定快b.不一定c.在大部分情况下要快d.取决于表递增还是递减

【南京理工大学1997一、7（2分）】

9.具有12个关键字的有序表，折半查找的平均查找长度（）【中山大学1998二、10（2

分）】

a.3.1b.4c.2.5d.5

10.折半查找的时间复杂性为（）【中山大学1999一、15】

a.o（n2）b.o（n）c.o（nlogn）d.o（logn）

11．当采用分快查找时，数据的组织方式为()【南京理工大学1996一、7（2分）】

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

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

据组成索引块

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

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

12.二叉查找树的查找效率与二叉树的(（1）)有关,在(（2）)时其查找效率最低【武汉交

通科技大学1996一、2(4分)】

(1):a.高度b.结点的多少c.树型d.结点的位置

(2):a.结点太多b.完全二叉树c.呈单枝树