🏠

🧪 CSP-J 原创模拟题自创

选择题 15 题 + 阅读 2 段 + 完善 2 段 · 难度对齐 CCF CSP-J 真题 · 限时挑战 120 分钟

📚 完整三大模块 🎯 选择题 30 分 📖 阅读 40 分 ✍️ 完善 30 分 ⏱ 总分 100 分
← 返回主页
正在载入题库…

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

本原创模拟卷覆盖 CSP-J 全部高频考点：计算机基础、组合数学、位运算、排序、树、图、动态规划、C++ 语法、STL、复杂度等。

1. 易 8 位补码 1000 0001 表示的十进制数是（ ）。
A. -1 B. -127 C. -128 D. 129
✅ 正确答案：B
解析：首位为 1 表示负数。补码 10000001 → 反码 01111110 → 原码 11111111 = -127。
速算法：-128 ~ 127 共 256 个数。最高位权值 -128，剩 1 → -128+1 = -127。
📌 补码记忆：8 位补码最小 -128（10000000），最大 +127（01111111）。
2. 易 表达式 3 << 2 | 1 的值是（ ）。
A. 11 B. 12 C. 13 D. 14
✅ 正确答案：C
解析：左移优先级高于按位或。
3 << 2 = 12 = 1100；12 | 1 = 1101 = 13。
3. 易 一棵有 n 个结点的完全二叉树，最后一层最少有（ ）个结点。
A. 1 B. 2 C. n - ⌊n/2⌋ D. 2⌊log₂n⌋
✅ 正确答案：A
解析：完全二叉树最后一层最少 1 个结点（前面所有层刚好填满）。例：n=8 填满 3 层；n=9 在第 4 层放 1 个。
4. 易 1 个字节（Byte）等于多少位（bit）？
A. 4 B. 8 C. 16 D. 32
✅ 正确答案：B
解析：1 字节 = 8 位。
5. 易 下列网络协议中属于应用层的是（ ）。
A. TCP B. IP C. HTTP D. ARP
✅ 正确答案：C
解析：OSI 7 层中：HTTP 属应用层；TCP 属传输层；IP、ARP 属网络层。
6. 中 6 个人排成一列，甲不在排头也不在排尾的方法数为（ ）。
A. 720 B. 480 C. 240 D. 120
✅ 正确答案：B（480）
解析：总排列 = 6! = 720；甲在排头：5! = 120；甲在排尾：5! = 120。
甲在"排头或排尾"用容斥：120 + 120 = 240（无重复，甲不可能同时在两端）。
所以甲既不在排头也不在排尾 = 720 − 240 = 480。
7. 中 求 1+2+...+100，下列哪种实现最高效？
A. for 循环累加 B. 递归累加 C. 高斯公式 n(n+1)/2 直接算 D. while 循环累加
✅ 正确答案：C
解析：C 是 O(1) 数学公式；A、D 是 O(n) 循环；B 递归 O(n) 且额外开销。
8. 中 关于栈和队列，下列说法错误的是（ ）。
A. 栈是后进先出（LIFO） B. 队列是先进先出（FIFO） C. 栈和队列都可以用数组实现 D. 栈的 push 在队尾
✅ 正确答案：D
解析：D 错。栈是 LIFO，push 在栈顶（即末端），但这是栈顶不是队尾（队尾是队列的概念）。C 正确，两者都可用数组或链表实现。
9. 中 表达式 int a = 5; a += a *= 2; 执行后 a 的值是？
A. 10 B. 15 C. 20 D. 30
✅ 正确答案：C
解析：从右往左：a *= 2 → a = 10；a += 10 → a = 20。
📌 结合方向：赋值类运算符（=、+=、*= 等）从右向左结合。
10. 中 对 100 万个有序数据查找某个值，下列哪种方法最合适？
A. 顺序查找 B. 二分查找 C. 哈希查找 D. 冒泡排序后查找
✅ 正确答案：B
解析：已有序且需要保持有序性 → 二分查找最优（O(log n)）；哈希需要重新构造哈希表，且无序也可以用。
11. 中 下列不属于面向对象三大特性的是（ ）。
A. 封装 B. 继承 C. 多态 D. 并发
✅ 正确答案：D
解析：OOP 三大特性：封装、继承、多态。并发是程序运行方式，不是 OOP 特性。
12. 中 一棵二叉树有 100 个叶子结点，至少有多少个度为 2 的结点？
A. 50 B. 99 C. 100 D. 101
✅ 正确答案：B
解析：二叉树 n₀ = n₂ + 1 ⇒ n₂ = n₀ - 1 = 99。
13. 中 下列 STL 容器中不允许随机访问的是（ ）。
A. vector B. deque C. list D. array
✅ 正确答案：C
解析：list 是双向链表，不支持下标访问，只能顺序遍历。其他三个都支持下标。
14. 中 一个有 6 个顶点的无向图，至少需要多少条边才能保证图连通？
A. 5 B. 6 C. 11 D. 15
✅ 正确答案：A
解析：连通图最少边数 = n - 1（生成树）= 5。
📌 公式：n 个顶点的连通无向图至少 n-1 条边（形成树）。
15. 难 用 Floyd 算法求任意两点最短路的时间复杂度是（ ）。
A. O(n) B. O(n²) C. O(n³) D. O(n log n)
✅ 正确答案：C
解析：Floyd 三重循环（k、i、j）→ O(n³)。
📌 对比：Dijkstra + 邻接表 O((n+m) log n)；Floyd O(n³)。
📌 模拟卷选择题答案： B C A B C B C D C B D B C A C
（共 15 题，每题 2 分，本模块满分 30 分）

二、阅读程序（共 2 段，40 分）

阅读 1：链表归并排序难

C++程序代码（点击行号可定位）
  1. 01
  2. 02// 阅读程序 1：链表归并排序（输出合并后的有序链表）
  3. 03struct Node {
  4. 04 int data;
  5. 05 Node* next;
  6. 06};
  7. 07
  8. 08Node* merge(Node* a, Node* b) {
  9. 09 if (!a) return b;
  10. 10 if (!b) return a;
  11. 11 Node* head = nullptr;
  12. 12 if (a->data <= b->data) {
  13. 13 head = a;
  14. 14 head->next = merge(a->next, b);
  15. 15 } else {
  16. 16 head = b;
  17. 17 head->next = merge(a, b->next);
  18. 18 }
  19. 19 return head;
  20. 20}
  21. 21
  22. 22void print(Node* head) {
  23. 23 while (head) {
  24. 24 cout << head->data << " ";
  25. 25 head = head->next;
  26. 26 }
  27. 27}
  28. 28
  29. 29int main() {
  30. 30 // 链表 a: 1 → 4 → 6
  31. 31 // 链表 b: 2 → 3 → 5 → 7
  32. 32 // 创建代码略
  33. 33 Node* a = ...;
  34. 34 Node* b = ...;
  35. 35 print(merge(a, b));
  36. 36}
  37. 37
▶ 输入样例 
链表 a：1 4 6
链表 b：2 3 5 7
（数据在 main 中硬编码，无标准输入）
▶ 输出样例 
1 2 3 4 5 6 7
🪜 分步模拟（递归合并 a=1→4→6 与 b=2→3→5→7）
1 执行L29~L34：构造两条升序链表 a = 1→4→6，b = 2→3→5→7
2 执行L35 调用 merge(a,b)；L12 比较 1≤2 成立，走 L13~L14：取 1，递归 merge(4→6, 2→3→5→7)
3 比较 4>2，走 L15~L17 else 分支：取 2，递归 merge(4→6, 3→5→7)
4 比较 4>3：取 3，递归 merge(4→6, 5→7)
5 比较 4≤5：取 4，递归 merge(6, 5→7)
6 比较 6>5：取 5，递归 merge(6, 7)
7 比较 6≤7：取 6，递归 merge(nullptr, 7)；L09 判 a 为空，直接返回 7 接在 6 后面
8 逐层回溯得到 1→2→3→4→5→6→7；执行L22~L27 print 依次输出 1 2 3 4 5 6 7
📤 程序输出？
✅ 答案：1 2 3 4 5 6 7
解析：merge 函数递归合并两个升序链表。每次取两链表头部较小者接上，整体复杂度 O(n₁+n₂)。
模拟过程：
a=1<4 vs b=2，取 1；递归 merge(4→6, 2→3→5→7)
a=4 vs b=2，取 2；递归 merge(4→6, 3→5→7)
a=4 vs b=3，取 3；递归 merge(4→6, 5→7)
a=4 vs b=5，取 4；递归 merge(6, 5→7)
a=6 vs b=5，取 5；递归 merge(6, 7)
a=6 vs b=7，取 6；递归 merge(nullptr, 7) → 返回 7
最终链：1→2→3→4→5→6→7
📌 归并排序时间复杂度：O(n log n)，稳定，适合链表（不需要随机访问）。
📊 merge 函数的时间复杂度？
A. O(min(n,m)) B. O(max(n,m)) C. O(n+m) D. O(n×m)
✅ 答案：C
解析：每次比较要么 a 后移要么 b 后移，总比较次数 = n+m。所以 O(n+m)。

阅读 2：字符串哈希（子串判重）中

C++程序代码（点击行号可定位）
  1. 01
  2. 02// 阅读程序 2：统计字符串 s 中长度为 k 的不同子串数
  3. 03// 用滚动哈希：hash[i] = hash[i-1]*131 + (s[i]-'a'+1)
  4. 04// 子串 s[i..i+k-1] 的哈希 = hash[i+k-1] - hash[i-1] * 131^k
  5. 05typedef long long ll;
  6. 06
  7. 07int countUniqueSubstrings(string s, int k) {
  8. 08 int n = s.length();
  9. 09 vector<ll> h(n);
  10. 10 for (int i = 0; i < n; ++i) {
  11. 11 h[i] = (i == 0 ? 0 : h[i-1] * 131) + (s[i] - 'a' + 1);
  12. 12 }
  13. 13 set<ll> seen;
  14. 14 for (int i = 0; i + k <= n; ++i) {
  15. 15 ll subHash = h[i + k - 1];
  16. 16 if (i > 0) subHash -= h[i - 1] * pow(131, k);
  17. 17 seen.insert(subHash);
  18. 18 }
  19. 19 return seen.size();
  20. 20}
  21. 21
▶ 输入样例 
s = "abcabc"
k = 2
▶ 输出样例 
3
🪜 分步模拟（s="abcabc"，k=2，字符编码 a=1,b=2,c=3）
1 执行L08~L12 算前缀哈希：h[0]=1（a），h[1]=1×131+2=133，h[2]=133×131+3=17426，后续同理
2 执行L13：建空集合 seen = {}
3 执行L14~L17，i=0：subHash = h[1] = 133（子串 "ab"）→ 插入 seen
4 i=1：subHash = h[2] − h[0]×131² = 17426 − 1×17161 = 265（"bc"）→ 插入 seen
5 i=2：subHash = h[3] − h[1]×131² = 394（"ca"）→ 插入 seen，此时 seen={133,265,394}
6 i=3：subHash = 133（"ab" 重复）→ set 自动去重，不增加元素
7 i=4：subHash = 265（"bc" 重复）→ 同样被去重；循环结束（i=5 时 i+k>n 不成立）
8 执行L19：返回 seen.size() = 3，即不同子串 {ab, bc, ca} 共 3 个
📤 当 s="abcabc", k=2 时，函数返回？
✅ 答案：3
解析：长度为 2 的子串有 "ab", "bc", "ca", "ab", "bc"。去去后："ab", "bc", "ca" 共 3 个不同子串。
📌 滚动哈希：字符串哈希可 O(1) 求任意子串哈希，常用于去重、匹配。注意：存在哈希冲突风险，实际场景需双模或加随机种子。
📊 countUniqueSubstrings 的时间复杂度？
A. O(n) B. O(n log n) C. O(n²) D. O(n log² n)
✅ 答案：B
解析：遍历 O(n)，每次 set 插入 O(log n)（红黑树），总 O(n log n)。用 unordered_set 可降至 O(n) 均摊。
📌 阅读程序答题技巧：① 先通读程序，画出框架；② 手动模拟最小输入；③ 关注边界条件（空、单个、极端）。

三、完善程序（共 2 段，每段 5 空，每空 3 分，共 30 分）

完善 1：求区间第 K 大（小顶堆 + 二分答案）难

C++程序代码（带 ①~② 填空标记）
  1. 01
  2. 02// 完善程序 1：在数组 a[1..n] 中求第 k 大的数
  3. 03// 思路：用小顶堆维护最大的 k 个数，堆顶就是第 k 大
  4. 04#include <queue>
  5. 05using namespace std;
  6. 06
  7. 07int findKthLargest(int a[], int n, int k) {
  8. 08 priority_queue<int, vector<int>, greater<int>> pq;
  9. 09 for (int i = 0; i < n; ++i) {
  10. 10 pq.push(a[i]);
  11. 11 if (①) pq.pop();
  12. 12 }
  13. 13 ②;
  14. 14}
  15. 15
▶ 输入样例 
a[] = {3, 2, 1, 5, 6, 4}
n = 6, k = 2
▶ 输出样例 
5
🪜 分步模拟（填对 ①② 后，a={3,2,1,5,6,4}，k=2）
1 执行L09~L10：push 3 → 堆 {3}；push 2 → 堆 {2,3}，size=2 未超过 k，不弹出
2 push 1 → 堆 {1,2,3}；L11 ① pq.size() > k 成立（3>2）→ pop 堆顶最小值 1 → 堆 {2,3}
3 push 5 → {2,3,5}，size=3>2 → pop 2 → 堆 {3,5}
4 push 6 → {3,5,6} → pop 3 → 堆 {5,6}
5 push 4 → {4,5,6} → pop 4 → 堆 {5,6}，循环结束
6 执行L13 ② return pq.top()：堆里是最大的 2 个数 {5,6}，堆顶 5 即第 2 大 → 输出 5
① ② 处的正确选项
思路：维护一个大小 ≤ k 的小顶堆。当堆中元素超过 k 个时弹出最小的；最后堆顶就是第 k 大。

空ABCD
①pq.size() > kpq.size() == ki > ka[i] < pq.top()
②return pq.top();return pq.size();return k;return a[k-1];

正确答案：① A ② A

解析：
  • ① 当堆中元素数超过 k 时弹出最小值（堆顶），保持堆里是当前最大的 k 个数。选 A。
  • ② 遍历结束后堆顶就是第 k 大元素（因为堆里是最大的 k 个，最小的就是第 k 大）。选 A。
📌 时间复杂度：O(n log k)，比排序 O(n log n) 更快，尤其当 k 较小时。

完善 2：拓扑排序（判断有向无环图）中

C++程序代码（带 ①~④ 填空标记）
  1. 01
  2. 02// 完善程序 2：判断有向图是否有环（拓扑排序）
  3. 03// 入度为 0 的节点入队；每次取出入度为 0 的节点，删除其所有出边
  4. 04#include <vector>
  5. 05#include <queue>
  6. 06using namespace std;
  7. 07
  8. 08int n; // 顶点数
  9. 09vector<int> adj[1000]; // 邻接表
  10. 10int inDegree[1000]; // 入度
  11. 11
  12. 12bool hasCycle() {
  13. 13 queue<int> q;
  14. 14 for (int i = 0; i < n; ++i) {
  15. 15 if (①) q.push(i);
  16. 16 }
  17. 17 int cnt = 0;
  18. 18 while (!q.empty()) {
  19. 19 int u = q.front(); q.pop();
  20. 20 cnt++;
  21. 21 for (int v : adj[u]) {
  22. 22 ②;
  23. 23 if (③) q.push(v);
  24. 24 }
  25. 25 }
  26. 26 return ④;
  27. 27}
  28. 28
▶ 输入样例 
n = 4
边：0→1，0→2，1→3，2→3
（有向无环图 DAG）
▶ 输出样例 
0  // hasCycle() = false，图中无环
🪜 分步模拟（填对 ①~④ 后，4 个点 4 条边的 DAG）
1 执行L14~L15 ① inDegree[i] == 0：入度为 inDegree = {0:0, 1:1, 2:1, 3:2}，只有顶点 0 入度为 0 → q = {0}
2 执行L18~L20：取出 u=0，cnt=1
3 执行L21~L23 ② inDegree[v]--：邻居 1、2 的入度都 1→0，③ 判入度为 0 成立 → 入队，q = {1, 2}
4 取 u=1，cnt=2；邻居 3 的入度 2→1，不为 0 不入队
5 取 u=2，cnt=3；邻居 3 的入度 1→0 → 入队
6 取 u=3，cnt=4；无邻居，队空退出循环
7 执行L26 ④ cnt < n：4 < 4 不成立 → 返回 false（0，无环）
8 反例：若再加一条边 3→0 构成环，4 个点入度都 ≥ 1，队列始终为空，cnt=0 < n=4 → 返回 true（1，有环）
① ② ③ ④ 处的正确选项
思路：Kahn 算法。所有入度为 0 的点入队；依次弹出，邻居入度 -1 后若为 0 则入队。若处理点数 cnt < n 则有环。

空ABCD
①inDegree[i] == 0inDegree[i] > 0i == 0adj[i].empty()
②inDegree[v]++inDegree[v]--inDegree[v] = 0inDegree[u]--
③inDegree[v] == 0inDegree[v] > 0v == uadj[v].empty()
④cnt == ncnt < ncnt > nq.empty()

正确答案：① A ② B ③ A ④ B

解析：
  • ① 把所有入度为 0 的点入队，选 A。
  • ② 处理边 u→v 时把 v 的入度 -1，选 B。
  • ③ 入度减为 0 时 v 入队，选 A。
  • ④ 若 cnt < n 说明还有点没被处理（有环），返回 true；否则 false。选 B。
📌 应用：编译依赖、课程安排、任务调度都用到拓扑排序。
📌 完善程序答题技巧：① 先读懂程序要解决的算法问题；② 看每个空前后的代码语义；③ 把 4 个选项代入，看哪个能让程序跑通。

📌 本模拟卷为原创题目，用于练习和自测，建议限时 120 分钟完整作答

解析仅供参考，如有疑问欢迎讨论