2026 CCF CSP-S 第一轮 提高级 C++ 语言试题（模拟卷 C）

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

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

• 2
• 4
• 6
• 8

---

2. {{ select(2) }} 在平衡二叉搜索树（如 AVL 树）中，查找一个元素的时间复杂度为（ ）。

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

---

3. {{ select(3) }} 一个有 n 个顶点的无向连通图，要恰好成为一棵树，最少需要（ ）条边。

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

---

4. {{ select(4) }} 从 8 个不同的元素中选出 3 个并排成一列（考虑顺序），共有（ ）种不同的结果。

• 336
• 512
• 210
• 40320

---

5. {{ select(5) }} 表达式 x & (x - 1) 的作用是（ ）。

• 将 x 二进制表示中最低位的 1 变为 0
• 将 x 二进制表示中最高位的 1 变为 0
• 将 x 的所有二进制位取反
• 交换 x 的奇偶二进制位

---

6. {{ select(6) }} 在包含 n 个元素的有序数组中二分查找一个元素，时间复杂度为（ ）。

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

---

7. {{ select(7) }} 一棵完全二叉树共有 100 个结点，则这棵树的高度为（ ）。（根结点的深度为 1）

• 6
• 7
• 8
• 9

---

8. {{ select(8) }} 以下排序算法中，属于稳定排序的是（ ）。

• 快速排序
• 堆排序
• 归并排序
• 选择排序

---

9. {{ select(9) }} 拓扑排序适用的图是（ ）。

• 有向无环图
• 无向连通图
• 完全图
• 任意树

---

10. {{ select(10) }} $\gcd(84, 36)$ 的值为（ ）。

• 6
• 12
• 18
• 24

---

11. {{ select(11) }} 汉诺塔问题中，将 n 个盘子从一根柱子移到另一根柱子的最少移动次数为（ ）。

• $2^n - 1$
• $2^n$
• $2^{n+1} - 1$
• $n^2$

---

12. {{ select(12) }} KMP 字符串匹配算法的时间复杂度为（ ）。

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

---

13. {{ select(13) }} 在 8 位二进制补码表示中，-1 的补码是（ ）。

• 10000001
• 10000000
• 11111111
• 11111110

---

14. {{ select(14) }} 在最长公共子序列（LCS）的动态规划中，dp[i][j] 表示（ ）。

• 字符串 s1 的前 i 个字符与 s2 的前 j 个字符的最长公共子序列长度
• 字符串 s1 的第 i 个字符与 s2 的第 j 个字符是否相等
• 字符串 s1 的前 i 个字符与 s2 的前 j 个字符的最长公共子串长度
• 字符串 s1 与 s2 的公共前缀长度

---

15. {{ select(15) }} 在小端（little-endian）存储方式下，32 位整数 0x12345678 在内存中的第一个字节是（ ）。

• 0x12
• 0x78
• 0x34
• 0x56

---

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

程序 1

#include <iostream>
using namespace std;

int main() {
    int n, ans = 0;
    cin >> n;
    while (n > 0) {
        n /= 5;
        ans += n;
    }
    cout << ans << endl;
    return 0;
}

判断题

16. {{ select(16) }} 该程序计算的是 n! 中因子 5 的个数，即 n! 末尾 0 的个数。（ ）

• √ 正确
• × 错误

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

• √ 正确
• × 错误

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

• √ 正确
• × 错误

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

• √ 正确
• × 错误

选择题

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

• 20
• 24
• 25
• 30

21. {{ select(21) }} 该算法的时间复杂度为（ ）。

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

---

程序 2

#include <iostream>
using namespace std;

const int MAXN = 105, MAXV = 1005;
int w[MAXN], v[MAXN], dp[MAXV];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout << dp[m] << endl;
    return 0;
}

判断题

22. {{ select(22) }} 该程序解决的是 01 背包问题，求容量为 m 的背包能装下的最大总价值。（ ）

• √ 正确
• × 错误

23. {{ select(23) }} 内层循环从大到小遍历容量，是为了保证每个物品最多被选取一次。（ ）

• √ 正确
• × 错误

24. {{ select(24) }} 当输入为 "1 5\n3 4"（1 个物品，重量 3、价值 4，背包容量 5）时，程序的输出为 4。（ ）

• √ 正确
• × 错误

选择题

25. {{ select(25) }} 当输入为 "3 10\n2 3\n3 4\n4 5" 时，程序的输出为（ ）。

• 9
• 10
• 12
• 13

26. {{ select(26) }} 该算法的时间复杂度为（ ）。

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

27. {{ select(27) }} 若将内层循环改为 for (int j = w[i]; j <= m; j++)（从小到大遍历容量），程序变为求解（ ）。

• 01 背包问题
• 完全背包问题
• 多重背包问题
• 程序将编译错误

---

程序 3

#include <iostream>
using namespace std;

const int MAXN = 100005;
int a[MAXN], tmp[MAXN];
long long ans = 0;

void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
            ans += mid - i + 1;
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int i = l; i <= r; i++) a[i] = tmp[i];
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    mergeSort(0, n - 1);
    cout << ans << endl;
    return 0;
}

判断题

28. {{ select(28) }} 该程序使用归并排序的过程统计数组中的逆序对个数。（ ）

• √ 正确
• × 错误

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

• √ 正确
• × 错误

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

• √ 正确
• × 错误

选择题

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

• 6
• 8
• 10
• 15

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

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

33. {{ select(33) }} 若将 a[i] <= a[j] 改为 a[i] < a[j]，当输入为 "2\n1 1" 时，程序的输出为（ ）。

• 0
• 1
• 2
• 3

---

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

程序 1：Dijkstra 最短路

给定一个 n 个顶点 m 条边的带权有向图（边权非负），求从起点 s 出发到所有顶点的最短距离。使用朴素 Dijkstra 算法。试补全程序。

#include <iostream>
using namespace std;

const int MAXN = 105, INF = 1e9;
int g[MAXN][MAXN], dist[MAXN];
bool vis[MAXN];

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            g[i][j] = (i == j ? 0 : INF);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = min(g[u][v], w);
    }
    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[s] = ①;
    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;
        }
        if (u == -1 || dist[u] == INF) break;
        vis[u] = true;
        for (int v = 1; v <= n; v++) {
            if (②) {
                dist[v] = ③;
            }
        }
    }
    for (int i = 1; i <= n; i++) cout << dist[i] << " ";
    return 0;
}

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

• 0
• 1
• INF
• -1

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

• vis[v]
• !vis[v] && dist[v] > dist[u] + g[u][v]
• dist[v] > g[u][v]
• dist[v] < dist[u] + g[u][v]

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

• dist[u]
• dist[u] + g[u][v]
• g[u][v]
• dist[v] + g[u][v]

37. {{ select(37) }} 当输入为 "3 3 1\n1 2 5\n2 3 7\n1 3 10" 时，程序输出的 dist[3] 为（ ）。

• 10
• 12
• 15
• 17

38. {{ select(38) }} 该朴素 Dijkstra 算法的时间复杂度为（ ）。

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

---

程序 2：树状数组（Fenwick Tree）

实现树状数组，支持单点修改和区间求和查询。数组下标从 1 开始。试补全程序。

#include <iostream>
using namespace std;

const int MAXN = 100005;
int tree[MAXN], n;

int lowbit(int x) {
    return x & (-x);
}

void add(int x, int k) {
    while (x <= n) {
        tree[x] += k;
        x += ①;
    }
}

int sum(int x) {
    int res = 0;
    while (x > 0) {
        res += tree[x];
        x -= ②;
    }
    return res;
}

int main() {
    int m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        add(i, a);
    }
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) add(x, y);
        else cout << ③ << endl;
    }
    return 0;
}

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

• lowbit(x)
• lowbit(y)
• 1
• x

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

• lowbit(y)
• lowbit(x)
• 1
• y

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

• sum(y) - sum(x - 1)
• sum(x) - sum(y)
• sum(y) + sum(x)
• sum(y - x)

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

• 6
• 7
• 9
• 10

43. {{ select(43) }} 函数 lowbit(x) 的返回值是（ ）。

• x 二进制表示中最高位的 1 对应的值
• x 二进制表示中最低位的 1 对应的值
• x 的二进制位数
• x 的奇偶性