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

1. 在 C++ 中，表达式 (-97 % 13) + 0b110101 - 0xCE 的值与下列哪个表达式的值不同（ ）。

{{ select(1) }}

• (-97 % -13) + 0b110101 - 0xCE
• (-6 % 7) + 0x35 - 0316
• (-6 % 7) + 0b110101 - 0xCE
• (-97 % 13) + 0b110101 - 0xCD

2. 为了统计一个非负整数的二进制形式中 $1$ 的个数，代码如下，则空格内应填入的语句是（ ）。

int count(int x)
{
    if (x == 0)
        return 0;
    else
        return 1 + count(_____);
}

{{ select(2) }}

• x - 1
• x & (x - 1)
• x >> 1
• x << 1

3. 逻辑异或（$\oplus$）是一种二元运算，其真值表为 $1\oplus0=0\oplus1=1$，$1\oplus1=0\oplus0=0$。以下关于逻辑异或的性质，正确的是（ ）。

{{ select(3) }}

• 支配律：$a\oplus1=1$
• 结合律：$(a\oplus b)\oplus c=a\oplus(b\oplus c)$
• 关于逻辑与的分配律：$a\oplus(b\land c)=(a\oplus b)\land(a\oplus c)$
• 关于逻辑或的分配律：$a\oplus(b\lor c)=(a\oplus b)\lor(a\oplus c)$

4. 现有 5 样商品，每样数量为 1，重量分别为 $6,5,4,3,7$，对应价值分别为 $12,11,9,7,13$。背包容量为 20，装入背包的物品能获得的最大总价值是（ ）。

{{ select(4) }}

• $43$
• $41$
• $40$
• $38$

5. 从 5 个红球和 4 个白球中任取 3 个球，则至少有一个红球的取法数为（ ）。

{{ select(5) }}

• $84$
• $80$
• $75$
• $70$

6. 已知 $f[0]=1$，$f[1]=2$，并且对于所有 $n\ge2$ 有 $f[n]=(2\times f[n-1]+f[n-2])\bmod7$，那么 $f[2026]$ 的值是（ ）。

{{ select(6) }}

• $0$
• $1$
• $2$
• $5$

7. 对图 $G$ 中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图 $G$ 的一个正常着色。正常着色图 $G$ 所必需的最少颜色数称为 $G$ 的色数。那么下图的色数是（ ）。

{{ select(7) }}

• $3$
• $4$
• $5$
• $6$

8. 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有 5 个顶点、8 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。

{{ select(8) }}

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

9. 二叉树 $T$ 的广度优先遍历序列为 A、B、C、D、E、F、G、H、I，已知 A 是 C 的父结点，D 是 G 的父结点，F 是 I 的父结点，树中所有结点的最大深度为 3，根结点的深度为 0，可知 E 的父结点可能是（ ）。

{{ select(9) }}

• A、B
• B、C
• A、B、F
• B、C、E

10. 已知字符集 a、b、c、d、e、f、g、h。若各字符的哈夫曼编码依次是 0100、10、0000、0101、001、011、11、0001，则编码序列 0100011001001011110101 的译码结果是（ ）。

{{ select(10) }}

• acgabfh
• adbagbb
• afbeagd
• afeefgd

11. 已知网格上每个格子有一个数字，a[i][j] 表示第 $i$ 行第 $j$ 列格子上的数字。若 dp[i][j] 表示从网格左上角 $(0,0)$ 走到第 $i$ 行第 $j$ 列时能取得的最小数字和，且每次只能向右或向下移动。对于 $i>0$ 且 $j>0$ 的位置，正确的状态转移代码为（ ）。

{{ select(11) }}

• dp[i][j] = a[i][j] + min(dp[i-1][j], dp[i][j-1]);
• dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i][j-1]);
• dp[i][j] = min(dp[i-1][j], dp[i][j-1]);
• dp[i][j] = a[i][j] + dp[i-1][j-1];

12. 给定正整数 $N=9754832160$，现需要删除其中 6 个数字。每次删除一个数字，并保证每次删除的都是当前状态下的最小数，则第四次应该删除的数字是（ ）。

{{ select(12) }}

• $3$
• $4$
• $6$
• $8$

13. 已知 p 为 int 类型，q 为 int * 类型，下列不符合语法的是（ ）。

{{ select(13) }}

• *q = p;
• p = *q;
• *(p + q) = p;
• *(p + q) = q;

14. 对于一棵二叉树，独立集是指两两互不相邻的结点构成的集合。例如，图1有5个不同的独立集（1个双点集合、3个单点集合、1个空集），图2有14个不同的独立集。那么，图3有（ ）个不同的独立集。

{{ select(14) }}

• $3280$
• $5536$
• $6560$
• $6866$

15. 下列关于无向连通图特性的叙述中，正确的是（ ）。

I. 所有顶点的度之和为偶数
II. 边数大于顶点个数
III. 至少有一个顶点的度为 1

{{ select(15) }}

• 只有 I
• 只有 II
• I 和 II
• I 和 III

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

第1题

int solve(int n, int a[], int b[])
{
    std::sort(a, a + n);
    std::sort(b, b + n);

    int ans = std::abs(a[0] - b[0]);
    int i = 0, 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. 当存在一组 $i$ 与 $j$ 满足 a[i] = b[j] 时，程序返回 0（ ）。

{{ select(16) }}

• 正确
• 错误

17. 当存在一组 $i\ne j$ 满足 a[i] = a[j] 时，程序返回 0（ ）。

{{ 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)$

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

第2题

using i64 = long long;
i64 solve(i64 n)
{
    i64 c = 0;
    i64 p = 1;
    i64 t = 0;
    while (n > 0)
    {
        int d = n % 10;
        n /= 10;
        if (d > 0)
        {
            c += n * p;
        }
        else
        {
            c += (n - 1) * p;
            c += t + 1;
        }
        t += d * p;
        p *= 10;
    }
    return c;
}

22. 运行过程中，t 与 c 两个变量将会越来越大（ ）。

{{ select(22) }}

• 正确
• 错误

23. 若将程序中所有的 10 改成 8，程序的返回值不会变大（ ）。

{{ select(23) }}

• 正确
• 错误

24. 程序的时间复杂度是 $\Theta(\log n)$（ ）。

{{ select(24) }}

• 正确
• 错误

25. 当 $n=2026$ 时，程序返回（ ）。

{{ select(25) }}

• $509$
• $510$
• $529$
• $531$

26. 当 $n=31415$ 时，程序返回（ ）。

{{ select(26) }}

• $12379$
• $12380$
• $12381$
• $12382$

27. solve(n) 函数的功能是（ ）。

{{ select(27) }}

• 统计 $n$ 的十进制表示中数字 0 的数量
• 统计 1 到 $n$ 的所有正整数中“出现过 0 的整数数量”
• 统计 1 到 $n$ 的所有正整数的十进制表示中数字 0 出现的总次数
• 统计 1 到 $n$ 的所有正整数的十进制表示中数字 0 出现的总次数，并将位数短于 $n$ 的数在左侧补 0 后计入这些 0

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

第3题

int A[1024];
int cache[1024];

int build(int begin, int end, int node)
{
    if (begin + 1 == end) {
        std::cin >> A[begin];
        return A[begin];
    }
    else {
        auto mid = (begin + end) / 2;
        auto lson = node * 2 + 1;
        auto rson = lson + 1;
        auto left = build(begin, mid, lson);
        auto right = build(mid, end, rson);
        if (left <= right) {
            cache[node] = true;
            return left;
        }
        else {
            cache[node] = false;
            return right;
        }
    }
}

void print(int begin, int end, int node) {
    if (begin + 1 == end) {
        std::cout << A[begin] << " ";
    }
    else {
        auto mid = (begin + end) / 2;
        auto lson = node * 2 + 1;
        auto rson = lson + 1;
        if (cache[node]) {
            print(begin, mid, lson);
            print(mid, end, rson);
        }
        else {
            print(mid, end, rson);
            print(begin, mid, lson);
        }
    }
}

void solve(int n)
{
    build(0, 1 << n, 0);
    print(0, 1 << n, 0);
}

28. 输入 3 1 4 2 并调用 solve(2)，输出为 1 3 2 4（ ）。

{{ select(28) }}

• 正确
• 错误

29. 输入 0 1 2 3 4 5 6 7 并调用 solve(3)，输入和输出完全相同（ ）。

{{ select(29) }}

• 正确
• 错误

30. 输入 8 7 6 5 4 3 2 1 并调用 solve(3)，输出与输入恰好相反（ ）。

{{ select(30) }}

• 正确
• 错误

31. 输入是 $1$ 到 $8$ 的任意一个排列时，调用 solve(3) 总会输出升序排列 1 2 3 4 5 6 7 8（ ）。

{{ select(31) }}

• 正确
• 错误

32. 输入 3 1 4 1 5 9 2 6 并调用 solve(3)，输出是（ ）。

{{ select(32) }}

• 1 3 1 4 2 6 5 9
• 3 1 4 1 5 9 2 6
• 1 1 2 3 4 5 6 9
• 6 2 9 5 1 4 1 3

33. 调用 solve(n) 时，cache[] 数组中会被使用的下标范围是（ ）。

{{ select(33) }}

• $[0,2^n)$
• $[0,2^n]$
• $[0,2^{n+1})$
• $[0,2^{n+1}]$

34. 调用 solve(n) 的时间复杂度为（ ）。

{{ select(34) }}

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

35. 输入 9 2 7 4 1 8 3 6 并调用 solve(3)，输出是（ ）。

{{ select(35) }}

• 2 9 4 7 1 8 3 6
• 2 7 4 9 1 3 6 8
• 1 8 3 6 2 9 4 7
• 2 9 4 7 1 3 6 8

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

第1题

给定整数 $N$、$A$ 以及 $M$，请计算并输出：

$$(1+A^1+A^2+\cdots+A^{N-1})\bmod M$$

using i64 = long long;
std::pair<i64, i64> solve(i64 n, i64 A, i64 M)
{
    if (n == 0)
        return {____(1)____};
    else if (n % 2 == 1) {
        auto result = solve(____(2)____, A, M);
        auto sum = result.first;
        auto pow = result.second;
        sum = ____(3)____;
        pow = pow * A % M;
        return {sum, pow};
    }
    else {
        auto result = solve(____(4)____, A, M);
        auto sum = result.first;
        auto pow = result.second;
        sum = ____(5)____;
        pow = ____(6)____;
        return {sum, pow};
    }
}

int main()
{
    i64 N, A, M;
    std::cin >> N >> A >> M;
    std::cout << solve(N, A, M).first << "\n";
}

36. （1）处应填（ ）。

{{ select(36) }}

• 0, 0
• 0, 1
• 1, 0
• 1, 1

37. （2）（4）处应填（ ）。

{{ select(37) }}

• n - 1, n - 1
• n - 1, n / 2
• n / 2, n - 1
• n / 2, n / 2

38. （3）处应填（ ）。

{{ select(38) }}

• sum * A % M
• pow * sum % M
• (1 + sum * A) % M
• (1 + pow) * sum % M

39. （5）处应填（ ）。

{{ select(39) }}

• sum * A % M
• pow * sum % M
• (1 + sum * A) % M
• (1 + pow) * sum % M

40. （6）处应填（ ）。

{{ select(40) }}

• sum * A % M
• pow * A % M
• pow * sum % M
• pow * pow % M

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

第2题

给定一个 $n\times n$ 的网格。第 $i+1$ 行、第 $j+1$ 列的格子（$0\le i,j<n$）记作 $(i,j)$。格子 $(i,j)$ 的颜色由字符 $p[i\bmod n][j\bmod n]$ 决定，如果是 B，则 $(i,j)$ 是黑格；如果是 W，则是白格。

给定 $q$ 个查询，请依次处理。每个查询给出 4 个整数 $A,B,C,D$，求出以 $(A,B)$ 为左上角、$(C,D)$ 为右下角的矩形区域内包含的黑格数量。

#include<iostream>
int n, q;
int s[1001][1001];
long long sum(int row, int col) {
    long long a = 1LL * ____(1)____ ;
    long long b = 1LL * (row/n) * s[n][col%n];
    long long c = 1LL * (col/n) * s[row%n][n];
    long long d = 1LL * ____(2)____ ;
    return ____(3)____ ;
}
int main() {
    std::cin >> n >> q;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            char c;
            std::cin >> c;
            ____(4)____ ;
        }
    while (q-->0) {
        int x1, x2, y1, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        std::cout << ____(5)____ << "\n";
    }
}

41. （1）处应填（ ）。

{{ select(41) }}

• row * col
• (row/n) * (col/n) * s[n][n]
• row * col * s[row%n][col%n]
• (row/n) * (col/n) * s[row%n][col%n]

42. （2）处应填（ ）。

{{ select(42) }}

• s[n][n]
• s[row][col]
• s[row-1][col-1]
• s[row%n][col%n]

43. （3）处应填（ ）。

{{ select(43) }}

• a + b + c + d
• a + b + c - d
• a - b - c + d
• a - b - c - d

44. （4）处应填（ ）。

{{ select(44) }}

• s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + (c == 'B')
• s[i][j] = s[i][j-1] + s[i-1][j] + s[i-1][j-1] + (c == 'W')
• s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + (c == 'B')
• s[i+1][j+1] = s[i+1][j] + s[i][j+1] + s[i][j] + (c == 'W')

45. （5）处应填（ ）。

{{ select(45) }}

• sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1)
• sum(x2, y2) - sum(x2, y1 + 1) - sum(x1, y2 + 1) + sum(x1 - 1, y1 - 1)
• sum(x2 - 1, y2 - 1) - sum(x2 - 1, y1) - sum(x1, y2 - 1) + sum(x1, y1)
• sum(x2 + 1, y2 + 1) - sum(x2 + 1, y1) - sum(x1, y2 + 1) + sum(x1, y1)