本题考察栈先进后出的性质，调用函数入口为main()，main()入栈，接着调用S(1)，S(1)入栈，S(1)需要递归调用S(0)，S(0)入栈，题目要求“自栈底到栈顶保存的信息”，即main()→S(1)→S(0)，如果是“自栈顶到栈底保存的信息”就要反过来。

本题选A。

评：这道题的代码含义不理解，递归计算  。

方法一：枚举

先序序列为满足二叉树递归遍历顺序为“根左右”的输出序列。

其实只要枚举一半就行，本人枚举了左子树结点数大于右子树结点数的所有情况，另一半对称，总计 7×2=14 。

但注意，如果结点个数为奇数个，需要考虑左子树结点数等于右子树结点数的情况。

本题选B。

方法二：计算

可以发现，暴力枚举需要非常小心，稍有不慎就会遗漏。如果先序序列为入栈顺序，中序序列为出栈顺序，由先序序列和中序序列可以唯一的确定一棵二叉树，出栈序列为 �=4 的卡特兰数：  。

本题选B。

哈夫曼树是构造哈夫曼编码过程的图形化展示，哈夫曼树有许多重要的性质，哈夫曼树是一棵完满二叉树，每个结点的度只能为 0 或 2。

我们先根据选项构造出对应的完满二叉树，再检查该完满二叉树是否为哈夫曼树。

为了更加贴近哈夫曼树：

• 任意一个结点的左孩子权值小于或等于右孩子权值。
• 一个非叶结点的权值等于其左孩子权值和右孩子权值之和。

选项A的根结点的左孩子10的左右孩子权值出现了两种情况，意味着这两条路径一定不会出现在同一棵哈夫曼树中。错误。

选项B的根结点24的左右孩子权值出现了两种情况，意味着这两条路径一定不会出现在同一棵哈夫曼树中。错误。

选项C虽然成功构造出了一棵完满二叉树，但这棵完满二叉树不是一棵哈夫曼树，错误原因有两点：

• 第一点：哈夫曼树中不会出现权值为 0 的结点，因为哈夫曼树对应哈夫曼编码，每个叶结点的权值表示词频或出现几率，权只为 0 表示该单词不存在，显然哈夫曼编码不可能对不存在的单词进行统计。也就是哈夫曼树中每个结点的权值为正数。
• 第二点：哈夫曼编码是一种贪心编码，每次选择词频最小的两个字符，我们假设 0 合法，我们用 0、 10、3 和 11 这四个关键字尝试还原这棵哈夫曼树，我们发现还原失败。其实也可直接观察，第一次选中 0 和 10，第二次选中 3 和 11，明显有第一次选中的 10 大于第二次选中的 3，不符合哈夫曼编码。也就是说，如果命题组加大难度，将选项C修改为 24, 10, 9 和 24, 14, 11，虽然没有违反第一点，但违反第二点，仍然错误。

选项D的这棵完满二叉树是一棵哈夫曼树，可以进行如下验证。

本题选D。

这道题只能逐个分析选项。

A选项中，根结点的度不一定为2，A错误。

B选项中，一棵平衡二叉树是一棵二叉搜索树，由于中序遍历可得到一个降序序列，树中最小元素一定是最右结点，即无右子树，但可能有左子树，所以不一定是叶结点，B错误。

C选项中，AVL树的插入分两步，第一步是按照二叉搜索树的规则插入元素，该元素此时是叶结点，第二步是调整二叉搜索树为AVL树，如果此时二叉搜索树不平衡，需要进行旋转，旋转后该元素所在结点不一定是叶结点，C错误。

D正确。

本题选D。

D

方法：枚举

根据顶点集和边集画出有向图：

由于图比较简单，很容易枚举出所有深度优先遍历序列，为了不要混乱，按照顶点下标从小到大的顺序枚举：

本题选D。

方法一：模拟 + 枚举 + 取差集

Kruskal算法：首先将边从图中剥离然后按照边权值从小到大排序。然后从小到大依次将边复原到图中，插入后检查是否成环，如果成环，丢弃插入的边，重复上述过程直到有顶点都连通。

Kruskal过程模拟如下图所示：

解答：

第一次出现“失配”（s[i] ≠ t[j]）时，i = j = 5，隐藏含义是主串和模式串下标都从0开始，这个条件非常重要。

方法一：计算 next 数组后模拟

第一步：计算出模式串的next数组。

本人自编口诀优化前的next数组：第一格负一，第二格零，前缀等于后缀取最长。

这里由于主串和模式串下标都从0开始，没必要用优化后的next数组求解。优化后的next数组增加的1和下标都从0开始相比下标都从1开始减少的1正好相抵。

第二步：遍历主串对模式串进行匹配。

第一次匹配在模式串下标为5的位置出现失配，找到之前匹配的子串为abaab，最长相同前缀与后缀为ab，将前缀的ab移动到后缀ab的位置。

或者查表next数组失配字符c，其下标为5，其next值为next[5] = 2，已匹配字符数为5，移动位数 = 已匹配字符数 - 失配位置对应的匹配值 = 5 - 2 = 3。模式串向后移动3格，从失配位置开始重新进行匹配，此时 i = 5, j = 2。

或者查表next数组失配字符c，其下标为5，其next值为next[5] = 2，j指针直接跳转到模式串下标为2的位置，从失配位置开始重新进行匹配，此时 i = 5, j = 2。

本题选C。

方法三：贪心

贪心找到最多匹配的情况，同样画出上图。虽然这个方法不严谨，好在本题足够简单，从失配位置开始重新进行匹配，很容易看到i = 5, j = 2。

本题选C。

补充本人对本题完整KMP匹配过程的模拟。

C

除了基数排序外，其它三种排序都是基于比较的排序算法，元素的移动次数与关键字的初始排列次序有关。

解答：

删除8后，用小根堆最后一个元素占位，然后需要维护堆的性质，设根结点下标为1，调用MIN-HEAPIFY(A, 1)，MIN-HEAPIFY伪代码如下：

MIN-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l ≤ A.heap-size and A[l] < A[i]
        smallest = l
    else smallest = i
    if r ≤ A.heap-size and A[r] < A[smallest]
        smallest = r
    if smallest ≠ i
        exchange A[i] with A[smallest]
        MIN-HEAPIFY(A, smallest)

总共发生3次比较。

本题选C。

A

希尔排序是插入排序的一种，又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。