方法一：模拟

先模拟出进栈、退栈操作序列，然后检查是否出现连续三次进行退栈操作，题目明确要求“不允许连续三次进行退栈操作”。

A选项：a进栈，b进栈，c进栈，d进栈，d出栈，c出栈，e进栈，e出栈，b出栈，f进栈，f出栈，a出栈。没有出现连续三次进行出栈操作，正确。

B选项：a进栈，b进栈，c进栈，c出栈，b出栈，d进栈，d出栈，a出栈，e进栈，e出栈，f进栈，f出栈。没有出现连续三次进行出栈操作，正确。

C选项：a进栈，b进栈，b进栈，c进栈，c出栈，a出栈，d进栈，e进栈，e出栈，f进栈，f出栈，d出栈。没有出现连续三次进行出栈操作，正确。

D选项：a进栈，a出栈，b进栈，c进栈，d进栈，e进栈，f进栈，f出栈，e出栈，d出栈，c出栈，b出栈。出现连续五次出栈操作，错误。

本题选D。

方法二：观察选项

栈的性质为先进后出，序列a, b, c, d, e, f反转为序列f, e, d, c, b, a，如果出现连续三次进行出栈操作，则一定出现长度大于或等于 3 的f, e, d, c, b, a的子序列，D选项出现了f, e, d, c, b，长度大于 3。

本题选D。

为了方便下面表述，仅能进行入队操作的一端称为A端，既能进行入队操作又能进行出队操作的一端称为B端。

方法一：模拟

按照a, b, c, d, e依次入队的顺序进行模拟。

A选项：a从A端入队，b从B端入队，c从A端入队，d从A端入队，e从A端入队，b, a, c, d, e依次从B端出队。

B选项：a从A端入队，b从B端入队，c从A端入队，d从B端入队，e从A端入队，d, b, a, c, e依次从B端出队。

C选项：a从A端入队，无法继续执行，错误。

D选项：a从A端入队，b从B端入队，c从B端入队，d从A端入队，e从B端入队，e, c, b, a, d依次从B端出队。

本题选C。

方法二：栈+队列

某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，这是一个输出受限的双端队列，当然命题组为了降低难度，没有给出专业术语，根据描述就知道如何操作，这样就是一个一个模拟。

当然，由于这个双端队列两端都能操作，模拟难度极大，这时候我们需要进行简化。

简化思路一：既能进行入队操作又能进行出队操作的一端视为一个完整的栈，仅能进行入队操作的一端用于插入元素。即简化为栈+插入。

栈是先进后出的数据结构，如果所有元素入栈后出栈，得到的是输入序列的逆序序列。

简化思路二：仅能进行入队操作的一端视为队列的尾部，既能进行入队操作又能进行出队操作的一端中具有出队功能的部分视为队列的头部，这样得到一个完整的队列，既能进行入队操作又能进行出队操作的一端中具有入队功能的部分用于插入元素。即简化为队列+插入。

队列是先进先出的数据结构，得到的是输出序列与输入序列一致。

由于这道题要求元素全部入队后进行操作，可以简化为栈+队列。如图(a)所示。

栈部分的子序列先出队，形成一个逆序子序列，队列部分的子序列后出队，形成一个顺序子序列。如图(b)所示。

A选项：a, c, d, e是a, b, c, d, e的顺序子序列，a, c, d, e从A端入队，b是a, b, c, d, e的逆序子序列，b从B端入队，得到序列为 b,a,c,d,e 。正确。

B选项：a, c, e是a, b, c, d, e的顺序子序列，a, c, e从A端入队，d, b是a, b, c, d, e的逆序子序列，b, d从B端入队，得到序列为 d,b,a,c,e 。正确。

C选项：a, e是a, b, c, d, e的子序列，a, e从A端入队，d, b, c不是a, b, c, d, e的逆序子序列，错误。

D选项：a, d是a, b, c, d, e的子序列，a, d从A端入队，e, c, b是a, b, c, d, e的逆序子序列，b, c, e从B端入队，得到序列为 e,c,b,a,d 。正确。

本题选C。

方法三：找规律

入队序列a, b, c, d, e转化为下标序列1, 2, 3, 4, 5，为一个单调递增序列。

A选项：b, a, c, d, e转化为2, 1, 3, 4, 5

B选项：d, b, a, c, e转化为4, 2, 1, 3, 5

C选项：d, b, c, a, e转化为4, 2, 3, 1, 5

D选项：e, c, b, a, d转化为5, 3, 2, 1, 4

很明显，只有C选项的折线图中间有一个凸起。这个绝对不是巧合哦！本题结果序列至多由一个下标单调递减序列和一个下标单调递增序列拼接而成。C选项明显不符合要求。

本题选C。

方法一：定义

若结点 x 为根结点，则无后继；

若结点 x 为其父结点的右孩子结点，则其后继为其父结点；

若结点 x 为其父结点的左孩子结点，且父结点无右孩子结点，则其后继为其父结点；

若结点 x 为其父结点的左孩子结点，且双亲有右孩子结点，则其后继为其父结点的右子树中按后序遍历的第一个结点。

本题选D。

方法二：后序遍历

后序遍历序列与后序线索树有对应关系。

图中二叉树后序遍历序列为d, b, c, a，后序线索树中c的前驱为b，后继为a，只有D选项符合要求。

需要注意的是，结点c在后序线索树中的指向结点a的后继指针不能用二叉树原有的指针，因为这里采用的是孩子表示法，原有指针是从a指向c的。

本题选D。

将平衡二叉树（AVL树）调整平衡的方法主要有旋转法和中序遍历法。

旋转法

观察插入不平衡结点的在所在子树上的路径：

• 先经过一个左指针，再经过一个左指针，对应LL平衡旋转。LL平衡旋转为右单旋转。
• 先经过一个右指针，再经过一个右指针，对应RR平衡旋转。RR平衡旋转为左单旋转。
• 先经过一个左指针，再经过一个右指针，对应LR平衡旋转。LR平衡旋转为先左后右双旋转。
• 先经过一个右指针，再经过一个左指针，对应RL平衡旋转。RL平衡旋转为先右后左双旋转。

本题出现RL平衡旋转。先R旋，再L旋。

中序遍历法

下面介绍中序遍历法，标记出插入不平衡结点从所在子树上的根结点到插入结点路径上的3个元素，写出子树的中序遍历序列，先标记3个元素为橙色，再标记3个橙色元素中间元素为红色，红色元素即为子树新的根结点，左边橙色元素为左子树根结点，右边橙色元素为右子树根结点。

在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是24和53。

本题选C。

在一棵树中， 点数边数点数=边数+1 ，设树度为 m ，度为 i 的结点数为 ni ，有 

由题意：

解得： n0=82

本题选B。

哈夫曼树不一定是完全二叉树，A选项错误。

哈夫曼树中只有度为 0 或 2 的结点，一定没有度为 1 的结点，B选项正确。

构造哈夫曼树时，先选出两个权值最小的结点进行构造，所以树中两个权值最小的结点一定是兄弟结点，C选项正确。

用反证法，如果哈夫曼树中某一非叶结点的下一层存在某一结点的权值大于该非叶结点的权值，则可以将两种进行替换使得这棵树的带权路径长度变得更低，由于哈夫曼树是带权路径最小的二叉树，矛盾。D选项正确。

本题选A。

参考答案：C

答案解析：考查图的连通性。

要保证无向图 G 在任何情况下都是连通的，即任意变动图 G 中的边，G 始终保持连通，首先需要 G的任意六个结点构成完全连通子图 G1，需 15 条边，然后再添一条边将第 7 个结点与 G1 连接起来，共需 16 条边。

每次选择入度为 0 的结点剥离并输出。

可以得到 3 个不同的输出序列。

本题选B。

方法一：二叉搜索树

可以画出对应的二叉搜索树。

明显走到最深的下标为 32 或 33 的失败结点，路径长度为 5 ，需要和下标为 1,2,4,8,16 的结点进行比较。

本题选B。

方法二：公式法

若采用折半查找法查找一个顺序表中不存在的元素，最大比较次数为对应二叉搜索树的高度，设结点数为 n ，

二叉搜索树高度为

代入 n=16 ，解得 h=5 。

本题选B。

参考答案：D

答案解析：考查快速排序。

递归次数与各元素的初始排列有关。如果每一次划分后分区比较平衡，则递归次数少，如果划分后分区不平衡，则递归次数多。递归次数与处理顺序无关。

参考答案：A

答案解析：考查各种排序算法的过程。

看第一趟可知仅有 88 被移到最后.

如果是希尔排序，则 12，88，10 应变为 10，12，88。因此排除希尔排序。

如果是归并排序，则应长度为 2 的子序列是有序的，由此可排除归并。

如果是基数排序，则 16，5，10 应变为 10，5，16，由此排除基数。

可以看到，每一趟都有一个元素移到其最终位置，符合冒泡排序特点。

设数组为 A[0:n−1] 。

方法一：使用辅助数组

我们可以利用数组随机访问的性质，使用辅助数组来将每个元素放至正确的位置。遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i−p)modn 的位置，最后将新数组拷贝至原数组即可。

但要注意，C或C++或Java语言中，负数取模的结果小于等于0，例如 (-1) % 3 返回 -1 而不是 2，当 i−p<0 时以对 i−p 模 n 的结果为下标访问数组可能导致数组越界，所以在取模运算前加上一个数组长度 n 。

C代码如下（含测试用例）：

#include <stdio.h>

void rotate(int* a, int n, int p) {
    int newArr[n];
    for (int i = 0; i < n; i++) {
        newArr[(i - p + n) % n] = a[i];
    }
    for (int i = 0; i < n; i++) {
        a[i] = newArr[i];
    }
}

int main() {
    int a[] = {1, 2, 3, 4, 5};
    rotate(a, 5, 2);
    for (int i = 0; i < 5; i++) {
        printf("%d", a[i]);
    }
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

void rotate(vector<int>& a, int p) {
    int n = (int)a.size();
    vector<int> newArr(n);
    for (int i = 0; i < n; ++i) {
        newArr[(i - p + n) % n] = a[i];
    }
    for (int i = 0; i < n; ++i) {
        a[i] = newArr[i];
    }
}

int main() {
    vector<int> a = {1, 2, 3, 4, 5};
    rotate(a, 2);
    for (int i = 0; i < 5; i++) {
        cout << a[i];
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。总共遍历两遍数组。
• 空间复杂度： O(n) 。开辟大小为 n 的辅助数组。

方法二：环状替换

我们从位置0开始，最初令 temp=A[0] 。根据规则，位置 0 的元素会放至 (0−p)modn 的位置，令 x=(0−p)modn ，此时交换 temp 和 A[x] ，完成位置 x 的更新。然后，我们考察位置 x ，并交换 temp 和 A[(x−p)modn] ，从而完成下一个位置的更新。不断进行上述过程，直至回到初始位置 0 。

由于最终回到了起点，故该过程恰好走了整数数量的圈，不妨设为 a 圈；再设该过程总共遍历了 b 个元素。因此，我们有 an=bp ，即 an 一定为 n 和 p 的公倍数。又因为我们在第一次回到起点时就结束，因此 a 要尽可能小，故 an 一定为 n 和 p 的最小公倍数 lcm(n,p) ，其中 lcm 表示最小公倍数。 b=lcm(n,p)/p 。

每轮遍历访问 b=lcm(n,p)/p 个元素，需要 n/b=gcd(n,p) 轮才能遍历所有元素，其中 gcd 表示最大公约数。

C代码如下（含测试用例）：

#include <stdio.h>

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void rotate(int* a, int n, int p) {
    int count = gcd(p, n);
    for (int start = 0; start < count; ++start) {
        int current = start;
        int prev = a[start];
        do {
            int next = (current - p + n) % n;
            swap(&a[next], &prev);
            current = next;
        } while (start != current);
    }
}

int main() {
    int a[] = {1, 2, 3, 4, 5};
    rotate(a, 5, 2);
    for (int i = 0; i < 5; i++) {
        printf("%d", a[i]);
    }
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void rotate(vector<int>& a, int p) {
    int n = (int)a.size();
    int count = gcd(p, n);
    for (int start = 0; start < count; ++start) {
        int current = start;
        int prev = a[start];
        do {
            int next = (current - p + n) % n;
            swap(a[next], prev);
            current = next;
        } while (start != current);
    }
}

int main() {
    vector<int> a = {1, 2, 3, 4, 5};
    rotate(a, 2);
    for (int i = 0; i < 5; i++) {
        cout << a[i];
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。数组中每个元素被遍历一次。
• 空间复杂度： O(1) 。使用常数个辅助变量。

方法三：数组翻转

我们可以先将所有元素翻转，这样尾部的 n−p 个元素就被移至数组头部，然后我们再翻转 A[0:n−p−1] 和 A[n−p:n−1] 即能得到最后的答案。

C代码如下（含测试用例）：

#include <stdio.h>

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void reverse(int* a, int start, int end) {
    while (start < end) {
        swap(&a[start], &a[end]);
        start += 1;
        end -= 1;
    }
}

void rotate(int* a, int n, int p) {
    reverse(a, 0, n - 1);
    reverse(a, 0, n - p - 1);
    reverse(a, n - p, n - 1);
}

int main() {
    int a[] = {1, 2, 3, 4, 5};
    rotate(a, 5, 2);
    for (int i = 0; i < 5; i++) {
        printf("%d", a[i]);
    }
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

void reverse(vector<int>& a, int start, int end) {
    while (start < end) {
        swap(a[start], a[end]);
        start += 1;
        end -= 1;
    }
}

void rotate(vector<int>& a, int p) {
    int n = (int)a.size();
    reverse(a, 0, n - 1);
    reverse(a, 0, n - p - 1);
    reverse(a, n - p, n - 1);
}

int main() {
    vector<int> a = {1, 2, 3, 4, 5};
    rotate(a, 2);
    for (int i = 0; i < 5; i++) {
        cout << a[i];
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。数组中每个元素被交换两次。
• 空间复杂度： O(1) 。使用常数个辅助变量。