B
第一次：3+2= 5，S1：5，8，5（栈顶）；S2：*，-（栈顶）
第二次：8-5= 3，S1：5，3（栈顶）；S2：*（栈顶）
第三次：5*3= 15，S1：15；S2：空

这道题很简单，模拟计算过程就行，唯一要注意的是先弹出的是a，后弹出的b，且计算时b op a，b在前，a在后。审题务必仔细。

C
队列先进先出，按次序出队，按次序入栈，即按1,2,3,4,5,6依次入栈。C选项：3先出栈，则2比1先出栈。

方法一：模拟

A的操作顺序为①①②②①①③③。

B的操作顺序为②①①①①①③。

C无法找到合适的操作序列。

D的操作顺序为②②②②②①③③③③③。

本题选C。

方法二：单调性

由于只能通过栈改变序列中某子串单调性一次，所以输出序列中没有按照先进先出顺序出队的子串一定通过栈要被反转。

A中子串3, 4没有按序出队，被反转成4, 3，正确。

B中子串1没有按序出队，被反转成1，正确。

C中子串1, 2没有按序出队，但没有被反转，错误。

D中子串1, 2, 3, 4, 5, 6没有按序出队，被反转成6, 5, 4, 3, 2, 1，正确。

本题选C。

如果本题加大难度，输入序列为乱序，需要进行元素值和元素下标的一对一映射，写代码需要建立两个键值哈希表，一个键为元素值，值为元素下标，另一个键为元素下标，值为元素值。

C语言下标为0，按行优先存储。

方法一：画图

本题选A。

方法二：计算

也可以直接计算：

第一步：计算 m1,1 到 m6,6 的元素个数。

12+11+10+9+8+1=51

第二步：修正下标从0开始，需要减一。

51−1=50

本题选A。

A

方法一：推理

因为每个非叶结点都有2个子结点，所以二叉树T只有度为0和度为2的结点，可得：

n0=k

n0=n2+1

n=n0+n2

解得 n=2k−1 。

本题选A。

方法二：画图举例

一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。可得这棵二叉树为满二叉树。

直接画出一个高度为3的满二叉树。

k=4,n=7 可得 n=2k−1 。

本题选A。

方法一：构造

按照题目条件构造哈夫曼树。

每次取最小的两个子树的根结点合并。过程如下图所示：

左指针标0，右指针标1，从根结点到叶结点的路径即为该字符的哈夫曼编码。

本题选A。

方法二：代入选项

从选项构造哈夫曼树，检查是否符合哈夫曼编码性质。

选项B中a的编码是d的编码的前缀，错误。

选项C中a的编码是b的编码的前缀，错误。

选项D构造出的哈夫曼树不符合WPL最小规则，错误。

但其实这样做可能更加麻烦，需要画出4棵哈夫曼树依次进行检查。

检查后只有A符合要求。

本题选A。

二叉排序树中序遍历序列单调递增序列。

中序遍历有两种方法，本人分别命名为投影法和环线法。

有 x1<x3<x5<x4<x2 。

本题选C。

补充一下二叉树前序遍历、中序遍历、后序遍历递归版的特征：

• 前序遍历顺序为“根左右”，在第一次访问某结点时输出该结点的关键字。
• 中序遍历顺序为“左根右”，在第二次访问某结点时输出该结点的关键字。
• 后序遍历顺序为“左右根”，在第三次访问某结点时输出该结点的关键字。

D

方法一：枚举

枚举所可能的拓扑序列。

每次找入度为0的点依次剥离，如下图所示：

总共有4种可能的输出序列。

A、B、C均能够找到对应的输出序列。

本题选D。

方法二：代入选项

带入选项中的拓扑序列检查是否符合题目中的有向图。

A、B、C均符合。

本题选D。

B

本题考察B树的基本性质。

方法一：公式法

方法二：构造法

C

我们先构造出插入所有元素后的散列表。

可以计算出查找关键字22, 43, 15成功需要探测的次数，如下图所示。

查找22的探测次数为1：

查找43的探测次数为2：

查找15的探测次数为3：

平均查找长度为求查找长度的数学期望：

ASL_成功=(3+2+1)/3=2

D

先看第一趟，1从最开始的5号位移动到0号位，说明第一趟步长是5，直接排除A,B；再看第二趟，2从第一趟排序结果的第4位移动到1号位，说明第二趟步长是3

void shellsort(int[] arr, int length) {
    int index = 0;
    int value = 0;
    for(int flag = length/2; flag>0; flag /= 2;) {
        for(int i=flag; i<length; i++) {
            index = i;
            value = arr[index];
            if(value < arr[index-flag]) {
                while((index-flag > 0 ||index-flag == 0) && value < arr[index-flag]) {
                    arr[index] = arr[index-flag];
                    index = index - flag;
                }
                arr[index] = value;
            }
        }
    }
}

这道题考察希尔排序的特征，希尔排序中间过程是间隔有序的。

需要考察的间隔很多，我们可以直接参考选项，第一趟排序的间隔只有3和5，我们先考察3，从数组第一个元素开始为1, 5, 4, ...到这里就没必要查下去了，数组已经不单调了。直接排除A和B。

下面考察C和D，只需要观察第二题排序的间隔。我们先考察2，从数组第一个元素开始为1, 6, 3, ...到这里就没必要查下去了，数组已经不单调了。直接排除C。

现在A、B和C都被排除，只能选D，当然不放心的话你也可以验证一下D，完全符合希尔排序的特征。

A

画出建堆过程：

对应Python测试代码：

array = [-6,-1,-5,-9,-8,-4,-7]
heapq.heapify(array)
print(array)

建堆的时间复杂度 O(n) 。