第 1 题（2 分）

在 C++ 中，$32$ 位有符号整数类型 int 能表示的最小值是？

{{ select(1) }}

• $-2^{32}$
• $-2^{31} + 1$
• $-2^{31}$
• $-2^{30}$

---

第 2 题（2 分）

二进制小数 $(0.1011)_2$ 对应的十进制数是？

{{ select(2) }}

• $0.5625$
• $0.6250$
• $0.6875$
• $0.7500$

---

第 3 题（2 分）

执行下列 C++ 代码后，输出的结果是？（已知 '0' 的 ASCII 码为 $48$，'A' 的 ASCII 码为 $65$）

char c = '9' - '0' + 'A';
cout << c;

{{ select(3) }}

• 9
• J
• I
• 74

---

第 4 题（2 分）

设 $x$ 为正整数，下列表达式中，其值恰好等于 $x$ 的二进制表示中最低位的 $1$ 所代表的数值（例如 $x = 12 = (1100)_2$ 时结果为 $4$）的是？

{{ select(4) }}

• x & (x - 1)
• x | (x - 1)
• x ^ (x - 1)
• x & (-x)

---

第 5 题（2 分）

设 $a, b$ 为布尔变量（取值 $0$ 或 $1$），逻辑表达式 (a ^ b) | (a & b) 与下列哪个表达式的值始终相等？

{{ select(5) }}

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

---

第 6 题（2 分）

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

{{ select(6) }}

• v.size() 返回的是 v 当前已分配的存储容量。
• 对一个空的 vector 调用 v.back() 会返回 $0$。
• 执行 v.push_back(x) 后，之前保存的指向 v 中元素的迭代器可能失效。
• 执行 v.clear() 后，v.capacity() 一定变为 $0$。

---

第 7 题（2 分）

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

#include <iostream>
using namespace std;
void f(int a[], int n) {
    n = 5;
    a[0] = 5;
}
int main() {
    int a[3] = {1, 2, 3};
    int n = 3;
    f(a, n);
    cout << a[0] << " " << n << endl;
    return 0;
}

{{ select(7) }}

• 1 3
• 5 3
• 5 5
• 1 5

---

第 8 题（2 分）

在 $1 \sim 100$ 的所有正整数中，既不能被 $2$ 整除、也不能被 $3$ 整除、也不能被 $5$ 整除的数共有多少个？

{{ select(8) }}

• $26$
• $24$
• $28$
• $30$

---

第 9 题（2 分）

$6$ 名同学排成一排照相，要求甲、乙两人必须相邻，且甲不能站在最左端。共有多少种不同的排法？

{{ select(9) }}

• $240$
• $192$
• $120$
• $216$

---

第 10 题（2 分）

一段文本只由 A、B、C、D、E 五种字符组成，它们出现的次数分别为 $5, 4, 3, 2, 1$。若采用哈夫曼编码对这段文本进行压缩，则编码后的总长度是多少比特？

{{ select(10) }}

• $33$
• $30$
• $35$
• $45$

---

第 11 题（2 分）

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

{{ select(11) }}

• DEBFGCA
• DEBGFCA
• EDBFGCA
• DBEFCGA

---

第 12 题（2 分）

元素 $1, 2, 3, 4, 5$ 依次入栈（入栈过程中可以随时出栈），下列序列中不可能是出栈序列的是？

{{ select(12) }}

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

---

第 13 题（2 分）

一个有 $8$ 个顶点的无向简单图（无自环、无重边），要保证该图一定是连通的，至少需要多少条边？

{{ select(13) }}

• $7$
• $8$
• $28$
• $22$

---

第 14 题（2 分）

在一个含有 $1000$ 个元素的升序数组中用二分查找查找某个元素，最坏情况下需要比较多少次？

{{ select(14) }}

• $9$
• $10$
• $11$
• $1000$

---

第 15 题（2 分）

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

int f(int n) {
    if (n <= 2) return n;
    return f(n - 1) + 2 * f(n - 2) + 1;
}

{{ select(15) }}

• $21$
• $43$
• $85$
• $42$

---

第 16 题（13 分）

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

#include <cstdio>
int f(int n) {
    int s = 0;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            s += i;
            if (i != n / i) s += n / i;
        }
    }
    return s;
}
int main() {
    int n;
    scanf("%d", &n);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (f(i) == 2 * i) ++ans;
    }
    printf("%d\n", ans);
    return 0;
}

假设输入的 $n$ 为正整数且 $1 \leq n \leq 10^5$。

判断题

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

{{ select(16) }}

• T
• F

17. 将第 $7$ 行改为 s += n / i;（即删去 if (i != n / i) 的判断），当输入为 $30$ 时程序的输出会发生改变。（ ）

{{ select(17) }}

• T
• F

18. 在题目给定的输入范围内，变量 s 有可能超出 int 的表示范围而发生溢出。（ ）

{{ select(18) }}

• T
• F

单选题

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

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

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

• $O(n)$
• $O(n \log n)$
• $O(n \sqrt n)$
• $O(n^2)$

21. 使第 $17$ 行的条件 f(i) == 2 * i 成立的最小正整数 $i$ 是（ ）。 {{ select(21) }}

• $1$
• $6$
• $12$
• $28$

---

第 17 题（13.5 分）

#include <algorithm>
#include <cstdio>
int n, m;
int w[107], v[107];
int f[1007];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= w[i]; --j) {
            f[j] = std::max(f[j], f[j - w[i]] + v[i]);
        }
    }
    printf("%d\n", f[m]);
    return 0;
}

假设输入的 $n, m$ 均为正整数，$1 \leq n \leq 100$，$1 \leq m \leq 1000$；除特殊说明外，$w[i], v[i]$ 均为正整数。

判断题

22. 当输入为 3 5、1 2、2 4、3 5（即 $n=3$，$m=5$，三个物品的重量与价值依次为 $(1,2),(2,4),(3,5)$）时，输出为 $9$。（ ）

{{ select(22) }}

• T
• F

23. 将第 $12$ 行改为 for (int j = w[i]; j <= m; ++j) {，则对于上一小题的输入，输出仍为 $9$。（ ）

{{ select(23) }}

• T
• F

24. 若输入中某个物品的 $w[i]$ 为 $0$，程序会陷入死循环。（ ）

{{ select(24) }}

• T
• F

单选题

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

• $O(n + m)$
• $O(nm)$
• $O(n^2)$
• $O(m^2)$

26. 当输入为 4 8、2 3、3 4、4 5、5 6 时，输出为（ ）。 {{ select(26) }}

• $9$
• $11$
• $10$
• $12$

27. 若在第 $7$ 行之后增加语句，把 f[1] 到 f[m] 全部初始化为一个极小的负数（f[0] 仍为 $0$），其余代码不变，则程序求的是（ ）。 {{ select(27) }}

• 总重量不超过 $m$ 时的最大价值（与原程序相同）
• 装入物品件数最少时的总价值
• 总重量恰好等于 $m$ 时的最大价值（无法恰好装满时输出为负数）
• 程序一定输出 $0$

---

第 18 题（13.5 分）

#include <cstdio>
int n, k;
int a[27];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    int ans = 0;
    for (int s = 0; s < (1 << n); ++s) {
        int sum = 0, cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (s >> i & 1) {
                sum += a[i];
                ++cnt;
            }
        }
        if (cnt > 0 && sum % k == 0) ++ans;
    }
    printf("%d\n", ans);
    return 0;
}

假设输入的 $1 \leq n \leq 20$，$1 \leq k \leq 1000$，$a_i$ 均为不超过 $1000$ 的正整数。

判断题

28. 第 $13$ 行的 s >> i & 1 与 (s >> i) & 1 等价。（ ）

{{ select(28) }}

• T
• F

29. 将第 $10$ 行的 s < (1 << n) 改为 s <= (1 << n)，程序的输出可能变大。（ ）

{{ select(29) }}

• T
• F

30. 若输入的所有 $a_i$ 都是 $k$ 的倍数，则输出为 $2^n - 1$。（ ）

{{ select(30) }}

• T
• F

单选题

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

• $O(n^2)$
• $O(2^n)$
• $O(n \cdot 2^n)$
• $O(n \cdot k)$

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

• $5$
• $4$
• $6$
• $7$

33. 若去掉题目对 $n$ 的范围限制（并假设数组足够大），当 $n$ 取到（ ）时，第 $10$ 行的 1 << n 开始无法用 int 正确表示。 {{ select(33) }}

• $20$
• $30$
• $31$
• $32$

---

第 19 题（15 分）

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

（1）（进制转换）给定非负整数 $n$（$0 \leq n \leq 10^9$）与进制 $k$（$2 \leq k \leq 16$），输出 $n$ 的 $k$ 进制表示。当某一位的数字大于等于 $10$ 时，用大写字母 A～F 表示（A 表示 $10$，B 表示 $11$，……，F 表示 $15$）。例如输入 255 16 输出 FF，输入 1000 8 输出 1750，输入 0 7 输出 0。

程序思路：反复取 $n$ 除以 $k$ 的余数，得到从低位到高位的各位数字，依次追加到字符串 s 的末尾，最后把 s 倒序输出。试补全程序。

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    string s = "";
    if (n == 0) s = "0";
    while (n > 0) {
        int d = __①__;
        if (d < 10) s += __②__;
        else s += __③__;
        n = __④__;
    }
    for (int i = __⑤__; i >= 0; --i) cout << s[i];
    cout << endl;
    return 0;
}

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

• n / k
• n % k
• n - k
• k % n

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

• d
• "0" + d
• (char)('0' + d)
• (char)('A' + d)

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

• (char)('A' + d)
• (char)('a' + d)
• (char)('0' + d)
• (char)('A' + d - 10)

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

• n / k
• n % k
• n - d
• n / k + 1

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

• 0
• s.length()
• s.length() - 1
• n - 1

---

第 20 题（15 分）

（2）（表达式求值）给定一个合法的中缀表达式字符串 $s$（长度不超过 $1000$），只包含非负整数、运算符 +、-、*、/ 以及小括号 (、)，不含空格。求表达式的值。其中 / 表示整除（保证除数不为 $0$），运算过程中所有中间结果和最终结果均在 int 范围内。例如输入 1+(2*3-4)/5 输出 1，输入 10-4-3 输出 3。

程序使用两个栈：num 存放数字，op 存放运算符。从左到右扫描字符串：遇到数字字符，则把这个（可能有多位的）整数完整读出并压入 num；遇到 ( 直接压入 op；遇到 ) 则不断取出 op 栈顶的运算符进行计算，直到遇到 (，并把这个 ( 弹出；遇到运算符，则先把 op 栈顶中"可以先算"的运算符依次计算完，再把当前运算符压栈。扫描结束后，把 op 中剩余的运算符全部计算完，此时 num 中剩下的唯一元素就是答案。

函数 pri 返回运算符的优先级（*、/ 高于 +、-）；函数 calc 取出 num 栈顶的两个数和 op 栈顶的一个运算符做一次运算，并把结果压回 num。试补全程序。

#include <cctype>
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int pri(char c) {
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    return 0;
}

stack<int> num;
stack<char> op;

void calc() {
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    char c = op.top(); op.pop();
    int r = 0;
    if (c == '+') r = a + b;
    if (c == '-') r = a - b;
    if (c == '*') r = a * b;
    if (c == '/') r = a / b;
    num.push(r);
}

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        if (isdigit(s[i])) {
            int x = 0;
            while (i < s.length() && isdigit(s[i])) {
                x = __①__;
                ++i;
            }
            __②__;
            num.push(x);
        } else if (s[i] == '(') {
            op.push(s[i]);
        } else if (s[i] == ')') {
            while (op.top() != '(') calc();
            op.pop();
        } else {
            while (!op.empty() && __③__) calc();
            op.push(s[i]);
        }
    }
    while (__④__) calc();
    cout << __⑤__ << endl;
    return 0;
}

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

• x + (s[i] - '0')
• x * 10 + (s[i] - '0')
• x * 10 + s[i]
• s[i] - '0'

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

• ++i
• i = 0
• --i
• // 不执行任何操作

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

• pri(op.top()) > pri(s[i])
• pri(op.top()) <= pri(s[i])
• op.top() != '('
• pri(op.top()) >= pri(s[i])

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

• !op.empty()
• !num.empty()
• op.size() > 1
• num.empty()

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

• num.size()
• num.top()
• op.top()
• x