数据结构习题（第六章）
一、单向选择题
1、关于二叉树，下列说法正确的是（）
A、二叉树的度都为2
B、二叉树的度可以小于2
C、每一个结点的度都为2
D、至少有一个结点的度为2
2、设深度为h（h>0）的二叉树中只有度为0和度为2的结点，则此二叉树所含的结点总数至少为（）。
A、2h
B、2h-1
C、2h+1
D、h+1
3、在树中，若结点A有4个兄弟，而且B是A的双亲，则B 的度为（）。
A、3
B、4
C、5
D、6
4、若一棵完全二叉树中某结点无左孩子，则该结点一定是（）。
A、度为1的结点
B、度为2的结点
C、分支结点
D、叶子结点
5、深度为k的完全二叉树至多有（）个结点，至少有（）个结点。
A、2k-1-1
B、2k-1
C、2k-1
D、2k
6、前序序列为ABC的不同二叉树有（）不同形态。
A、3
B、4
C、5
D、6
7、若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其后序序列为
（），层次编码序列为（）。
A、BCAGFED
B、DAEBCFG
C、ABCDEFG
D、BCAEFGD
8、遍历一棵具有n个结点的二叉树，在前序序列、中序序列和后序序列中所有叶子的相对次序（）。
A、都不相同
B、完全相同
C、前序与中序不同
D、中序与后序不同
9、在由4棵树组成的森林中，第一、第二、第三和第四棵树的结点个数分别为30，10，20，5。当把森林转换成二叉树后，对应的二叉树中，根结点左子树的结点个数为（B ），根结点右子树的结点个数为（）。
A、20
B、29
C、30
D、35
10、具有n个结点（n>1）的二叉树的前序序列和后序序列正好相反，则该二叉树除叶子结点外每个结点（）。
A、仅有左孩子
B、仅有右孩子
C、仅有一个孩子
D、都有左右孩子。
11、将一棵树转换成二叉树，树的前根序列与其对应的二叉树的（A ）相等；树的后根序列与其对应的二叉树的（）相等。
A、前序序列
B、中序序列
C、后序序列
D、层次序列
12、二叉树在线索化以后，仍不能有效解决的问题是（）。
A、前序线索树中求前序直接后继结点
B、中序线索树中求中序直接前驱结点
C、中序线索树中求中序后继结点
D、后序线索树中求后序直接后继结点
13、一棵具有124个叶子结点的完全二叉树，最多有（）个结点。
A、247
B、248
C、249
D、250
二、填空题
1、若一棵树的广义表表示为A(B(E,F),C(H,I,J,K),L),D(M(N)))。则该树的度为（），树的深度为（），树中叶子结点个数为（）。
2、若度为4的树T中度为1、2、
3、4的结点个数分别为
4、3、2、2，则T中叶子结点
的个数为（）个。
3、一棵具有n个结点的二叉树，若它有m个叶子结点，则该二叉树中度为1的结点个数为（）。
4、深度为k（k>0）的二叉树至多有（）个结点，第i层上至多有（）个结点。
5、已知二叉树有52个叶子结点，度为1的结点个数为30，则总结点个数为（）。
6、已知二叉树中有30个叶子结点，则二叉树的总结点个数至少是（）。
7、高度为6的完全二叉树至少有( )个结点。
8、一棵含有68个结点的完全二叉树，它的高度是（）。
9、已知一棵完全二叉树的第6层上有6个结点（根结点的层数为1），则总的结点个数是（），其中叶子结点个数是（）。
10、已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多为（107 ）。
11、一棵树转换成二叉树后，这棵二叉树的根结点一定没有（）孩子，若树中有m个分支结点，则与其对应的二叉树中无右孩子的结点个数为（）。
12、若用二叉链表表示具有n个结点的二叉树，则有（）个空链域。
13、具有m个叶子结点的赫夫曼树，共有（）个结点。
14、树的后根遍历序列与其对应的二叉树的（中序）遍历序列相同。
三、应用题
1、已知二叉树按照层次遍历（由树根开始从上而下，每一层自左而右）序列为
ABCDEFGHIJK，中序遍历序列是DBGEHJACIKF。请构造一棵二叉树。
2、已知二叉树的中序遍历序列是ACBDGHFE，后序遍历序列是ABDCFHEG，请构造一
棵二叉树。
3、已知二叉树的前序、中序和后序遍历序列如下，请填写*处的字母。
（1）前序遍历序列：*BC***G*
（2）中序遍历序列：CB*EAGH*
（3）后序遍历序列：*EDB**FA
4、对于给定的一组权值{3,5,6,7,9}，请构造相应的哈夫曼树，并计算其加权路径长度。
四、算法设计题
1、设二叉树以二叉链表为数据结构，请编写一个求二叉树叶子结点个数的算法。
提示：从根结点开始，若结点的左、右孩子均为空，则计数器加1，否则，依次遍历其左子树和右子树。
2、以二叉链表为数据结构，请编写计算二叉树深度的算法。
提示：计算二叉树深度的递归计算模型为：
0 当t=NULL
depth(t)=
max{depth(t->lchild), depth(t->rchild)}+1 当t!=NULL
3、设二叉树以二叉链表为数据结构，请编写一个算法，复制这棵二叉树。
提示：若二叉树不空，则申请一个结点空间，复制根结点数据，再分别递归复制其左链和右链。
