---

1. 表达式 $\mathrm{a}*(b + c) - d / f$ 转后缀表达式的结果是（）。 {{ select(1) }}

• $abc*+df-/$
• $abc+*df/-$
• $bc+a*df/-$
• $abc+x-df/$

---

2. 以下字符串中，字典序最小的是（）。 {{ select(2) }}

• NOIP2017
• NOIPC
• NOIPC++
• NOIPP

---

3. 在 $\mathrm{C++}$ 中，表达式 $0 \sim 1 \sim 1 \sim 1 \sim 3 \% 9 + 5$ 的值是（）。 {{ select(3) }}

• 7
• 8
• 14
• 15

---

4. 已知数组A中，每个元素 $A[i,j]$ 在存储时要占3字节，设 $i$ 从1变化到8，$j$ 从1变化到10，分配内存时是从地址 $SA$ 开始连续按行存储分配的。$A[5,8]$ 的起始地址为（）。 {{ select(4) }}

• $SA+141$
• $SA+180$
• $SA+222$
• $SA+225$

---

5. 在TCP/IP协议族中，最核心的网络协议是（）。 {{ select(5) }}

• UDP
• HTTP
• TCP
• IP

---

6. 应用快速排序的分治思想可以实现一个求第 $K$ 大数的程序。假定不考虑极端的最坏情况，在平均情况下算法的期望时间复杂度为（）。 {{ select(6) }}

• $O(n^{2})$
• $O(\log n)$
• $O(n)$
• $O(n\log n)$

---

7. 为解决计算机主机与外设之间速度不匹配的问题，通常会设置一个缓冲池。主机将输出数据依次写入该缓冲池，而外设从该缓冲池中依次取出数据。该缓冲池应该是一个（）结构。 {{ select(7) }}

• 栈
• 队列
• 二叉树
• 链表

---

8. $(1\mathrm{E}34)_{16} - (676)_{8}$ 的结果是（）。 {{ select(8) }}

• $(11100011111110)_{2}$
• $(7276)_{10}$
• $(1\mathrm{C6C})_{16}$
• $(16166)_{8}$

---

9. 一棵二叉树的前序遍历序列为 $ABDECFGH$，后序遍历序列为 $EDBGFHCA$。下列选项中，（）不是可能的中序遍历序列。 {{ select(9) }}

• $DEBAFGCH$
• $EDBAGFCH$
• $DBEAFGCH$
• $BEDAFGCH$

---

10. 一个栈的输入序列为 $12345$，下列序列中，（）不可能是栈的输出序列。 {{ select(10) }}

• $54321$
• $24135$
• $32541$
• $13542$

---

11. Linux是一个用C语言写成的开源计算机操作系统内核，有大量的操作系统是基于Linux内核创建的。以下操作系统中，（）使用的不是Linux内核。 {{ select(11) }}

• Android
• CentOS
• Windows
• Ubuntu

---

12. 下列关于计算机算法的说法中，正确的是（）。 {{ select(12) }}

• 对于一个问题，我们能通过优化算法，不断降低算法复杂度
• 判断一个算法的好坏，主要依据它在某台计算机上具体实现时的运行时间
• 一个算法必须至少有一个输入
• 算法复杂度理论中，$P = NP$ 问题（NP完全问题）仍是一个未解之谜

---

13. 以下关于二叉树性质的描述中，正确的是（）。 {{ select(13) }}

• 在任意非空二叉树中，若叶节点的个数为 $n_0$，度为2的节点数为 $n_2$，则 $n_0 = n_2 + 1$
• 深度为 $k$ 的二叉树至多有 $2^k$ 个节点
• 没有一棵二叉树的前序遍历序列与后序遍历序列相同
• 具有 $n$ 个节点的完全二叉树的深度为 $\lfloor \log_2(n + 1) \rfloor$

---

14. 排序算法是稳定的，这句话的意思是，排序前后，关键码相同的记录的相对位置不发生改变。以下排序算法不稳定的是（）。 {{ select(14) }}

• 插入排序
• 快速排序
• 冒泡排序
• 归并排序

---

15. 给定 $m$ 种颜色和有 $n$ 个点的手环，要求用这 $m$ 种颜色给这条手环着色。若两种着色方案可通过旋转或翻转相互得到，则视为同一种着色方案，如对于有3个点的手环，ABC的着色方案与BCA（旋转）、ACB（翻转）视为同一种方案。当 $m = 2$ 且 $n = 2$ 时，一共有3种着色方案，分别为AA、AB、BB。那么当 $m = 5$ 且 $n = 4$ 时，一共有（）种着色方案。 {{ select(15) }}

• 625
• 160
• 60
• 120

---

阅读程序（1）：

#include <iostream>
using namespace std;
unsigned short tot;
void Hanoi(int n, char A, char B, char C) {
    ++tot;
    if (n == 1) {
        cout << A << "->" << C << "//";
        return;
    }
    Hanoi(n - 1, A, C, B);
    cout << A << "->" << C << "//";
    Hanoi(n - 1, B, A, C);
}
int main() {
    int n;
    cin >> n;
    Hanoi(n, 'A', 'B', 'C');
    cout << '\n' << tot << '\n' << tot << '\n';
    return 0;
}

16. 将 ++tot 移到 Hanoi() 函数返回之前的最后一行，输出结果不会发生变化。 {{ select(16) }}

• 正确
• 错误

---

17. 输入的 $n = 2$ 时，输出的第一行为 $A \rightarrow B / B \rightarrow C / A \rightarrow C /$。 {{ select(17) }}

• 正确
• 错误

---

18. 输入的 $n = 3$ 时，输出的第二行为8。 {{ select(18) }}

• 正确
• 错误

---

19. 本程序的含义可以是：有三根柱子，第一根柱子从上到下依次套有编号为 $1 \sim n$ 的圆环，现在每次可以移动某根柱子顶部的圆环到另一根柱子的顶部，并要求编号较大的圆环始终不能在编号较小的上面，输出一种操作次数最少的方案以及对应的操作次数。 {{ select(19) }}

• 正确
• 错误

---

阅读程序（2）：

#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;
const int N = 105;
int a[N][N];
int main() {
    int n, x, y, count;
    cin >> n;
    memset(a, 0, sizeof(a));
    count = a[x = 0][y = n - 1] = 1;
    while (count < n * n) {
        while (x + 1 < n && !a[x + 1][y]) a[++x][y] = ++count;
        while (y - 1 >= 0 && !a[x][y - 1]) a[x][--y] = ++count;
        while (x - 1 >= 0 && !a[x - 1][y]) a[--x][y] = ++count;
        while (y + 1 < n && !a[x][y + 1]) a[x][++y] = ++count;
    }
    for (x = 0; x < n; x++) {
        for (y = 0; y < n; y++) {
            cout << setw(5) << a[x][y];
        }
        cout << endl;
    }
    return 0;
}

20. 删除 memset(a, 0, sizeof(a)); 不影响程序运行结果。 {{ select(20) }}

• 正确
• 错误

---

21. 将 while (count < n * n) 改为 while (count <= n * n)，不影响程序运行结果。 {{ select(21) }}

• 正确
• 错误

---

22. 输入的 $n = 4$ 时，程序输出的 $a[3][2]$ 的值为15。 {{ select(22) }}

• 正确
• 错误

---

23. （4分）本程序的时间复杂度为（ {{ select(23) }}

• $O(n)$
• $O(n^2)$
• $O(n^3)$
• $O(n^2\log n)$

---

24. （4分）输入的 $n = 100$ 时，$a[33][66]$ 的值为（ {{ select(24) }}

• 8779
• 8707
• 10957
• 8845

---

阅读程序（3）：

#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
string s;
int main() {
    int k; // 保证输入 0 <= k < 26
    cin >> k >> s;
    int n = s.length();
    for (int i = 0; i < n; i++) {
        if (s[i] <= 'Z' && s[i] + k > 'Z')
            s[i] = (s[i] + k) % 'Z' + 'A' - 1;
        else if ('A' <= s[i] && s[i] <= 'Z')
            s[i] += k;
    }
    char pre;
    int st = -1;
    for (int i = 0; i < n; i++) {
        if (s[i] < 'A' || s[i] > 'Z') {
            if (st == -1) {
                st = i;
                pre = s[i];
            } else {
                char tmp = s[i];
                s[i] = pre;
                pre = tmp;
            }
        }
    }
    if (st != -1) s[st] = pre;
    cout << s << endl;
    return 0;
}

25. 删除 if (st != -1) s[st] = pre;，不影响程序运行结果。 {{ select(25) }}

• 正确
• 错误

---

26. 如果输入的 s 不含大写字母，则输出结果与 k 的值无关。 {{ select(26) }}

• 正确
• 错误

---

27. 如果知道输出结果，能够反推出唯一的输入。 {{ select(27) }}

• 正确
• 错误

---

28. 当 k 的值确定时，不存在两个不同的输入使得输出相同。 {{ select(28) }}

• 正确
• 错误

---

29. 如果输入是 6 KU96APY5，则输出为（）。 {{ select(29) }}

• QB96GWE5
• QA59GVE6
• PA59GWF6
• PB96GWE5

---

30. 如果输出是 ab1287F2Tguz，则输入可能为（）。 {{ select(30) }}

• 0 ab1287F2Tguz
• 3 b1287BgTuza
• 16 b1287ZPpDuza
• 13 b12872MgAuza

---

完善程序（1）：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 105;
int a[N][N];
int in[N], s[N];
int n, m, u, v;
void Topo() {
    queue<int> q;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (①) q.push(i);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        s[cnt++] = ②;
        for (int i = 1; i <= n; i++) {
            if (③) {
                ④;
                if (in[i] == 0) q.push(i);
            }
        }
    }
}
int main() {
    memset(in, 0, sizeof(in));
    memset(a, 0, sizeof(a));
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        in[v]++;
        ⑤;
    }
    Topo();
    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        cout << s[i];
    }
    cout << endl;
    return 0;
}

31. ①处应填（ {{ select(31) }}

• in[i] == 0
• in[i] == 1
• a[1][u] == 0
• a[1][u] == 1

---

32. ②处应填（ {{ select(32) }}

• q.front()
• cur
• q.back()
• s[cur]

---

33. ③处应填（ {{ select(33) }}

• --in[i]
• a[u][v] == 1
• a[cur][i] == 1
• !in[i]

---

34. ④处应填（ {{ select(34) }}

• in[i]++
• in[i]--
• q.pop()
• q.push(cur)

---

35. ⑤处应填（ {{ select(35) }}

• in[u]++
• in[u]--
• a[u][v] == 1
• a[v][u] == 1

---

完善程序（2）：

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

bool Place(int k, int i, int *x) {
    for (int j = 0; j < k; j++)
        if (x[j] == i || ①)
            return false;
    return true;
}

void NQueens(int k, int n, int *x) {
    for (int i = 0; i < n; i++)
        if (Place(k, i, x)) {
            ②;
            if (③) {
                for (int j = 0; j < n; j++)
                    cout << x[j] << " ";
                cout << endl;
            } else {
                ④;
            }
        }
}

int main() {
    int x[8];
    for (int i = 0; i < 8; i++) x[i] = -1;
    ⑤;
    return 0;
}

36. ①处应填（ {{ select(36) }}

• x[j] == i - 1
• abs(x[j] - i) <= 1
• abs(x[j] - k) == i - j
• abs(x[j] - i) == k - j

---

37. ②处应填（ {{ select(37) }}

• x[i] = k
• x[k] = n - i
• x[k] = i
• x[i] = x[k]

---

38. ③处应填（ {{ select(38) }}

• k > n - 1
• k >= n - 1
• k == n
• k > n

---

39. ④处应填（ {{ select(39) }}

• NQueens(k, n - 1, x)
• NQueens(k + 1, n, x)
• NQueens(k + 1, n - 1, x)
• cout << x[k] << " "

---

40. ⑤处应填（ {{ select(40) }}

• NQueens(1, 8, x)
• NQueens(0, 7, x + 1)
• NQueens(0, 8, x)
• NQueens(1, 8, x + 1)

---