04　树和二叉树
【单选题】
1. 下列选项中不属于树形结构逻辑特征的是（C）。
A、有的结点有多个直接后继　B、有的结点没有直接后继
C、有的结点有多个直接前驱　D、有的结点没有直接前驱
2. 下列叙述中错误的是（B）。
A、树的度与该树中结点的度的最大值相等　B、二叉树就是度为2的有序树
C、有5个叶子结点的二叉树中必有4个度为2的结点　D、满二叉树一定是完全二叉树
3. 一棵二叉树中第6层上最多有（C）个结点。
A、2　B、31　C、32　D、64
4. 一棵高为k的二叉树最少有（B）个结点。
A、k-1　B、k　C、k+1　D、2k-1　E、2k-1
5. 一棵高为k的二叉树最多有（C）个结点。
A、k+1　B、2k-1　C、2k-1　D、2k　E、2k+1
6. 一棵高为k的完全二叉树最少有（B）个结点。
A、2k-1-1　B、2k-1　C、2k-1　D、2k
7. 一棵高为k的完全二叉树最多有（C）个结点。
A、2k-1-1　B、2k-1　C、2k-1　D、2k
8. 一棵度为3的树中，度为3的结点有2个，度为2的结点有2个，度为1的结点有2个，则度为0的结点有（D）个。
A、4　B、5　C、6　D、7
9. 含1000个结点的完全二叉树的高度为（B）。
A、9　B、10　C、11　D、12
10. 设完全二叉树T中含有n个结点，对这些结点从0开始按层序进行编号，若编号为i的结点有左孩子，则左孩子的编号为（D）。
A、2(i-1)　B、2i-1　C、2i　D、2i+1　E、2(i+1)
11. 已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（D）。
A、-A+B*C/DE　B、-A+B*CD/E　C、-+*ABC/DE　D、-+A*BC/DE
12. 已知一棵二叉树的先序序列为abdegcfh，中序序列为dbgeachf，则该二叉树的后序序列为（B）。
A、gedhfbca　B、dgebhfca　C、abcdefgh　D、acbfedhg
13. 先序遍历与中序遍历所得遍历序列相同的二叉树为（D）。
A、根结点无左孩子的二叉树　B、根结点无右孩子的二叉树
C、所有结点只有左子树的二叉树　D、所有结点只有右子树的二叉树
14. 下列叙述中正确的是（D）。
A、由先序遍历序列和后序遍历序列可以惟一确定一棵二叉树
B、由森林转化而得的二叉树，其根结点一定有右子树
C、完全二叉树一定是满二叉树
D、在结点数目相同的二叉树中，完全二叉树的路径长度最短
15. 由树转换而得的二叉树，根结点（B）。
A、没有左子树　B、没有右子树　C、左右子树都有　D、视树的形态而定
16. 由一个非空森林转换而得的二叉树，其根结点（D）。
A、一定没有左子树  B、一定没有右子树
C、左右子树一定都有　D、左、右子树可能都有，也可能都没有
17. 度为m的赫夫曼树中，若叶子结点个数为n，则非叶结点个数为（C）。
A、n-1　B、m-1　C、[(n-1)/(m-1)]　D、[n/(m-1)]-1　E、[(n+1)/(m+1)]-1
【填空题】
1. 森林是（m棵互不相交的树的集合，其中m≥0）。
2. 在k叉树的第i层上最多有（ki-1）个结点。
3. 一棵高为k的m叉树中最少有（k）个结点，最多有（）个结点。
4. 具有2400个结点的完全二叉树的深度为（12）。
5. 若二叉树T有n个叶子结点，则T必有（n-1）个度为2的结点。
6. 一棵深度为k且有（2k-1）个结点的二叉树称为满二叉树。
7. 设对完全二叉树T上的结点按层序进行连续编号，根结点的编号为1。若编号为i的结点有双亲，则其双亲的编号为（）；若编号为i的结点有左孩子，则其左孩子的编号为（2i）；若编号为i的结点有右孩子，则其右孩子的编号为（2i+1）。
8. 对树进行后序遍历等价于对由该树转换而得的二叉树进行（中）序遍历；对树进行先序遍历等价于对由该树转换而得的二叉树进行（先）序遍历。
9. 对森林进行后序遍历等价于对由该森林转换而得的二叉树进行（中）序遍历；对森林进行先序遍历等价于对由该森林转换而得的二叉树进行（先）序遍历。
【计算题】
1. 画出所有先序遍历序列为ABCD的二叉树。
解：A(#,B(#,C(#,D)))、A(#,B(#,C(D,#)))、A(#,B(C,D))、A(#,B(C(#,D),#))、A(#,B(C(D,#),#))、A(B,C(#,D))、A(B,C(D,#))、A(B(#,C),D)、A(B(C,#),D)、A(B(#,C(#,D)),#)、A(B(#,C(D,#)),#)、A(B(C,D),#)、A(B(C(#,D),#),#)、A(B(C(D,#),#),#)。
2. 一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上的每个结点都有k个孩子结点。若按层序从1开始对全部结点编号，则：
(1)第i层上有多少个结点？
(2)编号为p的结点的第i个孩子结点（若存在）的编号是多少？
(3)编号为p的结点的双亲结点（若存在）的编号是多少？
解：
(1)第1层有1个结点，第i层结点数=第i-1层结点数*k（2≤i≤h），可得第i层结点数为个。
(2)当根结点以及前面的p-1个结点的孩子都编了号之后，才开始为结点p的孩子编号，可得结点p的第i个孩子的编号为(1+(p-1)*k)+i。
(3)若p=1，则为根结点，无双亲，否则可设双亲结点编号为ｓ，由⑵可知结点s的孩子结点的编号范围为(s-1)*k+2～(s-1)*k+k+1，即，又由s为整数，可得二叉树的深度为k(p≠1)。
3. 一棵含n个结点的k叉树，可能达到的最大深度是多少，可能达到的最小深度是多少?。
解：可能达到的最大深度是n，最小深度是。
4. 已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，…，nk个度为k的结点，则该树有多少叶子结点？
解：。
5. 设树T中有n个结点，且所有分支结点的度均为k，试求T中叶子结点个数。
解：。
6. 已知完全二叉树T上共有900个结点，试求：(1)T的高度；(2)T中叶子结点个数；(3)T中度为1的结点个数。
解：⑴10；⑵450；⑶1。
7. 按层序对深度为k的完全二叉树中全部结点从1开始编号，试求叶子结点可能的最小编号。
解：。
8. 由遍历序列画出二叉树/树/森林。
(1)设一棵二叉树的先序序列为ABCDEFG，中序序列为CBEDFAG，试画出该二叉树。
(2)设一棵二叉树的中序序列为DBGEHAFCI，后序序列为DBHEBFICA，试画出该二叉树。
(3)已知树的先序遍历序列为GFKDAIEBCHJ，树的后序遍历序列为DIAEKFCJHBG，试画出该树。
(4)已知森林的先序遍历序列为ABCDEFGHIJKL，后序遍历序列为CBEFDGAJIKLH，试画出该森林。
(5)已知二叉树的层序序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，试画出该二叉树。
解：
(1)(2)(3)
(4)(5)
9. 设有二叉树如下：
(1)试写出该二叉树的先、中、后、层序遍历序列；
(2)试画出对应的先、中、后序线索二叉树存储结构。
解：
(1)先序遍历序列：ABDGCEFH；中序遍历序列：DGBAECHF；后序遍历序列：GDBEHFCA；层序遍历序列：ABCDEFGH。
(2)
先序线索二叉树：
中序线索二叉树：
后序线索二叉树：
10. 试将如下森林转为二叉树。
解：
11. 试将下图中的树转为二叉树。
解：
12. 设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10，试为这8个字母设计赫夫曼编码。
解：设8个字母为a、b、c、d、e、f、g、h，以出现频率为权值可构造赫夫曼树如下，然后以左分支表0，右分支表1，由根结点到字母所在叶子结点的路径，可得对应01串，此即该字母的赫夫曼编码（a：1010　b：00　c：10000　d：1001　e：11　f：10001　g：01　h：1011）。
【算法题】
下列算法题中可能用到的类如下：
public class BiTreeNode {//二叉结点类

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