第5章 树和二叉树 复习测试
一、填空题。
1．深度为k的二叉树共有2k-1个结点，该二叉树为（ 满 ）二叉树。
2．二叉树在二叉链表方式下，p指向二叉树的一个结点，p结点无右孩子的条件是（ p->rtag==1 ）。
3．每个二叉链表必须有一个指向（ 头 ）结点的指针，该指针具有标识二叉链表的作用。
4．有m个叶结点的哈夫曼树上结点的数目是（ 2m-1 ）。
5．哈夫曼树是带权路径长度（ 最短 ）的树，通常权值较大的结点离根（ 越近 ）。
6．有n个叶子结点的哈夫曼树中，其分支结点的总数为（ n-1 ）个。
7．若深度为6的完全二叉树的的第6层有3个叶子，则该二叉树一共有（ 34 ）个结点。
8．深度为k的完全二叉树至少有（ 2K-1 ）个结点，至多有（ 2K-1 ）个结点。
二、选择题。
1．如果结点A是结点B的双亲，而且结点B有4个兄弟，则结点A的度是（ D ）。
A）3 B）3
C）4 D）5
2．树中所有结点的度之和等于所有结点总个数加（ A ）。
A）－1 B）0
C）1 D）2
3．具有3个结点的二叉树有（ C ）种形态。
A）3 B）4
C）5 D）7
4．以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n>0），空链域的个数为（ C ）。
A）2n-1 B）n-1
C）n+1 D）2n+1
5．在一棵非空的二叉树的中序遍历序列中，其根结点的右边（ A ）。
A）只有右子树上的所有结点 B）只有左子树上的所有结点
C）只有右子树上的部分结点 D）只有左子树上的部分结点
6．若X是中序线索二叉树中一个有左孩子的结点，且X不为根，则X的前驱为（ B ）。
A）X的双亲 B）X的左子树中最右结点
C）X的右子树中最左的结点 D）X的左子树中最右叶结点
7．若二叉树的前序和后序序列正好相反，则该二叉树一定是（ B ）的二叉树。
A）空或者只有一个结点
B）任一结点若有子树则只有左子树或只有右子树
C）任一结点无左孩子
D）任一结点无右孩子
8．设森林F中有3棵树，第一、第二、第三棵树的结点个数分别为M1、M2、M3，则与森林F对应的二叉树的右子树的结点个数是（ B ）。
A）M1+M2 B）M2+M3
C）M1+M3 D）M1+M2+M3
9．线索二叉树是一种（ 完全二叉树算法C ）结构。
A）逻辑 B）逻辑和存储
C）存储 D）线性
10.线索二叉树中某结点*p没有右孩子的充要条件是（ C ）。
A）p->lchild==NULL B）p->rtag==0
C）p->rtag==1 D）p->lchild==NULL
11.任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ B ）。
A）不能确定 B）一定不会变化
C）一定会变化 D）只有完全二叉树不发生变化
12．使用n个权值生成的哈夫曼树中共有（ B ）个结点。
A）2n B）2n-1
C）2n+1 D）2(n-1)
三、判断题。
1．二叉树也是树。 （ T ）
2．已知二叉树的先序序列和后序序列，则可以唯一确定一棵二叉树。 （ F ）
3．完全二叉树中，若一个结点没有左孩子，则它必须是叶子。 （ T ）
4．在结点数多于1的哈夫曼树中没有度为1的结点。 （ F ）
5．若一个结点是某二叉树先序遍历序列的最后一个结点，则它必是该二叉树中序遍历序列中最后一个结点。 （ F ）
6．线索二叉树中，任一结点均有指向其前驱和后继的线索。 （ T ）
7．在二叉树的后序遍历序列中，任一结点均处于其子女的后面。 （ T ）
8．由树转换成的二叉树的根结点无右子树。 （ T ）
9．单支树适合用一维数组存储，因为一维数组均以先序遍历存储结点。（ F ）
10．哈夫曼编码是一种能使字符串长度最短的等长前缀编码。 （ F ）
四、应用题。
1．画出具有3个结点的二叉树有几种不同形态。
解：
2．写出下列二叉树的先序、中序和后序遍历的结点序列。
解：先序序列：ABCDEF
中序序列：BCDAFE
后序序列：DCBFEA
3．给定权值7，14，3，32，5，12，构造相应的哈夫曼树。
解：所构造的哈夫曼树如下图所示：
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论