第八章 查找表
一、选择题
1.若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为( )。
A. (n-1)/2 B. n/2 C. (n+1)/2 D. n
2. 对N个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为( )
A.(N+1)/2 B. N/2 C. N D. [(1+N)*N ]/2
3.顺序查找法适用于查找顺序存储或链式存储的线性表,平均比较次数为((1)),二分法查找只适用于查找顺序存储的有序表,平均比较次数为((2))。在此假定N为线性表中结点数,且每次查找都是成功的。
A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N 4. 下面关于二分查找的叙述正确的是 ( )
A. 表必须有序,表可以顺序方式存储,也可以链表方式存储 C. 表必须有序,而且只能从小到大排列
B. 表必须有序且表中数据必须是整型,实型或字符型 D. 表必须有序,且表只能以顺序方式存储 5. 对线性表进行二分查找时,要求线性表必须( )
A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 6.适用于折半查找的表的存储方式及元素排列要求为( ) A.链接方式存储,元素无序 B.链接方式存储,元素有序
C.顺序方式存储,元素无序 D.顺序方式存储,元素有序 7. 用二分(对半)查找表的元素的速度比用顺序法( )
A. 必然快 B. 必然慢 C. 相等 D. 不能确定
8.当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度( )
A.必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 9. 具有12个关键字的有序表,折半查找的平均查找长度( ) A. 3.1 B. 4 C. 2.5 D. 5 10. 折半查找的时间复杂性为( )
A. O(n) B. O(n) C. O(nlog) D. O(log) 11.当采用分快查找时,数据的组织方式为 ( )
A.数据分成若干块,每块内数据有序
2
n
n
2
B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块
C. 数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块 D. 数据分成若干块,每块(除最后一块外)中数据个数需相同
12. 二叉查找树的查找效率与二叉树的( (1))有关, 在 ((2))时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 13. 要进行顺序查找,则线性表(1);要进行折半查询,则线性表(2);若表中元素个数为n,则顺序查找的平均比较次数为(3);折半查找的平均比较次数为(4)。 (1)(2):A. 必须以顺序方式存储; B. 必须以链式方式存储;
C. 既可以以顺序方式存储,也可以链式方式存储;
D. 必须以顺序方式存储,且数据已按递增或递减顺序排好; E. 必须以链式方式存储,且数