A.用指针方式存储有n个结点的二叉树,至少要有n＋1个指针B.m阶B树中,每个非叶子结点的后件个数

Question

A．用指针方式存储有n个结点的二叉树，至少要有n+1个指针

B．m阶B树中，每个非叶子结点的后件个数大于等于

C．m阶B树中，具有k个后件的结点，必含有k-1个键值

D．平衡树一定是丰满树

Answer 1

正确答案：C
解析：由于二叉树的前序、中序和后序遍历方法都是递归定义的，所以最适合采用递归程序来实现。此外，递归程序的实现基础是栈操作，所以二叉树的遍历也可以使用栈操作来完成，但是用栈操作来实现遍历的程序逻辑结构没有递归程序那么清晰，而且用栈来实现的二叉树遍历代码比较难懂，其优点是代码的机器执行效率较高。在查找二叉树中，由根结点到所有其他结点的路径长度总和称为内部路径长度。具有最小内部路径长度的树称为丰满树，对丰满查找树进行插入或者删除操作后，会产生一棵非丰满树。为了保证查找二叉树的高度为log2n，从而保证在查找二叉树上实现的插入、删除和查找等基本操作的平均时间为O(log2n)，往树中插入或删除结点时，要调整树的形态来保持树的“平衡”，使之既保持查找二叉树性质不变，又保证树的高度在任何情况下均为O(log2n)，从而确保树上的基本操作在最坏情况下的时间均为O(log2n)。平衡二叉树是指树中任一结点的左、右子树的高度大致相同，即平衡树上任一结点的左、右子树仍然保持平衡。平衡树的查找效率和丰满树相近，但是在插入或者删除结点时，平衡树能动态地调整保持平衡的特点。如果任一结点的左、右子树的高度均相同(如满二叉树)，则二叉树是完全平衡的。通常，只要二叉树的高度为O(log2n)，就可看做是平衡的。平衡二叉树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下，n个结点的平衡二叉树的高度约为1.44log2n。而完全平衡的二叉树高度约为log2n，平衡二叉树是接近最优的。根据丰满树和平衡树的定义可知，丰满树一定是平衡树，但平衡树不一定是丰满树。m阶B树是一种平衡的m叉树，具有如下的性质：(1)每个结点的后件(孩子)个数不大于m。(2)除根结点和叶子结点外，每个结点的后件个数不大于。(3)具有k个后件的非叶子结点含有k-1个键值。(4)所有叶子结点在同一层上，而且不包含任何关键字信息，不附有信息。