http://jpkc.lit.edu.cn/sjjg/zxxx/gzxt/gzxt9-3.html
选择题
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．N2
4． 下面关于二分查找的叙述正确的是 ( )。
A． 表必须有序，表可以顺序方式存储，也可以链表方式存储
B． 表必须有序且表中数据必须是整型，实型或字符型
C． 表必须有序，而且只能从小到大排列
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（n2） B． O（n） C． O（nlogn） D． O（logn）
11．当采用分快查找时，数据的组织方式为( )。
A．数据分成若干块，每块内数据有序
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． 必须以链式方式存储，且数据已按递增或递减的次序排好。
（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)
14．在等概率情况下,线性表的顺序查找的平均查找长度ASL为( （1） ),有序表的折半查找的ASL为( （2） ),对静态树表,在最坏情况下,ASL为( （3） ),而当它是一棵平衡树时,ASL为( （4） ),在平衡树上删除一个结点后可以通过旋转使其平衡,在最坏情况下需( （5） )次旋转。供选择的答案： （1）（2）（3）（4）（5）:
A． O(1) B． O( log2n ) C． O((log2n)2) D．O(nlog2n) E． O(n)
15．对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的答案:
A． 相同的 B．不同的
16．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。
A． 分快查找 B． 顺序查找 C． 折半查找 D． 基于属性
17．既希望较快的查找又便于线性表动态变化的查找方法是 ( )。
A．顺序查找 B． 折半查找 C． 索引顺序查找 D． 哈希法查找
18．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。
A．（100,80,90，60，120，110，130） B．（100，120，110,130，80，60， 90）
C．（100，60，80,90，120，110，130） D．(100，80,60，90，120，130，110)
19．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。
A． LL B． LR C． RL D． RR
20．下列关于m阶B-树的说法错误的是( )。
A．根结点至多有m棵子树
B．所有叶子都在同一层次上
C． 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树
D． 根结点中的数据是有序的
答案
1． C 2． A 3．1 D 3．2 C 4． D 5． B
6． D 7． D 8． C 9． A 10．D 11． B
12．1 C 12．2 C 13．1 C 13．2 D 13．3 G 13．4 H
14．1 E 14．2 B 14．3 E 14．4 B 14．5 B 15．1 B
15．2 A 16． A 17． C 18． C 19． C 20． D