数据结构 第事章练习题

第1题

如果结点A有3个兄弟，结点B是A的双亲，则结点B的度是？

• A. 1
• B. 2
• C. 3
• D. 4

答案：D. 4

解析： 结点的度是指其直接拥有的子结点（孩子）的个数。结点A有3个兄弟，意味着它们有共同的双亲。所以，双亲结点B的孩子总数是 A 加上 A的3个兄弟，共4个。因此，B的度是4。

第2题

二叉树是度为2的树，这种说法是否正确？

• A. 正确
• B. 错误

答案：B. 错误

解析： 该说法错误。二叉树的定义是：每个结点的度最多为2（即度可以是0、1或2）的有序树。而“度为2的树”意味着树中每个结点的度都必须是2，这显然不符合二叉树的定义。

第3题

深度为k的完全二叉树至少有（）个结点。

• A. $2^{k - 2} + 1$
• B. $2^{k-1}$
• C. $2^k - 1$
• D. $2^{k-1} - 1$

答案：B. $2^{k-1}$

解析： 在这里，“深度为k”通常指“高度为k”。一棵高度为k的完全二叉树，其第1层到第k-1层必须是满的。前k-1层作为一棵满二叉树，其结点总数为 $2^{(k-1)} - 1$。为了使树的高度达到k，第k层至少需要有1个结点。因此，最少结点数 = $(2^{(k-1)} - 1) + 1$ = $2^{(k-1)}$。

第4题

一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。

• A. n = h + m
• B. h + m = 2n
• C. m = h - 1
• D. n = 2m - 1

答案：D. n = 2m - 1

解析： 在满二叉树中，结点总数 n = 2^h - 1，叶子结点数 m = 2^(h-1)。我们可以将这两个公式代入选项D进行验证：2m - 1 = 2 * (2^(h-1)) - 1 = 2^h - 1，这个结果正好等于n。因此，n = 2m - 1 成立。

第5题

在二叉树的前序遍历序列中，任意一个结点均处在其子女的前面，这种说法是否正确？

• A. 正确
• B. 错误

答案：A. 正确

解析： 前序遍历的顺序是“根-左-右”。对于树中的任意一个子树，根结点（即双亲）总是最先被访问的，然后才是它的左、右子树（其中包含了它的子女）。因此，该说法是正确的。

第6题

任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（）。

• A. 肯定不发生改变
• B. 肯定发生改变
• C. 不能确定
• D. 有时发生变化

答案：A. 肯定不发生改变

解析： 叶子结点没有子树。无论采用哪种遍历方式（前序、中序、后序），对于从左到右分布的叶子结点，访问的顺序总是从左边的叶子到右边的叶子。三种遍历方式改变的只是非叶子结点（双亲结点）相对于其子树的访问时机，但叶子结点之间的相对左右顺序是固定的。

第7题

二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

• A. 空或只有一个结点
• B. 高度等于其结点数
• C. 任一结点无左孩子
• D. 任一结点无右孩子

答案：B. 高度等于其结点数

解析： 前序遍历是“根-左-右”，后序遍历是“左-右-根”。若两者序列正好相反，意味着这棵树的结构非常特殊，它或者为空，或者每个结点最多只有一个孩子（即退化成一个链表）。一个有n个结点的链表状的树，其高度也为n。选项A虽然也可能，但B包含了更一般的情况。

第8题

用一维数组存储二叉树时，总是以前序遍历存储结点，这种说法是否正确（）。

• A. 正确
• B. 错误

答案：B. 错误

解析： 使用一维数组存储二叉树，最常见和最方便的方式是按层序遍历的顺序存储。这种方式（称为顺序存储结构）可以方便地通过数组下标计算来找到任一结点的双亲和孩子结点，尤其适用于完全二叉树。前序遍历不是通常采用的存储方式。

第9题

讨论树、森林和二叉树的关系，目的是为了（）。

• A. 借助二叉树上的运算方法去实现对树的一些运算
• B. 将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题
• C. 将树、森林转换成二叉树
• D. 体现一种技巧，没有什么实际意义

答案：B. 将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题

解析： 任何树或森林都可以唯一地转换成一棵二叉树。这样做的根本目的，就是为了能够复用为二叉树设计的、已经非常成熟的存储结构和丰富的算法（如各种遍历、查找等），来处理更普遍、更复杂的树和森林结构，从而简化问题的解决过程。

第10题

设森林中有4棵树，树中结点的个数依次为n1、n2、n3、n4，则把森林转换成二叉树后，其根结点的左子树上有（）个结点。

• A. $n_1 - 1$
• B. $n_1$
• C. $n_1 + n_2 + n_3$
• D. $n_2 + n_3 + n_4$

答案：A. $n_1 - 1$

解析： 森林转换成二叉树的规则是：第一棵树的根作为二叉树的根，第一棵树的子树林则转换成二叉树根的左子树。因此，二叉树根结点的左子树就是由第一棵树除去根结点外的所有结点构成的，其数量为 $n_1 - 1$。

第11题

设森林中有4棵树，树中结点的个数依次为n1、n2、n3、n4，则把森林转换成二叉树后，其根结点的右子树上有（ ）个结点。

• A. $n_1 - 1$
• B. $n_1$
• C. $n_1 + n_2 + n_3$
• D. $n_2 + n_3 + n_4$

答案：D. $n_2 + n_3 + n_4$

解析： 在森林转换成二叉树的规则中，森林里的后续树木（从第二棵开始）会依次连接到前一棵树根结点的右侧。在最终生成的二叉树里，原森林的第二、三、四棵树的所有结点，共同构成了根结点的右子树。因此结点总数为 $n_2 + n_3 + n_4$。

第12题

如果T’是由有序树T转换而来的二叉树，那么，T中结点的后序序列就是 T’ 中结点的（）序列。

• A. 前序
• B. 中序
• C. 后序
• D. 层序

答案：B. 中序

解析： 这是一个在树、森林与二叉树转换中非常重要的性质。对一棵树（或森林）进行后序遍历（先遍历孩子们/子树，最后访问根），其得到的结点序列，与对它转换后的二叉树进行中序遍历（先遍历左子树，再访问根，最后遍历右子树）得到的序列是完全相同的。

第13题

下述编码中（）不是前缀编码。

• A. (00, 01, 10, 11)
• B. (0, 1, 00, 11)
• C. (0, 10, 110, 111)
• D. (1, 01, 000, 001)

答案：B. (0, 1, 00, 11)

解析： 前缀编码的核心要求是，在一个编码方案中，任何一个字符的编码都不能是另一个字符编码的前缀。在选项B中，编码0是编码00的前缀，这违反了前缀编码的定义。因此，它不是前缀编码。

第14题

为5个使用频率不等的字符设计哈夫曼编码，不可能的方案是（）。

• A. 000, 001, 010, 011, 1
• B. 0000, 0001, 001, 01, 1
• C. 000, 001, 01, 10, 11
• D. 00, 100, 101, 110, 111

答案：D. (00, 100, 101, 110, 111)

解析： 哈夫曼编码所构成的二叉树是一棵严格二叉树，其所有叶子结点（代表编码）的路径长度 li 必须满足克拉夫特不等式，并且对于哈夫曼树这个等式严格成立：Σ 2^(-li) = 1。 我们来验证选项D： 2^(-2) + 2^(-3) + 2^(-3) + 2^(-3) + 2^(-3) = 1/4 + 4 * (1/8) = 1/4 + 1/2 = 3/4。 因为结果不等于1，所以它无法构成一个严格的二叉树，也就不可能是哈夫曼编码方案。

第15题

设哈夫曼编码的长度不超过4，若已经对两个字符编码为1和01，则最多还可以为（ ）个字符编码。

• A. 2
• B. 3
• C. 4
• D. 5

答案：C. 4

解析： 我们可以把整个编码空间看作是1。

• 编码1占用了编码空间的 1/2。
• 编码01占用了以0为前缀的空间的 1/2，即整个空间的 1/2 * 1/2 = 1/4。
• 已用空间为 1/2 + 1/4 = 3/4。
• 剩余可用空间为 1 - 3/4 = 1/4。 为了使编码的字符数最多，我们应该用尽可能长的码字来填充剩余空间。题目限制长度不超过4，每个长度为4的码字占用 1/16 的空间（例如0000, 0001等）。 因此，最多还可以增加的字符数为：(剩余空间) / (每个长码字占用的空间) = (1/4) / (1/16) = 4 个。

第16题

具有100个结点的完全二叉树的叶子结点数为？

答案：50

解析： 对于有n个结点的完全二叉树，其叶子结点数 n0 等于 ceil(n/2) (n/2向上取整)。因此，叶子结点数为 ceil(100/2) = 50。

*第17题

已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有多少个叶子结点？

答案：2

解析： 树的叶子结点是度为0的结点，设其数量为n0。根据树的性质：所有结点的度数之和 = 2 * 边数，以及 结点总数 = 边数 + 1。

• 结点总数 N = n0 + 2 + 3 + 4 = n0 + 9。
• 边数 E = N - 1 = n0 + 8。
• 度数之和 Sum(D) = (n0 * 0) + (2 * 1) + (3 * 2) + (4 * 3) = 0 + 2 + 6 + 12 = 20。
• 因为 Sum(D) = 2E，所以 20 = 2 * (n0 + 8)。
• 解方程得 10 = n0 + 8，所以 n0 = 2。

*第18题

设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最小值是？

答案：2h - 1

解析： 只有度为0和度为2的结点的二叉树称为严格二叉树。要使高度为h的树结点数最少，就应该让它尽可能“瘦”，即构成一条主干链，只在必要时分叉以增加高度。

• h=1时，最少1个结点。
• h=2时，最少3个结点。
• h=3时，最少5个结点。 观察规律可知，每增加1层高度，至少需要增加2个结点。形成的数列是 1, 3, 5, … 这是一个首项为1，公差为2的等差数列，其通项公式为 1 + (h-1)*2 = 2h - 1。

第19题

某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是？

答案：CDBGFEA

解析：

1. 根据前序序列 ABCDEFG，根结点是 A。
2. 在中序序列 CBDAFGE 中找到A，其左边 CBDA 是左子树，右边 FGE 是右子树。
3. 对左子树分析：其前序是 BCDE，中序是 CBDA。可知子树的根是 B，B的左孩子是C，右子树是D。
4. 对右子树分析：其前序是 EFG，中序是 FGE。可知子树的根是 E，E的左子树是FG。
5. 对FG子树分析：其前序是FG，中序是FG。可知子树的根是F，F的右孩子是G。
6. 重建树结构后，进行后序遍历（左-右-根），得到序列 C D B G F E A。

*第20题

在有n个叶子的哈夫曼树中，分支结点总数为？

答案：n - 1

解析： 哈夫曼树是一棵严格二叉树，只有度为0（叶子结点）和度为2（分支结点）的结点。对于任何严格二叉树，叶子结点数(n0)和分支结点数(n2)之间存在关系：n0 = n2 + 1。 题目中叶子有n个，即 n0 = n。代入公式得 n = n2 + 1，因此分支结点总数 n2 = n - 1。