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

---

1. 阅读下面代码，输出结果是？

int a = 7, b = 3;
cout << a / b * b + a % b;

{{ select(1) }}

• 6
• 7
• 8
• 10

---

2. 十六进制数 $2A_{16}$ 与二进制数 $101011_2$ 的和对应的十进制值是？

{{ select(2) }}

• 83
• 84
• 85
• 86

---

3. 阅读下面代码，输出结果是？

int x = 0, y = 1;
if (x && ++y) {
    y += 10;
}
cout << y;

{{ select(3) }}

• 0
• 1
• 2
• 11

---

4. 阅读下面代码，输出结果是？

string s = "algorithm";
cout << s.substr(2, 4);

{{ select(4) }}

• gori
• gorit
• lgo
• orit

---

5. 如果一棵二叉树高度为 $h$，根结点高度为 1，则高度至少为多少时，二叉树最多可以包含不少于 2026 个结点？

{{ select(5) }}

• 9
• 10
• 11
• 12

---

6. 一个不含重边和自环的无向图有 5 个顶点，若用邻接矩阵表示，矩阵中最多可能有多少个非零元素？

{{ select(6) }}

• 10
• 15
• 20
• 25

---

7. 有向无环图中有边 $(1,4), (2,4), (3,4)$。该图共有多少种不同的拓扑排序？

{{ select(7) }}

• 3
• 6
• 12
• 24

---

8. 下列关于队列的说法，正确的是？

{{ select(8) }}

• 队列是后进先出的数据结构
• 队列只能使用链表实现
• 队列常用于广度优先搜索
• 队列中的元素必须按大小有序

---

9. 有 5 本不同的书排成一排，其中指定的两本书不能相邻，共有多少种排列方式？

{{ select(9) }}

• 48
• 60
• 72
• 96

---

10. 递归函数定义如下：

f(1)=1
f(n)=2*f(n-1)+1  (n>=2)

{{ select(10) }}

• 15
• 31
• 32
• 63

---

11. C++ 中 priority_queue<int> 默认情况下，队首元素是？

{{ select(11) }}

• 最早加入的元素
• 最晚加入的元素
• 当前最小的元素
• 当前最大的元素

---

12. 下面代码片段的时间复杂度是？

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j *= 2)
        cout << i + j << endl;

{{ select(12) }}

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

---

13. 对含有 4096 个元素的有序数组进行二分查找，最坏情况下最多需要比较多少次？

{{ select(13) }}

• 11
• 12
• 13
• 14

---

14. 有 5 个字符，其出现频率分别为 $3, 4, 5, 6, 20$。若使用哈夫曼编码，则频率为 3 的字符编码长度为？

{{ select(14) }}

• 1
• 2
• 3
• 4

---

15. 在 C++ 表达式中，下列运算符通常优先级最高的是？

{{ select(15) }}

• =
• &&
• +
• *

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

阅读程序（一）

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

string cal(string s) {
    string t;

    for (int i = 0; i < s.size(); i++) {
        if (!t.empty() && t.back() == s[i])
            t.pop_back();
        else
            t += s[i];
    }

    if (t.empty())
        return "EMPTY";
    return t;
}

int main() {
    string s;
    cin >> s;
    cout << cal(s) << endl;
    return 0;
}

假设输入字符串非空，只包含小写字母。

判断题

---

16. 当输入为 abba 时，程序输出为 EMPTY。

{{ select(16) }}

• 正确
• 错误

---

17. 当输入为 aabbcc 时，程序输出为 EMPTY。

{{ select(17) }}

• 正确
• 错误

---

18. 若输入字符串长度为奇数，程序不可能输出 EMPTY。

{{ select(18) }}

• 正确
• 错误

单项选择题

---

19. 当输入为 abbaca 时，程序输出为？

{{ select(19) }}

• EMPTY
• ca
• ba
• aca

---

20. 设输入字符串长度为 $n$，该程序的时间复杂度为？

{{ select(20) }}

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

阅读程序（二）

#include <iostream>
using namespace std;

int c[15], dp[105];

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

    for (int i = 1; i <= n; i++)
        cin >> c[i];

    dp[0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = c[i]; j <= m; j++) {
            dp[j] += dp[j - c[i]];
        }
    }

    cout << dp[m] << endl;
    return 0;
}

假设 $1 \le n \le 10$，$1 \le m \le 100$，且所有 $c_i$ 均为正整数。

判断题

---

21. 程序执行过程中，$dp_0$ 的值始终为 1。

{{ select(21) }}

• 正确
• 错误

---

22. 程序统计的是使用若干个数凑出 $m$ 的有序方案数。

{{ select(22) }}

• 正确
• 错误

---

23. 若将第二层循环改为从 $m$ 到 $c_i$ 递减枚举，则每个 $c_i$ 最多只能使用一次。

{{ select(23) }}

• 正确
• 错误

单项选择题

---

24. 若输入为：

3 5
1 2 5

{{ select(24) }}

• 3
• 4
• 5
• 6

---

25. 若输入为：

2 6
2 3

{{ select(25) }}

• 1
• 2
• 3
• 4

---

26. 该程序的时间复杂度为？

{{ select(26) }}

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

阅读程序（三）

#include <iostream>
using namespace std;

int fa[105], dep[105];

int lca(int x, int y) {
    while (dep[x] > dep[y])
        x = fa[x];

    while (dep[y] > dep[x])
        y = fa[y];

    while (x != y) {
        x = fa[x];
        y = fa[y];
    }

    return x;
}

int main() {
    int n, x, y;
    cin >> n;

    fa[1] = 0;
    dep[1] = 1;

    for (int i = 2; i <= n; i++) {
        cin >> fa[i];
        dep[i] = dep[fa[i]] + 1;
    }

    cin >> x >> y;

    int z = lca(x, y);
    cout << z << " " << dep[x] + dep[y] - 2 * dep[z] << endl;

    return 0;
}

假设输入表示一棵以 1 为根的有根树，且对任意 $i > 1$，都有 $1 \le fa_i < i$。

判断题

---

27. 若输入的 $x$ 和 $y$ 相等，则程序输出的第二个数一定为 0。

{{ select(27) }}

• 正确
• 错误

---

28. 程序输出的第二个数表示 $x$ 到 $y$ 的简单路径上经过的边数。

{{ select(28) }}

• 正确
• 错误

---

29. 若将 dep[1] = 1 改为 dep[1] = 0，程序输出的第二个数一定不变。

{{ select(29) }}

• 正确
• 错误

单项选择题

---

30. 若输入为：

7
1 1 2 2 3 3
4 5

{{ select(30) }}

• 1 2
• 2 2
• 2 3
• 4 0

---

31. 若输入为：

7
1 1 2 2 3 3
4 6

{{ select(31) }}

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

---

32. 若输入为：

9
1 1 2 2 4 4 5 5
6 9

{{ select(32) }}

• 1 5
• 2 4
• 4 4
• 5 3

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

完善程序（一）

下面程序计算 $a^b \bmod p$，其中 $b$ 为非负整数，$p$ 为正整数。请补全程序。

#include <iostream>
using namespace std;

using ll = long long;

ll pw(ll a, ll b, ll p) {
    ll r = 1 % p;
    a %= p;

    while (b > 0) {
        if (①)
            r = ②;

        a = ③;
        b = ④;
    }

    return ⑤;
}

int main() {
    ll a, b, p;
    cin >> a >> b >> p;

    cout << pw(a, b, p) << endl;
    return 0;
}

---

33. ① 处应填？

{{ select(33) }}

• b == 0
• b % 2 == 1
• a % 2 == 1
• p % 2 == 1

---

34. ② 处应填？

{{ select(34) }}

• r + a
• r * a % p
• a * a % p
• b * a % p

---

35. ③ 处应填？

{{ select(35) }}

• a + a
• a * b % p
• a * a % p
• r * r % p

---

36. ④ 处应填？

{{ select(36) }}

• b - 1
• b + 1
• b * 2
• b / 2

---

37. ⑤ 处应填？

{{ select(37) }}

• a
• b
• p
• r

完善程序（二）

下面程序使用 Floyd 算法求无向带权图中两点之间的最短距离。若两点不连通，输出 -1。请补全程序。

#include <iostream>
using namespace std;

const int INF = 1000000000;

int d[105][105];

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = ①;
        }
    }

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        if (②)
            d[u][v] = d[v][u] = w;
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (③)
                    d[i][j] = ④;
            }
        }
    }

    int s, t;
    cin >> s >> t;

    if (⑤)
        cout << -1 << endl;
    else
        cout << d[s][t] << endl;

    return 0;
}

---

38. ① 处应填？

{{ select(38) }}

• i == j ? 0 : INF
• i == j ? INF : 0
• 0
• INF

---

39. ② 处应填？

{{ select(39) }}

• w > d[u][v]
• w < d[u][v]
• u == v
• d[u][v] == 0

---

40. ③ 处应填？

{{ select(40) }}

• d[i][j] < d[i][k] + d[k][j]
• d[i][k] + d[k][j] < d[i][j]
• d[i][k] < d[k][j]
• d[i][j] == INF

---

41. ④ 处应填？

{{ select(41) }}

• d[i][j]
• d[i][k]
• d[k][j]
• d[i][k] + d[k][j]

---

42. ⑤ 处应填？

{{ select(42) }}

• d[s][t] == 0
• d[s][t] == INF
• s == t
• d[s][t] < INF