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

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

1. {{ select(1) }} 以下关于 C++ 编译过程的描述，正确的是（ ）。

• 预处理在编译之前执行
• 链接在编译之前执行
• 编译生成的是源代码文件
• 预处理生成的是可执行文件

---

2. {{ select(2) }} 一个 32 位 CPU 的地址总线宽度为 32 位，其可寻址的最大内存空间为（ ）。

• 2GB
• 4GB
• 8GB
• 16GB

---

3. {{ select(3) }} 以下哪种数据结构不适合用于实现优先队列？（ ）

• 二叉堆
• 平衡二叉搜索树
• 单向链表
• 斐波那契堆

---

4. {{ select(4) }} 有 5 本不同的数学书和 3 本不同的物理书，将它们排成一排，要求所有数学书必须相邻。问有多少种不同的排列方式？（ ）

• 1440
• 2880
• 4320
• 5760

---

5. {{ select(5) }} 在一个无向图中，所有顶点的度数之和为 24，则该图有（ ）条边。

• 6
• 12
• 24
• 48

---

6. {{ select(6) }} 以下排序算法中，在最坏情况下时间复杂度为 $O(n \log n)$ 的是（ ）。

• 冒泡排序
• 直接插入排序
• 归并排序
• 选择排序

---

7. {{ select(7) }} 函数 int f(int n) { return n == 0 ? 0 : n + f(n - 1); }，f(5) 的返回值为（ ）。

• 25
• 15
• 120
• 10

---

8. {{ select(8) }} 中缀表达式 $a + b \times c - (d + e)$ 对应的后缀表达式（逆波兰表示法）为（ ）。

• a b c * + d e + -
• a b + c * d e + -
• a b c + * d e - +
• a b c * + d e - +

---

9. {{ select(9) }} C++ STL 中的 sort 函数，其平均时间复杂度为（ ）。

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

---

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

• D E B F C A
• D B E F C A
• E D B F C A
• D E F B C A

---

11. {{ select(11) }} 一个有 $n$ 个顶点 $m$ 条边的有向无环图（DAG），其拓扑排序的个数至少为（ ）。

• 0
• 1
• $n$
• $m$

---

12. {{ select(12) }} 十六进制数 1A3F 转换为十进制数是（ ）。

• 6719
• 6720
• 6655
• 6735

---

13. {{ select(13) }} 同时掷两个公平的六面骰子，点数之和为 7 的概率是（ ）。

• $\frac{1}{6}$
• $\frac{1}{12}$
• $\frac{1}{9}$
• $\frac{5}{36}$

---

14. {{ select(14) }} 在 64 位系统中，以下结构体 sizeof 的值最可能是（ ）。

struct S {
    char a;
    int b;
    short c;
};

• 7
• 8
• 12
• 16

---

15. {{ select(15) }} 以下哪种算法策略通常用于求解"0-1 背包问题"？（ ）

• 贪心算法
• 动态规划
• 分治算法
• 以上都不能求解

---

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

程序 1

#include <iostream>
using namespace std;

const int MOD = 10007;

int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    int x, y;
    cin >> x >> y;
    cout << qpow(x, y) << endl;
    return 0;
}

判断题

16. {{ select(16) }} 该程序计算的是 $x^y \bmod 10007$ 的值。（ ）

• √ 正确
• × 错误

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

• √ 正确
• × 错误

18. {{ select(18) }} 函数 qpow 的时间复杂度是 $O(\log y)$。（ ）

• √ 正确
• × 错误

选择题

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

• 243
• 245
• 125
• 15

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

• 2401
• 343
• 49
• 28

21. {{ select(21) }} 若将 MOD 改为 7，输入为 "3 3" 时，程序的输出为（ ）。

• 2
• 6
• 1
• 4

---

程序 2

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 105;
int g[N][N], dist[N];
int n, m;

int bfs(int s, int t) {
    memset(dist, -1, sizeof(dist));
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == t) return dist[u];
        for (int v = 1; v <= n; v++) {
            if (g[u][v] && dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return -1;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u][v] = g[v][u] = 1;
    }
    cout << bfs(1, n) << endl;
    return 0;
}

判断题

22. {{ select(22) }} 该程序计算的是从顶点 1 到顶点 n 的最短路径长度（边数）。（ ）

• √ 正确
• × 错误

23. {{ select(23) }} 输入的图必须是无向连通图，否则程序一定不能正确运行。（ ）

• √ 正确
• × 错误

24. {{ select(24) }} 该 BFS 实现的时间复杂度是 $O(n + m)$。（ ）

• √ 正确
• × 错误

选择题

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

• 2
• 3
• 4
• -1

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

• 1
• 2
• -1
• 0

27. {{ select(27) }} 若将 if (g[u][v] && dist[v] == -1) 改为 if (g[u][v])（去掉 dist 检查），以下说法正确的是（ ）。

• 程序正常运行，结果不变
• 程序可能死循环或得到错误的最短距离
• 程序的输出始终为 0
• 程序时间复杂度降低

---

程序 3

#include <iostream>
using namespace std;

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

int main() {
    int n, a[1000];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int x;
    cin >> x;
    cout << f(a, n, x) << endl;
    return 0;
}

判断题

28. {{ select(28) }} 函数 f 实现的是 lower_bound 功能：返回数组中第一个大于等于 x 的元素的下标。（ ）

• √ 正确
• × 错误

29. {{ select(29) }} 如果数组中所有元素都小于 x，函数 f 返回 0。（ ）

• √ 正确
• × 错误

30. {{ select(30) }} 函数 f 要求数组 a 必须是升序排列的。（ ）

• √ 正确
• × 错误

选择题

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

• 1
• 2
• 3
• 4

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

• -1
• 0
• 4
• 5

33. {{ select(33) }} 若数组中有重复元素，输入为 "6\n1 2 2 2 3 4\n2"，程序的输出为（ ）。

• 1
• 2
• 3
• 0

---

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

程序 1：并查集（Union-Find）

实现并查集数据结构，支持合并两个集合和查询两个元素是否属于同一集合的操作。使用路径压缩优化。试补全程序。

#include <iostream>
using namespace std;

const int MAXN = 10005;
int fa[MAXN];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = ①;
}

void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) {
        ②;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) ③;
    for (int i = 0; i < m; i++) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            merge(x, y);
        } else {
            if (④) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
    return 0;
}

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

• find(x)
• find(fa[x])
• x
• fa[fa[x]]

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

• fa[fx] = fy
• fa[fy] = fx
• fa[x] = y
• fx = fy

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

• fa[i] = 0
• fa[i] = i
• fa[i] = -1
• fa[i] = n

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

• find(x) != find(y)
• find(x) == find(y)
• x == y
• fa[x] == fa[y]

38. {{ select(38) }} find 函数中使用了哪种优化技术？（ ）

• 按秩合并
• 路径压缩
• 启发式合并
• 未使用任何优化

---

程序 2：最长公共子序列（LCS）

给定两个字符串 s1 和 s2，求它们的最长公共子序列的长度。试补全程序。

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

const int MAXN = 1005;
int dp[MAXN][MAXN];

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int n = s1.length(), m = s2.length();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = ①;
            } else {
                dp[i][j] = ②;
            }
        }
    }
    cout << ③ << endl;
    return 0;
}

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

• dp[i-1][j] + 1
• dp[i][j-1] + 1
• dp[i-1][j-1] + 1
• dp[i-1][j-1]

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

• max(dp[i-1][j], dp[i][j-1])
• min(dp[i-1][j], dp[i][j-1])
• dp[i-1][j-1]
• dp[i-1][j] + dp[i][j-1]

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

• dp[n][m]
• dp[n-1][m-1]
• max(dp[n][m], dp[n-1][m-1])
• dp[0][0]

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

• 2
• 3
• 4
• 5

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

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