一、单项选择题（共15题，每题2分，共计30分）

1. 在内存储器中每个存储单元都被赋予一个唯一的序号，称为（ ）。

{{ select(1) }}

• 地址
• 序号
• 下标
• 编号

2. 二进制数 11 1011 1001 0111 和 01 0110 1110 1011 进行按位与运算的结果是（ ）。

{{ select(2) }}

• 01 0010 1000 1011
• 01 0010 1001 0011
• 01 0010 1000 0001
• 01 0010 1000 0011

3. 在 C++ 中，下面哪个关键字用于声明一个变量，其值不能被修改？（ ）

{{ select(3) }}

• unsigned
• const
• static
• mutable

4. 有 6 个元素，按照 6, 5, 4, 3, 2, 1 的顺序进入栈 S，请问下列哪个出栈序列是非法的（ ）。

{{ select(4) }}

• 5, 4, 3, 6, 1, 2
• 4, 5, 3, 1, 2, 6
• 3, 4, 6, 5, 2, 1
• 2, 3, 4, 1, 5, 6

5. 用 5 个权值 10, 12, 15, 20, 25 构造哈夫曼树，该树的带权路径长度是多少？（ ）

{{ select(5) }}

• 176
• 186
• 196
• 206

6. 已知二叉树的前序遍历为 [A, B, D, E, C, F, G]，中序遍历为 [D, B, E, A, F, C, G]，请问该二叉树的后序遍历结果是？（ ）

{{ select(6) }}

• [D, E, B, F, G, C, A]
• [D, E, B, F, G, A, C]
• [D, B, E, F, G, C, A]
• [D, B, E, F, G, A, C]

7. 二进制数 101.11 对应的十进制数是（ ）。

{{ select(7) }}

• 6.5
• 5.5
• 5.75
• 5.25

8. 假设有序表中有 1000 个元素，则用二分法查找元素 X 最多需要比较（ ）次。

{{ select(8) }}

• 25
• 10
• 7
• 1

9. 10 个三好学生名额分配到 7 个班级，每个班级至少有一个名额，一共有（ ）种不同的分配方案。

{{ select(9) }}

• 84
• 72
• 56
• 504

10. 考虑一个有向无环图，该图包含 4 条有向边：(1,2), (1,3), (2,4) 和 (3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序？（ ）

{{ select(10) }}

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

11. 考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。

{{ select(11) }}

• N − 1
• N
• N + 1
• N²

12. 已知 f[0] = 1, f[1] = 1，并且对于所有 n ≥ 2 有 f[n] = (f[n−1] + f[n−2]) % 7。那么 f[2025] 的值是多少？（ ）

{{ select(12) }}

• 2
• 4
• 5
• 6

13. 以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。

{{ select(13) }}

• 冒泡排序算法是稳定的
• 简单选择排序是稳定的
• 简单插入排序是稳定的
• 归并排序算法是稳定的

14. 在 C++ 中，执行 int x = 255; cout << (x & (x - 1)); 后，输出的结果是？（ ）

{{ select(14) }}

• 255
• 254
• 128
• 0

15. 有四个人要从 A 点坐一条船过河到 B 点，船一开始在 A 点。该船一次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为 1, 2, 4, 8，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短（ ）时间可以让四个人都过河到 B 点（包括从 B 点把船开回 A 点的时间）。

{{ select(15) }}

• 14
• 15
• 16
• 17

---

二、阅读程序

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

程序 1

#include <cstdio>
#include <cstring>
using namespace std;
char st[100];
int main() {
    scanf("%s", st);
    int n = strlen(st);
    for (int i = 1; i <= n; ++i) {
        if (n % i == 0) {
            char c = st[i - 1];
            if (c >= 'a')
                st[i - 1] = c - 'a' + 'A';
        }
    }
    printf("%s", st);
    return 0;
}

判断题

16. 输入的字符串只能由小写字母或大写字母组成。（ ）

{{ select(16) }}

• √
• ×

17. 若将第 8 行的 i = 1 改为 i = 0，程序运行时会发生错误。（ ）

{{ select(17) }}

• √
• ×

18. 若将第 8 行的 i <= n 改为 i * i <= n，程序运行结果不会改变。（ ）

{{ select(18) }}

• √
• ×

19. 若输入的字符串全部由大写字母组成，那么输出的字符串就跟输入的字符串一样。（ ）

{{ select(19) }}

• √
• ×

选择题

20. 若输入的字符串长度为 18，那么输入的字符串跟输出的字符串相比，至多有（ ）个字符不同。

{{ select(20) }}

• 18
• 6
• 10
• 1

21. 若输入的字符串长度为（ ），那么输入的字符串跟输出的字符串相比，至多有 36 个字符不同。

{{ select(21) }}

• 36
• 100000
• 1
• 128

---

程序 2

#include <iostream>
#include <vector>
using namespace std;
​
int compute(vector<int>& cost) {
    int n = cost.size();
    vector<int> dp(n + 1, 0);
    dp[1] = cost[0];
    for (int i = 2; i <= n; i++) {
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i - 1];
    }
    return min(dp[n], dp[n - 1]);
}
​
int main() {
    int n;
    cin >> n;
    vector<int> cost(n);
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    cout << compute(cost) << endl;
    return 0;
}

判断题

22. 当输入的 cost 数组为 {10, 15, 20} 时，程序的输出为 15。（ ）

{{ select(22) }}

• √
• ×

23. 如果将 dp[i-1] 改为 dp[i-3]，程序可能会产生编译错误。（ ）

{{ select(23) }}

• √
• ×

24. 程序总是输出 cost 数组中最小的元素。（ ）

{{ select(24) }}

• √
• ×

选择题

25. 当输入的 cost 数组为 {1, 100, 1, 1, 1, 100, 1, 1, 100, 1} 时，程序的输出为（ ）。

{{ select(25) }}

• 6
• 7
• 8
• 9

26. 如果输入的 cost 数组为 {10, 15, 30, 5, 5, 10, 20}，程序的输出为（ ）。

{{ select(26) }}

• 25
• 30
• 35
• 40

27. 若将代码中的 min(dp[i-1], dp[i-2]) + cost[i-1] 修改为 dp[i-1] + cost[i-2]，输入 cost 数组为 {5, 10, 15} 时，程序的输出为（ ）。

{{ select(27) }}

• 10
• 15
• 20
• 25

---

程序 3

#include <algorithm>
#include <iostream>
#include <limits>
​
using namespace std;
​
const int MAXN = 105;
const int MAXK = 105;
​
int h[MAXN][MAXK];
​
int f(int n, int m)
{
    if (m == 1) return n;
    if (n == 0) return 0;
​
    int ret = numeric_limits<int>::max();
    for (int i = 1; i <= n; i++)
        ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
    return ret;
}
​
int g(int n, int m)
{
    for (int i = 1; i <= n; i++)
        h[i][1] = i;
    for (int j = 1; j <= m; j++)
        h[0][j] = 0;
​
    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            h[i][j] = numeric_limits<int>::max();
            for (int k = 1; k <= i; k++)
                h[i][j] = min(
                    h[i][j],
                    max(h[i - k][j], h[k - 1][j - 1]) + 1);
        }
    }
​
    return h[n][m];
}
​
int main()
{
    int n, m;
    cin >> n >> m;
    cout << f(n, m) << endl << g(n, m) << endl;
    return 0;
}

假设输入的 n、m 均是不超过 100 的正整数。

判断题

28. 当输入为 7 3 时，第 19 行用来取最小值的 min 函数执行了 449 次。（ ）

{{ select(28) }}

• √
• ×

29. 输出的两行整数总是相同的。（ ）

{{ select(29) }}

• √
• ×

30. 当 m 为 1 时，输出的第一行总为 n。（ ）

{{ select(30) }}

• √
• ×

选择题

31. 算法 g(n, m) 最为准确的时间复杂度分析结果为（ ）。

{{ select(31) }}

• O(n^(3/2) m)
• O(nm)
• O(n²m)
• O(nm²)

32. 当输入为 20 2 时，输出的第一行为（ ）。

{{ select(32) }}

• 4
• 5
• 6
• 20

33. （4 分）当输入 100 100 时，输出的第一行为（ ）。

{{ select(33) }}

• 6
• 7
• 8
• 9

---

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

程序 1：最小区间覆盖

给出 n 个区间，第 i 个区间的左右端点是 [aᵢ, bᵢ]。现在要在这些区间中选出若干个，使得区间 [0, m] 被所选区间的并覆盖（即每一个 0 ≤ i ≤ m 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 n 和 m（1 ≤ n ≤ 5000, 1 ≤ m ≤ 10⁹）。

接下来 n 行，每行两个整数 aᵢ, bᵢ（0 ≤ aᵢ, bᵢ ≤ m）。

提示：使用贪心法解决这个问题。先用 O(n²) 的时间复杂度排序，然后贪心选择这些区间。

#include <iostream>
​
using namespace std;
​
const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];
​
void sort() // 排序
{
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (①)
            {
                segment t = A[j];
                ②
            }
}
​
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> A[i].a >> A[i].b;
    sort();
    int p = 1;
    for (int i = 1; i < n; i++)
        if (③)
            A[p++] = A[i];
    n = p;
    int ans = 0, r = 0;
    int q = 0;
    while (r < m)
    {
        while (④)
            q++;
        ⑤;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

34. ① 处应填（ ）。

{{ select(34) }}

• A[j].b > A[j-1].b
• A[j].a < A[j-1].a
• A[j].a > A[j-1].a
• A[j].b < A[j-1].b

35. ② 处应填（ ）。

{{ select(35) }}

• A[j+1] = A[j]; A[j] = t;
• A[j-1] = A[j]; A[j] = t;
• A[j] = A[j+1]; A[j+1] = t;
• A[j] = A[j-1]; A[j-1] = t;

36. ③ 处应填（ ）。

{{ select(36) }}

• A[i].b > A[p-1].b
• A[i].b < A[i-1].b
• A[i].b > A[i-1].b
• A[i].b < A[p-1].b

37. ④ 处应填（ ）。

{{ select(37) }}

• q + 1 < n && A[q+1].a <= r
• q + 1 < n && A[q+1].b <= r
• q < n && A[q].a <= r
• q < n && A[q].b <= r

38. ⑤ 处应填（ ）。

{{ select(38) }}

• r = max(r, A[q+1].b)
• r = max(r, A[q].b)
• r = max(r, A[q+1].a)
• q++

程序 2：Josephus 问题

有 n 个人围成一个圈，依次标号 0 至 n − 1。从 0 号开始，依次 0, 1, 0, 1, … 交替报数，报到 1 的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。

试补全模拟程序。

#include <cstdio>
using namespace std;
const int MAXN = 1000000;
int n;
bool a[MAXN];
int main() {
    scanf("%d", &n);
    int p = 0, c = 0, i = 0;
    while (①) {
        if (!a[i]) {
            if (②) {
                c++;
                a[i] = true;
                ③;
            }
            ④;
        }
        ⑤;
    }
    for (int j = 0; j < n; j++)
        if (!a[j]) printf("%d\n", j);
    return 0;
}

39. ① 处应填（ ）。

{{ select(39) }}

• i < n
• c < n
• i < n - 1
• c < n - 1

40. ② 处应填（ ）。

{{ select(40) }}

• i % 2 == 0
• i % 2 == 1
• p
• !p

41. ③ 处应填（ ）。

{{ select(41) }}

• i++
• i = (i + 1) % n
• c++
• p ^= 1

42. ④ 处应填（ ）。

{{ select(42) }}

• i++
• i = (i + 1) % n
• c++
• p ^= 1

43. ⑤ 处应填（ ）。

{{ select(43) }}

• i++
• i = (i + 1) % n
• c++
• p ^= 1