第六章 树与二叉树：树是一种非线性的逻辑结构，它描述的数据元素之间的关系是一对多的，呈现出类似自然界中树的形状。这种树形的层次结构在生活中广泛存在，其应用也十分广泛。本章介绍树的有关概念和性质、二叉树的概念、存储、遍历、树、森林与二叉树的转换、哈夫曼树等。6.1树的基本概念:树形结构是一类非常重要的非线性结构，是以分支关系定义的层次结构，其应用非常广泛，其中二叉树是本章的重点。[单选题] 一棵完全二叉树上有1001个结点，其叶子结点的个数是（）。
6.2二叉树的概念与存储:二叉树是最基本、最重要的树形结构，它有5个重要性质，主要的存储方法是二叉链表存储。
6.3树与二叉树性质与应用举例:本节将对树与二叉树相关性质的应用习题进行解答。
6.4二叉树的遍历:二叉树的遍历是树与二叉树的许多操作的基础。本节主要介绍二叉树的4种遍历算法思想及其算法实现过程。这4种遍历有：先根遍历、中根遍历、后根遍历和层次遍历。对于前3种遍历本讲仅涉及其递归算法实现。
6.5二叉树遍历的非递归算法实现:二叉树遍历的非递归算法实现
6.6树与森林:本小节的主要内容一是树的存储表示法，二是树、森林与二叉树之间的转换，三是树和森林的遍历法。
6.7二叉树的线索化(上）:二叉树的线索化(上）
6.8二叉树的线索化(下）:二叉树的线索化(下）
6.9哈夫曼树的构造:信息编码方法的优劣直接影响信息传递的效率。一种好的编码方法应该满足译码无二义性，总编码长度最短。哈夫曼编码就是一种能满足这两个条件的编码方法。本节主要学习哈夫曼编码的原理以及如何构造哈夫曼树的算法过程。
500
250
505
A～C都不对
答案：A～C都不对
[单选题]一棵有124个叶结点的完全二叉树最多有（ ）个结点。
250
249
247
248[单选题]在n个结点的线索二叉树中，线索的数目为（ ）
n+1
2n
n
n-1[单选题]设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（ ）个结点。
26
25
12
13[单选题]树的基本遍历策略可分为先根遍历和后根遍历，而二叉树的基本遍历策略可分为先序、中序和后序这三种遍历。我们把由树转化得到的二叉树称为该树对应的二叉树，则（ ）是正确的。
树的先根遍历与其对应的二叉树先序遍历序列相同
树的后根遍历与其对应的二叉树后序遍历序列相同
树的先根遍历与其对应的二叉树中序遍历序列相同[多选题]完全二叉树（）。
适合于顺序存储结构存储
叶子结点可在任一层出现
某些结点有右子树时则必有左子树
不一定适合顺序存储结构存储
某些结点有左子树时则必有右子树[多选题]对于二叉树，下列描述正确的是（）
边的个数比结点个数少1个
第k层上最多有2k-1个结点
n个结点共有n-1个非空指针域
叶子结点数目比度数为2的结点数目多1个
高度为k的二叉树结点数最多时一定是满二叉树
一定有度数为1的结点[多选题]关于哈夫曼编码的说法正确的是（ ）
是一种最佳编码
编码无二义性
两个频度相同的字符其编码长度一定相等
WPL最小
不允许出现频度相同的字符[判断题]存在这样的二叉树，对它采用任何次序进行遍历得到的结果都相同。
对
错[判断题]二叉树就是结点度为2的有序树。
对
错[判断题]若一个结点是二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的先序遍历序列中的最后一个结点。
对
错[判断题] 一棵含有n个结点的完全二叉树，它的高度是⌊log2n⌋+1。
对
错[判断题]线索二叉树的左线索指向其某种遍历序列的直接前驱结点，右线索指向其某种遍历序列的直接后继结点。
对
错
温馨提示支付 ￥1.00 元后可查看付费内容,请先翻页预览!
