一、选择题1．设树的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1，则树中的叶子数为（
D
）。
A．5B．6C．7D．8叶子的度数为0；设叶子数为x，则此树的总节点数为14223141116（公式：节点数分叉数1，由图形便可以观察出来）；又根据题目可以知道节点数目还可以列出一个式子：4211x便可以得到等式：4211x16；所以x8，即叶子数为8。2．在下述结论中，正确的是（
D
）。
①只有一个结点的二叉树的度为0②二叉树的度为2③二叉树的左右子树可以任意交换④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树A．①②③B．②③④C．②④D．①④3．设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为
，森林F中第一棵数的结点个数是（A．m
C．
1
A
）。
B．m
1D．无法确定
4．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（A．9B．11C．15D．不确定
B
）。
解答：度为0的结点度为2的结点1
5．一棵完全二叉树上有1001个结点，其中叶子结点的个数（A．500B．254C．505
D
）。
D．以上都不对
解答：1023是满二叉树，有512片叶子。1001比1023少22个结点，所以有51222222501片叶子。511是满二叉树，有256片叶子。1001比511多490个结点，所以有25649049012501片叶子。
6．设给定权值总数有
个，其哈夫曼树的结点总数为（A．不确定B．2
1C．2

D
）。
D．2
1
f解答：（1）哈夫曼树没有度为1的结点（2）且权值所在结点都是叶子（3）二叉树中度为2的结点数比叶结点少1
7．一棵二叉树高度为h，所有结点的度为0或2，则这棵树最少有（A．2hB．2h1C．2h1D．h1
B
）个结点。
8．在一棵高度为k的满二叉树中，结点总数为（A．2k1B．2kC．2k1
C）
D．log2k1


9．树的后根序遍历等同于该树对应的二叉树的（A．先序序列二、填空题1．二叉树由B．中序序列
B
）。
C．后序序列
根节点
、
左子树
、、
右子树
三个基本单元组成。、
2．树在计算机内的表示方式有
双亲表示法
孩子表示法
孩子兄弟表
示法
。
3．在二叉树中，指针p所指结点为叶子结点的条件是
plchild
ull
prchlid
ull
。
4．二叉树中某一结点左子树的深度减去右子树的深度称为该结点的5．具有256个结点的完全二叉树的深度为
平衡因子
。
9
。
6．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有
12
个叶子结点。
7．深度为k的二叉树至少有
2k1_
r