第 1 题（2 分）

在 C++ 中，unsigned int 为 $32$ 位无符号整数。执行 unsigned int u = 0u - 1; cout << u; 后，输出的结果是？

{{ select(1) }}

• $-1$
• $4294967295$
• $2147483647$
• 编译错误

---

第 2 题（2 分）

十六进制数 $(2F)_{16}$ 转换为八进制数是？

{{ select(2) }}

• $(57)_8$
• $(47)_8$
• $(75)_8$
• $(27)_8$

---

第 3 题（2 分）

执行下列 C++ 代码后，输出的结果是？（char 为 $8$ 位有符号类型）

char c = 200;
cout << (int)c;

{{ select(3) }}

• $200$
• $-56$
• $56$
• $-55$

---

第 4 题（2 分）

设 int x = 10;，则表达式 x ^ (x >> 1) 的值是？

{{ select(4) }}

• $15$
• $5$
• $10$
• $0$

---

第 5 题（2 分）

以下 C++ 程序的输出是？

#include <iostream>
using namespace std;
int main() {
    int a = 0, b = 0;
    if (a++ > 0 && b++ > 0) {
        a = 100;
    }
    cout << a << b << endl;
    return 0;
}

{{ select(5) }}

• 11
• 10
• 00
• 01

---

第 6 题（2 分）

下列关于 C++ string 的说法，正确的是？

{{ select(6) }}

• s.length() 的返回值类型是 int。
• 对于 string s，表达式 s + 'a' 不合法，无法通过编译。
• s.substr(2, 3) 返回 s 中从下标 $2$ 开始、长度为 $3$ 的子串。
• 两个 string 对象用 == 比较时，比较的是它们在内存中的地址。

---

第 7 题（2 分）

以下 C++ 程序的输出是？

#include <iostream>
using namespace std;
void f(int &x, int y) {
    x = x * 2;
    y = y + x;
}
int main() {
    int a = 3, b = 4;
    f(a, b);
    f(b, a);
    cout << a << " " << b << endl;
    return 0;
}

{{ select(7) }}

• 3 4
• 6 4
• 6 8
• 12 8

---

第 8 题（2 分）

把 $10$ 个相同的小球放入 $3$ 个不同的盒子，要求每个盒子至少放 $1$ 个球，共有多少种不同的放法？

{{ select(8) }}

• $45$
• $55$
• $66$
• $36$

---

第 9 题（2 分）

某班有 $40$ 名学生，那么其中至少有多少名学生是在同一个月出生的？（即：无论生日如何分布，都一定存在某个月，出生于该月的学生不少于这个数）

{{ select(9) }}

• $3$
• $4$
• $5$
• $12$

---

第 10 题（2 分）

一棵有 $2026$ 个结点的完全二叉树，其深度（规定根结点所在层为第 $1$ 层）是多少？

{{ select(10) }}

• $11$
• $10$
• $12$
• $13$

---

第 11 题（2 分）

中缀表达式 a + b * (c - d) / e 对应的后缀表达式是？

{{ select(11) }}

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

---

第 12 题（2 分）

给定一个初始为空的栈 $S$ 和一个初始为空的队列 $Q$。依次处理整数序列 $4, 1, 3, 8, 6, 5, 2$：若当前数是奇数，则将其压入栈 $S$；若当前数是偶数，则当 $S$ 非空时弹出栈顶元素并立即输出，当 $S$ 为空时把该偶数加入队列 $Q$ 的末尾。序列处理完后，再把 $Q$ 中的元素依次出队并输出。最终输出的序列是？

{{ select(12) }}

• $4, 3, 1, 5$
• $1, 3, 5, 4$
• $3, 1, 5, 4$
• $3, 1, 5$

---

第 13 题（2 分）

一个无向简单图有 $6$ 个顶点，各顶点的度数分别为 $3, 3, 3, 2, 2, 1$，则该图的边数是？

{{ select(13) }}

• $7$
• $14$
• $6$
• $8$

---

第 14 题（2 分）

下列排序算法中，不稳定的是？

{{ select(14) }}

• 冒泡排序
• 插入排序
• 归并排序
• 快速排序

---

第 15 题（2 分）

已知 $f[0] = 1$，$f[1] = 1$，且对所有 $n \geq 2$ 有 $f[n] = (f[n-1] + f[n-2]) \bmod 5$。那么 $f[2026]$ 的值是？

{{ select(15) }}

• $0$
• $1$
• $3$
• $4$

---

第 16 题（13 分）

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

#include <cstdio>
typedef long long ll;
ll power(ll a, ll b, ll p) {
    ll r = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) r = r * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return r;
}
int main() {
    ll a, b, p;
    scanf("%lld%lld%lld", &a, &b, &p);
    printf("%lld\n", power(a, b, p));
    return 0;
}

假设输入满足 $1 \leq a \leq 10^9$，$0 \leq b \leq 10^{18}$，$2 \leq p \leq 10^9$。

判断题

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

{{ select(16) }}

• T
• F

17. 当输入的 $b = 0$ 时，无论 $a$ 和 $p$ 在给定范围内取何值，程序都输出 $1$。（ ）

{{ select(17) }}

• T
• F

18. 若把程序中所有的 ll 都改为 int（并相应地把 %lld 改为 %d），则在给定的输入范围内程序的输出不受影响。（ ）

{{ select(18) }}

• T
• F

单选题

19. 当输入为 3 100 7 时，输出为（ ）。 {{ select(19) }}

• $1$
• $2$
• $4$
• $6$

20. 当 $b > 0$ 时，第 $6$ 行 while 循环的循环体共执行了（ ）次。 {{ select(20) }}

• $b$
• $\lfloor \log_2 b \rfloor + 1$
• $\lceil \log_2 b \rceil$
• $\lfloor \sqrt b \rfloor$

21. 若删去第 $5$ 行 a %= p;，则在给定的输入范围内，程序（ ）。 {{ select(21) }}

• 输出一定不变
• 输出可能改变，但不会发生溢出
• 可能因乘法溢出而输出错误结果
• 一定陷入死循环

---

第 17 题（13.5 分）

#include <cstdio>
const int P = 1000000007;
int n, m;
int g[1007][1007];
long long f[1007][1007];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &g[i][j]);
    f[0][1] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (g[i][j] == 1) f[i][j] = 0;
            else f[i][j] = (f[i - 1][j] + f[i][j - 1]) % P;
        }
    }
    printf("%lld\n", f[n][m]);
    return 0;
}

程序读入一个 $n$ 行 $m$ 列的网格（$1 \leq n, m \leq 1000$），g[i][j] = 1 表示格子 $(i, j)$ 是障碍，g[i][j] = 0 表示可以通行。从左上角 $(1, 1)$ 出发，每步只能向右或向下走一格，求走到右下角 $(n, m)$ 的路径条数对 $10^9 + 7$ 取模的结果。

判断题

22. 当输入为 3 3 且 $9$ 个格子全为 $0$ 时，输出为 $6$。（ ）

{{ select(22) }}

• T
• F

23. 若删去第 $15$ 行中的 % P，则在给定的输入范围内，程序的输出不会改变。（ ）

{{ select(23) }}

• T
• F

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

{{ select(24) }}

• T
• F

单选题

25. 当输入为 3 4、0 0 0 0、0 1 1 0、0 0 0 0 时，输出为（ ）。 {{ select(25) }}

• $3$
• $2$
• $4$
• $10$

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

• 对所有 $1 \leq i \leq n$，$1 \leq j \leq m$，都有 $f[i][j] \leq f[n][m]$。
• 若输出为 $0$，则起点 $(1,1)$ 或终点 $(n,m)$ 必为障碍。
• 对所有 $2 \leq i \leq n$，都有 $f[i][j] \geq f[i-1][j]$。
• 若某一行的格子全是障碍，则输出一定为 $0$。

27. 将第 $12$、$13$ 行两层循环的顺序交换（外层枚举 $j$ 从 $1$ 到 $m$，内层枚举 $i$ 从 $1$ 到 $n$，循环体不变），则程序的输出（ ）。 {{ select(27) }}

• 与原来相同
• 可能比原来大
• 可能比原来小
• 程序可能陷入死循环

---

第 18 题（13.5 分）

#include <cstdio>
#include <cstring>
#include <stack>
char s[100007];
int main() {
    scanf("%s", s);
    int n = strlen(s);
    std::stack<int> st;
    st.push(-1);
    int ans = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '(') {
            st.push(i);
        } else {
            if (st.top() != -1 && s[st.top()] == '(') {
                st.pop();
                ++cnt;
                if (i - st.top() > ans) ans = i - st.top();
            } else {
                st.push(i);
            }
        }
    }
    printf("%d %d\n", ans, cnt);
    return 0;
}

假设输入的字符串只包含字符 ( 和 )，长度 $n$ 满足 $1 \leq n \leq 10^5$。

判断题

28. 当输入为 (()()) 时，输出为 6 3。（ ）

{{ select(28) }}

• T
• F

29. 若将第 $15$ 行的条件改为 s[st.top()] == '('（删去 st.top() != -1 &&），则当输入以 ) 开头时，程序会访问 s[-1]，属于数组越界。（ ）

{{ select(29) }}

• T
• F

30. 对任意输入，输出的第二个数 cnt 总等于第一个数 ans 的一半。（ ）

{{ select(30) }}

• T
• F

单选题

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

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

32. 该程序的时间复杂度为（ ）。 {{ select(32) }}

• $O(n \log n)$
• $O(n^2)$
• $O(n \cdot ans)$
• $O(n)$

33. 程序运行结束时，栈 st 中的元素个数（含最初压入的 $-1$）为（ ）。 {{ select(33) }}

• $n - cnt$
• $n - 2 \cdot cnt + 1$
• $n - 2 \cdot cnt$
• $cnt + 1$

---

第 19 题（15 分）

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

（1）（约数个数）给定正整数 $n$（$1 \leq n \leq 10^{12}$），求 $n$ 的正约数个数。

程序思路：对 $n$ 做质因数分解 $n = p_1^{c_1} p_2^{c_2} \cdots p_k^{c_k}$，则约数个数为 $(c_1 + 1)(c_2 + 1) \cdots (c_k + 1)$。从 $2$ 开始试除，每找到一个质因数 $i$ 就把它从 $n$ 中除尽并统计次数 cnt；试除只需进行到 $\sqrt n$，结束后若 $n$ 仍大于 $1$，说明剩下的 $n$ 本身是一个质因数（指数为 $1$）。例如输入 12 输出 6，输入 1 输出 1，输入 97 输出 2。试补全程序。

#include <iostream>
using namespace std;
int main() {
    long long n;
    cin >> n;
    long long ans = 1;
    for (long long i = 2; __①__; ++i) {
        if (__②__) {
            int cnt = 0;
            while (n % i == 0) {
                ++cnt;
                __③__;
            }
            ans = __④__;
        }
    }
    if (__⑤__) ans *= 2;
    cout << ans << endl;
    return 0;
}

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

• i * i < n
• i * i <= n
• i < n
• i * i <= n / 2

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

• n % i == 0
• i % n == 0
• n / i == 0
• n % i != 0

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

• n -= i
• n = n % i
• n /= i
• i /= n

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

• ans * cnt
• ans * (cnt + 1)
• ans + cnt + 1
• ans * 2

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

• n == 1
• n > 0
• ans > 1
• n > 1

---

第 20 题（15 分）

（2）（木材切割）有 $n$ 根木材，第 $i$ 根长度为 $a_i$（$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^9$，均为整数）。现在要把它们切成长度相等的整数长度木段，至少得到 $k$ 段（$1 \leq k \leq 10^9$）。每根木材可以切出若干段，剩余的部分丢弃。求满足要求的木段长度的最大值；若连长度为 $1$ 都无法切出 $k$ 段，输出 $0$。例如输入 3 7 与 232 124 456 时输出 114。

程序思路：木段长度越短，能切出的段数越多，因此答案具有单调性。在 $[1, \max a_i]$ 内二分答案：函数 check(len) 计算长度为 len 时总共能切出多少段；若段数不少于 $k$，说明 len 可行，记录答案并尝试更大的长度，否则尝试更小的长度。试补全程序。

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

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

• a[i] % len
• len / a[i]
• a[i] / len
• a[i] - len

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

• l <= r
• l < r
• l != r
• l >= r

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

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

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

• check(mid) <= k
• check(mid) == k
• check(mid) > k
• check(mid) >= k

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

• r = mid
• l = mid
• r = mid - 1
• r = mid + 1