在对一个初始为空的3阶B树依次插入以下关键字:20, 10, 30, 5, 15, 25, 35, 40,最终形成的B树的根节点包含哪些关键字?

答案解析

核心考点说明:本题考察B树的插入操作和分裂机制。理解B树的阶数定义和插入时的节点分裂是解题的关键。 解题思路分析:3阶B树,每个节点最多可以包含2个关键字,插入时,如果节点满了,需要分裂。插入过程如下: 1. 插入20:[20] 2. 插入10:[10, 20] 3. 插入30:[10, 20, 30] 此时根节点满了,需要分裂,中间元素20上移,成为新的根节点。新的树结构为:根[20],左子树[10],右子树[30] 4. 插入5: [5, 10],根[20],右子树[30] 5. 插入15: [5, 10, 15],需要分裂,中间元素10上移,此时树结构为:根[10, 20],左子树[5],中子树[15],右子树[30] 6. 插入25:根[10, 20],左子树[5],中子树[15],右子树[25,30] 7. 插入35:根[10, 20],左子树[5],中子树[15],右子树[25,30,35] 右子树分裂,中间元素30上移,变为根结点[10,20,30]。根结点再次分裂,20上移,形成新的根结点[20], 左子结点[10],右子结点[30],左子结点的子结点[5],右子结点的子结点[15,25,35] 最后插入40,树结构为根节点[20],左子结点[10], 子结点[5],右子结点[30], 子结点[15,25,35,40],再次分裂,根[20],左子节点[10],子节点[5],右子节点[30, 35],子节点[15,25]以及[40] 8. 根节点为[20], 第一层左子结点为[10], 右子节点[30,35]。因此根结点为20。 每个选项的详细分析: A. 20: 这是最终分裂后的根节点,正确。 B. 20, 30: 这是初次分裂时, 根结点和右子节点的合并,最终不为根节点。 C. 15, 30: 分裂过程中的中间节点,不为根节点。 D. 20, 30, 40: 根节点不可能含有3个元素。 易错点提醒:B树的插入和分裂是一个动态的过程,注意每个节点最多容纳的关键字数量,以及分裂时中间元素的上移。逐步分析,切勿跳步。本题中的多次分裂易导致出错。 正确答案的关键依据:B树插入分裂的动态过程, 每次分裂时中间元素上移,最终的根节点元素为20.
正确答案:A
随机推荐
开始刷题