文档介绍：第九章集合
一、选择题
,则在具有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
,平均比较次数为((1)),二分法查找只适用于查找顺序存储的有序表,平均比较次数为((2))。在此假定N为线性表中结点数,且每次查找都是成功的。【长沙铁道学院 1997 四、3 (4分)】
+1
4. 下面关于二分查找的叙述正确的是( ) 【南京理工大学 1996 一、3 (2分)】
A. 表必须有序,表可以顺序方式存储,也可以链表方式存储 C. 表必须有序,而且只能从小到大排列
B. 表必须有序且表中数据必须是整型,实型或字符型 D. 表必须有序,且表只能以顺序方式存储
5. 对线性表进行二分查找时,要求线性表必须( )【燕山大学 2001 一、5 (2分)】
,且数据元素有序 ,且数据元素有序
( ) 【南京理工大学 1997 一、6 (2分)】
,元素无序 ,元素有序
,元素无序 ,元素有序
7. 用二分(对半)查找表的元素的速度比用顺序法( ) 【南京理工大学 1998 一、11 (2分)】
必然快 B. 必然慢 C. 相等 D. 不能确定
,即可用折半查找,也可用顺序查找,但前者比后者的查找速度( )
C. 在大部分情况下要快 D. 取决于表递增还是递减
【南京理工大学 1997 一、7 (2分)】
9. 具有12个关键字的有序表,折半查找的平均查找长度( )【中山大学 1998 二、10 (2分)】
A. B. 4 C. D. 5
10. 折半查找的时间复杂性为( )【中山大学 1999 一、15】
A. O(n2) B. O(n) C. O(nlogn) D. O(logn)
,数据的组织方式为( ) 【南京理工大学 1996 一、7 (2分)】
,每块内数据有序
,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块
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): *n *n/2 G.(n+1)/2 (n+1)
,线性表的顺序查找的平均查找长度ASL为( (1) ),有序表的折半查找的ASL为( (2) ),对静态树表,在最坏情况下,ASL为( (3) ),而当它是一棵平衡树时,ASL为( (4) ),在平衡树上删除一个结点后可以通过旋转使其平衡,在最坏情况下需( (5) )次旋转。供选择的答案:【上海海运学院 1999 二、3 (5分)】
(1)(2)(3)(4)(5): A. O(1) B. O( log2n ) C. O((log2n)2) (nlog2n) E. O(n)
15.