一、单项选择题
1.已知一个长度为16的顺序L，气元素按关键字有序排列，或采用折半查找法查找一个不在L中存在的元素，则关键字的比较次数最多的是（）。
A．4 B. 5
C. 6
D. 7
2.顺序查找适合于存储结构为（）的线性表。
A.顺序存储结构或链式存储结构
B.散列存储结构
C.索引存储结构
D.压缩存储结构
3.对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任意一个元素的查找成功的平均查找长度为（）。
A.n/2
B.(n+1)/2
C.(n-1)/2
D.n/4
4.对长度为3的顺序表进行查找，若查找的第一个元素概率为1/2，查找第二个元素的概率为1/3，查找第三个元素的概率为1/6，则查找表中任意一个元素的平均查找长度为( )。
A.5/3
B.2
C.7/3
D.4/3
5.当采用分块查找时，数据的组织方式为（）。
A.数据分成若干块，每块内数据有序
B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
6.下列关于二分查找的叙述中，正确的是（）。
A．表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序且表中数据必须是整型，实型或字符型
C. 表必须有序，而且只能从小到大排列
D．表必须有序，且表只能以顺序方式存储
7.使用二分（折半）查找元素的速度比用顺序法（）。
A.必然快
B.必然慢
C.相等
D.不能确定
8.已知一个长度为16的顺序表，其元素按关键字有序排列，若采用折半查找查找一个不存在的元素，则比较的次数至少是（），至多是（）。
A.4
B.5
C.6
D.7
9.已知一个有序表（13,18,24,35,47,50,62,83,90,115,134），当二分查找值为90的元素师，查找成功的比较次数为（ ）。
A.1
B.2
C.4
D.6
10.折半查找过程所对应的判定树是一颗（ ）。
A.最小二叉树
B.平衡二叉树
C.完全二叉树
D.满二叉树
11.在有11个元素的 有序表A[1,2,3，…，11]中折半查找(()/2low high +⎢⎥⎣⎦),查找元素为A[11]时，被比较元素的下标依次是（ ）。
A.6，8，10，11
B.6，9，10，11
C.6，7，9，11
D.6，8，9，11
12.具有12个关键字的有序表中，对每个关键字的查找概率相同，遮半查找查找成功的平均查找长度为（ ），折半查找查找失败的平均查找长度为（ ）。
A.37/12
B.35/12
C.39/13
D.49/13
13.对有2500个记录的索引顺序表（分块表）进行查找，最理想的块长为（ ）。
A.50
B.125
C.500
D. 2log 2500⎡⎤⎢⎥
14.为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素最多需要执行（ ）次关键字比较。
A.10
B.14
C.16
D.21
15.设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找法来确定子块，且确定的字块中也采用顺序查找法，则在等概率情况下，分块查找成功的平均查找长度为（ ）。
A.21
B.23
C.41
D.62
16.对长为n 的有序表进行折半查找，其判定树的高度为（ ）。
A. 2log (1)n +⎡⎤⎢⎥
B. 2log (1)1n +-⎢⎥⎣⎦
C. 2log n ⎡⎤⎢⎥
D. 2log 1n -⎢
⎥⎣⎦ 17.下列叙述中，不符合m 介B 树定义要求的是（ ）。
A.根节点最多的有m 课子树
B.所有叶节点都在同一层上
C.各节点内关键字均升序或者降序排列
D.叶节点之间通过指针连接
18.下列关于m 介B-树的说法错误的是（ ）。
A.根节点至多有m 棵子树
B.所有节点都在用一层次上
C.非叶节点至少有m/2(m 为偶数)或m/2+1(m 为奇数)棵子树
D.根节点中的数据是有序的
19.当在一颗m 阶B 树中做插入操作时，若一个结点中的关键字等于（ ），则必须分裂成两个结点，当向一颗树m 阶的B 树做删除操作时，若一个结点中的关键字个数等于（ ），则可能需要同它的做兄弟或有兄弟结点合并成一个结点。
A. ,/22m m -⎡⎤⎢⎥
B. 1,/22m m --⎡⎤⎢⎥
C. 1,/2m m +⎡⎤⎢⎥
D. /2,/21m m +⎡⎤⎢⎥
20.下列关于m 阶B 树的说法正确的是（ ）。
I.
每个结点至少有两颗非空子树 II.
树中每个结点至多有m-1个关键字 III.
所有叶结点都在同一层 IV. 当插入一个元素引起B 树结点分裂后，树长高一层
A.I 、II
B.II 、III
C.III 、IV
D.I 、II 、IV
21.下列关于B 树和B+树叙述中，不正确的是（ ）。
A. B 树和B+树都能有效支持顺序查找
B. B 树和B+树都能有效支持随机查找
C. B 树和B+树都是平衡的多叉树
D. B 树和B+树都可以用于文件索引结构
22.含有n 个非叶结点的m 阶B-树中至少包含（ ）个关键字。
A. (1)n m +
B. n
C. ()/21n m -⎡⎤⎢⎥
D. ()(1)/211n m --+⎡
⎤⎢⎥ 23.已知一课3阶B 树中有2047个关键字，则此B 树的最大高度为（ ），最小高度为（ ）。
A.11
B.10
C.8
D.7
24.高度为5的3阶B 树至少有（ ）个结点，至少有（ ）个结点。
A.32
B.31
C.120
D.121
25.已知一棵5阶B 树中共有53个关键字，则树的最大高度为（ ），最小
