2026-05-18 树及算法

单项选择题

1. 给定一个二叉树，若前序遍历序列与中序遍历序列相同，则二叉树是（ ）。

2. 用 Huffman 算法构造一个最优二叉编码树，待编码的字符权值分别为 {3, 4, 5, 6, 8, 9, 11, 12}，请问该最优二叉编码树的带权外部路径长度为（ ）。（补充说明：树的带权外部路径长度定义为树中所有叶子结点的带权路径长度之和；其中，结点的带权路径长度定义为该结点到树根之间的路径长度与该结点权值的乘积）

3. 设结点 X 和 Y 是二叉树中任意的两个结点，在该二叉树的先根周游遍历序列中 X 出现在 Y 之前，而在其后根周游序列中 X 出现在 Y 之后，则 X 和 Y 的关系是（ ）。

4. 考虑一个森林 F，其中每个结点的子结点个数均不超过 2。如果森林 F 中叶子结点的总个数为 L，度数为 2 结点（子结点个数为 2）的总个数为 N，那么当前森林 F 中树的个数为（ ）。

5. 回溯法是一类广泛使用的算法，以下叙述中不正确的是（ ）。

6. 若定义二叉树中根结点的层数为零，树的高度等于其结点的最大层数加一。则当某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。

7. 任意一棵二叉树中，所有叶结点在前序、中序和后序周游序列中的相对次序（ ）。

8. 在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数为 1，则度为 0 的结点个数为（ ）。

9. 由同一组关键字集合构造的各棵二叉排序树（ ）。

10. 在映射抽象数据类型（ADT Map）的不同实现方法中，适合对动态查找表进行高效率查找的组织结构是（ ）。

判断题

11. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。

12. 若某非空二叉树的先序序列和后序序列正好相同，则该二叉树只有一个根结点。

13. 有 n 个结点的二叉排序树有多种，其中树高最小的二叉排序树是搜索效率最好。

14. 给定一棵二叉树，前序周游序列和中序周游序列分别是 HGEDBFCA 和 EGBDHFAC 时，其后序周游序列必是 EBDGACFH。

15. 假设一棵二叉搜索树的结点数值在 1 到 1000 之间，现在查找数值为 363 的结点。以下三个序列皆有可能是查过的序列：A) 2, 252, 401, 398, 330, 344, 397, 363；B) 925, 202, 911, 240, 912, 245, 363；C) 935, 278, 347, 621, 299, 392, 358, 363。

16. 构建一个含 N 个结点的（二叉）最小值堆，建堆的时间复杂度大 O 表示为 O(Nlog₂N)。

填空题

17. 在一棵含有 n 个结点的树中，只有度（树结点的度指子结点数量）为 k 的分支结点和度为 0 的终端（叶子）结点，则该树中含有的终端（叶子）结点的数目为_________。

18. 已知以数组表示的小根堆为 [8, 15, 10, 21, 34, 16, 12]，删除关键字 8 之后需要重新建堆，在此过程中，关键字的比较次数是_________。

19. 一棵含有 101 个结点的二叉树中有 36 个叶子结点，度为 2 的结点个数是_________，度为 1 的结点个数是_________。

20. 已知二叉树的前序遍历结果（先根周游序列）为 ADC，这棵二叉树的树型有_________种可能。

21. 已知二叉树的中序序列为 DGBAECF，后序序列为 GDBEFCA，该二叉树的前序序列是_________。

22. 对于具有 57 个结点的完全二叉树，如果按层次自顶向下，同一层自左向右，顺序从 0 开始对全部结点进行编号，则有：编号为 18 的结点的父结点的编号是_________，编号为 19 的结点的右子女结点的编号是_________。

综合题

23. 已知下列 pre2post 函数的功能是根据一个满二叉树的前序遍历序列，求其后序遍历序列，请完成填空（假设序列长度不超过 32）。

# 返回先根序列 preorder[start:start+length] 对应的后根序列
def pre2post(preorder, start, length):
    if length == 1:
        return ______________      # (1 分)
    else:
        length = ______________     # (2 分)
        left  = pre2post(preorder, ______________)   # (1 分)
        right = pre2post(preorder, ______________)   # (2 分)
        root  = ______________      # (2 分)
        return left + right + root

print(pre2post("ABC", 0, 3))      # 输出 BCA
print(pre2post("ABDECFG", 0, 7))  # 输出 DEBFGCA

24. 填空完成下列程序：输入一棵二叉树的扩充二叉树的先根周游（前序遍历）序列，构建该二叉树，并输出它的中根周游（中序遍历）序列。这里定义一棵扩充二叉树是指将原二叉树中的所有空引用增加一个表示为 @ 的虚拟叶结点。

输入样例：

ABD@G@@@CE@@F@@

输出样例：

DGBAECF

s = input()
ptr = 0

class BinaryTree:
    def __init__(self, data, left=None, right=None):
        self.data, self.left, self.right = data, left, right
    def addLeft(self, tree):    # tree 是子树
        self.left = tree
    def addRight(self, tree):   # tree 是子树
        self.right = tree
    def inorderTraversal(self):  # 中序遍历
        if self.left:
            ______①______        # (1 分)
        print(self.data, end="")
        if self.right:
            ______②______        # (1 分)

def buildTree():
    global ptr
    if s[ptr] == "@":
        ptr += 1
        ______③______           # (2 分)
    tree = ______④______        # (1 分)
    ptr += 1
    ______⑤______               # (2 分)
    ______⑥______               # (2 分)
    return tree

tree = ______⑦______            # (1 分)
tree.inorderTraversal()