树和二叉树练习.doc

树和二叉树阶段练习一 单项选择题1 深度为6的二叉树最多有 个结点。 A) 64 B) 63 B) 32 D) 312 任何一棵二叉树的叶结点在其先序、中序和后序遍历序列中的相对位置 。 A) 肯定发生变化 B) 有时发生变化 C) 肯定不发生变化 D) 无法确定3 设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少为 个。 A) k+1 B) 2k C) 2k-1 D) 2k+14 设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1，n2，n3和n4，那么当把森林T转换成一棵二叉树后，其根结点的右子树上有 个结点。A) n1-1 B) n1 C) n1+n2+n3 D) n2+n3+n45 讨论树、森林和二叉树的关系，目的是为了 。A) 借助二叉树上的运算 B) 将树、森林按二叉树的存储方式进行存储 C) 将树、森林转换成二叉树 D) 体现一种技巧，没有什么实际意义。6 下列说法中正确的是 。 A) 任何一棵二叉树中至少有一个结点的度为2 B) 任何一棵二叉树中的度肯定等于2C) 任何一棵二叉树中每个结点的度都为2 D) 任何一棵二叉树中度可以小于27 一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都大于它的左子树上的所有结点的值，而小于右子树上所有结点的值。需采用 遍历方式就可以得到这棵二叉树所有结点的递增序列。 A) 先序 B) 中序 C) 后序 D)层次8某二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为 。 A）acbed B）decab C）deabc D）cedba9对于任何一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则。 A） n0=n2+1 B） n2=n0+1 C） n0=2n2+1 D） n2=2n0+110在有n个结点的二叉链表中，值为非空的链域的个数为 。 A）n-1B）2n-1 C）n+1D）2n+1二 填空题1一个含有n个结点的二叉树的最小高度为 ；最大深度为 。2 任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为 个。3 若一棵二叉树的叶子数为n，则该二叉树中，左、右子树皆非空的结点个数为 。4 深度为8的满二叉树有 个结点。5树有三种常用的存储结构，即孩子链表法，双亲表示法和 。6一棵哈夫曼树T，其叶子结点的权分别为3，16，7，4，11，这棵哈夫曼树的带权路径长度为 。7已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有 个叶子结点。8 由树转换成二叉树时，其根结点的 子树总是空的。9 哈夫曼树是带权路径 的树，通常权值较大的结点离根 。10 若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第 个结点。三 应用题1 已知一棵树边的集合为， ，请画出这棵树，并回答下列问题：1） 根结点是哪个结点？2） 哪些是叶子结点？3） 哪个结点是结点E的双亲？哪些结点是E的祖先？哪些结点是E的子孙？哪些结点是E的兄弟？4） 树的深度是多少？5） 以C为根的子树的深度是多少？2 一棵度为2的树与一棵二叉树有何区别?3 试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。4 在结点个数为n (n1)的树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？5 如果一棵树有n1个度为1的结点, 有n2个度为2的结点, , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之。6 试分别找出满足以下条件的所有二叉树：1) 二叉树的前序序列与中序序列相同2) 二叉树的中序序列与后序序列相同3）二叉树的前序序列与后序序列相同7 分别用顺序存储结构和链式存储结构画出图7 所示二叉树的存储结构。8 分别写出图1所示二叉树的前序、中序、后序序列。 图1 一棵二叉树 9已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。10 将图2所示的森林转化为二叉树。图2 森林11写出图13所示的森林的先根和后根序列。12给定权值集合15, 03, 14, 02, 06, 09, 16, 17, 构造相应的哈夫曼树, 并计算它的带权路径长度。13 假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不等长Huffman编码, 并给出该电文的总码数。四 算法题1 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：（1）统计二叉树中叶结点的个数。（2）以二叉树为参数，交换每个结点的左孩子和右孩子。2 已