第6章 树和二叉树
一、选择题
1． 不含任何结点的空树（  ）。
A. 是一棵树                          B. 是一棵二叉树 
C. 是一棵树也是一棵二叉树;          D. 既不是树也不是二叉树
2. 一棵有n个结点的树的所有结点的度数之和为（  ）。
A. n-1    B. n    C. n+1    D. 2n
3. 在二叉树中某一个结点的深度为3，高度为4，则该树的高度是（  ）。
A. 5      B. 6      C. 7      D. 8
4. 先序中序后序遍历二叉树设高度为h的二叉树中只有度为0和度为2的结点，则该树的结点数至多为（  ）。
A. 2h-1        B. 2h+1      C. 2h-1        D. 2h+1
5. 设高度为h的二叉树中只有度为0和度为2的结点，则该树的结点数至少为（  ）。
A. 2h-1        B. 2h+1      C. 2h-1        D. 2h+1
6. 高度为h的满二叉树中有n个结点，其中有m个叶结点，则正确的等式是（  ）。
A. h+m=n      B. h+m=2n      C. m=h-1      D. n=2h-1
7．二叉树是非线性数据结构，所以（  ）。
A. 它不能用顺序存储结构存储             
B. 它不能用链式存储结构存储 
C. 顺序存储结构和链式存储结构都能存储   
D. 顺序存储结构和链式存储结构都不能使用
8. 一棵完全二叉树有25个叶结点，则该树最少有（  ）个结点。
A. 48    B. 49      C. 50      D. 51
9. 假设一个三叉树的结点数为36，则该树的最小高度为（  ）。
A. 2      B. 3      C. 4      D. 5
10. 设二叉树有n个结点，则二叉链表中非空指针数为（  ）。
A.  n-1  B. n  C. n+1    D. 2n
11. 先序序列和中序序列正好相反的二叉树是（  ）。
A. 完全二叉树    B. 满二叉树    C. 左单枝树    D. 右单枝树
12. 后序序列和中序序列正好相反的二叉树是（  ）。
A. 完全二叉树    B. 满二叉树    C. 左单枝树    D. 右单枝树
13．把一棵树转换为二叉树后，这棵二叉树的形态是（  ）。
A. 唯一的                          B. 有多种
C. 有多种，但根结点都没有左孩子    D. 有多种，但根结点都没有右孩子
14. 将一棵树T转换为孩子—兄弟链表表示的二叉树H，则T的后根序遍历是H 的（  ）。
A．前序遍历    B．中序遍历      C．后序遍历      D. 层次遍历
二、填空题
1. 在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则该树可能出现的最大高度是    ，其叶结点数为    ，而该树可能出现的最小高度是        ，其叶结点数为    。
2. 一棵完全二叉树有12个叶结点，则该树最多有      个结点。
（计算：n0=12， n2=n0-1=11， n=n0+n2+1=12+11+1=24）
3. 已知二叉树的先序序列为ABDCEF，中序序列为DBAECF，则该树的后序序列为          。
4. 二叉树的层次遍历需要使用        辅助才能实现。 
5. 设二叉树有n个结点，则二叉链表中空指针数为      。
6. 由3个结点所构成的二叉树有      种形态。
7.  一棵深度为6的满二叉树有    个分支结点和    个叶子。
8． 一棵具有257个结点的完全二叉树，它的深度为      。
9. 设一棵完全二叉树有700个结点，则共有        个叶子结点。
10. 设一棵完全二叉树有1000个结点，则此完全二叉树有      个叶子结点，有   
个度为2的结点，有      个结点只有非空左子树，有    个结点只有非空右子树。
11. 一棵有n(n>1)个结点的k叉树，可能的最大深度为    ，可能的最小深度为    。
三、判断题
1. 满二叉树是完全二叉树。（  ）
2. 二叉树的先序序列和中序序列可以唯一确定此二叉树。（ ）
3. Huffman树中包括度为0、度为1和度为2的结点。（  ）
4. 若二叉树用二叉链表存储，则n个结点的二叉链表中有n—1个非空指针域。（  ）
5. 二叉树中每个结点的两棵子树的高度差等于1。（  ） 
6. 二叉树中每个结点的两棵子树是有序的。（  ）   
7. 二叉树中每个结点有两棵非空子树或有两棵空子树。 （  ）
8. 二叉树中所有结点个数是2k-1-1，其中k是树的深度。（  ） 
9. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（  ） 
10. 对于一棵非空二叉树，根结点为第1层，则第i层上最多能有2i -1个结点。（  ）   
11. 用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（  ）
12. 具有12个结点的完全二叉树有5个度为2的结点。（  ）
四、应用题
1. 在一棵度为4的树中，有20个度为4的结点， 10个度为3的结点， 1个度为2的结点，10个度为1的结点，请计算树中度为0的结点个数。(写出计算过程)
2. 一棵二叉树有1024个结点，其中有叶子结点465个，计算树中度为2和度为1的结点各有多少个。
3. 请画出一棵先序序列和中序序列相同的二叉树（注：空树和只有根结点的树除外）。
4. 已知二叉树的层次遍历序列为ABCDEFG，中序序列为DBFEGAC，请画出该树。
5. 给定如图所示二叉树T，请画出与其对应的中序线索二叉树。
6. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
   
   
7. 把如图所示的树转化成二叉树。
             
五、算法题
1. 借助于栈实现二叉树的非递归中序遍历算法。（可以直接使用栈的基本操作）
2. 设二叉树以二叉链表做存储结构，编写递归算法实现以下功能：
(1) 统计二叉树中度为1的结点个数     
(2) 统计二叉树中叶子结点的个数
(3) 计算二叉树的高度
(4) 删除二叉树中所有的叶子结点
(5) 求指定结点的父结点(指定二叉树中某个结点的值)
3. 设二叉树以二叉链表做存储结构，利用先序遍历求先序序列中的第k个结点。
4. 设二叉树以二叉链表做存储结构，编写算法判断一个二叉树是否是完全二叉树。

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