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

1. 在计算机硬件系统中，用于执行算术运算和逻辑运算的核心部件是（ ）。 {{ select(1) }}

• 内存储器（RAM）
• 控制器（CU）
• 运算器（ALU）
• 外存储器（硬盘）

2. 二进制小数 $(0.1101)_2$ 转换为十进制小数是（ ）。 {{ select(2) }}

• $0.8125$
• $0.825$
• $0.75$
• $0.875$

3. 一个逻辑电路的真值表如下表所示，当输入 $A=1,\ B=0$ 时，输出 $Y=$（ ）。

{{ select(3) }}

• $0$
• $1$
• 不确定
• 无法判断

4. 记 1 KB 为 1024 字节、1 MB 为 1024 KB、1 GB 为 1024 MB，则 1 TB 等于（ ）字节。 {{ select(4) }}

• $10^3$
• $2^{40}$
• $10^{12}$
• $2^{30}$

5. 一个栈的入栈序列为 $1, 2, 3, 4$（按顺序依次入栈，可在任意时刻出栈），则以下哪个选项不可能是出栈序列？（ ） {{ select(5) }}

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

6. 一个 $n$ 个顶点的无向完全图，其邻接矩阵中非零元素的个数为（不考虑对角线）（ ）。 {{ select(6) }}

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

7. 下列各数中，值最大的是（ ）。 {{ select(7) }}

• $(101001)_2$
• $(52)_8$
• $(2B)_{16}$
• $(44)_{10}$

8. 中缀表达式 (a + b) * (c - d) + e / f 对应的后缀表达式是（ ）。 {{ select(8) }}

• a b + c d - * e f / +
• a b + c d - * e f + /
• a b c d + - * e f / +
• a b + c d - e f / + *

9. 在常见的 C++ STL 实现中，下列容器底层通常使用红黑树实现的是（ ）。 {{ select(9) }}

• vector
• queue
• stack
• map

10. 在单链表中，要从链表中移除指针 p 所指结点的后继结点（假设后继结点存在，暂不考虑内存释放），正确的操作是（ ）。 {{ select(10) }}

• p->next = p->next->next;
• p = p->next->next;
• p->next = p;
• p = p->next;

11. 已知一棵二叉树的前序遍历序列为 ABDCEGF，中序遍历序列为 DBAEGCF，则该二叉树的后序遍历序列为（ ）。 {{ select(11) }}

• DBGEFCA
• DBEGCFA
• DBGEACF
• DBAEGCF

12. 使用冒泡排序对 $5$ 个元素进行升序排序，在最坏情况下需要的比较次数是（ ）。 {{ select(12) }}

• $5$
• $9$
• $10$
• $25$

13. 有 $5$ 本不同的书，要放入 $3$ 个不同的书架（允许书架为空，不考虑架上排列顺序），共有（ ）种放法。 {{ select(13) }}

• $125$
• $243$
• $60$
• $15$

14. 由数字 $1, 2, 3, 4$ 组成无重复数字的四位数，其中比 $3000$ 小的数有（ ）个。 {{ select(14) }}

• $12$
• $16$
• $18$
• $24$

15. 对长度为 $2000$ 的升序数组使用如下标准二分查找程序。每次执行 while 循环并将待查元素与 a[mid] 比较，计为 1 次比较；当程序输出 false 时，表示待查元素不在数组中。在最坏情况下，最多需要比较（ ）次才能断定某个元素不在数组中。

bool binary_search(const int a[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (a[mid] == target) return true;
        if (a[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

{{ select(15) }}

• $10$
• $11$
• $12$
• $2000$

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 A，错误填 B；除特殊说明外，判断题每题 2 分，选择题每题 3 分，共 40 分）

第 1 题

#include <bits/stdc++.h>
using namespace std;

const int MOD = 26;
const int MAXL = 1220;
int n, r;
string s;
int ans[MAXL];

int main() {
    cin >> n >> r;
    r %= MOD;
    for (int i = 1; i <= n; i++) {
        memset(ans, 0, sizeof(ans));
        ans[0] = 1;
        cin >> s;
        int len = (int)s.size();
        for (int j = 0; j < len; j++)
            s[j] = (s[j] - 'A' + r) % MOD + 'A';
        cout << s << endl;
        for (int j = 0; j < len; j++) {
            for (int k = 0; k + 1 < MAXL; k++)
                ans[k] *= (int)s[j];
            for (int k = 0; k + 1 < MAXL; k++) {
                ans[k + 1] += ans[k] / 10;
                ans[k] %= 10;
            }
        }
        int p = MAXL - 1;
        while (p > 0 && !ans[p]) p--;
        for (; p >= 0; p--) cout << ans[p];
        cout << endl;
    }
    return 0;
}

保证 $1\le n\le 500$，$0\le r\le 10^9$；输入的每个字符串均由大写英文字母组成，长度为 $1$～$600$。对于每组字符串，程序输出两行：第一行是移位后的字符串，第二行是移位后各字符 ASCII 码的连乘积。

16. 当 $r$ 能被 $26$ 整除时，程序输出的第一行与输入的字符串 $s$ 完全相同。（ ） {{ select(16) }}

• 正确
• 错误

17. 删去 memset(ans, 0, sizeof(ans)); 后，程序在处理多组数据（$n>1$）时，第 2 组及以后各组的乘积输出可能出错。（ ） {{ select(17) }}

• 正确
• 错误

18. 若输入的字符串 $s$ 只包含字符 'A'，则程序输出的第二行只包含数字 1 和 0。（ ） {{ select(18) }}

• 正确
• 错误

19. 当输入如下时，程序输出的第一行为（ ）。

1 26
HELLO

{{ select(19) }}

• HELLO
• IFMMP
• KHOOR
• GDKKN

20. （4 分）当输入如下时，程序输出的第二行为（ ）。

1 0
AB

{{ select(20) }}

• 4290
• 131
• 6566
• 4225

第 2 题

#include <iostream>
using namespace std;

int main() {
    int x = 2026, y = 18;

    int a = x & y;
    int b = x | y;
    int c = x ^ y;
    int d = (x >> 2) & 1;
    int e = x & (-x);
    int cnt = 0, t = x;
    while (t) {
        cnt++;
        t = t & (t - 1);
    }
    int mask = 1 << y;
    bool check = (x & mask) != 0;
    int flip = x ^ ((1 << 4) - 1);
    bool power2 = (x > 0) && ((x & (x - 1)) == 0);

    cout << "a=" << a << endl;
    cout << "b=" << b << endl;
    cout << "c=" << c << endl;
    cout << "d=" << d << endl;
    cout << "e=" << e << endl;
    cout << "cnt=" << cnt << endl;
    cout << "mask=" << mask << endl;
    cout << "check=" << check << endl;
    cout << "flip=" << flip << endl;
    cout << "power2=" << power2 << endl;
    return 0;
}

21. 对于任意非负整数 $x$ 和 $y$，x & y 的值一定小于等于 max(x, y)。（ ） {{ select(21) }}

• 正确
• 错误

22. 对于任意正整数 $n$，n & (-n) 可以取出 $n$ 在二进制表示下最低位的 1 所代表的数值。（ ） {{ select(22) }}

• 正确
• 错误

23. while (t) { cnt++; t = t & (t - 1); } 执行完毕后，cnt 的值等于 x 在二进制表示下 1 的个数。（ ） {{ select(23) }}

• 正确
• 错误

24. 当 x = 2026 时，d = (x >> 2) & 1 的输出值是（ ）。 {{ select(24) }}

• $0$
• $1$
• $2$
• $4$

25. （4 分）当 x = 2026 时，e = x & (-x) 的输出值是（ ）。 {{ select(25) }}

• $2$
• $4$
• $8$
• $16$

第 3 题

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 505;
int a[MAXN][MAXN], s[MAXN][MAXN];
ll b[MAXN], ans, sum;
int n, m;
ll k;

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int j = 1; j <= m; j++)
        for (int i = 1; i <= n; i++)
            s[i][j] = s[i - 1][j] + a[i][j];
    for (int up = 1; up <= n; up++) {
        for (int down = up; down <= n; down++) {
            for (int j = 1; j <= m; j++)
                b[j] = s[down][j] - s[up - 1][j];
            int l = 1, r = 0;
            sum = 0;
            while (r < m) {
                r++;
                sum += b[r];
                if (sum <= k) ans += r - l + 1;
                else {
                    while (sum > k) {
                        sum -= b[l];
                        l++;
                    }
                    ans += r - l + 1;
                }
            }
        }
    }
    cout << ans;
    return 0;
}

输入的 $n, m$ 满足 $1 \le n, m \le 500$，$k$ 满足 $0 \le k \le 2.5 \times 10^8$，矩阵元素 $a[i][j]$ 满足 $0 \le a[i][j] \le 1000$。

26. 将 while 循环内的 sum += b[r]; 和 r++; 两行交换顺序，程序输出结果不变。（ ） {{ select(26) }}

• 正确
• 错误

27. 若 $k=0$ 且所有 $a[i][j] > 0$，程序输出的 ans 为 $0$。（ ） {{ select(27) }}

• 正确
• 错误

28. （3 分）删去 sum -= b[l]; 这一行，程序可能陷入死循环。（ ） {{ select(28) }}

• 正确
• 错误

29. 当输入如下时，程序的输出为（ ）。

2 2 5
1 2
3 4

{{ select(29) }}

• $5$
• $6$
• $7$
• $8$

30. （4 分）该程序计算的是（ ）。 {{ select(30) }}

• 矩阵中所有元素的和
• 矩阵中和不超过 $k$ 的子矩阵个数
• 矩阵中元素不超过 $k$ 的个数
• 最大子矩阵和

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

（1）最小质因子

对于一个正整数 $x$（$x \ge 2$），定义 $g(x)$ 为 $x$ 的最小质因子。例如 $g(10)=2$，$g(15)=3$，$g(7)=7$。给定正整数 $n$（保证 $2\le n\le 10^6$），试求 $1 \sim n$ 中 $g(x)$ 最大的数（若有多个满足条件的数，取最小的那个）。程序输出该数以及对应的 $g$ 值。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000000;
int min_pf[MAXN + 5];

int main() {
    int n;
    cin >> n;

    for (int i = 2; i <= n; i++) {
        ①;
    }

    for (int i = 2; i * i <= n; i++) {
        if (②) {
            for (int j = i * i; j <= n; j += i) {
                if (③) {
                    min_pf[j] = i;
                }
            }
        }
    }

    int best = 2, max_pf = ④;
    for (int i = 2; i <= n; i++) {
        if (⑤) {
            max_pf = min_pf[i];
            best = i;
        }
    }

    cout << best << " " << max_pf << endl;
    return 0;
}

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

• min_pf[i] = 0
• min_pf[i] = 1
• min_pf[i] = i
• min_pf[i] = n

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

• min_pf[i] == 0
• min_pf[i] == 1
• min_pf[i] == i
• min_pf[i] > i

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

• min_pf[j] == 0
• min_pf[j] == j
• min_pf[j] == i
• min_pf[j] < i

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

• 3
• n + 1
• 2
• MAXN

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

• min_pf[i] > max_pf
• min_pf[i] < max_pf
• min_pf[i] == max_pf
• min_pf[i] != max_pf

（2）区间至少覆盖两点

数轴上有 $n$ 个闭区间 $[l_i, r_i]$（均为整数，且保证 $l_i < r_i$）。现在需要选择尽可能少的互不相同的整数点，使得每个区间内至少包含 $2$ 个被选中的点。求最少需要选择的点数。保证 $1\le n\le 100000$，$-10^8\le l_i<r_i\le 10^8$。

例如区间 $[1, 3]$ 和 $[2, 4]$，只需在 $2$ 和 $3$ 处各放一个点，即可使两个区间都包含 $2$ 个点，故最少点数为 $2$。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
const int INF = 1000000000;

struct Interval {
    int l, r;
} a[MAXN + 5];

bool cmp(Interval x, Interval y) {
    return ①;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].l >> a[i].r;
    }
    sort(a + 1, a + n + 1, cmp);

    int ans = 0;
    int p1 = -INF, p2 = -INF;

    for (int i = 1; i <= n; i++) {
        if (②) {
            continue;
        } else if (③) {
            ans++;
            ④;
            p2 = a[i].r;
        } else {
            ans += 2;
            ⑤;
            p2 = a[i].r;
        }
    }

    cout << ans << endl;
    return 0;
}

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

• x.r != y.r ? x.r < y.r : x.l > y.l
• x.r != y.r ? x.r < y.r : x.l < y.l
• x.r != y.r ? x.r > y.r : x.l > y.l
• x.l != y.l ? x.l < y.l : x.r < y.r

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

• p1 >= a[i].l
• p2 >= a[i].l
• p1 <= a[i].l
• p2 <= a[i].l

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

• p1 >= a[i].l
• p2 >= a[i].l
• p1 >= a[i].r
• p2 >= a[i].r

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

• p1 = a[i].r
• p2 = a[i].r - 1
• p1 = p2
• p2 = p1

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

• p1 = a[i].r - 1
• p1 = a[i].l
• p1 = a[i].r + 1
• p2 = a[i].r - 1