夜雨聆风CSP-S 提高组 · 初赛模拟
📝 2026 CSP-S初赛模拟试卷（完整真题·含答案详解）
关注公众号 → 私信「试卷文档」→ 获取PDF完整版
📌 写在前面
亲爱的家长、同学们好： 这份CSP-S（提高组）初赛模拟试卷，参考近年初赛命题趋势编写，难度略高于J组。 全卷共 20题，满分100分，考试时间90分钟。 提高组更注重算法理解和代码实现能力，建议同学们先复习基础算法再做题。
一、单项选择题（共15题，每题4分，共60分）
第1题（4分）
以下哪个排序算法在最好情况下的时间复杂度是 O(n)？
✅ 答案：D 解析：插入排序在最好情况（数组已排序）下，只需比较 n-1 次，时间复杂度 O(n)。其他算法最好情况均不为 O(n)。
第2题（4分）
在Dijkstra 算法中，使用优先队列（堆）优化后，时间复杂度为？
✅ 答案：C 解析：Dijkstra + 优先队列，每次取出最小距离节点 O(log V)，所有边松弛操作 O(E)，总时间复杂度 O((V+E) log V)，简写为 O(E log V)（稀疏图）。
第3题（4分）
下列关于动态规划的描述，正确的是？
✅ 答案：B 解析：最优子结构是动态规划的核心性质。A错误（可以用递推）；C错误（DP往往比贪心更准确）；D错误（最短路可以用DP思想解决）。
第4题（4分）
C++中，关于 vector 和 array 的区别，下列说法正确是？
vector 大小固定，array 大小动态 | vector 大小动态，array 大小固定 |
array 不能用下标访问 |
✅ 答案：B 解析：vector 是动态数组，大小可随元素增减而变化；array 是固定大小的数组容器。
第5题（4分）
在一棵有 n 个节点的AVL树中，高度最高约为？
✅ 答案：A 解析：AVL树是严格平衡的二叉搜索树，高度最高约为 1.44 log₂n，保证了 O(log n) 的查找效率。
第6题（4分）
下列关于最小生成树的描述，错误的是？
✅ 答案：C 解析：最小生成树不一定唯一，当图中有多条权值相同的边时，可能存在多棵最小生成树。
第7题（4分）
C++11 中引入的 auto 关键字的作用是？
✅ 答案：A 解析：auto 关键字让编译器自动推导变量类型，如 auto it = vec.begin(); 自动推导为 vector<int>::iterator。
第8题（4分）
在C++中，以下哪种情况会发生"切片"（slicing）问题？
✅ 答案：A 解析：对象切片发生在将派生类对象赋值给基类对象时，派生类特有的部分会被"切掉"，导致信息丢失。应通过指针或引用实现多态。
第9题（4分）
下列关于快排（QuickSort） pivot 选择的描述，正确的是？
✅ 答案：B 解析：随机选择 pivot 期望时间复杂度为 O(n log n)，且最坏情况出现概率极低。三数取中法是对快排的常见优化，不会增加时间复杂度。
第10题（4分）
在C++中，关于 const 成员函数，下列说法正确的是？
const 成员函数不能调用非 const 成员函数 |
const 成员函数不能访问成员变量 |
const 成员函数不能返回值 |
const 成员函数不能是虚函数 |
✅ 答案：A 解析：const 成员函数保证不修改对象状态，因此不能调用可能修改对象的非 const 成员函数。B/C/D 均错误。
第11题（4分）
C++中，关于 std::move() 的描述，正确的是？
std::move() 一定会发生内存拷贝 | std::move() 将左值转换为右值引用 |
std::move() 只能用于内置类型 | std::move() 之后原对象一定变为空 |
✅ 答案：B 解析：std::move() 实际上不进行任何移动操作，只是将左值转换为右值引用，使编译器优先选择移动构造函数或移动赋值运算符。
第12题（4分）
在NOI 系列比赛中，关于文件输入输出，下列说法正确的是？
scanf/printf 进行文件读写 |
freopen() 或命令行重定向来重定向输入输出 |
fstream 直接打开文件 |
✅ 答案：B 解析：NOI 系列比赛规定使用标准输入输出，通过 freopen("xxx.in", "r", stdin) 和 freopen("xxx.out", "w", stdout) 进行文件重定向。这是比赛规范。
第13题（4分）
下列关于红黑树的描述，正确的是？
✅ 答案：C 解析：红黑树插入或删除后可能违反红黑性质，需要通过旋转和重新着色来修复。红黑树不是严格平衡（A错误），但比AVL树插入删除更快（D错误）。
第14题（4分）
C++中，关于模板（template）的描述，错误的是？
✅ 答案：C 解析：模板类的成员函数不是虚函数（除非显式声明为 virtual）。模板是编译期多态，虚函数是运行期多态，两者机制不同。
第15题（4分）
在C++中，关于智能指针，下列说法正确的是？
unique_ptr 可以复制 | shared_ptr 通过引用计数管理内存 |
weak_ptr 会增加引用计数 |
✅ 答案：B 解析：shared_ptr 通过引用计数跟踪有多少个 shared_ptr 共享同一对象，计数为0时自动释放内存。unique_ptr 不可复制（A错误）；weak_ptr 不增加引用计数（C错误）。
二、阅读程序题（共3题，每题8分，共24分）
阅读程序第1题（8分）
C++ 代码（拓扑排序）：
#include <iostream> #include <vector> #include <queue> using namespace std; int main() { int n, m, i, u, v; cin >> n >> m; vector<vector<int>> adj(n+1); vector<int> indeg(n+1, 0); for (i = 0; i < m; i++) { cin >> u >> v; adj[u].push_back(v); indeg[v]++; } queue<int> q; for (i = 1; i <= n; i++) { if (indeg[i] == 0) q.push(i); } int cnt = 0; while (!q.empty()) { u = q.front(); q.pop(); cnt++; for (auto v : adj[u]) { indeg[v]--; if (indeg[v] == 0) q.push(v); } } cout << cnt << endl; return 0; }判断题：
💡 解析：本题实现Kahn拓扑排序算法。若存在环，则环上顶点入度始终不为0，不会被加入队列，cnt < n。时间复杂度 O(V+E)。
阅读程序第2题（8分）
#include <iostream> #include <cstring> using namespace std; const int MAXN = 105; int dp[MAXN][MAXN]; int main() { int n, W, i, j; int w[MAXN], v[MAXN]; cin >> n >> W; for (i = 1; i <= n; i++) { cin >> w[i] >> v[i]; } memset(dp, 0, sizeof(dp)); for (i = 1; i <= n; i++) { for (j = 0; j <= W; j++) { if (j >= w[i]) { dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]); } else { dp[i][j] = dp[i-1][j]; } } } cout << dp[n][W] << endl; return 0; }该程序解决的是什么问题？
✅ 答案：B 解析：这是经典的0-1背包问题动态规划解法。dp[i][j] 表示前 i 个物品，背包容量为 j 时的最大价值。w[i] 是重量，v[i] 是价值。
阅读程序第3题（8分）
#include <iostream> #include <set> using namespace std; int main() { set<int> s; int a[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3}; for (int x : a) s.insert(x); cout << s.size() << endl; auto it = s.find(5); if (it != s.end()) s.erase(it); for (auto it2 = s.begin(); it2 != s.end(); ++it2) { cout << *it2 << " "; } cout << endl; return 0; }程序输出的两行分别是？
✅ 答案：C 解析：set 自动去重并升序排序，数组有10个元素但去重后为 {1,2,3,4,5,6,9} 共7个，size()=7。删除5后输出 1 2 3 4 6 9。
三、完善程序题（共2题，每题8分，共16分）
完善程序第1题：用Dijkstra算法求最短路（8分）
#include <iostream> #include <vector> #include <queue> using namespace std; typedef pair<int, int> pii; const int INF = 0x3f3f3f3f; vector<vector<pii>> adj; vector<int> dist; void dijkstra(int s) { dist.assign(adj.size(), INF); dist[s] = 0; priority_queue<pii, vector<pii>, greater<pii>> pq; pq.push(make_pair(0, s)); while (!pq.empty()) { int d = pq.top().first; int u = pq.top().second; pq.pop(); if (d > dist[u]) continue; for (auto e : adj[u]) { int v = e.first, w = e.second; if (______(1)______) { dist[v] = dist[u] + w; ______(2)______; } } } } int main() { int n, m, i, u, v, w; cin >> n >> m; adj.resize(n+1); for (i = 0; i < m; i++) { cin >> u >> v >> w; adj[u].push_back(make_pair(v, w)); adj[v].push_back(make_pair(u, w)); // 无向图 } dijkstra(1); for (i = 2; i <= n; i++) { cout << dist[i] << " "; } return 0; }请在空缺处填入正确内容：
💡 解析：Dijkstra核心松弛操作：若经过 u 到达 v 的距离更短，则更新 dist[v] 并将新距离加入优先队列。
完善程序第2题：并查集实现（8分）
#include <iostream> using namespace std; const int MAXN = 1005; int parent[MAXN]; int find(int x) { if (______(1)______) { parent[x] = find(parent[x]); // 路径压缩 return parent[x]; } return x; } void unite(int x, int y) { int rx = find(x); int ry = find(y); if (rx != ry) { ______(2)______; } } int main() { int n, m, i, op, a, b; cin >> n >> m; for (i = 1; i <= n; i++) parent[i] = i; for (i = 0; i < m; i++) { cin >> op >> a >> b; if (op == 1) unite(a, b); else cout << (find(a) == find(b) ? "YES" : "NO") << endl; } return 0; }请在空缺处填入正确内容：
💡 解析：并查集 find() 函数查找根节点并进行路径压缩；unite() 将两个集合合并，这里简单将 rx 的父节点设为 ry。
📥 获取完整试卷 + 答案详解 PDF
以上为试卷部分题目预览。 完整试卷（含全部20题 + 详细答案与解析）已整理为PDF文档。 点击下方按钮，关注公众号后私信领取！
👉 关注公众号，私信「试卷文档」领取PDF
关注公众号：私信「试卷文档」获取PDF试卷
我们专注信奥赛（CSP/NOI）升学规划每周分享备考干货、政策解读、真题解析
私信「试卷文档」
#CSP-S #信奥赛 #提高组 #初赛模拟 #科技特长生