一、 选择题
1．设树的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1，则树中的叶子数为（  ）。
A．5    B．6    C．7    D．8
2．在下述结论中，正确的是（ ）。
①只有一个结点的二叉树的度为0
②二叉树的度为2
③二叉树的左右子树可以任意交换
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树
A．①②③    B．②③④    C．②④    D．①④
3．设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中
第一棵数的结点个数是（ ）。
A．m-n        B．m-n-1
C．n+1        D．无法确定
4．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）。
A．9    B．11    C．15    D．不确定
5．一棵完全二叉树上有1001个结点，其中叶子结点的个数（ ）。
A．500    B．254    C．505    D．以上都不对
6．设给定权值总数有n个，其哈夫曼树的结点总数为（  ）。
A．不确定    B．2n+1    C．2n    D．2n-1
7．一棵二叉树高度为h，所有结点的度为0或2，则这棵树最少有（ ）个结点。
A．2h    B．2h-1    C．2h+1    D．h+1
8．在一棵高度为k的满二叉树中，结点总数为（ ）
A．2k-1    B．2k    C．2k-1    D．
9．树的后根序遍历等同于该树对应的二叉树的（ ）。
A．先序序列        B．中序序列    C．后序序列
二、填空题
1．二叉树由        、          、          三个基本单元组成。
2．树在计算机内的表示方式有        、          、              。
3．在二叉树中，指针p所指结点为叶子结点的条件是                      。
4．二叉树中某一结点左子树的深度减去右子树的深度称为该结点的          。
5．具有256个结点的完全二叉树的深度为              。
6．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有        个叶子结点。
7．深度为k的二叉树至少有        个结点，至多有        个结点。
8．深度为H的完全二叉树至少有        个结点，至多有      个结点，H和结点总数N之间的关系是        。
9．在完全二叉树中，编号为i和j的两个结点处于同一层的条件是            。
三、判断题
1．二叉树是度为2的有序树。    （ ）
2．完全二叉树一定存在度为1的结点。    （ ）
3．对于有n个结点的二叉树，其高度为log2n。    （ ）
4．深度为k的二叉树中结点总数≤2k-1。    （ ）
5．哈夫曼树肯定是一棵二叉树。    （ ）
6．二叉树的遍历结果不是唯一的。    （ ）
7．二叉树的遍历只是为了在应用中到一种线性次序。    （ ）
8．树的后根遍历和对应的二叉树的中序遍历次序一致。    （ ）
9．一个树的叶结点，在先序遍历和后序遍历下，皆以相同的相对位置出现。    （ ）
10．二叉树的先序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是哪个，则可确定这棵二叉树。    （ ）
四、 应用题
1．从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。
2．请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。
3．将算术表达式((a+b)+c*(d+e)+f)*(g+h)转化为二叉树。
4．一个深度为L的的满二叉树有以下性质：第完全二叉树算法L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：
（1）各层的结点的数目是多少？
（2）编号为n的结点的双亲结点（若存在）的编号是多少？
（3）编号为n的结点的第i个孩子结点（若存在）的编号是多少？
（4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？
请给出计算和推导过程。
5．已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？
6．一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。
7．证明：在任何一棵非空二叉树中有下面的等式成立：叶子结点个数=度为2的结点个数+1。
8．证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树的先序序列为ABDGECFH，中序序列为：DGBEAFHC。试画出该二叉树。
9．给定一组数列（15，8，10，21，6，19，3）分别代表字符A，B，C，D，E，F，G出现的频度，试叙述建立哈夫曼树的算法思想，画出哈夫曼树，给出各字符的编码值，并说明这种编码的优点。
五、 算法设计题
1．要求二叉树按二叉链表形式存储；
（1）写一个建立二叉树的算法。
（2）写一个判别给定的二叉树是否是完全二叉树的算法。
2．有n个结点的完全二叉树存放在一维数组]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。
3．设一棵二叉树以二叉链表为存储结构，结点结构为（lchild,data,rchild），设计一个算法将二叉树中所有结点的左、右子树相互交换。

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