数据结构与算法（仲恺农业工程学院）第五章测试_智慧树知到答案2021年

第五章 树与二叉树：本章介绍树和二叉树的概念、存储结构，二叉树的遍历等常用算法，及通过构建哈夫曼树对电文进行哈夫曼编码。通过本章学习，重点掌握（1）树的概念和存储结构（2）二叉树的概念、存储结构和性质（3）二叉树的各种遍历算法，并能利用该思想解决实际问题（4）树、森林和二叉树的转换（5）哈夫曼树的构建和哈夫曼编码。5.1树:本小节介绍树的概念及相关术语，树的逻辑表示方法，树的抽象数据类型，树的遍历方法和树的存储结构。
5.2二叉树:本小节介绍二叉树的概念及相关术语，二叉树的性质，二叉树的顺序和链式存储结构，树与二叉树间的转换，二叉树的基本运算算法实现
5.3二叉树的遍历:本小节介绍二叉树的先序遍历、中序遍历、后序遍历的过程及其递归算法的实现，给定二叉树遍历序列还原二叉树结构，二叉树的层序遍历及其算法实现
5.4线索二叉树:本小节介绍线索二叉树的概念，以及对一棵二叉树进行先序、中序和后序线索化的过程。
5.5哈夫曼树及其应用:本小节介绍哈夫曼树的概念，哈夫曼树的构造过程及算法实现，及应用哈夫曼树为电文进行哈夫曼编码。

[单选题]设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
7
6
8
5
答案：8
[单选题]一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
500
499
501
250[单选题]设给定权值总数有n 个，其哈夫曼树的结点总数为( )
2n-1
不确定
2n
2n+1[单选题]一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点
2h-1
2h
h+1
2h+1[单选题]将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（ ）
7
4
5
6[单选题]对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号
先序
后序
中序
层序[单选题]树的后根遍历序列等同于该树对应的二叉树的( )
中序
先序
层序
后序[单选题]在下列存储形式中，哪一个不是树的存储形式？（ ）
孩子兄弟表示法
顺序存储结构
孩子链表示法
双亲表示法[单选题]已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。
CBEDFA
不确定
CBEFDA
FEDCBA[单选题]某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
空或只有一个结点
任一结点无右子树
任一结点无左子树
高度等于其结点数[单选题]若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( )
X的左子树中最右结点
X的右子树中最左结点
X的双亲
X的左子树中最右叶结点[单选题]二叉树的第i层上最多含有结点数为（ ）。

 
 
 [单选题]n个结点的线索二叉树上含有的线索数为（     ）
n
2n
n-1
n+1[单选题]由3 个结点可以构造出多少种不同的二叉树？（    ）
4
2
5
3[单选题]当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A[l..n]中时，数组中第i个结点的左孩子为（     ）
A[i/2]
无法确定
A[2i+1](2i+1=<n)
A[2i](2i=<n)   [单选题]度为4，高度为h的树，（   ）。
至少有4h个结点
至少有h+4个结点
至多有个结点
至少有h+3个结点[单选题]用孩子链存储结构表示树，其优点之一是（   ）比较方便。
计算机指定结点的度
找指定结点的双亲
判断指定结点在第几层
判断两个结点是不是兄弟[单选题]根据使用频率为5个字符设计的哈夫曼编码不可能是（   ）。
100，11，10，1，0
000，001，010，011，1
111，110，10，01，00
001，000，01，11，10[单选题]一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（   ）。
ABCDEFG
CABDEFG
DACEFBG          
ADBCFEG [判断题]二叉树是度为2的有序树。（ ）
对
错[判断题]对于有N个结点的二叉树，其高度为。（ ）
对
错[判断题]二叉树的遍历只是为了在应用中找到一种线性次序。（ ）
错
对[判断题]一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。（ ）
对
错[判断题]中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）
对
错[判断题]由一棵二叉树的前序序列和后序序列可以唯一确定它。（ ）
对
错[判断题]完全二叉树中，若一个结点没有左孩子，则它必是树叶。（ ）
错
对[判断题]将一棵树转成二叉树，根结点没有左子树。（ ）
错
对[判断题]一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。（ ）
对
错[判断题]当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。（ ）
对
错