试题出自试卷《02331《数据结构》真题及答案解析（2017.4）》

问题1选项
A.53 90
B.53
C.90
D.65

D

【考点】本题考查查找-树表的查找-B树上的插入
【解析】（1）在B树中插入一个结点的过程：先在最低层的某个非终端结点中添加一个关键字。若该结点中关键字的个数不超过m-1，则插入完成，否则要产生结点“分裂”。“分裂”结点时把结点分成两个，将中间的一个关键字拿出来插入到该结点的双亲结点上，如果双亲结点中已有m-1个关键字，则插入后将引起双亲结点的分裂，这一过程可能波及B树的根结点，引起根结点的分裂，从而使B树长高一层。（2）具体过程：因为65介于61和70之间，所以插到该节点中，但插入后节点数超过了2，所以要分裂，把65拿到双新结点中，同时61和70分成两个结点，但这时53和90这个结点中因为插入了65，关键字超过了3，也要分裂，65升为双亲结点，53和90分成两个结点。所以该题答案为65。故本题选D。
【希赛点拨】一棵m（m≥3）阶的B树，或为空树，或为满足下列性质的m叉树：
（1）每个结点至少包含下列信息域：（n，p0，k1，p1，k2，…，kn，pn），其中，n为关键字的个数；ki（1≤i≤n）为关键字，且ki<ki+1（1≤i<n-1）；pi（0≤i≤n）为指向子树根结点的指针，且pi所指向子树中所有结点的关键字均小于ki+1，pn所指子树中所有结点关键字均大于kn；
（2）树中每个结点至多有m棵子树。
（3）若树为非空，则根结点至少有1个关键字，至多有m-1个关键字。因此，若根结点不是叶子，则它至少有两棵子树。
（4）所有的叶结点都在同一层上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向它们的指针均为空），叶子的层数为树的高度h。
（5）每个非根结点中所包含的关键字个数满足：⎾m/2⏋-1≤n≤m-1。因为每个内部结点的度数正好是关键字总数加1，所以，除根结点之外的所有非终端结点（非叶子结点的最下层的结点称为终端结点）至少有⎾m/2⏋棵子树，至多有m棵子树。