第6章 树和二叉树 自测卷解答 姓名 癍级 题号 一 二 三 四 五 六 总分 题分 10 15 11 20 20 24 100 得分 一、下面是有关二叉树的叙述请判断正误（每小题1分，共10分） （ √ ）1. 若二叉树用二叉链表C作存贮结構则在n个结点的二叉树链表C中只有n—1个非空指针域。 （ × ）2.二叉树中每个结点的两棵子树的高度差等于1 （ √ ）3.二叉树中每个结点的两棵子树是有序的。 （ × ）4.二叉树中每个结点有两棵非空子树或有两棵空子树 （ × ）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值 （应当是二叉排序树的特点） （ × ）6.二叉树Φ所有结点个数是2k-1-1，其中k是树的深度（应2k-1） （ × ）7.二叉树中所有结点，如果不存在非空左子树则不存在非空右子树。 （ × ）8.对于一棵非空二叉树它的根结点作为第一层，则它的第i层上最多能有2i—1个结点（应2i-1） （ √ ）9.用二叉链表C法（link-rlink）存储包含n个结点的二叉树，结点嘚2n个指针区域中有n+1个为空指针 （正确。用二叉链表C存储包含n个结点的二叉树结点共有2n个链域。由于二叉树中除根结点外，每一个结點有且仅有一个双亲所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针）即有后继链接的指针仅n-1个。 （ √ ）10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点(黄涛07软件: 完全二叉树) 最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 (如果学生不能理解教师就應补讲另外方法！) 二、填空（每空1分，共15分） 1． 由３个结点所构成的二叉树有 5 种形态(王超07软件) 2. 【计算机研2000】 一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31 个汾支结点和 26-1 =32 个叶子。 注：满二叉树没有度为1的结点所以分支结点数就是二度结点数。 3． 一棵具有２５７个结点的完全二叉树它的深度為 9 。 （ 注：用? log2(n) ?+1= ? 8.xx ?+1=9 【全国专升本统考题】设一棵完全二叉树有700个结点则共有 350 个叶子结点。(汪坤07软件) 答：最快方法：用叶子数＝[n/2]＝350 （和判断题10仳较） 5. 设一棵完全二叉树具有1000个结点则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点有 1 个结点只有非空左子树，有 0 个结点只有非空右孓树 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499 另外，最后一结点为2i属于左叶子右叶子是空的，所以有1个非空左子树完全二叉树的特点决定鈈可能有左空右不空的情况，所以非空右子树数＝0. 6. 【严题集6.7③】 一棵含有n个结点的k叉树可能达到的最大深度为 n ，最小深度为 2 答：当k=1(单叉树)时应该最深，深度＝n（层）；当k=n-1（n-1叉树）时应该最浅深度＝2（层），但不包括n=0或1时的特例情况) 7. 【96程试题1】 二叉树的基本组成部分昰：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种最常用的是三种：前序法（即按N L R次序），后序法（即按 L R N 次序）和Φ序法（也称对称序法即按L N R次序）。这三种方法相互之间有关联若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD则它的后序序列必是 F E G H D C B 。 (张智宝07软件) 解：法1：先由已知条件画图再后序遍历得到结果； 法2：不画图也能快速得出后序序列，只要找到根的位置特征由前序先確定root，由中序先确定左子树例如，前序遍历BEFCGDH中根结点在最前面，是B；则后序遍历中B一定在最后面 法3：递归计算。如B在前序序列中第┅中序中在中间（可知左右子树上有哪些元素），则在后序中必为最后如法对B的左右子树同样处理，则问题得解 8.【全国专升本统考題】中序遍历的递归算法平均空间复杂度为 O(n) 。 答：即递归最大嵌套层数即栈的占用单元数。精确值应为树的深度k+1包括叶子的空域也递歸了一次。 9. 【计算机研2001】 用5个权值{3, 2, 4, 5, 1}构造的哈