一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

1. 将 C++ 代码转化为机器代码的步骤是（ ）。

{{ select(1) }}

• 预处理、编译、链接
• 编辑、编译、运行
• 编译、运行、调试
• 编译、链接、运行

2. 存储一张 $4096 \times 2160$ 像素的 $32$ 位真彩色图片需要的空间最接近（ ）。

{{ select(2) }}

• $24.84$ MB
• $29.70$ MB
• $31.64$ MB
• $33.75$ MB

3. 算式 $(25_8 + 1011_2) \times 2_{16}$ 的结果以十进制表示为（ ）。

{{ select(3) }}

• $50$
• $52$
• $54$
• $64$

4. 某个栈一开始为空，接下来依次执行以下操作：

push(a)
push(b)
pop()
push(c)
push(d)
pop()
pop()
push(e)

则该栈的最小容量至少是（ ）。

{{ select(4) }}

• $2$
• $3$
• $4$
• $5$

5. 链表相比数组的优势在于（ ）。

{{ select(5) }}

• 随机访问速度快
• 插入与删除操作效率高
• 内存连续分配，缓存友好
• 不需要额外存储指针

6. 二叉树的前序遍历为 F,C,A,D,B,E，中序遍历为 A,C,B,D,F,E，则后序遍历序列是（ ）。

{{ select(6) }}

• A,B,C,D,E,F
• A,B,D,C,E,F
• A,C,B,E,D,F
• A,B,C,E,D,F

7. 一张有向图的顶点编号依次为 $1,2,3,4$，邻接矩阵如下，则合法的拓扑排序是（ ）。

[0,1,0,0]
[0,0,1,1]
[0,0,0,1]
[0,0,0,0]

{{ select(7) }}

• 1,2,3,4
• 1,3,2,4
• 1,2,4,3
• 1,3,4,2

8. 后缀表达式 $3\ 4 \times 2\ 5 + -\ 6 \times$ 的值是（ ）。

{{ select(8) }}

• $-30$
• $30$
• $42$
• $-42$

9. 将 $6$ 本不同的书分给 $3$ 人，每人至少 $1$ 本，有（ ）种分法。

{{ select(9) }}

• $540$
• $360$
• $90$
• $120$

10. 当 $x>0$ 时，表达式 (x & (x-1)) == 0 用于判断（ ）。

{{ select(10) }}

• x 是否为偶数
• x 是否为 $2$ 的幂
• x 是否为 $0$
• x 的二进制表示中是否存在两个及以上的 $1$

11. 对 $100$ 个不同的整数进行冒泡排序，最少需要比较（ ）次。

{{ select(11) }}

• $99$
• $4950$
• $100$
• $5050$

12. 函数 f(n) 定义如下：

int f(int n)
{
    if (n == 0) {
        return 1;
    }
    else {
        return n * f(n-2);
    }
}

则 f(6) 的返回值是（ ）。

{{ select(12) }}

• $24$
• $120$
• $720$
• $48$

13. 字符及其出现频率如下：

字符	A	B	C	D
出现频率	$40\%$	$30\%$	$20\%$	$10\%$

则 A 的哈夫曼编码长度是（ ）。

{{ select(13) }}

• $1$
• $2$
• $3$
• $4$

14. 有三个人需要过桥，过桥的时间分别为 $1$ 分钟、$3$ 分钟、$6$ 分钟。这座桥只允许两人同时过桥，两人过桥时，按单人最慢的时间计算。三人只有一盏灯，过桥时必须持有灯。则三人全部过桥最短总时间为（ ）。

{{ select(14) }}

• $9$ 分钟
• $10$ 分钟
• $11$ 分钟
• $12$ 分钟

15. 关于差分数组的性质，下列说法正确的是（ ）。

{{ select(15) }}

• 差分数组是原数组的前缀和。
• 差分数组的第 $i$ 项表示原数组中第 $i$ 项和第 $i-1$ 项的差值。
• 差分数组的第 $i$ 项表示原数组中第 $i$ 项和第 $i+2$ 项的差值。
• 差分数组无法通过前缀和恢复成原数组。

二、阅读程序（判断题正确填T，错误填F；判断题1分，选择题3分，共计37分）

第1篇

#include<iostream>
int main()
{
    int a, b;
    std::cin >> a >> b;
    int s = 0;
    int c = 0;
    while (a > 0 || b > 0)
    {
        int x = a % 10;
        int y = b % 10;
        a /= 10;
        b /= 10;
        if (x + y + c >= 10){
            c = 1;
            s++;
        }
        else {
            c = 0;
        }
    }
    std::cout << s << "\n";
}

16. 当输入为 1 1 时，程序的输出 2。

{{ select(16) }}

• 正确
• 错误

17. 若输入的两个数都是不超过 $99999$ 的正整数，则输出的结果可能大于 $5$。

{{ select(17) }}

• 正确
• 错误

18. 输出的 s 应该永远小于或等于 a 且永远小于或等于 b。

{{ select(18) }}

• 正确
• 错误

19. 当输入为 998244353 31415926 时，则程序的最终输出为（ ）。

{{ select(19) }}

• 1029660279
• 4
• 5
• 966828427

20. 当输入为 307506234 692493766 时，则程序的最终输出为（ ）。

{{ select(20) }}

• 384987532
• 8
• 996998991
• 9

第2篇

#include<iostream>

int main()
{
    int d;
    std::cin >> d;
    char s[1000];
    int size = 0;
    char c;
    while (std::cin >> c){
        while (size > 0 and d > 0){
            char top = s[size - 1];
            if (top < c){
                d--;
                size--;
            }
            else{
                break;
            }
        }
        s[size++] = c;
    }
    while (d > 0){
        d--;
        size--;
    }
    for (int i = 0; i < size; ++i) {
        std::cout << s[i];
    }
}

21. 把 while (size > 0 and d > 0) 改成 while (size >= 0 and d > 0) 后程序功能保持不变。

{{ select(21) }}

• 正确
• 错误

22. 代码 s[size++] = c; 可以修改为 size += 1; s[size] = c;。

{{ select(22) }}

• 正确
• 错误

23. 若循环 while (std::cin >> c) 执行了 $10$ 次，当 d 的输入值超过 $10$ 时，程序会崩溃。

{{ select(23) }}

• 正确
• 错误

24. 当输入为 3 31415926 时，则程序的输出为（ ）。

{{ select(24) }}

• 314
• 926
• 45926
• 11526

25. 记循环 while (std::cin >> c) 执行了 $n$ 次，该程序的时间复杂度为（ ）。

{{ select(25) }}

• $\Theta(n)$
• $\Theta(nd)$
• $\Theta(n\log n)$
• $\Theta(n+d)$

26. 这段程序的功能是移除输入的 $d$ 个字符，使得剩余字符串（ ）。

{{ select(26) }}

• 字典序下最小
• 字典序下最大
• 不同的字符最多
• 下降子序列最长

第3篇

#include<iostream>

int choose[20];
int dfs(int m, int n)
{
    if (m == n) {
        bool flag = true;
        for (int i = 0; i + 1 < n; ++i) {
            if (choose[i] && choose[i+1]) {
                flag = false;
            }
        }
        if (flag) {
            return 1;
        }
        else {
            return 0;
        }
    }
    else {
        choose[m] = true;
        int pick = dfs(m+1, n);
        choose[m] = false;
        int drop = dfs(m+1, n);
        return pick + drop;
    }
}

int fib(int n)
{
    int f[21];
    f[0] = 1;
    f[1] = 2;
    for (int i = 2; i <= n; ++i) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

int main()
{
    int n;
    std::cin >> n;
    std::cout << dfs(0, n) << " ";
    std::cout << fib(n) << "\n";
}

27. 当输入的 $n$ 介于 $0$ 到 $20$ 之间时，dfs(0,n) 的返回值永远等于 fib(n)。

{{ select(27) }}

• 正确
• 错误

28. 程序结束后，choose 数组的元素全部等于 false。

{{ select(28) }}

• 正确
• 错误

29. fib 的时间复杂度是 $\Theta(n)$。

{{ select(29) }}

• 正确
• 错误

30. dfs 的时间复杂度是 $\Theta(n^2)$。

{{ select(30) }}

• 正确
• 错误

31. dfs 函数采用的算法思想是（ ）。

{{ select(31) }}

• 迭代
• 分治
• 枚举
• 动态规划

32. 当输入为 4 时，则程序的最终输出为（ ）。

{{ select(32) }}

• 7 8
• 8 7
• 8 8
• 7 7

33. dfs 函数的主要功能是（ ）。

{{ select(33) }}

• 统计长度为 $n$ 的序列的子段数量
• 统计长度为 $n$ 的序列中不含连续 $1$ 的二进制序列数量
• 统计关于 $n$ 的一些组合数的数量
• 统计所有长度为 $n$ 的二进制序列数量

34. 在 dfs 函数中，choose 数组的主要作用是什么？

{{ select(34) }}

• 没有作用
• 记录当前递归路径的选择状态
• 作为动态规划的记忆表
• 存储用于输出的序列

三、完善程序（单选题，每小题3分，共计33分）

第1题

给定 $n$ 个数字 $a_1,a_2,\dots,a_n$，从 $1$ 到 $n$ 中挑出两个下标 $i$ 与 $j$ 并要求 $i<j$，然后将 $a_i$ 与 $a_j$ 组成一个有序的序对 $(a_i,a_j)$。

请统计，能从序列中挑选出多少种互不相等的数对？数对 $(x,y)$ 与 $(p,q)$ 称之为不相等，是指 $x\neq p$ 或者 $y\neq q$。

#include<iostream>

const int maxn = 100005;
int a[maxn];
int c[maxn];
bool present[maxn];

int main()
{
    int n;
    std::cin >> n;
    int num = 0;
    long long pair = 0;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
        pair += ____①____;
        pair -= c[____②____];
        ____③____ = num;
        if (____④____){
            present[a[i]] = true;
            ____⑤____;
        }
    }
    std::cout << pair << "\n";
}

35. ① 处应填（ ）。

{{ select(35) }}

• num
• i
• a[i]
• 1

36. ② 处应填（ ）。

{{ select(36) }}

• num
• i
• a[i]
• 1

37. ③ 处应填（ ）。

{{ select(37) }}

• c[i]
• c[a[i]]
• a[i]
• a[c[i]]

38. ④ 处应填（ ）。

{{ select(38) }}

• present[a[i]]
• present[c[i]]
• !present[c[i]]
• !present[a[i]]

39. ⑤ 处应填（ ）。

{{ select(39) }}

• num+=c[i]
• num+=a[i]
• present[c[i]] = true
• num++

第2题

给定一个网格，该网格由 $n\times m$ 个方格组成，每个方格内有一个正整数，其中第 $i$ 行第 $j$ 列的整数为 $a_{i,j}$。我们可以使用任意多块 $1\times 2$ 的骨牌覆盖网格上的数字，每块骨牌不得重叠，也不能越过网格的边界。被骨牌覆盖的数字就消失了。请问应该如何摆放骨牌，使得没有消失的数字的异或之和达到最大。所谓异或，就是 C++ 的 ^ 操作。注意不覆盖任何骨牌也是一种选择。

#include<iostream>

int a[20][20];
bool covered[20][20];
int n, m;

int solve(int x, int y, int sum)
{
    if (y == m) {
        return ____②____;
    }
    if (____③____) {
        return sum;
    }
    int D = 0;
    if ( covered[x][y] )
        D = solve(x, y+1, sum);
    else
        D = ____④____;
    int V = 0;
    int H = 0;
    if (!covered[x][y] && y+1 < m && !covered[x][y+1])
    {
        covered[x][y] = covered[x][y+1] = true;
        V = ____⑤____;
        covered[x][y] = covered[x][y+1] = false;
    }
    if (!covered[x][y] && x+1 < n)
    {
        covered[x][y] = covered[x+1][y] = true;
        H = ____⑥____;
        covered[x][y] = covered[x+1][y] = false;
    }
    return std::max(D, std::max(H, V));
}

int main(){
    std::cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
        }
    }
    std::cout << ____①____ << "\n";
}

40. ① 处应填（ ）。

{{ select(40) }}

• solve(0, 0, 0)
• solve(0, 0, 1)
• solve(1, 1, 0)
• solve(1, 1, 1)

41. ② 处应填（ ）。

{{ select(41) }}

• solve(x+1, 0, sum)
• solve(x+1, y, sum)
• solve(x, y+1, sum)
• solve(x+1, y+1, sum)

42. ③ 处应填（ ）。

{{ select(42) }}

• x > n
• x == n
• x == n - 1
• x < n

43. ④ 处应填（ ）。

{{ select(43) }}

• solve(x, y+1, sum ^ a[x][y])
• solve(x+1, y, sum ^ a[x][y])
• solve(x, y+1, a[x][y])
• solve(x+1, y, sum)

44. ⑤ 处应填（ ）。

{{ select(44) }}

• solve(x, y+1, sum ^ a[x][y])
• solve(x+1, y, sum ^ a[x][y])
• solve(x, y+1, sum)
• solve(x+1, y, sum)

45. ⑥ 处应填（ ）。

{{ select(45) }}

• solve(x, y+1, sum ^ a[x][y])
• solve(x+1, y, sum ^ a[x][y])
• solve(x, y+1, sum)
• solve(x+1, y, sum)