夜雨聆风本模拟题基于近十年CSP-J初赛命题规律编制，覆盖计算机基础、进制运算、数据结构、图论、组合数学等高频考点，整理的过程中难免有误，如有发现之处，及时反馈，我们将及时更新，谢谢大家。
如果有需要原题的留言，分享给你们。
一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
1. 在C++中，以下哪个数据类型不属于基本数据类型？（ ）
A. int
B. float
C. char
D. struct
答案：D
解析：struct是复合数据类型，由基本数据类型组合而成。int、float、char均为C++基本数据类型。
2. 二进制数 1101.11 对应的十进制数是（ ）。
A. 13.75
B. 13.5
C. 14.75
D. 13.25
答案：A
解析：整数部分1101₂ = 1×8+1×4+0×2+1×1 = 13；小数部分 0.11₂ = 1×2⁻¹+1×2⁻² = 0.5+0.25 = 0.75。
3. 在计算机中，1MB等于多少二进制位（bit）？（ ）
A. 1,000,000
B. 1,048,576
C. 8,000,000
D. 8,388,608
答案：D
解析：1MB = 1024KB，1KB = 1024Byte，1Byte = 8bit，因此 1MB = 1024×1024×8 = 8,388,608 bit。
4. 以下哪个选项不是操作系统？（ ）
A. Linux
B. Windows
C. Android
D. Notepad
答案：D
解析：Notepad是Windows系统中的文本编辑软件，不是操作系统。Linux、Windows、Android均为操作系统。
5. 在无向图中，所有顶点的度数之和等于（ ）。
A. 图的边数
B. 图的边数的两倍
C. 图的顶点数
D. 图的顶点数的两倍
答案：B
解析：每条边连接两个顶点，为这两个顶点各贡献1度，因此所有顶点度数之和 = 2×边数。
6. 已知二叉树的前序遍历为 A B D E C F G，中序遍历为 D B E A F C G，该二叉树的后序遍历是（ ）。
A. D E B F G C A
B. D E B F G A C
C. D B E F G C A
D. D E B G F C A
答案：A
解析：由前序遍历知根为A，由中序遍历知左子树为DBE、右子树为FCG，递归还原可得后序遍历为DEBFGCA。
7. 入栈序列为 1, 2, 3, 4, 5, 6（1先入栈），以下哪个出栈序列是不可能实现的？（ ）
A. 6 5 4 3 2 1
B. 1 6 5 4 3 2
C. 2 4 6 5 3 1
D. 1 3 5 2 4 6
答案：D
解析：D选项中，1出栈后，2入栈。3入栈后3出栈，4、5入栈后5出栈。此时栈中为2、4，4在2上方，接下来要出栈2是不可能的。
8. 有5个男生和3个女生站成一排，规定3个女生必须相邻，共有多少种不同的排列方式？（ ）
A. 4320
B. 5040
C. 3600
D. 2880
答案：A
解析：捆绑法。将3个女生视为一个整体，与5个男生共6个元素排列：A(6,6)=720；3个女生内部排列：A(3,3)=6。总数 = 720×6 = 4320。
9. 若有序表中有1000个元素，用二分查找法查找某元素，最多需要比较（ ）次。
A. 25
B. 10
C. 7
D. 1
答案：B
解析：二分查找最多比较次数为⌈log₂(1000)⌉ = 10（因为2⁹=512，2¹⁰=1024，1000介于两者之间，向上取整为10）。
10. 计算机中，编译程序的主要功能是（ ）。
A. 直接执行源代码
B. 将源代码转换为机器代码
C. 进行代码调试
D. 管理程序运行时的内存
答案：B
解析：编译器将高级语言编写的源代码翻译成计算机可以直接执行的机器代码。
11. 后缀表达式 "6 2 3 + - 3 8 2 / + * 2 ^ 3 +" 对应的中缀表达式是（ ）。
A. ((6 - (2 + 3)) × (3 + 8/2))² + 3
B. 6 - 2 + 3 × 3 + 8/2² + 3
C. (6 - (2 + 3)) × ((3 + 8/2)²) + 3
D. 6 - ((2 + 3) × (3 + 8/2))² + 3
答案：A
解析：后缀表达式转为中缀表达式，按运算符出现顺序逐步构建。6 2 3 + - 表示 6-(2+3)，3 8 2 / + 表示 3+8/2，两结果相乘后再平方，最后加3。
12. 设有字符集{a,b,c,d,e,f}，对应频率分别为5%、9%、12%、13%、16%、45%，以下哪组是这些字符对应的哈夫曼编码？（ ）
A. 1111, 1110, 101, 100, 110, 0
B. 1010, 1001, 1000, 011, 010, 00
C. 000, 001, 010, 011, 10, 11
D. 1010, 1011, 110, 111, 00, 01
答案：A
解析：哈夫曼编码中，频率越高的字符编码越短。f频率45%最高应取最短码，排除B（f为00不是最短）和D。根据哈夫曼树构造规则验证可得A为正确编码。
13. 有向无环图有4条有向边：(1,2)、(1,3)、(2,4)、(3,4)，以下哪个是该图的一个有效拓扑排序？（ ）
A. 4, 2, 3, 1
B. 1, 2, 3, 4
C. 1, 2, 4, 3
D. 2, 1, 3, 4
答案：B
解析：拓扑排序要求每条有向边(u,v)中u必须排在v之前。边(1,2)要求1在2前，边(1,3)要求1在3前，边(2,4)和(3,4)要求2、3在4前。B满足所有条件。
14. 一个班级有10个男生和12个女生，要选出一个3人小组且至少包含1个女生，共有多少种选择方式？（ ）
A. 1420
B. 1770
C. 1540
D. 2200
答案：A
解析：总人数22人，任选3人共C(22,3)=1540种。全是男生的选法为C(10,3)=120种。至少1女 = 1540-120 = 1420种。
15. 以下关于栈的叙述，正确的是（ ）。
A. 栈是一种先进先出（FIFO）的数据结构
B. 栈只能在栈底进行插入和删除操作
C. 栈可以用数组或链表实现
D. 栈中元素不能随机访问
答案：C
解析：栈是先进后出（LIFO）结构，插入删除在栈顶进行，故A、B错误。栈可以用数组或链表实现，C正确。D本身表述正确但不如C更全面准确，单选题选C。
二、阅读程序（共3题，每题约13-14分，共计40分）
说明：阅读程序题包含判断题和选择题。判断题正确填√，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分。程序输入不超过数组或字符串定义的范围。
程序一
#include<iostream>#include<cstring>using namespace std;char s[100];int n;intmain(){cin >> s;n = strlen(s);for (int i = 0; i < n; i++) {if (i % 2 == 0) {if (s[i] >= 'a' && s[i] <= 'z')s[i] = s[i] - 'a' + 'A';} else {if (s[i] >= 'A' && s[i] <= 'Z')s[i] = s[i] - 'A' + 'a';}}cout << s << endl;return 0;}
判断题
16. 若输入的字符串为"HelloWorld"，输出结果为"hEllOwOrlD"（）
17. 若输入的字符串全部由小写字母组成，则输出结果中奇数位置的字符保持不变（）
18. 程序运行结束后，变量i的值一定等于n。（ ）
单选题
19. 若输入的字符串为"abcde"，则输出为（ ）。
A. AbCdE
B. aBcDe
C. AbCdE
D. aBcDe
20. 若输入的字符串长度为10且全部为小写字母，则输出结果中大写字母的个数为（）
A. 5
B. 10
C. 0
D. 无法确定
# 程序二
#include<iostream>using namespace std;int a[100];int n;intf(int x){int cnt = 0;while (x > 0) {if (x % 2 == 1) cnt++;x /= 2;}return cnt;}intmain(){cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}int ans = 0;for (int i = 0; i < n; i++) {ans += f(a[i]);}cout << ans << endl;return 0;}
判断题
21. 函数f(x)的功能是计算x的二进制表示中1的个数。（ ）
22. 若输入n=3，数组元素为1 2 3，则输出为3。（ ）
23. 若将第7行的x > 0改为x >= 0，程序仍然能正常运行。（ ）
单选题
24. 若输入为：
47 8 9 10
程序的输出为（）。
A. 6
B. 7
C. 8
D. 9
25. 函数f(2026)的返回值为（ ）。
A. 8
B. 9
C. 10
D. 11
程序三
#include<iostream>using namespace std;int n;int a[1000];intsolve(int left, int right){if (left >= right) return 0;int maxPos = left;for (int i = left + 1; i <= right; i++) {if (a[i] > a[maxPos]) {maxPos = i;}}return (right - left) + solve(left, maxPos - 1) + solve(maxPos + 1, right);}intmain(){cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}cout << solve(0, n - 1) << endl;return 0;}
判断题
26. 若数组a中的元素全部相等，则程序的输出为n(n-1)/2。（ ）
27. 若数组a严格递增，即a[0] < a[1] < ... < a[n-1]，则函数solve每次找到的最大值都在区间最右端。（ ）
28. 将第7行的maxPos = left改为maxPos = 0，程序的运行结果不会改变。（ ）
单选题
29. 若输入为：
53 1 4 1 5
程序的输出为（）。
A. 5
B. 6
C. 7
D. 8
30. 若n=6，数组元素为6 5 4 3 2 1（严格递减），则输出为（ ）。
A. 6
B. 10
C. 15
D. 21
31. 函数solve的功能最接近以下哪个选项（ ）。
A. 计算数组最大值
B. 计算逆序对数量
C. 计算以最大值为根节点的递归深度相关值
D. 计算数组元素之和
参考答案
题号 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
答案 | × | √ | √ | A | A | √ | × | × | B | A | √ | √ | × | D | C | C |
简要解析
程序一：偶数位置（0-based）小写转大写，奇数位置大写转小写。
第16题："HelloWorld"→"HeLlOwOrLd"（原题描述不符，判×）；
第17题：奇数位置（索引1,3,5...）大写转小写，小写字母保持不变，正确；
第18题：i是局部变量，循环结束后值为n，但循环内修改了i的值吗？没有，故i=n，正确。
程序二：f(x)计算二进制中1的个数。
第21题正确；
第22题：f(1)=1，f(2)=1，f(3)=2，总和=4而非3，判×（注意：此处题目可能有误，按程序实际计算应为4）；
第23题：x>=0会导致死循环（0永远不小于0），判×。
程序三：递归函数每次找区间最大值，累加(right-left)再递归处理左右子区间。(right-left)等于区间长度减1，即区间内元素个数减1。总输出等于每个元素被作为最大值处理的次数之和，即每个非叶子节点贡献其区间长度减1。对于严格递减序列6 5 4 3 2 1，每次最大值都在最左端，递归深度为n，总贡献为5+4+3+2+1=15，选C。
三、程序完善题（共2题，每题15分，共计30分）
说明：阅读程序，根据题目要求，从备选项中选择正确的选项填入空白处，使程序能够正确运行。每题有5个空，每空3分。
程序一（进制转换）
题目描述：将输入的十进制正整数n 转换为 m 进制（2 ≤ m ≤ 16），并输出转换结果。对于大于9的数字，用大写字母 A-F 表示。
#include<iostream>#include<cstring>using namespace std;char ans[100];int n, m;intmain(){cin >> n >> m;int len = 0;while (n > 0) {int r = n % m;if (r < 10) {ans[len] = ①;} else {ans[len] = ②;}len++;n = ③;}if (len == 0) {cout << 0 << endl;} else {for (int i = ④; i >= 0; i--) {cout << ans[i];}cout << endl;}return 0;}
备选项：
①
A. '0' + r
B. '0' - r
C. r -'0'
D. 以上均可
②
A. 'A' + r - 10
B. 'A' - r + 10
C. 'A' + r
D. r - 10 -'A'
③
A. n / m
B. n % m
C. n - r
D. n * m
④
A. len
B. len - 1
C. len + 1
D. 0
⑤ 若输入 n=255, m=16，则输出为（ ）。
A. FF
B. 255
C. 11111111
D. 0F0F
程序二（约瑟夫问题）
题目描述：有n 个人围成一圈，从第 1 个人开始报数，报到 m 的人出列，然后从下一个人重新开始报数，直到所有人都出列。输出出列顺序。使用循环链表实现。
#include<iostream>using namespace std;struct Node {int data;Node *next;};int n, m;Node* create(int n){Node *head, *tail, *p;head = new Node;head->data = 1;tail = head;for (int i = 2; i <= n; i++) {p = new Node;p->data = i;⑥ = p;tail = p;}⑦ = head;return head;}intmain(){cin >> n >> m;Node *head = create(n);Node *pre = NULL, *cur = head;while (⑧) {for (int i = 1; i < m; i++) {pre = cur;cur = ⑨;}cout << cur->data << " ";pre->next = cur->next;delete cur;cur = ⑩;；n--;}return 0;}
备选项：
⑥
A. tail->next
B. tail->data
C. head->next
D. p->next
⑦
A. tail->next
B. tail->data
C. head->next
D. p->next
⑧
A. cur != NULL
B. n > 0
C. cur->next != NULL
D. cur != head
⑨
A. cur->next
B. pre->next
C. head->next
D. cur
⑩
A. pre
B. cur
C. pre->next
D. head
参考答案
# 程序一
题号 | ① | ② | ③ | ④ | ⑤ |
答案 | A | A | A | B | A |
解析：
① '0' + r：将数字 r（0-9）转换为对应的字符 '0'-'9'。
② 'A' + r - 10：将数字10-15转换为字符 'A'-'F'。例如 r=10，'A'+10-10='A'；r=15，'A'+15-10='F'。
③ n = n / m：每次除以进制基数，继续处理下一位。
④ len - 1：因为最后一次循环后 len 指向最后一个有效字符的下一个位置，所以从 len-1 开始逆序输出。
⑤ 255转十六进制：255 ÷ 16 = 15 余 15 → FF，选A。
# 程序二
题号 | ⑥ | ⑦ | ⑧ | ⑨ | ⑩ |
答案 | A | A | B | A | C |
解析：
⑥ tail->next = p：将新节点 p 链接到链表尾部（tail 的后面）。
⑦ tail->next = head：创建完循环链表后，将尾节点的 next 指向头节点，形成环。
⑧ n > 0：当还有人未出列时继续循环。每次出列一个人后，n 会递减。
⑨ cur->next：报数时，指针 cur 后移一位，pre 记录 cur 的前驱。
⑩ pre->next：删除 cur 后，从被删除节点的下一个节点（即 pre->next）重新开始报数。
