2. 计算机
  3. 二叉树的前序、中序和后序遍历法最适合采用(49)来实现。查找树中，由根结点到所有其他结点的路径长度的总和称为(50)，而使上述路径长度总和达到最小的树称为(51)，它一定是(52)。在关于树的几个叙述中，只有(53)是正确的。

二叉树的前序、中序和后序遍历法最适合采用(49)来实现。查找树中，由根结点到所有其他结点的路径长度的总和称为(50)，而使上述路径长度总和达到最小的树称为(51)，它一定是(52)。在关于树的几个叙述中，只有(53)是正确的。

admin2019-03-04  110
问题 二叉树的前序、中序和后序遍历法最适合采用(49)来实现。查找树中，由根结点到所有其他结点的路径长度的总和称为(50)，而使上述路径长度总和达到最小的树称为(51)，它一定是(52)。在关于树的几个叙述中，只有(53)是正确的。
选项 A、用指针方式存储有n个结点的二叉树，至少要有n+1个指针
B、m阶B树中，每个非叶子结点的后件个数大于等于
C、m阶B树中，具有k个后件的结点，必含有k-1个键值
D、平衡树一定是丰满树
答案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)所有叶子结点在同一层上，而且不包含任何关键字信息，不附有信息。
转载请注明原文地址:https://kaotiyun.com/show/BXTZ777K
本试题收录于： 数据库系统工程师上午基础知识考试题库软考中级分类
0

数据库系统工程师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)