一、单项选择题

01．下图所示是一棵（A ).

A.4阶B树                B.3阶B树                C.4阶B+树               D.无法确定

02.下列关于m阶B树的说法中，错误的是( C ).
A.根结点至多有m棵子树
B.所有叶结点都在同一层次上
C.非叶结点至少有m/2 (m为偶数）或(m +1)/2 (m为奇数）棵子树
D.根结点中的数据是有序的
解析：除根结点外的所有非叶结点至少有[m/2]棵子树，对于根结点，最多有m棵子树，若其不说叶结点，则至少有2棵子树

03.以下关于m阶B树的说法中，正确的是（B).
Ⅰ.每个结点至少有两棵非空子树
Ⅱ.树中每个结点至多有m-1个关键字
Ⅲ.所有叶结点在同一层
IV.插入一个元素引起B树结点分裂后，树长高一层
A.Ⅰ、Ⅱ                 B.Ⅱ、Ⅲ               C.Ⅲ、IV                D.Ⅰ、Ⅱ、IV
解析：每个非根的内部结点必须至少有[m/2]棵子树，而根结点至少要有两棵子树，所以选项Ⅰ不正确。选项ⅡⅢ显然正确，对于Ⅳ，插入一个元素引起B树结点分裂后，只要从根结点到该元素插入位置的路径上至少有一个结点未满，B树就不会长高;只有当结点的分裂传到根结点，并使根结点也分裂时，才会导致树高增1，因此选项IⅣ错误。

04．在一棵m阶B树中做插入操作前，若一个结点中的关键字个数等于()，则插入操作后必须分裂成两个结点;在一棵m阶B树中做删除操作前，若一个结点中的关键字个数等于( )，则删除操作后可能需要同它的左兄弟或右兄弟结点合并成一个结点。 B

解析：由于B树每个结点内的关键字个数最多为m-1,所以当关键字个数大于m-1时，则应该分裂，每个结点内的关键字个数至少为[m/2]-1个，所以关键字个数少于[m/2]-1时，则可能与其他结点合并(除非只有根结点)

05．具有n个关键字的m阶B树，应有（A）个叶结点。
A. n+1
B. n-1
C. mn
D. nm/2
解析:B树的叶结点对应查找失败的情况，对有n个关键字的查找集合进行查找 失败可能性有n+1种

06．高度为5的3阶B树至少有（B）个结点，至多有（D)个结点。
A.32
B.31
C.120
D.121

07．含有n个非叶结点的m阶B树中至少包含（D)个关键字。

解析：1个根结点至少有一个关键字，其余的n-1个结点至少有「m/2]-1个关键字。(n-1)([m/2]-1)+1

08.已知一棵5阶B树中共有53个关键字，则树的最大高度为(C)，最小高度为(B)。
A.2
B.3
C.4
D.5
解析：树中每个结点至多有m=5棵子树，至多有m-1=4个关键字，除根结点以外的非叶子结点至少有[m/2]=3棵子树，至少有[m/2]-1=2个关键字。求最大高度，则分支尽量少，每个结点内的关键字尽量少，根1关键字2分支，其他非叶2关键字3子树，高度为4的关键字数为1+2*(2+2*3+3*6)=53。求最小高度，则分支尽量多，每个结点内的关键字尽量多，所有结点4关键字5分支，一层4个关键字，2层5分支每个分支4个关键字，共24个，不够存，所以至少要三层才能存满53个关键字

09.已知一棵3阶B树中有2047个关键字，则此B树的最大高度为( A )，最小高度为(D)
A.11
B.10
C. 8
D.7
解析：树中每个结点至多有m=3棵子树，至多含有m-1=2个关键字，除根结点以外的非叶子结点至少有[m/2]=2棵子树，至少有[m/2]-1=1个关键字。最大高度：分支尽量少，每个结点内关键字尽量少，根1关键字2分支，其余非叶1关键字2分支。2^11-1=2047。最小高度：分支尽量多，每个结点内关键字尽量多，所有结点2关键字3分支

10.下列关于B树和B+树的叙述中，不正确的是( A ).
A.B树和B+树都能有效地支持顺序查找
B.B树和B+树都能有效地支持随机查找
C.B树和B+树都是平衡的多叉树
D.B树和B+树都可以用于文件索引结构
解析：B树仅支持随机查找，不支持顺序查找

11.在7阶B树中搜索第2016个关键字，若根结点已读入内存，则最多需启动( A  )次I/O.
A.4
B.5
C.6
D.7
12.【2009统考真题】下列叙述中，不符合m阶B树定义要求的是( D )。
A.根结点至多有m棵子树
B.所有叶结点都在同一层上
C.各结点内关键字均升序或降序排列
D.叶结点之间通过指针链接
解析：m阶B树不要求将各叶结点之间用指针链接，选项D描述的实际上是B+树。

13.【2012统考真题】已知一棵3阶B树，如下图所示。删除关键字78得到一棵新B树，
其最右叶结点中的关键字是( D )。

A. 60
B.60,62
C.62,65
D.65

14.【2013统考真题】在一棵高度为2的5阶B树中，所含关键字的个数至少是( A ).
A.5
B.7
C.8
D.14
解析：对于5阶B树，根结点的分支数最少为2(关键字数最少为1)，其他非叶结点的分支数最少为[n/2]向上=3(关键字数最少为2)，因此关键字个数最少的情况如下图所示(叶结点不计入高度)

15.【2014统考真题】在一棵有15个关键字的4阶B树中，含关键字的结点个数最多是(D)
A.5
B.6
C.10
D.15
解析：关键字数量不变，要求结点数量最多，即要求每个结点中含关键字的数量最少。根据4阶B树的定义，根结点最少含1个关键字，非根结点中最少含[4/2]-1=1个关键字，所以每个结点中关键字数量最少都为1个，即每个结点都有2个分支，类似于排序二叉树，而15个结点正好可以构造一个4层的4阶B树，使得终端结点全在第四层，符合B树的定义，因此选D。

16. 【2016统考真题】B+树不同于B树的特点之一是(A)。
A.能支持顺序查找
B.结点中含有关键字
C.根结点至少有两个分支
D.所有叶结点都在同一层上
解析：由于B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，因此可以进行顺序查找，而B树不支持顺序查找（只支持多路查找)。

17.【2017统考真题】下列应用中，适合使用B+树的是（ B ).
A.编译器中的词法分析
B.关系数据库系统中的索引
C.网络中的路由表快速查找
D.操作系统的磁盘空闲块管理

18.【2018统考真题】高度为5的3阶B树含有的关键字个数至少是(B).
A.15
B.31
C.62
D.242
解析：m阶B树的基本性质：根结点以外的非叶结点最少含有[m/2]-1=1个关键字，而根结点中含有1个关键字，因此所有非叶结点都有两个孩子，此时树形与h=5的满二叉树相同，可求得关键字最少为31个。

19.【2020统考真题】依次将关键字5，6，9，13，8，2，12，15插入初始为空的4阶B树后，根结点中包含的关键字是（ B ).
A. 8
B.6，9
C.8，13
D.9，12

20.【2021统考真题】在一棵高度为3的3阶B树中，根为第1层，若第2层中有4个关键字，则该树的结点数最多是( A ).
A.11
B.10
C.9
D.8
解析：3阶B树，每个结点至多含有3-1=2个关键字(至少1个)，至多有3棵子树，题目规定第二层有4个关键字，要使B树的结点数达到最多，则这4个关键字包含在3个结点中，B树树形如下图所示，A,B,C...M表示关键字，最多有11个结点。

21.【2022统考真题】在下图所示的5阶B树T中，删除关键字260之后需要进行必要的调整，得到新的B树T1。下列选项中，不可能是T1根结点中关键字序列的是(D)。

A.60,90,280
B.60,90,350
C.60,85,110,350
D.60,90,110,350

22.【2023统考真题】下列关于非空B树的叙述中，正确的是(B).
Ⅰ插入操作可能增加树的高度
Ⅱ.删除操作一定会导致叶结点的变化
Ⅲ.查找某关键字总是要查找到叶结点
Ⅳ.插入的新关键字最终位于叶结点中
A.仅Ⅰ                        B.仅Ⅰ、Ⅱ                        C.仅Ⅲ、Ⅳ                D、仅I、II、IV
解析：B树的插入操作可能导致叶结点分裂，而叶结点分裂可能导致父结点分裂，若这个分裂过程传导到根结点，则会导致B树高度增1，Ⅰ正确。若被删结点是叶结点，则显然会导致叶结点变化;若被删结点不是叶结点，则要先将被删结点和它的前驱或后继交换，最终转换为删除叶结点，还是导致叶结点变化，Ⅱ正确。若在非叶结点中查找到了给定的关键字，则不用向下继续查找，Ⅲ错误。插入关键字的初始位置是最底层叶结点，但可能因结点分裂而被转移到父结点中，IV错误。