1 第六章 树和二叉树 一、判断题 ( t )01、若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 ( f )02、二叉树中每个结点的两棵子树的高度差等于 1。 (t )03、二叉树中每个结点的两棵子树是有序的。 ( f )04、二叉树中每个结点有两棵非空子树或有两棵空子树。 ( f )05、二叉树中所有结点个数是 2k-1-1，其中k是树的深度。 (f )06、二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 ( f )07、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。 (t )08、用二叉链表法存储包含 n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 (t)09、具有12个结点的完全二叉树有5个度为 2的结点。 ( f )10、二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值，且小于其右非空子树(若存在的话)所有结点的关键字值。 ( f )11、二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索。 ( t )12、二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。 二、填空题 01、由 3个结点所构成的二叉树有_5_种形态。 02、一棵深度为 6的满二叉树有____个分支结点和____个叶子。 03、一棵具有257个结点的完全二叉树，它的深度为____。 04、设一棵完全二叉树有700个结点，则共有____个叶子结点。 05、设一棵完全二叉树具有1000个结点，则此完全二叉树有____个叶子结点，有____个度为 2的结点，有____个结点只有非空左子树，有____个结点只有非空右子树。 06、一棵含有n个结点的k叉树，可能达到的最大深度为____，最小深度为____。 07、二叉树的基本组成部分是：根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种：前序法(即按N L R次序)，后序法(即按 LRN次序)和中序法(也称对称序法，即按 L N R次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是 BEFCGDH，中序序列是 FEBGCHD，则它的后序序列必是____。 08、用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是____。 三、选择题 ( )01、树最适合用来表示__。 A)有序数据元素 B)无序数据元素 C)元素之间具有分支层次关系的数据 D)元素之间无联系的数据 ( )02、假定在一棵二叉树中，双分支结点数为 15，单分支结点数为 30，则叶子结点数为__个。 A)15 B)16 C)...
