习题4
1. 填空题
（1）已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为（___________）。 答案：129
（2）4个结点可构成（___________）棵不同形态的二叉树。
答案：12
（3） 设树的度为5，其中度为1~5的结点数分别为6、5、4、3、2个，则该树共有（___________）个叶子。
答案：31
（4）在结点个数为n（n>1）的各棵普通树中，高度最小的树的高度是（___________），
它有（___________）个叶子结点，（___________）个分支结点。高度最大的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。
答案：2 n-1 1 n 1 n-1
（5）深度为k的二叉树，至多有（___________）个结点。
答案：2k-1
（6）有n个结点并且其高度为n的二叉树的数目是（___________）。
答案：2n-1
（7）设只包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为（___________），最小结点数为（___________）。
答案：2k-1 k
（8）将一棵有100个结点的完全二叉树按层编号，则编号为49的结点为X，其双亲PARENT（X）的编号为（）。
答案：24
（9）已知一棵完全二叉树中共有768个结点，则该树中共有（___________）个叶子结点。
答案：384
（10）已知一棵完全二叉树的第8层有8个结点，则其叶子结点数是（___________）。
答案：68
（11）深度为8（根的层次号为1）的满二叉树有（___________）个叶子结点。
答案：128
（12）一棵二叉树的前序遍历是FCABED，中序遍历是ACBFED，则后序遍历是（___________）。 答案：ABCDEF
（13）某二叉树结点的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则该二叉树结点的前序遍历序列为（___________），该二叉树对应的树林包括（___________）棵树。 答案：EACBDGF 2
2. 选择题
（1）在一棵度为3的树中，度为3的结点的个数为2，度为2的结点个数为1，则度为0的结点个数为（ ）。
A. 4 B. 5 C. 6 D. 7
（2）下列陈述中正确的是（ ）。
A. 二叉树是度为2的有序数
一次性手腕带
B. 二叉树中结点只有一个孩子时无左右之分
C. 二叉树中必有度为2的结点
D. 二叉树中最多只有两棵子树，并且有左右之分
（3）树中如果结点M有3个兄弟，而且N是M的双亲，则N的度是（ ）
A. 3 B. 4 C. 5 D. 1
（4）设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ）。
A. 2h B. 2h－1 C. 2h+1 D. h+1
（5）高度为5的完全二叉树至少有（ ）个结点。
A. 16 B. 32 C. 31 D. 5
（6）具有假如我是一个病人65个结点的完全二叉树的高度为（ ）。（根的层次号为0）
西辽河A. 8 B. 7 C.6 D. 5
（7）对一个满二叉树，m个树叶，n个结点，深度为h，则（ 无 ）。
A. n=h+m B. h+m=2n
C. m=h-1 D. n=2h-1
（8）任一棵二叉树，其叶子结点数为n0，度为2的结点数为n2，则存在关系（ ）。
A. n2 +1=n0 B. n0 +1=n2
C. 2n2 +1=n0 D. n2 =2n0 +1
（9）某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（ ）。
A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca
（10）设m、n为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（ ）。
A. n在m右方 B. n是m祖先
C. n在m左方 D.n是m子孙
（11）一棵二叉树的广义表表示为a（b（c，d），e（f（g））），则得到的层序遍历序列为（ ）。
A. abcdefg B. cbdaegf C. cdbgfea D. abecdfg
（12） 将一棵树t转换为二叉树h,则t的后序遍历是h的( )。
A.中序遍历 B.前序遍历 C.后序遍历 D.层序遍历
（13）对二叉树进行（ ）遍历，可以得到该二叉树所有结点构成的排序序列。
A. 前序 B. 中序 C. 后序 D. 层序
（14）设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ ）个。
A. n-1 B. n C. n+1 D. n+2
（15）利用3，6，8，12，5，7这6个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（ ）。
lsd法
A.3 B. 4 C.5 D. 6
（16）若度为mt10a的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。
A. n-1 B. [n/m]-1
C. [(n-1)/(m-1)] D. [n/(m-1)]-1
说明：在这里度为m的哈夫曼树是指仅含有度为0和m的结点的m叉树。因此有：
(1) Ｎ＝n+nm
(2) N = 1 + mnm
3. 试分别画出具有3个结点的树和二叉树的所有不同形态。
答案：树：
二叉树：
4． 试出分别满足下面条件的所有二叉树：
（1）前序序列和中序序列相同；东乡论坛
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议