第六章树和二叉树 2
完全二叉树算法一、选择题
1. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )
A．不确定B．2n C．2n+1 D．2n-1
2. 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为〔〕个
A．4 B．5 C．6 D．7
3. 二叉树的第I层上最多含有结点数为〔〕
A．2I B．2I−1-1 C．2I−1D．2I-1
4.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度〔〕
A．4 B．5 C．6 D．7
5.一个具有1025个结点的二叉树的高h为〔〕
A．11 B．10
C．11至1025之间D．10至1024之间
6. 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。[理工大学2000 一、4 〔2分〕] A．先序B．中序
C．后序D．从根开始按层次遍历
7. 在下列存储形式中，哪一个不是树的存储形式？〔〕
A．双亲表示法B．孩子链表表示法
C．孩子兄弟表示法D．顺序存储表示法
8. 下面的说法中正确的是〔〕.
〔1〕任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；
〔2〕按二叉树定义，具有三个结点的二叉树共有6种。
A．(1)(2) B．(1) C．(2) D．(1)、(2)都错
9. 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是〔〕的二叉树。
A．空或只有一个结点B．任一结点无左子树
C．高度等于其结点数D．任一结点无右子树
10.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足〔〕
A．所有的结点均无左孩子B．所有的结点均无右孩子
C．只有一个叶子结点D．是任意一棵二叉树
11. 在完全二叉树中，若一个结点是叶结点，则它没〔〕。
A．左子结点B．右子结点
C．左子结点和右子结点D．左子结点，右子结点和兄弟结点
12．在下列情况中，可称为二叉树的是〔〕
A．每个结点至多有两棵子树的树
B. 哈夫曼树
C．每个结点至多有两棵子树的有序树
D. 每个结点只有一棵右子树
E．以上答案都不对
13. 线索二叉树是一种〔〕结构。
A．逻辑B．逻辑和存储C．物理D．线性
14. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( )
A．X的双亲B．X的右子树中最左的结点
C．X的左子树中最右结点D．X的左子树中最右叶结点
15.引入二叉线索树的目的是〔〕
A．加快查结点的前驱或后继的速度
B．为了能在二叉树中方便的进行插入与删除
C．为了能方便的到双亲
D．使二叉树的遍历结果唯一
二、判断题
1. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。
2.对一棵二叉树进行层次遍历时，应借助于一个栈。
3.由一棵二叉树的前序序列和后序序列可以唯一确定它。
4. 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。
5. 二叉树的遍历只是为了在应用中到一种线性次序。
6. 二叉树中序线索化后，不存在空指针域。
7. 非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子
8.霍夫曼树的结点个数不能是偶数。
三、应用题
1. 试证明，在具有n(n>=1)个结点的m次树中，有n(m-1)+1个指针是空的。
2. 将下列由三棵树组成的森林转换为二叉树。〔只要求给出转换结果〕
3. 已知一个森林的先序序列和后序序列如下，请构造出该森林。
先根序列：ABCDEFGHIJKLMNO
后根序列：CDEBFHIJGAMLONK
4. 已知一组字符与其权值如下：
a:35, b:9, c:19, d:27, e:81, f:14, g:21, h:12, i:25, j:5, k:11, l:8
请构造相应的哈夫曼树，画出结果哈夫曼树并计算出WPL。
四、算法设计题
1. 设计算法返回二叉树T的先序序列的最后一个结点的指针，要求采用非递归形式，且不能用栈。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。