第 1 题（2 分）

在 C++ 中，int 为 $32$ 位有符号整数。执行 int x = 2147483647; x = x + 1; cout << x; 后，输出的结果是？

{{ select(1) }}

• $2147483648$
• $-2147483648$
• $0$
• $-1$

---

第 2 题（2 分）

十进制数 $2026$ 用二进制表示（不含前导 $0$），共需要多少位？

{{ select(2) }}

• $11$
• $10$
• $12$
• $8$

---

第 3 题（2 分）

已知小写字母 a 的 ASCII 码为 $97$，大写字母 A 的 ASCII 码为 $65$。执行 char c = 'a'; cout << (char)(c ^ 32); 后，输出的结果是？

{{ select(3) }}

• a
• 65
• A
• !

---

第 4 题（2 分）

十进制数 $2026$ 的二进制表示中，数字 $1$ 的个数是？

{{ select(4) }}

• $7$
• $9$
• $10$
• $8$

---

第 5 题（2 分）

设 $a, b$ 为布尔变量，下列表达式中与 !(a || b) 的值始终相等的是？

{{ select(5) }}

• !a || !b
• !(a && b)
• !a ^ !b
• !a && !b

---

第 6 题（2 分）

下列软件中，不属于操作系统的是？

{{ select(6) }}

• Ubuntu
• iOS
• Photoshop
• Windows

---

第 7 题（2 分）

以下 C++ 代码段执行后，变量 cnt 的值是？

int cnt = 0;
for (int i = 1; i <= 100; i *= 2) {
    cnt++;
}

{{ select(7) }}

• $7$
• $6$
• $8$
• $100$

---

第 8 题（2 分）

把 $6$ 名同学平均分成 $3$ 个小组（每组 $2$ 人，小组之间不区分顺序），共有多少种不同的分法？

{{ select(8) }}

• $15$
• $90$
• $45$
• $30$

---

第 9 题（2 分）

在平面直角坐标系中，一个机器人从 $(0, 0)$ 出发，每步只能向右或向上走一个单位，要走到 $(4, 3)$，且必须经过点 $(2, 1)$。共有多少条不同的路径？

{{ select(9) }}

• $35$
• $18$
• $12$
• $21$

---

第 10 题（2 分）

用 $5$ 个权值 $2, 3, 5, 7, 11$ 构造哈夫曼树，该树的带权路径长度是多少？

{{ select(10) }}

• $60$
• $56$
• $62$
• $28$

---

第 11 题（2 分）

一棵二叉树的中序遍历为 DBEAFC，后序遍历为 DEBFCA，则它的前序遍历是？

{{ select(11) }}

• ABCDEF
• ABDECF
• ADBECF
• ABDEFC

---

第 12 题（2 分）

元素 $1, 2, 3, 4$ 按顺序依次入栈（入栈过程中可以随时出栈），所有可能的不同出栈序列共有多少种？

{{ select(12) }}

• $24$
• $16$
• $12$
• $14$

---

第 13 题（2 分）

一个无向连通图能够"一笔画"（即存在一条经过每条边恰好一次的路径）的充分必要条件是：图中度数为奇数的顶点个数为？

{{ select(13) }}

• $0$
• $2$
• $0$ 或 $2$
• 任意个

---

第 14 题（2 分）

在升序数组 $\{1, 3, 5, 7, 9, 11, 13, 15, 17\}$（下标 $0 \sim 8$）中，用二分查找（每次取 $mid = \lfloor (l + r) / 2 \rfloor$，与 $a[mid]$ 比较）查找元素 $13$，需要比较多少次才能找到？

{{ select(14) }}

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

---

第 15 题（2 分）

函数 g(n) 的定义如下，则 g(5) 的返回值是多少？

int g(int n) {
    if (n < 2) return 1;
    return g(n / 2) + g(n - 1);
}

{{ select(15) }}

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

---

第 16 题（13 分）

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 A，错误填 B；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分。题中"第 $N$ 行"指代码块中从第一行 #include 起算的第 $N$ 行）

#include <cstdio>
const int N = 1000007;
bool np[N];
int cnt[N];
int main() {
    int l, r;
    scanf("%d%d", &l, &r);
    np[1] = true;
    for (int i = 2; i * i <= r; ++i) {
        if (!np[i]) {
            for (int j = i * i; j <= r; j += i) np[j] = true;
        }
    }
    for (int i = 1; i <= r; ++i) {
        cnt[i] = cnt[i - 1] + (np[i] ? 0 : 1);
    }
    printf("%d\n", cnt[r] - cnt[l - 1]);
    return 0;
}

假设输入满足 $1 \leq l \leq r \leq 10^6$。

判断题

16.（$1$ 分）当输入为 1 10 时，程序输出 $4$。（ ）

{{ select(16) }}

• T
• F

17. 将第 $11$ 行的 j = i * i 改为 j = 2 * i，程序的输出不变。（ ）

{{ select(17) }}

• T
• F

18. 当输入的 $l = 1$ 时，第 $17$ 行会访问 cnt[0]，属于数组越界。（ ）

{{ select(18) }}

• T
• F

单选题

19. 当输入为 10 30 时，输出为（ ）。 {{ select(19) }}

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

20. 第 $9 \sim 13$ 行（筛法部分）的时间复杂度为（ ）。 {{ select(20) }}

• $O(r)$
• $O(r \log r)$
• $O(r \log \log r)$
• $O(r \sqrt r)$

21. 若删去第 $8$ 行 np[1] = true;，则程序的输出会发生改变的输入是（ ）。 {{ select(21) }}

• 所有输入
• 仅当 $l = 1$ 时
• 仅当 $r = 1$ 时
• 任何输入下输出都不变

---

第 17 题（13.5 分）

#include <cstdio>
int n;
int a[100007];
long long f[100007];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    long long ans = a[1];
    f[1] = a[1];
    for (int i = 2; i <= n; ++i) {
        if (f[i - 1] > 0) f[i] = f[i - 1] + a[i];
        else f[i] = a[i];
        if (f[i] > ans) ans = f[i];
    }
    printf("%lld\n", ans);
    return 0;
}

程序读入长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$（$1 \leq n \leq 10^5$，$|a_i| \leq 10^9$），求其中连续、非空的一段子序列的最大和。

判断题

22. 当输入为 9 与 -2 1 -3 4 -1 2 1 -5 4 时，输出为 $6$。（ ）

{{ select(22) }}

• T
• F

23. 若输入的 $a_i$ 全为负数，则程序输出 $0$。（ ）

{{ select(23) }}

• T
• F

24. 将第 $11$ 行的 f[i - 1] > 0 改为 f[i - 1] >= 0，则对任意输入，程序的输出都不变。（ ）

{{ select(24) }}

• T
• F

单选题

25. 当输入为 6 与 3 -4 2 5 -1 4 时，输出为（ ）。 {{ select(25) }}

• $10$
• $11$
• $7$
• $9$

26. 程序运行结束后，下列关于数组 f 的说法一定正确的是（ ）。 {{ select(26) }}

• 对所有 $2 \leq i \leq n$，都有 $f[i] \geq f[i-1]$。
• $f[n]$ 等于输出的答案。
• 对所有 $1 \leq i \leq n$，都有 $f[i] > 0$。
• 对所有 $1 \leq i \leq n$，都有 $f[i] \geq a[i]$。

27. 若把 f 数组和变量 ans 的类型都改为 int（并把 %lld 改为 %d），则在给定的输入范围内（ ）。 {{ select(27) }}

• 一定不会溢出，输出不变
• 可能发生溢出，输出可能错误
• 一定发生溢出
• 无法通过编译

---

第 18 题（13.5 分）

#include <cstdio>
int cnt;
long long f(int n) {
    ++cnt;
    if (n <= 1) return 1;
    return f(n / 2) + f(n / 3);
}
int main() {
    int n;
    scanf("%d", &n);
    long long r = f(n);
    printf("%lld %d\n", r, cnt);
    return 0;
}

假设输入满足 $-10^9 \leq n \leq 10^9$。程序输出两个数：f(n) 的返回值 $r$，以及函数 f 被调用的总次数 cnt。

判断题

28. 当输入为 $6$ 时，输出为 4 7。（ ）

{{ select(28) }}

• T
• F

29. 当输入为负数时，递归不会终止，程序会因栈溢出而崩溃。（ ）

{{ select(29) }}

• T
• F

30. 对任意输入，输出的第二个数 cnt 总是奇数。（ ）

{{ select(30) }}

• T
• F

单选题

31. 当输入为 $20$ 时，输出为（ ）。 {{ select(31) }}

• 9 17
• 9 16
• 8 15
• 10 19

32. 对任意输入，输出的两个数 $r$ 与 cnt 之间一定满足（ ）。 {{ select(32) }}

• $cnt = r + 1$
• $cnt = 2r$
• $cnt = 2r - 1$
• $cnt = r^2$

33. 将第 $5$ 行改为 if (n <= 1) return n;，则当输入为 $6$ 时，输出为（ ）。 {{ select(33) }}

• 4 7
• 3 6
• 2 7
• 3 7

---

第 19 题（15 分）

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

（1）（日期计算）输入一个合法的公历日期：年 $y$（$1 \leq y \leq 9999$）、月 $m$、日 $d$。输出两个数：这一天是当年的第几天，以及这一天之后当年还剩多少天。闰年的判定规则：能被 $4$ 整除但不能被 $100$ 整除，或者能被 $400$ 整除。例如输入 2024 3 1 输出 61 305，输入 2023 12 31 输出 365 0，输入 2000 2 29 输出 60 306。

程序思路：数组 days[i] 存放平年第 $i$ 月的天数；先把前 $m - 1$ 个整月的天数累加，再加上当月的 $d$ 天；若当年是闰年且日期已过 $2$ 月，则再加 $1$ 天。试补全程序。

#include <iostream>
using namespace std;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool leap(int y) {
    return __①__;
}
int main() {
    int y, m, d;
    cin >> y >> m >> d;
    int ans = __②__;
    for (int i = 1; __③__; ++i) ans += days[i];
    if (__④__) ans += 1;
    int total = __⑤__;
    cout << ans << " " << total - ans << endl;
    return 0;
}

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

• y % 4 == 0
• y % 4 == 0 && y % 100 != 0
• (y % 4 == 0 && y % 100 != 0) || y % 400 == 0
• y % 4 == 0 || y % 400 == 0

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

• d
• d - 1
• 0
• 1

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

• i <= m
• i < m
• i <= 12
• i < d

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

• leap(y)
• m > 2
• leap(y) && m >= 2
• leap(y) && m > 2

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

• 365
• 365 + leap(y)
• 366
• 365 + (m > 2)

---

第 20 题（15 分）

（2）（逆序对）给定长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$（$1 \leq n \leq 10^5$），求其中逆序对的个数，即满足 $i < j$ 且 $a_i > a_j$ 的数对 $(i, j)$ 的个数。例如输入 5 与 6 1 5 2 4 时输出 6。

程序思路：使用归并排序。函数 msort(l, r) 对区间 $[l, r]$ 排序并统计其中的逆序对：先递归处理左右两半，再把两个有序的半区间合并到辅助数组 t 中。合并时若左半的 a[i] 大于右半的 a[j]，则左半中从 a[i] 到 a[mid] 的每个元素都与 a[j] 构成逆序对，一次性计入答案。合并完成后把 t 中的结果拷回 a。试补全程序。

#include <iostream>
using namespace std;
int n;
int a[100007], t[100007];
long long cnt = 0;
void msort(int l, int r) {
    if (l >= r) return;
    int mid = __①__;
    msort(l, mid);
    msort(__②__);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) t[k++] = a[i++];
        else {
            __③__;
            t[k++] = a[j++];
        }
    }
    while (i <= mid) t[k++] = a[i++];
    while (__④__) t[k++] = a[j++];
    for (int p = l; p <= r; ++p) __⑤__;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    msort(1, n);
    cout << cnt << endl;
    return 0;
}

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

• (l + r) / 2
• (l + r) / 2 + 1
• (r - l) / 2
• l + 1

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

• mid, r
• l, mid
• mid + 1, r
• mid + 1, r - 1

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

• cnt += 1
• cnt += j - i
• cnt += r - i + 1
• cnt += mid - i + 1

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

• j <= r
• i <= r
• j <= mid
• j < r

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

• t[p] = a[p]
• a[p] = t[p]
• a[p] = t[p - l]
• a[p] = t[k]