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

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

{{ select(1) }} 在 Linux 系统中，以下哪个命令用于列出当前目录下的所有文件（包括隐藏文件）？（ ）

• ls
• ls -a
• ls -l
• dir

---

{{ select(2) }} 以下排序算法中，在最坏情况下时间复杂度不是 $O(n^2)$ 的是（ ）。

• 冒泡排序
• 插入排序
• 快速排序（每次选取第一个元素作为基准）
• 归并排序

---

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

• 3
• 5
• 7
• 9

---

{{ select(4) }} 从 10 个不同的元素中选出 4 个组成一个子集，共有多少种不同的选法？（ ）

• 210
• 5040
• 420
• 120

---

{{ select(5) }} 在以下数据结构中，查找、插入、删除操作的平均时间复杂度均为 $O(\log n)$ 的是（ ）。

• 哈希表
• 平衡二叉搜索树（如 AVL 树）
• 单向链表
• 栈

---

{{ select(6) }} 已知递推关系 $T(1)=1$，$T(n)=2T(n/2)+n$，则 $T(n)$ 的渐近时间复杂度为（ ）。

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

---

{{ select(7) }} 一个有 $n$ 个顶点的无向连通图，要恰好成为一棵树，必须有（ ）条边。

• $n$
• $n-1$
• $n+1$
• $2n$

---

{{ select(8) }} 二分查找算法要求被查找的数组满足什么条件？（ ）

• 必须是有序的
• 必须是无序的
• 数组长度必须是 2 的幂
• 数组中的元素必须是整数

---

{{ select(9) }} 在模素数 $p$ 意义下，利用费马小定理，整数 $a$（$a \not\equiv 0 \pmod{p}$）的乘法逆元等于（ ）。

• $a^{p-2} \bmod p$
• $a^{p-1} \bmod p$
• $a \bmod p$
• $p-a$

---

{{ select(10) }} 设有一个最小堆（小根堆），堆中元素个数为 $n$。执行一次删除堆顶元素操作并恢复堆性质，需要的时间复杂度为（ ）。

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

---

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

• 6
• 7
• 8
• 10

---

{{ select(12) }} $n$ 个顶点的无向完全图含有（ ）条边。

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

---

{{ select(13) }} 入栈序列为 1, 2, 3, 4, 5, 6，以下哪个出栈序列不可能出现？（ ）

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

---

{{ select(14) }} 在 C++ 中，关于虚函数（virtual function）的描述，正确的是（ ）。

• 构造函数可以声明为虚函数
• 虚函数不能有默认参数
• 虚函数通过虚函数表（vtable）实现动态多态
• 静态成员函数可以声明为虚函数

---

{{ select(15) }} 下列关于动态规划（DP）的描述，错误的是（ ）。

• 动态规划要求问题具有最优子结构性质
• 动态规划通常使用递推或记忆化搜索实现
• 任何递归算法都可以转化为动态规划
• 动态规划通常以空间换取时间

---

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

程序 1

#include <iostream>
using namespace std;

int popcount(int x) {
    int cnt = 0;
    while (x) {
        x = x & (x - 1);
        cnt++;
    }
    return cnt;
}

int main() {
    int n, k;
    cin >> n >> k;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (popcount(i) == k) ans++;
    }
    cout << ans << endl;
    return 0;
}

判断题

{{ select(16) }} 函数 popcount(x) 计算的是 x 的二进制表示中 1 的个数。（ ）

• √ 正确
• × 错误

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

• √ 正确
• × 错误

{{ select(18) }} 若将 popcount 函数中的 while (x) 改为 while (x > 0)，程序的功能不变。（ ）

• √ 正确
• × 错误

{{ select(19) }} popcount(0) 的返回值为 1。（ ）

• √ 正确
• × 错误

选择题

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

• 3
• 4
• 5
• 10

{{ select(21) }} 当输入为 "15 2" 时，程序的输出为（ ）。

• 4
• 5
• 6
• 7

---

程序 2

#include <iostream>
using namespace std;

const int MAXN = 1005;
int a[MAXN], dp[MAXN][2];

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

    dp[1][0] = 0;
    dp[1][1] = a[1];
    for (int i = 2; i <= n; i++) {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        dp[i][1] = dp[i-1][0] + a[i];
    }
    cout << max(dp[n][0], dp[n][1]) << endl;
    return 0;
}

判断题

{{ select(22) }} 该程序解决的是"在数组中选取若干个元素，使得选取的元素互不相邻，求最大和"的问题。（ ）

• √ 正确
• × 错误

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

• √ 正确
• × 错误

{{ select(24) }} 若数组 a 中的元素全为负数，程序输出的最大值为 0。（ ）

• √ 正确
• × 错误

选择题

{{ select(25) }} 当输入为 "5\n3 7 2 8 4" 时，程序的输出为（ ）。

• 11
• 13
• 15
• 17

{{ select(26) }} 当输入为 "6\n5 1 4 9 2 6" 时，程序的输出为（ ）。

• 15
• 18
• 19
• 20

{{ select(27) }} 该程序的时间复杂度和空间复杂度分别为（ ）。

• $O(n)$, $O(n)$
• $O(n^2)$, $O(n)$
• $O(n)$, $O(1)$
• $O(2^n)$, $O(n)$

---

程序 3

#include <iostream>
using namespace std;

const int MOD = 1000000007;

long long fib(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long c = (a + b) % MOD;
        a = b;
        b = c;
    }
    return b;
}

long long solve(int n) {
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = (ans + fib(i)) % MOD;
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}

判断题

{{ select(28) }} 函数 fib(n) 计算的是第 n 个斐波那契数（定义 fib(0)=0, fib(1)=1）。（ ）

• √ 正确
• × 错误

{{ select(29) }} 当输入为 5 时，程序的输出为 12。（ ）

• √ 正确
• × 错误

{{ select(30) }} 函数 solve(n) 的返回值等于 fib(n+2) - 1（在模 MOD 意义下）。（ ）

• √ 正确
• × 错误

选择题

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

• 88
• 89
• 143
• 232

{{ select(32) }} 该程序的总体时间复杂度为（ ）。

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

{{ select(33) }} 若将 solve 函数中的循环改为 for (int i = 2; i <= n; i += 2)（只累加偶数项），当输入为 6 时，输出为（ ）。

• 12
• 20
• 33
• 54

---

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

程序 1：二分查找 upper_bound

实现 upper_bound 函数：在已排序的数组 a[0..n-1] 中，返回第一个大于目标值 x 的元素的位置（下标）。若所有元素均 ≤ x，则返回 n。试补全程序。

#include <iostream>
using namespace std;

int upper_bound(int a[], int n, int x) {
    int l = 0, r = ①;
    while (l < r) {
        int mid = (l + r) / 2;
        if (②) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return ③;
}

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

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

• n - 1
• n
• 0
• x

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

• a[mid] < x
• a[mid] <= x
• a[mid] > x
• a[mid] >= x

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

• l
• r
• l - 1
• mid

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

• 1
• 2
• 3
• 4

{{ select(38) }} 若数组中所有元素都小于或等于 x，函数返回（ ）。

• 0
• n
• n - 1
• -1

---

程序 2：拓扑排序（Kahn 算法）

给定一个 n 个顶点 m 条边的有向无环图（DAG），输出其拓扑排序序列。使用 Kahn 算法（基于入度的 BFS）。试补全程序。

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

const int MAXN = 100005;
vector<int> g[MAXN];
int indeg[MAXN];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        ①;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (②) q.push(i);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int v : g[u]) {
            ③;
            if (indeg[v] == 0) {
                ④;
            }
        }
    }
    return 0;
}

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

• indeg[u]++
• indeg[v]++
• indeg[u]--
• indeg[v]--

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

• indeg[i] == 0
• indeg[i] == 1
• indeg[i] > 0
• indeg[i] < n

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

• indeg[v]++
• indeg[v]--
• indeg[u]++
• indeg[u]--

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

• q.push(v)
• q.push(u)
• q.pop()
• continue

{{ select(43) }} 若输入为 "4 3\n1 2\n2 3\n1 4"，则程序的输出为（ ）。

• 1 2 4 3
• 1 2 3 4
• 1 4 2 3
• 以上两种都可能