第六章树及二叉树.doc

第六章 树和二叉树
一、选择题
4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
A．5 B．6 C．7 D．8
【南京理工大学 2000 一、8 （1.5分）】
5. 在下述结论中，正确的是（ ）【南京理工大学 1999 一、4 （1分）】
①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③ B．②③④ C．②④ D．①④
8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A．9 B．11 C．15 D．不确定 【北京工商大学2001一.7(3分)】
12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）【西安交通大学 1996 三、2 (3分)】
A． 250 B． 500 C．254 D．505 E．以上答案都不对
13. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) 【福州大学 1998 一、5 (2分)】
A．不确定 B．2n C．2n+1 D．2n-1
14. 有n个叶子的哈夫曼树的结点总数为（ ）。【青岛大学 2002 二、1 （2分）】
A．不确定 B．2n C．2n+1 D．2n-1
16. 有关二叉树下列说法正确的是（ ）【南京理工大学 2000 一、11 （1.5分）】
A．二叉树的度为2 B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
17．二叉树的第I层上最多含有结点数为（ ）
【中山大学1998二、7 （2分）】【北京理工大学 2001 六、5（2分）】
A．2I B． 2I-1-1 C． 2I-1 D．2I -1
33．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。
A．CBEFDA B． FEDCBA C． CBEDFA D．不定 【浙江大学 1999 四、2 ( 4分)】
34．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。
A．acbed B．decab C．deabc D．cedba 【山东大学 2001 二、7 ( 1分)】
三、填空题
2．树在计算机内的表示方式有_(1)__，_(2)__，_(3)__。【哈尔滨工业大学 2000 二、4 (3分)】
7．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个
叶子结点。【厦门大学 2000 六2 （16%/3分）】
14．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______
【北方交通大学 2001 二、6】【南京理工大学 1999 二、4 （2分）】
22．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，
则编号最小的叶子的序号是__(1)_；编号是i的结点所在的层次号是_(2)__（根所在的层次号规定为1层）。
【南京理工大学 2001 二、2（2分）】
四、应用题
26．对于任何一棵非空的二叉树,假设叶子结点的个数为n0,而次数为2的结点个数为n2,请给出n0和n2之间所满足的关系式n0=f(n2).要求给出推导过程。【复旦大学 1998 五 (8分)】
36．证明：在任何一棵非空二叉树中有下面的等式成立：叶结点的个数=二度结点的个数+1
【天津大学 1999 四 】