第九章  集合
一、 选择题
1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度asl为(    )。【北京航空航天大学 2000 一、8 （2分）】                      
a． (n-1)/2       b. n/2        c. (n+1)/2        d. n
2. 对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为(   ) 【南京理工大学1998一、7（2分）】
a．（n+1）/2      b. n/2      c. n      d. [（1+n）*n ]/2
3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。 在此假定n为线性表中结点数，且每次查找都是成功的。【长沙铁道学院 1997 四、3 (4分)】
a.n+1       b.2log2n       c.logn       d.n/2       e.nlog2n    f.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.1            b. 4            c. 2.5            d. 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. 呈单枝树   d. 结点太复杂。
13. 要进行顺序查找，则线性表（1）；要进行折半查询，则线性表（2）；若表中元素个数为n,则顺序查找的平均比较次数为（3）；折半查找的平均比较次数为（4）。【北方交通大学 1999 一、2 （4分）】
  （1）（2）：a. 必须以顺序方式存储； b. 必须以链式方式存储；c. 既可以以顺序方式存储，也可以链式方式存储；
d. 必须以顺序方式存储，且数据已按递增或递减顺序排好；
e. 必须以链式方式存储，且数据已按递增或递减的次序排好。
（3）（4）：a.n   b.n/2   c.n*n   d.n*n/2    e.log2n    f.nlog2n    g.(n+1)/2    h.log2(n+1)

上一页12345下一页