PTA（测验）2025-2026-1《数据结构》测验2（树和二叉树）

zhangzhang2025-12-012025-12-01

选择题

5

5.先序序列为abcd的二叉树共有（）棵。

A.13

B.14

C.15

D.16

记公式：Cₙ = (1/(n+1)) × C(2n, n)
跟出栈序列一个公式

9

9.二叉树在线索化后，仍不能有效求解的问题是( )。

A.先序线索二叉树中求先序后继

B.中序线索二叉树中求中序后继

C.中序线索二叉树中求中序前驱

D.后序线索二叉树中求后序后继

A. 先序线索二叉树中求先序后继

先序遍历顺序：根 → 左子树 → 右子树。

求先序后继的逻辑（直接通过当前节点指针 / 线索找到）：

若当前节点有左子树 → 后继是左子树的根（直接用左指针）；
若当前节点无左子树 → 后继是右子树的根（直接用右指针，若右空则是线索指向的后继）。

无需遍历其他节点，可有效求解

B. 中序线索二叉树中求中序后继

中序遍历顺序：左子树 → 根 → 右子树。

求中序后继的逻辑（线索树的核心优势）：

若当前节点有右线索（右指针是空指针改造的） → 直接指向后继；
若当前节点有右子树 → 后继是右子树中最左的节点（可通过右指针直接找到，无需遍历整树）。

逻辑规整，可有效求解

C. 中序线索二叉树中求中序前驱

与 “求中序后继” 对称，逻辑同样规整：

若当前节点有左线索 → 直接指向前驱；
若当前节点有左子树 → 前驱是左子树中最右的节点（直接通过左指针找到）。

可有效求解

D. 后序线索二叉树中求后序后继

后序遍历顺序：左子树 → 右子树 → 根。

问题的关键：后序的 “后继” 依赖 “父节点” 的状态，而线索树中节点不存储父指针，仅靠自身左 / 右线索无法判断：

例：当前节点是左子树的叶子节点，其后继可能是父节点的右子树（需先找父节点，再看父节点的右子树）；
但线索树中没有父指针，无法直接确定父节点，必须回溯或遍历才能找到后继，无法通过当前节点的线索 / 指针直接获取。

不能有效求解

11

11.若对如图所示的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是( )。

A.e，c

B.e，a

C.d，c

D.b，a

先把中序写出来：debxac，看x左右指针是不是空，如果是空就把中序序列x左右填上，如果有不是空的，就写实际指针指向的

13

13.树的基本遍历策略可分为先序遍历和后序遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。以下结论（）是正确的。

A.树的先序遍历序列与其对应的二叉树的先序遍历序列相同；

B.树的后序遍历序列与其对应的二叉树的后序遍历序列相同；

C.树的先序遍历序列与其对应的二叉树的中序遍历序列相同；

D.以上都不对

选A

填空题

2-2

已知一个森林的先序序列和后序序列如下，请构造出该森林，并回答下列问题。
先序序列：ABCDEFGHIJKLMNO
后序序列：CDEBFHIJGA MLONK
（1）该森林包括（ 2 ）颗树。
（2）每棵树的深度分别是（ 3-3 ）。
【注意】假如有3棵树，它们的深度按顺序依次是3，4和5，则填写3-4-5即可，数字之间用减号(-)连接，首尾及中间均没有空格，后面类似空格均按此方法填写。
（3）每棵树的度分别是（ 3-2 ）。
（4）每棵树的树根分别是（ AK ）。
【注意】假如有3棵树，它们的树根按顺序依次是A，B和C，则填写ABC即可，注意大小写，首尾及中间均没有空格，后面类似空格均按此方法填写。
（5）第1颗树的第2层的结点从左到右依次是（ BFG ）。
（6）最后1颗树的第2层的结点从左到右依次是（ LN ）。
（7）结点B，F，J，L和O的度分别是（ 3-0-0-1-0 ）。
（8）结点B的孩子结点从左到右依次是（ CDE ）。
（9）结点N的孩子结点从左到右依次是（ O ）。
（10）结点H的祖先结点从上到下依次是（ AG ）。

要确定两棵树：

1
2
3

	A				K
B	F	G		  L	  N
  CDE	   HIJ      M		O

如何确定：已知先序（第一个是根A），再看后序，因为后序是根是最后一个，说明CDEBFHIJGA是一棵树上面的（此时要把先序中有这些字母的与其他的隔开→ABCDEFGHIJ KLMNO），看A前一个是G，说明G是一个根，看向先序G后面的就是他的孩子（根后面就是孩子），再看向后序G前面的已经写了的HIJ就不看了，往前一个就是F，看向先序，F后面没有说明，F没有孩子，继续看后续……

2-3

已知字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8、11，求与其相应的Huffman树（按照左子树取小的原则）及每个字符的哈夫曼编码并回答下列问题。
（1）按要求构造的Huffman树的高度是（ 5 ）。
（2）该Huffman树的第4层有（ 3 ）个叶子结点。
（3）该Huffman树的第3层有（ 4 ）个节点。
（4）在该Huffman树中，字符A对应结点的祖先结点（不包括字符A对应的结点）的权值从上到下依次是（ 47-20-9-5 ）。
【注意】假如祖先结点的权值从上到下依次1，2，3，4，5，6，7，则填写1-2-3-4-5-6-7即可，数字之间用减号(-)连接。首尾及中间均没有空格，后面类似空格均按此方法填写。
（5）在该Huffman树中，7个字符（A、B、C、D、E、F、G）对应结点所在的层数依次是（ 5-3-4-4-5-4-3 ）。
（6）字符D对应的Huffman编码是（ 000 ）。
（7）字符E对应的Huffman编码是（ 0010 ）。
（8）字符F对应的Huffman编码是（ 111 ）。
（9）字符G对应的Huffman编码是（ 01 ）。
（10）该Huffman树的带权路径长度WPL值是（ 123 ）。