试题出自试卷《02331《数据结构》-查找》

B

【考点】本题考查查找-树表的查找-B树的定义和性质，在B树上进行插入、删除和查找操作的实现
【解析】一颗m（m>=3）阶的B树，每个非根节点中所包含的关键字个数满足：[m/2]-1<=n<=m-1，m阶B树根节点最少含一个关键字，非根节点最少含有=3-1=2个关键字。故本题选B。
【希赛点拨】一棵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棵子树。