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

1. {{ select(1) }} 在 C++ 中，表达式 (6 & 3) ^ 5 的值是（ ）。

• 7
• 5
• 3
• 1

---

2. {{ select(2) }} 快速排序在最坏情况下的时间复杂度为（ ）。

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

---

3. {{ select(3) }} 哈希表在平均情况下的查找时间复杂度为（ ）。

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

---

4. {{ select(4) }} 从 10 个不同的候选人中选出 3 人，分别担任班长、学习委员、体育委员 3 个不同的职务，共有（ ）种不同的安排。

• 120
• 720
• 210
• 5040

---

5. {{ select(5) }} 一棵深度为 5 的满二叉树，其结点总数为（ ）。（根的深度为 1）

• 15
• 31
• 32
• 63

---

6. {{ select(6) }} 一个有 n 个顶点的有向完全图共有（ ）条边。

• $\frac{n(n-1)}{2}$
• $n(n-1)$
• $n^2$
• $n+1$

---

7. {{ select(7) }} 已知 $f(1) = 1$，$f(n) = n \times f(n-1)$，则 $f(5)$ 的值为（ ）。

• 15
• 24
• 120
• 125

---

8. {{ select(8) }} 堆排序在最坏情况下的时间复杂度为（ ）。

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

---

9. {{ select(9) }} 在 C++ 中，表达式 x << 2 等价于（ ）（不考虑溢出）。

• $x / 4$
• $x \times 2$
• $x \times 4$
• $x + 4$

---

10. {{ select(10) }} 已知一棵二叉树的前序遍历为 A B C，中序遍历为 B A C，则其后序遍历为（ ）。

• B C A
• C B A
• A C B
• B A C

---

11. {{ select(11) }} 拓扑排序适用于（ ）。

• 有向无环图
• 无向连通图
• 有向有环图
• 完全图

---

12. {{ select(12) }} 斐波那契数列 $f(0)=0, f(1)=1$，则 $f(8)$ 的值为（ ）。

• 13
• 21
• 34
• 55

---

13. {{ select(13) }} 优先队列通常使用（ ）这种数据结构实现。

• 数组
• 堆
• 链表
• 栈

---

14. {{ select(14) }} 完全背包问题与 01 背包问题的核心区别在于（ ）。

• 完全背包中每个物品可以重复选取
• 完全背包中每个物品最多选取一次
• 完全背包的背包容量更大
• 两种问题没有区别

---

15. {{ select(15) }} 下列关于 C++ 虚函数的说法，正确的是（ ）。

• 构造函数不能声明为虚函数
• 构造函数可以声明为虚函数
• 静态成员函数可以声明为虚函数
• 虚函数不能实现多态

---

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

程序 1

#include <iostream>
using namespace std;

int main() {
    int n, cnt = 0;
    cin >> n;
    while (n) {
        n = n & (n - 1);
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

判断题

16. {{ select(16) }} 该程序统计的是 n 的二进制表示中 1 的个数。（ ）

• √ 正确
• × 错误

17. {{ select(17) }} 当输入为 7 时，程序的输出为 3。（ ）

• √ 正确
• × 错误

18. {{ select(18) }} 当输入为 0 时，程序的输出为 1。（ ）

• √ 正确
• × 错误

19. {{ select(19) }} 当输入为 16 时，程序的输出为 1。（ ）

• √ 正确
• × 错误

选择题

20. {{ select(20) }} 当输入为 255 时，程序的输出为（ ）。

• 7
• 8
• 9
• 16

21. {{ select(21) }} 若将 n = n & (n - 1) 改为 n = n >> 1，程序变为统计（ ）。

• n 的二进制位数
• n 的二进制中 1 的个数
• n 的二进制中 0 的个数
• n 的奇偶性

---

程序 2

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

判断题

22. {{ select(22) }} 该程序计算的是 a 和 b 的最大公约数。（ ）

• √ 正确
• × 错误

23. {{ select(23) }} 当输入为 "12 8" 时，程序的输出为 4。（ ）

• √ 正确
• × 错误

24. {{ select(24) }} 当输入为 "7 13" 时，程序的输出为 1。（ ）

• √ 正确
• × 错误

选择题

25. {{ select(25) }} 当输入为 "48 36" 时，程序的输出为（ ）。

• 6
• 12
• 18
• 24

26. {{ select(26) }} 当输入为 "0 5" 时，程序的输出为（ ）。

• 0
• 5
• 1
• 无法确定

27. {{ select(27) }} 该算法（欧几里得算法）的时间复杂度为（ ）。

• $O(1)$
• $O(\log \min(a, b))$
• $O(\min(a, b))$
• $O(\max(a, b))$

---

程序 3

#include <iostream>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    int a[1005];
    for (int i = 0; i < n; i++) cin >> a[i];

    int l = 0, r = n - 1, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] == x) {
            ans = mid;
            break;
        } else if (a[mid] < x) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

判断题

28. {{ select(28) }} 该程序在升序数组 a 中查找 x，输出其下标（从 0 开始）；若找不到则输出 -1。（ ）

• √ 正确
• × 错误

29. {{ select(29) }} 当输入为 "5 3\n1 2 3 4 5" 时，程序的输出为 2。（ ）

• √ 正确
• × 错误

30. {{ select(30) }} 若数组 a 不是有序的，该程序的查找结果可能不正确。（ ）

• √ 正确
• × 错误

选择题

31. {{ select(31) }} 当输入为 "5 6\n1 2 3 4 5" 时，程序的输出为（ ）。

• -1
• 0
• 5
• 6

32. {{ select(32) }} 当输入为 "6 4\n1 3 4 4 6 8" 时，程序的输出为（ ）。

• 3
• 2
• 4
• -1

33. {{ select(33) }} 若将 l = mid + 1 改为 l = mid，r = mid - 1 改为 r = mid，当查找的元素不存在时，程序可能（ ）。

• 结果不变
• 陷入死循环
• 运行更快
• 编译错误

---

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

程序 1：最大连续子段和

给定一个长度为 n 的整数数组 a[1..n]，求它的最大连续子段和（至少包含一个元素）。使用 Kadane 算法。试补全程序。

#include <iostream>
using namespace std;

const int MAXN = 100005;
int a[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int ans = a[1], cur = a[1];
    for (int i = 2; i <= n; i++) {
        if (cur < 0) cur = ①;
        cur += a[i];
        if (cur > ans) ans = ②;
    }
    cout << ③ << endl;
    return 0;
}

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

• 0
• a[i]
• cur
• ans

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

• cur
• ans
• a[i]
• 0

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

• ans
• cur
• a[1]
• n

37. {{ select(37) }} 当输入为 "5\n1 -2 3 -1 4" 时，程序的输出为（ ）。

• 5
• 6
• 7
• 8

38. {{ select(38) }} 若数组中所有元素均为负数，程序的输出为（ ）。

• 0
• 数组中的最大元素（负数）
• 数组中的最小元素（负数）
• 无法确定

---

程序 2：高精度加法

给定两个正整数（可能超过 64 位整数的表示范围），用高精度加法计算它们的和并输出。试补全程序。

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

const int MAXN = 1005;
int a[MAXN], b[MAXN], c[MAXN];

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int la = s1.length(), lb = s2.length();
    for (int i = 0; i < la; i++) a[i] = s1[la - 1 - i] - '0';
    for (int i = 0; i < lb; i++) b[i] = s2[lb - 1 - i] - '0';

    int len = max(la, lb);
    for (int i = 0; i < len; i++) {
        c[i] += a[i] + b[i];
        if (c[i] >= 10) {
            c[i] -= 10;
            ①;
        }
    }
    if (②) len++;
    for (int i = len - 1; i >= 0; i--) cout << c[i];
    return 0;
}

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

• c[i + 1]++
• c[i]++
• a[i + 1]++
• b[i + 1]++

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

• c[len] > 0
• c[len] == 0
• c[len - 1] > 0
• a[len] > 0

41. {{ select(41) }} 当输入为 "99\n1" 时，程序的输出为（ ）。

• 100
• 99
• 101
• 110

42. {{ select(42) }} 当输入为 "123\n456" 时，程序的输出为（ ）。

• 579
• 576
• 585
• 597

43. {{ select(43) }} 若两个数字串的长度均为 n，该算法的时间复杂度为（ ）。

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