应用台导航页

主页
博客
知识库
工作台
集萃
友链
关于

408计算机考研数据结构树真题——选择题

408计算机考研数据结构树真题——选择题

更新于 2026-10-16

— 4292 字

先序和中序遍历序列还原树也不会操作。

2010 年

【2010年真题】下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（）。

408考研2010年真题第三题图

【解析】

后序遍历序列：访问顺序为“左子树 $\to$ 右子树 $\to$ 根结点”。遍历序列为： $d, b, c, a$ 。

【答案】D

【2010年真题】第5题在一棵度数为 $4$ 的树 $T$ 中，若有个度为的结点，个度为的结点，个度为的结点，个度为的结点，则树的叶结点个数是（）。

相关内容

408计算机考研树大题
更新于2026-10-16

文章大纲

2010 年
2011 年
2012年
2013年
2014年
2015年
心得笔记

理解哈夫曼树的WPL

相关练习题目

文章 ID: 612

相关内容

408计算机考研树大题
更新于2026-10-16
408计算机考研图大题
更新于2026-10-16
2021年英一范文有声书
更新于2026-10-16
9.1 二重积分的概念和性质
更新于2026-10-16
9.2 二重积分的计算技巧
更新于2026-10-15

Dors 是花野猫开发为知识工作者打造的数字花园应用，包含的博客、个人记事本、及其他实用功能。

花园

花坛——博客
果园——知识库

工坊——作者开发的实用工具

小记
秒切——一键按秒分割视频
中国重点高校地理位置可视化网站
中国行政区划数据查询平台
excel 重命名工具

misc

生活章程
画廊
just have fun!

© 2022 - present. All Rights Reserved.滇ICP备2025063395号-1

花野猫打造

20

20

20

4

10

3

1

2

10

1

T

A. 41
B. 82
C. 113
D. 122

【解析】

设树中度为 $i(i=0,1,2,3,4)$ 的结点数分别为 $N_i$ ，树中结点总数为 $N$ ，则树中各结点的度之和等于 $N-1$ ，即根据题设中的数据，即可得到

【答案】B

【2010年真题】第6题对 $n\ (n \ge 2)$ 个权值均不相同的字符构成赫夫曼树。下列关于该赫夫曼树的叙述中，错误的是（）。

A. 该树一定是一棵完全二叉树
B. 树中一定没有度为 1 的结点
C. 树中两个权值最小的结点一定是兄弟结点
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值

【解析】

A 项错误： 赫夫曼树（最优二叉树）只保证带权路径长度（WPL）最短，树的形态通常是不平衡的，甚至可能退化为单支倾斜结构，并不保证满足完全二叉树的定义。
B 项正确： 赫夫曼树构造过程中每次都是选取两棵权值最小的子树合并为一棵新二叉树，新生成的根结点度一定为 $2$ ，原叶结点度为 $0$ ，因此赫夫曼树中只有度为 $0$ 和度为 $2$ 的结点。
C 项正确： 最开始合并的一定是初始字符中权值最小的两个结点，它们合并后作为新结点的左右孩子，因此必为兄弟结点。
D 项正确： 赫夫曼树中任意非叶结点的权值等于其左右孩子权值之和。而每次合并均选取当前最小的权值进行合并，自底向上构建，因此上层非叶结点的权值必然不小于其下一层任意结点的权值。

【答案】A

2011 年

【2011年真题第4题】若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（）。
A. 257 B. 258 C. 384 D. 385

解析：

根据完全二叉树的性质，最后一个分支结点的序号为 $\lfloor n/2 \rfloor=\lfloor 768/2 \rfloor=384$ ，故叶子结点的个数为 $768 - 384 = 384$ 。

【另解 1】由二叉树的性质 $n = n_0 + n_1 + n_2$ 和 $n_{0} = n_{2}$ 可知，，，显然，，则。

【另解 2】完全二叉树的叶子结点只可能出现在最下两层，由题可计算完全二叉树的高度为10。第 10 层的叶子结点数为 $768-(2^9-1)=257$ ；第 10 层的叶子结点在第 9 层共有 $\lceil 257/2 \rceil=129$ 个父结点，第 9 层的叶子结点数为 $(2^9-1)-129=127$ ，则叶子结点的总数为。

第5题：
若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是（）。
A. 1, 2, 3, 4 B. 2, 3, 4, 1
C. 3, 2, 4, 1 D. 4, 3, 2, 1

前序序列为 NLR，后序序列为 LRN，由于前序序列和后序序列刚好相反，故不可能存在一个结点同时存在左右孩子，即二叉树的高度为 4。1 为根结点，由于根结点只能有左孩子（或右孩子），因此，在中序序列中，1 或在序列首或在序列尾，ABCD 皆满足要求。仅考虑以 1 的孩子结点2 为根结点的子树，它也只能有左孩子（或右孩子），因此，在中序序列中，2 或在序列首或序列尾，ABD 皆满足要求。

第6题：
已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点的个数是（）。
A. 115 B. 116 C. 1895 D. 1896

解析：树转换为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数 = 分支结点数 $+1=2011-116+1=1896$ 。通常本题应采用特殊法解，设题意中的树是如右图所示的结构，则对应的二叉树中仅有前 115 个叶结点有右孩子，故无右孩子的结点个数 $=2011-115=1896$ 。

2012年

【2012年真题3】若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根结点的孩子结点______。 A. 只有 e　B. 有 e、b　C. 有 e、c　D. 无法确定

前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两个结点的前序序列为 XY 与后序序列为 YX 时，则 X 为 Y 的祖先。考虑前序序列 a, e, b, d, c、后序序列 b, c, d, e, a，可知 a 为根结点，e 为 a 的孩子结点。此外，a 的孩子结点的前序序列 e, b, d, c、后序序列 b, c, d, e，可知 e 是 bcd 的祖先，故根结点的孩子结点只有 e。故选 A。

【排除法】显然 a 为根结点，且确定 e 为 a 的孩子结点，排除 D。各种遍历算法中左右子树的遍历次序是固定的，若 b 也为 a 的孩子结点，则在前序序列和后序序列中 e、b 的相对次序应是不变的，故排除 B，同理排除 C。

【特殊法】前序序列和后序序列对应着多棵不同的二叉树树形，我们只需画出满足该条件的任一棵二叉树即可，任意一棵二叉树必定满足正确选项的要求。

2013年

【2013真题第4题】已知三叉树 T 中6个叶结点的权分别是 2, 3, 4, 5, 6, 7，T 的带权（外部）路径长度最小是____。

A.27 B.46 C.54 D.56

【2013真题第5题】若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y，则 X 的右线索指向的是____。

A.X 的父结点
B.以 Y 为根的子树的最左下结点
C.X 的左兄弟结点 Y
D.以 Y 为根的子树的最右下结点

答案：A

2014年

【2014年真题第5题】将森林F转换为对应的二叉树T，F中叶结点的个数等于____。

A. T中叶结点的个数
B. T中度为1的结点个数
C. T中左孩子指针为空的结点个数
D. T中右孩子指针为空的结点个数

【2014年真题第6题】 5个字符有如下4种编码方案，不是前缀编码的是____。

A. 01, 0000, 0001, 001, 1
B. 011, 000, 001, 010, 1
C. 000, 001, 010, 011, 100
D. 0, 100, 110, 1110, 1100

2015年

先序序列为 a, b, c, d 的不同二叉树的个数是____。 A. 13 B. 14 C. 15 D. 16
下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是____。 A. 24, 10, 5 和 24, 10, 7 B. 24, 10, 5 和 24, 12, 7 C. 24, 10, 10 和 24, 14, 11 D. 24, 10, 5 和 24, 14, 6
现有一棵无重复关键字的平衡二叉树（AVL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是____。 A. 根结点的度一定为 2 B. 树中最小元素一定是叶结点 C. 最后插入的元素一定是叶结点 D. 树中最大元素一定是无左子树

心得笔记

树的五条性质一定要记熟（里面就有完全二叉树的性质）
完全二叉树和满二叉树没有区分清楚。满二叉树不可能是 768 个节点，但完全二叉树768个结点是可能的
我不知道的事情：结点数等于分支总数+1 。
遍历性质的题，前序 XY + 后序 YX ，那 XY 一定不是兄弟，那么 X 是 Y 的祖先。
线索化的规则之前就没搞清楚，首先只有空指针域改作线索，其次若左指针为空，令其指向前驱；若右指针为空，令其指向后继。
树与二叉树的转化也不会：孩子兄弟表示法中：原树每个非叶结点，在二叉树里都会多出一个无右孩子的结点；
带权外部路径长度 WPL是什么我也没搞清楚
13年第4题，还和外部排序的最佳归并树有关。

理解哈夫曼树的WPL

对字符编码，如果采用定长编码，太浪费存储空间，所以需要变长
但是不能有公共前缀，否则无法解码，如果把字符表示为树中的叶子结点，从根节点出发，到任意叶子结点，中间不会经过叶子结点，因此编码不存在公共前缀
够成树的过程中，总是优选挑选小权重的叶子、树来组合。这样小权重的路径最长（编码最长），则路径与权重的乘积（总比特数）不会太大

可以从字符出现频率入手，先统计每个字符出现次数，让高频字符用短编码。

路径长度 =>一个字符的编码长度
权值 => 字符出现次数
带权路径长度 => 每个字符的编码长度乘以出现字符出现次数（只乘叶子结点的权）
树的带权路径长度 => 所有叶子结点的带权路径长度之和，即字符串编码后的总比特数

以哈夫曼编码为线索，理解哈夫曼树中的 WPL 这个概念。哈夫曼编码的目标是使全文总比特数最少。这个编码后的全文总比特数，用哈夫曼树中的 WPL 来表示。首先，叶子结点对应待编码的各个字符，用权值表示字符出现的频次，用从根到叶子的边数（路径长度）表示该字符编码后的比特位数，则结点的带权路径长度就是该字符在全文中所占的总比特数。将所有叶子结点的带权路径长度相加，即为全文编码后的总比特数。而哈夫曼树的构造方法，保证了WPL最小，在哈夫曼编码这个应用场景中，就确保了编码后占用的存储空间最小。

相关练习题目

（度数与结点数关系）一棵树共有 $n$ 个结点，其中所有分支结点的度均为 $k$ ，则该树中的叶结点数为 $(nk-n+1)/k$ 。

树中的叶结点数为 $n_0$ ，则分支结点（非叶结点）数为 $n - n_0$ 。树中所有结点的度数之和（即总分支数）为： $(n - n_0) \cdot k$ ，又总分支数（在任意一棵包含个结点的树中，除根结点外，每个结点上方都有且仅有一条边与之对应），联立求解得：

408计算机考研图大题

更新于2026-10-16

2021年英一范文有声书

更新于2026-10-16

9.2 二重积分的计算技巧

更新于2026-10-15

N - 1

1+N_1+2N_2+3N_3+4N_4 = N_0+N_1+N_2+N_3+N_4

N_0=82

+

1

n_0 = n_2 + 1

n_{0} = n_{2} + 1

n = 2n_0-1 + n_1

2n_0-1 + n_1 = 768

n_1=1

2n_0=768

n_0=384

(29−

1)−

129=

127

257 + 127 = 384

0

)

⋅

k

= n - 1

n

n_0 = \frac{n k - n + 1}{k}

9.1 二重积分的概念和性质

更新于2026-10-16