《树和二叉树练习》由会员分享，可在线阅读，更多相关《树和二叉树练习（3页珍藏版）》请在金锄头文库上搜索。
1、树和二叉树阶段练习一 单项选择题 1 深度为 6 的二叉树最多有 个结点。A) 64 B) 63 B) 32 D) 31 2 任何一棵二叉树的叶结点在其先序、中序和后序遍历序列中的相对位置 。A) 肯定发生变化 B) 有时发生变化 C) 肯定不发生变化 D) 无法确定 3 设深度为 k 的二叉树上只有度为 0 和度为 2 的结点，则这类二叉树上所含结点总数最少 为 个。A) k+1 B) 2k C) 2k-1 D) 2k+1 4 设森林 T 中有 4 棵树，第一、二、三、四棵树的结点个数分别是 n1，n2，n3和 n4，那么 当把森林 T 转换成一棵二叉树后，其根结点的右子树上有 个结点。 A
2、) n1-1 B) n1 C) n1+n2+n3 D) n2+n3+n4 5 讨论树、森林和二叉树的关系，目的是为了 。 A) 借助二叉树上的运算 B) 将树、森林按二叉树的存储方式进行存储 C) 将树、森林转换成二叉树 D) 体现一种技巧，没有什么实际意义。 6 下列说法中正确的是 。A) 任何一棵二叉树中至少有一个结点的度为 2 B) 任何一棵二叉树中的度肯定等于 2 C) 任何一棵二叉树中每个结点的度都为 2 D) 任何一棵二叉树中度可以小于 2 7 一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都大于它的左子树 上的所有结点的值，而小于右子树上所有结点的值。需采用 遍历方
3、式就可以得 到这棵二叉树所有结点的递增序列。A) 先序 B) 中序 C) 后序 D)层次 8 某二叉树的后序遍历序列为 dabec，中序遍历序列为 debac，则先序遍历序列为 。A）acbed B）decab C）deabc D）cedba 9 对于任何一棵二叉树 T，如果其叶子结点数为 n0，度为 2 的结点数为 n2，则 。A） n0=n2+1 B） n2=n0+1 C） n0=2n2+1 D） n2=2n0+1 10 在有 n 个结点的二叉链表中，值为非空的链域的个数为 。A）n-1B）2n-1C）n+1D）2n+1 二 填空题 1 一个含有 n 个结点的二叉树的最小高度为 ；最大深度
4、为 。 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 哈夫曼树是带权路径 的树，通
5、常权值较大的结点离根 。 10 若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后序 遍历序列中的第 个结点。 三 应用题 1 已知一棵树边的集合为 ， ， ，请画出这棵树，并回答下列问题： 1） 根结点是哪个结点？ 2） 哪些是叶子结点？ 3） 哪个结点是结点 E 的双亲？哪些结点是 E 的祖先？哪些结点是 E 的子孙？哪些结 点是 E 的兄弟？ 4） 树的深度是多少？ 5） 以 C 为根的子树的深度是多少？ 2 一棵度为 2 的树与一棵二叉树有何区别? 3 试分别画出具有 3 个结点的树和具有 3 个结点的二叉树的所有不同形态。 4 在结点个数为 n (n1)的树中
6、，高度最小的树的高度是多少？它有多少个叶结点？多少 个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 5 如果一棵树有 n1个度为 1 的结点, 有 n2个度为 2 的结点, , nm个度为 m 的结点, 试问 有多少个度为 0 的结点? 试推导之。 6 试分别找出满足以下条件的所有二叉树： 1) 二叉树的前序序列与中序序列相同 2) 二叉树的中序序列与后序序列相同 3）二叉树的前序序列与后序序列相同 7 分别用顺序存储结构和链式存储结构画出图 7 所示二叉树的存储结构。 8 分别写出图 1 所示二叉树的前序、中序、后序序列。图 1 一棵二叉树 9 已知一棵二叉树的前序
7、遍历的结果是 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 已知一棵完全二叉树存放于一个一维数组 Tn中，Tn中存放的是各结点的值。试设计 一个算法，从 T0开始顺序读出各结点的值，建立该二叉树的二叉链表表示。 3 请写一算法，求一棵二叉树的高度。 4 请写一算法，按层次遍历二叉树。
