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

1. $32$ 位无符号位 int 类型的存储范围是（ ）。

{{ select(1) }}

• $0 \sim 4294967295$
• $-2147483648 \sim 2147483647$
• $0 \sim 4294967296$
• $0 \sim 65535$

2. 以下判断一个正整数 n 是否是偶数的代码中，错误的是（ ）。

{{ select(2) }}

• if (n % 2 == 0)
• if (!(n % 2))
• if (n & 1)
• if (n % 2 != 1)

3. 在 C++ 中，5 ^ -5 和 5 & -5 的值分别为（ ）。

{{ select(3) }}

• $-2, 1$
• $2, -1$
• $-2, -1$
• $2, 1$

4. 一棵哈夫曼树，拥有 $13$ 个叶结点。则该哈夫曼树的结点总数为（ ）。

{{ select(4) }}

• $25$
• $26$
• $27$
• 无法确定

5. 下列关于树的描述中正确的是（ ）。

{{ select(5) }}

• 有 $n$ 个结点的树，边数只能是 $n-1$ 条。
• 在哈夫曼树中，叶子结点的比非叶子结点多 $1$ 或 $2$ 个。
• 完全二叉树是二叉排序树。
• 在二叉树的后序遍历序列中，若结点 $u$ 在结点 $v$ 之前，则 $u$ 一定是 $v$ 的祖先

6. 下面代码构成的是（ ）类型的数据结构。

struct Node
{
    int value;
    Node* link;
};
Node* add(Node* node, int value)
{
    Node* new_node = new Node;
    new_node->link = node;
    new_node->value = value;
    return new_node;
}
Node* del(Node* node)
{
    Node* new_node = node->link;
    delete node;
    return new_node;
}
int main()
{
    Node* head = add(nullptr, 1);
    head = add(head, 2);
    head = del(head);
}

{{ select(6) }}

• 双向链表
• 栈
• 循环链表
• 队列

7. 以下代码调用 F(n) 的时间复杂度为（ ）。

int F(int n)
{
    if (n <= 2)
        return 1;
    else
        return F(n-1) + F(n-2);
}

{{ select(7) }}

• $\Theta(1)$
• $\Theta(n)$
• $\Theta(n^2)$
• $\Theta(2^n)$

8. 在简单图中，有 $n$ 个顶点的强连通图最少有（ ）条边，最多有（ ）条边。

{{ select(8) }}

• $n-1, n$
• $n-1, n(n-1)$
• $n, n(n-1)$
• $n, n(n-1)/2$

9. 以下关于强连通图的说法中，正确的是（ ）。

{{ select(9) }}

• 图中一定有环
• 每个顶点的度数都大于 $0$
• 对于大于 $1$ 个点的强连通图，任意两个顶点之间都有路径相连
• 每个顶点至少都连有一条边

10. 用线性探测法把 $k$ 个关键字相同但内容不同的数据存入哈希表中，至少要进行（ ）次探测。

{{ select(10) }}

• $k+1$
• $k-1$
• $(k+1)\cdot k/2$
• $(k-1)\cdot k/2$

11. 求 a,b,c,d,e,f 六个字母的全排列中不允许出现 ace 和 df 子串的排列数（ ）。

{{ select(11) }}

• $177$
• $377$
• $477$
• $582$

12. 一堆卡片共 $2025$ 张，设定一个数量，不断从牌堆中取该数量的牌，记 $A$ 表示该数量为素数的方案数，记 $B$ 为该数量为奇数的方案数。则 $A+B=$（ ）。

{{ select(12) }}

• $16$
• $17$
• $18$
• $19$

13. 若存在正整数 $k(1 \le k \le n-1)$ 使得 $C(n,k-1)$、$C(n,k)$、$C(n,k+1)$ 构成等差数列（其中 $C(n,k)$ 为组合数，且 $C(n,k)=\frac{n!}{k!(n-k)!}$），则不超过 $2025$ 的质数个数为（ ）。

{{ select(13) }}

• $14$
• $15$
• $22$
• $43$

14. 已知一棵二叉树有 $2025$ 个结点，则其中至多有（ ）个结点有 $2$ 个子结点。

{{ select(14) }}

• $1010$
• $1011$
• $1012$
• $1013$

15. 从乘法算式 $1 \times 2 \times 3 \times 4 \times \cdots \times 24 \times 25$ 中，最少要删掉（ ）个数才能使剩下的数的乘积是完全平方数。共有（ ）种不同的删除方法。

{{ select(15) }}

• $3, 1$
• $3, 2$
• $5, 2$
• $5, 1$

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

第1题

int solve(int n, int a[], int b[])
{
    std::sort(a, a + n);
    std::sort(b, b + n);
    int ans = std::max(a[0] - b[0], b[0] - a[0]);
    int i = 0;
    int j = 0;
    while (i < n && j < n)
    {
        if (a[i] < b[j])
        {
            int diff = b[j] - a[i];
            if (ans > diff)
                ans = diff;
            i++;
        }
        else
        {
            int diff = a[i] - b[j];
            if (ans > diff)
                ans = diff;
            j++;
        }
    }
    return ans;
}

判断题

16. 当 a[0] == b[0] 时，程序返回 0。（ ）。

{{ select(16) }}

• 正确
• 错误

17. 若程序在运行时，跳过了数组 a 或 b 的排序步骤，程序会进入死循环。（ ）。

{{ select(17) }}

• 正确
• 错误

18. 当输入数据出现负数时，程序可能返回负数（ ）。

{{ select(18) }}

• 正确
• 错误

选择题

19. 若 n=3，a=[5, 1, 12]，b=[7, 9, 4]，程序的输出结果是（ ）。

{{ select(19) }}

• 1
• 2
• 3
• 4

20. 程序返回的是（ ）。

{{ select(20) }}

• 数组 a 中的元素与数组 b 中的元素的最大差值
• 数组 a 中的元素与数组 b 中的元素的最小差值
• 数组 a 的最大值与数组 b 最小值的差
• 数组 b 的最大值与数组 a 最小值的差

21. 该程序的时间复杂度为（ ）。

{{ select(21) }}

• $\Theta(n^2)$
• $\Theta(n\log n)$
• $\Theta(n)$
• $\Theta(\log^2 n)$

第2题

int solve(int n, int a[])
{
    int ret = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            int sum = 0;
            for (int k = j; k <= i; ++k)
            {
                sum += a[k];
            }
            ret += sum;
        }
    }
    return ret;
}

判断题

22. 若在进入 solve 函数执行其他操作之前，先对 a[] 排序，返回值不变（ ）。

{{ select(22) }}

• 正确
• 错误

23. 当 $n=1$ 时，函数返回值为 a[0]（ ）。

{{ select(23) }}

• 正确
• 错误

24. 若数组 a[] 中所有元素均为 $0$，则当 $n$ 取 $1$ 到 $100$ 之间的整数时，函数一定返回 $0$（ ）。

{{ select(24) }}

• 正确
• 错误

选择题

25. 若 n = 10 且 a = {1, 1, ..., 1}，程序的返回值是（ ）。

{{ select(25) }}

• $10$
• $100$
• $165$
• $210$

26. 若 n = 5，且 a = {3, 1, 4, 1, 5}，则程序返回（ ）。

{{ select(26) }}

• $14$
• $75$
• $78$
• $80$

27. 该程序的时间复杂度为（ ）。

{{ select(27) }}

• $\Theta(n)$
• $\Theta(n^2)$
• $\Theta(n^2 \cdot \log n)$
• $\Theta(n^3)$

28. 改进 solve 函数，最佳改进算法的时间复杂度为（ ）。

{{ select(28) }}

• $\Theta(n)$
• $\Theta(n^2)$
• $\Theta(n^2 \cdot \log n)$
• $\Theta(n^3)$

第三题

using std::string;

string post(const string& pre, const string& in)
{
    if (pre == "") return "";
    char root = pre[0];

    int i = 0;
    while (root != in[i]) ++i;

    string left_in = in.substr(0, i);
    string right_in = in.substr(i+1);

    string left_pre = pre.substr(1, i);
    string right_pre = pre.substr(i+1);

    string left_post = post(left_pre, left_in);
    string right_post = post(right_pre, right_in);

    return left_post + right_post + root;
}

判断题

29. 去掉参数 pre 的 const 修饰符，程序会发生编译错误（ ）。

{{ select(29) }}

• 正确
• 错误

30. 去掉参数 pre 的 &，程序会发生编译错误（ ）。

{{ select(30) }}

• 正确
• 错误

31. 当参数 pre 中出现参数 in 所没有的字符时，程序会发生运行时错误（ ）。

{{ select(31) }}

• 正确
• 错误

32. 当程序正常运行时，post 函数返回的字符串与参数 pre 等长（ ）。

{{ select(32) }}

• 正确
• 错误

选择题

33. 当输入 pre = "ABDEC"，in = "DBEAC"，函数返回（ ）。

{{ select(33) }}

• ABDEC
• DBECA
• DEBCA
• DBEAC

34. 当输入 pre = "*+12-34"，in = "1+2*3-4"，函数返回（ ）。

{{ select(34) }}

• 1234+-*
• 43-21+*
• 4-3*2+1
• 12+34-*

35. 当输入 pre = "12345"，in = "54321" 时，函数返回（ ）。

{{ select(35) }}

• 53241
• 54321
• 12345
• 45321

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

第1题

给定 $n$ 根火柴的长度 $a_1,a_2,\cdots,a_n$，请用这些火柴围成一个面积最大的三角形。注意所有的火柴都必须用上，不得丢弃。输出最大三角形的面积。假设最大面积为 $s$，则输出 $16s^2$。$1 \le a_i \le 40$，数据保证至少有一种方案可以围成三角形。

#include<iostream>
using i64 = long long;
int n;
int a[40];
bool mem[40][40*40][40*40];
i64 value[40][40*40][40*40];

i64 solve(int i, int x, int y, int z)
{
    if (i < n)
    {
        if (mem ____(1)____ > 0)
            return value ____(2)____;
        i64 s1 = solve(i+1, x + a[i], y, z);
        i64 s2 = solve(i+1, x, y + a[i], z);
        i64 s3 = solve(i+1, x, y, z + a[i]);
        mem[i][x][y] = true;
        return value[i][x][y] = ____(3)____;
    }
    else
    {
        if ( ____(4)____ ) return 0;
        i64 p = ____(5)____ ;
        return ____(6)____ ;
    }
}

int solve()
{
    std::cin >> n;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> a[i];
    }
    std::cout << solve(0, 0, 0, 0);
}

36. (1)(2) 处应填（ ）。

{{ select(36) }}

• [i][x][y],[i][x][y]
• [i][x][y],[x][y][z]
• [x][y][z],[i][x][y]
• [x][y][z],[x][y][z]

37. (3) 处应填（ ）。

{{ select(37) }}

• s1 + s2 + s3
• *std::max_element({s1, s2, s3}.begin(), {s1, s2, s3}.end())
• std::max(std::max(s1, s2), std::max(s3, z))
• std::max(std::max(s1, s2), s3)

38. (4) 处应填（ ）。

{{ select(38) }}

• x + y <= z && x + z <= y && y + z <= x
• x + y <= z || x + z <= y || y + z <= x
• x + y > z || x + z > y || y + z > x
• x + y >= z && x + z >= y && y + z >= x

39. (5) 处应填（ ）。

{{ select(39) }}

• x * y * z
• x + y + z
• (x * y) / 2
• (x + y + z) / 2

40. (6) 处应填（ ）。

{{ select(40) }}

• p * (p - 2 * x) * (p - 2 * y)
• (p / 2) * (p / 2 - x) * (p / 2 - y) * (p / 2 - z)
• p * (p - 2 * x) * (p - 2 * y) * (p - 2 * z)
• p + (p - 2 * x) + (p - 2 * y) + (p - 2 * z)

第2题

给定一个 $N \times M$ 的迷宫网格（含不可通行的 #、可通行的 .、双向必传送且耗时 $0$ 的滑梯对（大写字母）、出口 = 和起点 @），从起点出发，移动相邻草地耗时 $1$，传送耗时 $0$。计算从起点到达出口所需的最短时间。

#include<iostream>
char a[1000][1000];
int d[1000][1000];
int n, m;
int qx[1000*1000];
int qy[1000*1000];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int sumx[26];
int sumy[26];
void bfs(int x, int y) {
    qx[0] = x;
    qy[0] = y;
    d[x][y] = 1;
    int head = 0;
    int tail = 1;
    while (head < tail) {
        int x = qx[____(1)____];
        int y = qy[____(2)____];
        ____(3)____++;
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (____(4)____) {
                if (____(5)____) continue;

                if ('A' <= a[nx][ny] and a[nx][ny] <= 'Z') {
                    char c = a[nx][ny];
                    nx = ____(6)____ ;
                    ny = ____(7)____ ;
                }

                if ( ____(8)____ ) {
                    d[nx][ny] = ____(9)____ ;
                    qx[tail] = nx;
                    qy[tail] = ny;
                    tail++;
                }
            }
        }
    }
}

int main()
{
    std::cin >> n >> m;
    int sx, sy, tx, ty;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
            if (a[i][j] == '@') {sx = i; sy = j;}
            if (a[i][j] == '=') {tx = i; ty = j;}
            if ('A' <= a[i][j] and a[i][j] <= 'Z') {
                sumx[a[i][j] - 'A'] += i;
                sumy[a[i][j] - 'A'] += j;
            }
        }
    bfs(sx, sy);
    std::cout << ____(10)____ << "\n";
}

41. (1)(2)(3) 处应填（ ）。

{{ select(41) }}

• head,head,head
• head,head,tail
• tail,tail,head
• tail,tail,tail

42. (4)(5) 处应填（ ）。

{{ select(42) }}

• 0 <= nx or nx < n or 0 <= ny or ny < m, a[nx][ny] == '#'
• 0 <= nx and nx < n and 0 <= ny and ny < m, a[nx][ny] != '#'
• 0 <= nx or nx < n or 0 <= ny or ny < m, a[nx][ny] != '#'
• 0 <= nx and nx < n and 0 <= ny and ny < m, a[nx][ny] == '#'

43. (6)(7) 处应填（ ）。

{{ select(43) }}

• sumx[c-'A'] + nx,sumy[c-'A'] + ny
• nx - sumx[c-'A'], ny - sumy[c-'A']
• sumx[c-'A'], sumy[c-'A']
• sumx[c-'A'] - nx,sumy[c-'A'] - ny

44. (8)(9) 处应填（ ）。

{{ select(44) }}

• d[nx][ny] == 0, d[x][y]
• d[nx][ny] == 0, d[x][y] + 1
• d[nx][ny] != 0, d[x][y] + 1
• d[nx][ny] != 0, d[x][y] - 1

45. (10) 处应填（ ）。

{{ select(45) }}

• sumx[tx] + sumy[ty]
• d[tx][ty]
• d[tx][ty] - 1
• d[tx][ty] + 1