树和二叉树习.doc

第六章 树和二叉树 知识点1 树的基本概念 选择 4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（D） A．5 B．6 C．7 D．8 7. 树是结点的有限集合，它（C (1）)根结点，记为T。其余结点分成为m（m0）个(A（2）)的集合T1，T2， …，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数称为该结点的(C（3） )。供选择的答案： （1）(4) A. 有0个或1个 B. 有0个或多个 C. 有且只有一个 D. 有1个或1个以上 （2） A. 互不相交 B.允许相交 C.允许叶结点相交 D.允许树枝结点相交 （3） A. 权 B.维数 C.次数 D.序 判断 29．树形结构中元素之间存在一个对多个的关系。√ 填空题 7．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有___12 __个叶子结点。 24．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是__4___。 32．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为___21__。 应用题 知识点2 二叉树的基本概念和性质 选择 5. 在下述结论中，正确的是（ .D ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（.B） A．9 B．11 C．15 D．不确定 11．具有10个叶结点的二叉树中有（.B ）个度为2的结点， A．8 B．9 C．10 D．ll 12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（E） A． 250 B． 500 C．254 D．505 E．以上答案都不对 16. 有关二叉树下列说法正确的是（B ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 17．二叉树的第I层上最多含有结点数为（C ） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 18. 一个具有1025个结点的二叉树的高h为（C ） A．11 B．10 C．11至1025之间 D．10至1024之间 19．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有(B )结点 A．2h B．2h-1 C．2h+1 D．h+1 20．对于有n 个结点的二叉树, 其高度为（ D ） A．nlog2n B．log2n C．?log2n?|+1 D．不确定 21. 一棵具有 n个结点的完全二叉树的树高度（深度）是（A ） A．?logn?+1 B．logn+1 C．?logn? D．logn-1 22．深度为h的满m叉树的第k层有（A）个结点。(1=k=h) A．mk-1 B．mk-1 C．mh-1 D．mh-1 23．在一棵高度为k的满二叉树中，结点总数为（C ） A．2k-1 B．2k C．2k-1 D．?log2k?+1 24．高度为 K的二叉树最大的结点数为（C ）。 A．2k B．2k-1 C．2k -1 D．2k-1-1 25. 一棵树高为K的完全二叉树至少有（C ）个结点 A．2k –1 B. 2k-1 –1 C. 2k-1 D. 2k 45．在完全二叉树中，若