1 / 4 第 6 章树和二叉树自测卷姓名：学号：班级：题号一二三四五六总分题分10 15 11 20 20 24 100 得分一、下面是有关二叉树的叙述，请判断正误（每小题1 分，共 10 分）（）1. 若二叉树用二叉链表作存贮结构，则在n 个结点的二叉树链表中只有n— 1 个非空指针域。（）2. 二叉树中每个结点的两棵子树的高度差等于1。（）3. 二叉树中每个结点的两棵子树是有序的。（）4. 二叉树中每个结点有两棵非空子树或有两棵空子树。（）5. 二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（）6. 二叉树中所有结点个数是2k-1-1 ，其中 k 是树的深度。（）7. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（）8. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i 层上最多能有2i －1 个结点。（）9. 用二叉链表法（link-rlink）存储包含n 个结点的二叉树，结点的2n 个指针区域中有n+1 个为空指针。（）10. 具有 12 个结点的完全二叉树有5 个度为 2 的结点。二、填空（每空1 分，共 15 分）1． 由３个结点所构成的二叉树有种形态。2. 一棵深度为6 的满二叉树有个分支结点和个叶子。3． 一棵具有２５７个结点的完全二叉树，它的深度为。4.设一棵完全二叉树有700 个结点，则共有个叶子结点。5. 设一棵完全二叉树具有1000 个结点，则此完全二叉树有个叶子结点，有个度为 2 的结点，有个结点只有非空左子树，有个结点只有非空右子树。6. 【严题集 6.7 ③】 一棵含有n 个结点的 k 叉树，可能达到的最大深度为，最小深度为。7. 二叉树的基本组成部分是：根（N）、左子树（ L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R 次序），后序法（即按次序）和中序法（也称对称序法，即按L N R 次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。8. 中序遍历的递归算法平均空间复杂度为。9. 用 5 个权值 {3, 2, 4, 5, 1}构造的哈夫曼（Huffman ）树的带权路径长度是。2 / 4 三、选择题（每小题1 分，共 11 分）（）1． 不含任何结点的空树。（Ａ）是一棵树; （Ｂ）是一棵二叉树; （Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树（）2．二叉树是非线性数...
