历年CSP-J初赛真题解析 | 2023年CSP-J初赛

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总贴：历年CSP-J初赛真题解析 | 汇总_热爱编程的通信人的博客-CSDN博客

单项选择题

第1题（C++语言基础）

在C++中，下面哪个关键字用于声明一个变量，其值不能被修改？（ ）

A.unsigned

B.const

C.static

D.mutable

【答案】：B

【解析】

unsigned表示无符号，static静态变量是在程序运行期间保持其存在和值，mutable修饰的变量，将永远处在可变的状态。const修饰的变量是不能被更新的

第2题（数据表示与计算）

八进制数12345670 ( 8 ) 12345670_{(8)}12345670(8)​和07654321 ( 8 ) 07654321_{(8)}07654321(8)​的和为（ ）

A.22222221(8)

B.21111111(8)

C.22111111(8)

D.22222211(8)

【答案】：D

【解析】

参考十进制的逢十进一的计算方法，八进制就是逢八进一，1234567890(8)+07654321(8)=22222211(8)

第3题（C++语言基础）

阅读下述代码， 请问修改data的value成员以存储3.14， 正确的方式是（ ）

union Data{ int num; float value; char symbol; }; union Data data;

A.data.value = 3.14;

B.value.data = 3.14;

C.data->value = 3.14;

D.value->data = 3.14;

【答案】：A

【解析】

union和struct都是由不同的数据类型成员组成的，结构体所有成员占用的内存空间是累加的，而联合体中所有的成员共用一块地址空间。可以参考struct，访问其成员变量使用 类型变量名.成员变量名，即data.value。->用于指针的访问。选A

第4题（线性表）

假设有一个链表的节点定义如下：

struct Node { int data; Node* next; }

现在有一个指向链表头部的指针：Node* head， 如果想要在链表中插入一个新节点，其成员data的值为42， 并使新节点成为链表的第一个节点， 下面哪个操作是正确的？

A.Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;

B.Node* newNode = new Node; head->data=42; newNode->next = head； head = newNode;

C.Node* newNode = new Node; newNode->data=42; head->next = newNode;

D.Node* newNode = new Node; newNode->data=42; newNode->next = head;

【答案】：A

【解析】

第一句，4个选项均相同，表示定义Node类型newNode。第二句表示将其成员的data的值设为42，使用newNode->data = 42。因为newNode要成为第一个节点，所以newNode->next需要指向现有的head，即newNode->next = head。此时newNode变为了head，所以A与D相比多了个这一句，head = newNode。

第5题（树）

根节点的高度为1，一棵拥有2023个节点的三叉树高度至少为（ ）

A.6

B.7

C.8

D.9

【答案】：C

【解析】

“至少为”说明要求高度最小的值，画完全三叉树可以满足题目要求。第1层1个节点，第2层3个节点，第3层9个节点，第4层27个节点，第5层81个节点，第6层243个节点，第7层729个节点，第8层2187个节点。前7层相加为1093，不足2023，加上第8层超过2023，所以至少8层。

第6题（组合学）

小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息。则小明一共有（ ）种选择时间段的方案。

A.31

B.18

C.21

D.33

【答案】：B

【解析】

假设七个时间段为1234567，依次枚举n个时间段的组合数。

选择1个时间段有7种：1、2、3、4、5、6、7

选择2个时间段有4+3+2+1=10种：14、15、16、17、25、26、27、36、37、47

选择3个时间段有1种：147

所以移动18种，选B

第7题（计算机语言与算法）

以下关于高精度运算的说法错误的是（ ）

A.高精度计算主要是用来处理大整数或需要保留多位小数的运算。

B.大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商。

C.高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。

D.高精度加法运算的关键在于逐位相加并处理进位。

【答案】：C

【解析】

高精度乘法的运算时间与参与运算的两个整数的长度乘积有关，选C，具体高精度计算实现可以参考洛谷P1303题解。

第8题（栈和队列）

后缀表达式“623±382/+*2^3+”对应的中缀表达式是（ ）。

A.((6-(2+3))*(3+8/2))^2+3

B.6-2+3*3+8/2^2+3

C.(6-(2+3))*((3+8/2)^2)+3

D.6-((2+3)*(3+8/2))^2+3

【答案】：A

【解析】

中缀变后缀有3个步骤，第一步加括号，第二步将运算符移到括号右边，第三步去除括号。这里反着做一遍。

加括号：((((6(23)+)-(3(82)/)+)*2)^3)+

括号移到中间：((((6-(2+3))*(3+(8/2)))^2)+3)

逐步移除多余括号，得到：((6-(2+3))*(3+8/2))^2+3

选A

第9题（数据表示与计算）

数101010(2)和166(8)的和为（ ）。

A.10110000(2)

B.236(8)

C.158(10)

D.A0(16)

【答案】：D

【解析】

统一换算成十进制数后计算101010(2)=42(10)，166(8)=118(10)，160(10)=A0(16)=240(8)=10100000(2)，选D

第10题（树）

假设有一组字符{a,b,c,d,e,f}，对应的频率分别为5%、9%、12%、13%、16%、45%。请问以下哪个选项是字符a,b,c,d,e,f分别对应的一组哈夫曼编码？（ ）

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节点没有子节点，观察答案A，说明f为0，通过排除法可以直接选A。

第11题（树）

给定一棵二叉树， 其前序遍历结果为：ABDECFG， 中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么？（ ）

A.EDBGFCA

B.EDGBFCA

C.DEBGFCA

D.DBEGFCA

【答案】：A

【解析】

中序遍历是先访问左子树，然后访问根，再访问右子树。前序遍历是先访问根，然后访问左子树，再访问右子树。后续遍历是先访问左子树，然后访问右子树，再访问根。

根据前序和中序遍历，可以画出二叉树，后序遍历为EDBGFCA，选A

第12题（图）

考虑一个有向无环图，该图包含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

【解析】

访问2、3前需要先访问1，访问4前需要先访问2或3，选B

第13题（数据表示与计算）

在计算机中，以下哪个选项描述的数据存储容量最小？（ ）

A.字节（byte）

B.比特（bit）

C.字（word）

D.千字节（kilobyte）

【答案】：B

【解析】

计算机最小存储单位是bit。字由若干个bit组成。选B

第14题（组合学）

一个餐有10个男生和12个女生，如果要选出一个3人的小组，并且小组中必须至少包含1个女生，那么有多少种可能的组合？（ ）

A.1420

B.1770

C.1540

D.2200

【答案】A

【解析】

选1个女生，组合=C(12,1)*C(10,2)=540

选2个女生，组合=C(12,2)*C(10,1)=660

选3个女生，组合=C(12,3)=220

共计1420种组合

第15题（软件系统）

以下哪个不是操作系统？（ ）

A.Linux

B.Windows

C.Android

D.HTML

【答案】：D

【解析】

HTML是超文本标记语言，不是操作系统

阅读程序

#include <iostream> #include <cmath> using namespace std; double f(double a, double b, double c) { //海伦公式，求三角新面积。但a、b、c不一定能够组成一个三角形 double s = (a + b + c) / 2; return sqrt(s * (s - a) * (s - b) * (s - c)); } int main() { cout.flags(ios::fixed); //定点形式显示浮点数 cout.precision(4); //指定小数位数为4位 int a, b, c; cin >> a >> b >> c; cout << f(a,b,c) << endl; return 0; }

假设输入的所有数都为不超过1000的正整数，完成下面的判断题和单选题：

第16题

当输入为“2 2 2”时，输出为“1.7321"。（ ）

A.正确

B.错误

【答案】：A

【解析】

将"2 2 2"带入计算，得到1.7321

第17题

将第7行中的“(s - b) * (s - c)”改“(s - c) * (s - b)”不会影响程序运行的结果。（ ）

A.正确

B.错误

【答案】：A

【解析】

乘法满足交换律，更换两者的顺序，不影响程序运行结果

第18题

程序总是输出四位小数。（ ）

A.正确

B.错误

【答案】A

【解析】

当a、b、c无法构成面积时，计算结果为0.0000，也仍然保留四位小数（用devc++运行出现nan的错误）

第19题

当输入为“3 4 5”时，输出为（ ）

A.“6.0000”

B.“12.0000”

C.“24.0000”

D.“30.0000”

【答案】：A

【解析】

将"3 4 5"带入计算，其实就是求直角三角形的面积，得到6.0000，选A

第20题

当输入为“5 12 13”时，输出为（ ）。

A.“24.0000”

B.“30.0000”

C.“60.0000”

D.“120.0000”

【答案】：B

【解析】

同19题，也是求直角三角形的面积，得30.0000，选B

#include <iostream> #include <vector> #include <algorithm> using namespace std; int f(string x, string y) { int m = x.size(); int n = y.size(); vector<vector<int>> v(m+1, vector<int>(n+1, 0)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { //v[i][j]表示字符串x和y的最长公共子序列的长度。子序列指的是可以在字符串中任意删掉一些字符后剩下的部分，公共子序列则要求同时是两个字符串的子序列 if (x[i-1] == y[j-1]) { v[i][j] = v[i-1][j-1] + 1; } else { v[i][j] = max(v[i-1][j], v[i][j-1]); } } } return v[m][n]; } bool g(string x, string y) { if (x.size() != y.size()) { //先筛去两个字符串长度不一致的情况 return false; } return f(x + x, y) == y.size(); //在字符串x尾部再复制一份后进行判断 } int main() { string x, y; cin >> x >> y; cout << g(x, y) << endl; return 0; }

第21题

f函数的返回值小于等于min(n, m) 。（ ）

A.正确

B.错误

【答案】：A

【解析】

返回两个字符串的最长公共子序列长度，肯定不会超过某一个字符串的长度

第22题

f函数的返回值等于两个输入字符串的最长公共子串的长度。（ ）

A.正确

B.错误

【答案】：B

【解析】

子串不等于子序列，子串要求字符在原字符串中连续出现，而子序列只有顺序要求

第23题

当输入两个完全相同的字符串时， g函数的返回值总是true。（ ）

A.正确

B.错误

【答案】：A

【解析】

两个相同的字符串，公共子序列长度等于y字符串的长度，所以正确

第24题

将第19行中的“v[m][n]”替换为“v[n][m]"，那么该程序（ ）。

A.行为不变

B.只会改变输出

C.一定非正常退出

D.可能非正常退出

【答案】：D

【解析】

换为v[n][m]，可能某一维下标访问会越界，此时会非正常退出。

第25题

当输入为“csp-j p-jcs”时，输出为（ ）

A.“0”

B.“1”

C.“T”

D.“F”

【答案】：B

【解析】

如果一看代码就知道是求最长公共子序列，那直接可以得到答案。如果不了解，可以尝试打表，二维列表中的元素值为v[i][j]。具体打完的表如下：

i 0 1 2 3 4 5 j 0 0 0 0 0 0 0 1 0 0 0 0 1 1 2 0 0 0 0 1 2 3 0 1 1 1 1 2 4 0 1 2 2 2 2 5 0 1 2 3 3 3 6 0 1 2 3 4 4 7 0 1 2 3 4 5 8 0 1 2 3 4 5 9 0 1 2 3 4 5 10 0 1 2 3 4 5

v[5][5]等于5，与y字符串长度相同，选B

第26题

当输入为“csppsc spsccp”时，输出为（ ）。

A.“T”

B.“F”

C.“0”

D.“1”

【答案】：D

【解析】

同25题，如果一下子看出是求最长公共子序列，那直接可以得到答案。如果不了解，可以尝试打表，二维列表中的元素值为v[i][j]。具体打完的表如下：

i 0 1 2 3 4 5 6 j 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 2 0 1 1 1 1 1 1 3 0 1 2 2 2 2 2 4 0 1 2 2 2 2 3 5 0 1 2 3 3 3 3 6 0 1 2 3 4 4 4 7 0 1 2 3 4 5 5 8 0 1 2 3 4 5 5 9 0 1 2 3 4 5 6 10 0 1 2 3 4 5 6 11 0 1 2 3 4 5 6 12 0 1 2 3 4 5 6

v[14][6]等于6，与y字符串长度相同，选D

#include <iostream> #include <cmath> using namespace std; int solve1(int n) { return n * n; } int solve2(int n) { int sum = 0; for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { if (n/i == i) { sum += i*i; } else { sum += i*i + (n/i)*(n/i); } } } return sum; } int main() { int n; cin >> n; cout << solve2(solve1(n)) << " " << solve1(solve2(n)) << endl; return 0; }

第27题

如果输入的n为正整数， solve2函数的作用是计算n所有的因子的平方和。（ ）

A.正确

B.错误

【答案】：A

【解析】

通过第32题带入计算，n=5时，solve(25)得到651，可以推算出solve2函数的作用就是计算n的所有因子的平方和，即1+25+625=651

第28题

第13-14行的作用是避免n的平方根因子1（或n/i）进入第16行而被计算两次。（ ）

A.正确

B.错误

【答案】：A

【解析】

通过第32题带入计算，i=1时，第13-14行没有将其加到sum中，是在第16行被计算，所以描述正确

第29题

如果输入的n为质数， solve2(n)的返回值为n 2 + 1 n^2+1n2+1。（ ）

A.正确

B.错误

【答案】：A

【解析】

通过第32题带入计算，n=5时，solve2(5)为26，符合题目描述

第30题

如果输入的n为质数p的平方， 那么solve2(n) 的返回值为（ ）。

A.p 2 + p + 1 p^2+p+1p2+p+1

B.n 2 + n + 1 n^2+n+1n2+n+1

C.n 2 + 1 n^2+1n2+1

D.p 4 + 2 p 2 + 1 p^4+2p^2+1p4+2p2+1

【答案】：B

【解析】

通过第32题，n=25，此时p=5，因为solve(25)=651，将p=5带入4个选项中，应该是p^4+p2+1，D错误。将n=25带入4个选项中，B正确。

第31题

当输入为正整数时，第一项减去第二项的差值一定（ ）

A.大于0

B.大于等于0且不一定大于0

C.小于0

D.小于等于0且不一定小于0

【答案】：D

【解析】

通过第32题，第一项减去第二项的差值为负数，所以A、B肯定错误。满足差值为0的数，就是这个数的平方等于这个数的各个因子的平方和。1就是这个数，所以选D。

第32题

当输入为“5”时，输出为（ ）。

A.“651 625”

B.“650 729”

C.“651 676”

D.“652 625”

【答案】：C

【解析】

将5带入计算，solve2(solve(1))等于651，solve1(solve2(5))等于676，选C。

完善程序

（寻找被移除的元素）问题：原有长度为n+1、公差为1等差升序数列；将数列输入到程序的数组时移除了一个元素，导致长度为n的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。

试补全程序。

#include <iostream> #include <vector> using namespace std; int find_missing(vector<int>& nums) { int left = 0, right = nums.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] == mid + __1__) { __2__; } else { __3__; } } return __4__; } int main() { int n; cin >> n; vector<int> nums(n); for (int i = 0; i < n; i++) cin >> nums[i]; int missing_number = find_missing(nums); if (missing_number == __5__) { cout << "Sequence is consecutive" << endl; } else { cout << "Missing number is " << missing_number << endl; } return 0; }

第33题

1处应填（ ）

A.1

B.nums[0]

C.right

D.left

【答案】：B

【解析】

第9行可以判断出代码为二分搜索，所以第11行和第13行肯定是left和right两个指针的移动，故第10行应该是判断满足什么条件时，left指针需要移动。mid左侧为连续的数字时，left需要移动。num[mid]= mid+num[0]时，左侧数字是连续的，选B。

可以代入nums = [1,2,3,5,6]进行验算，第一次while循环，mid = 2，nums[2] == 3，满足nums[mid] == mid + num[0]（3 == 2 + 1）。

第34题

2处应填（ ）

A.left = mid + 1

B.right = mid - 1

C.right = mid

D.left = mid

【答案】：A

【解析】

mid左侧数据满足连续时，left指针需要移到mid的右侧，所以A选项left = mid+1满足。

第35题

3处应填（ ）

A.left = mid + 1

B.right = mid - 1

C.right = mid

D.left = mid

【答案】：C

【解析】

mid左侧数据不连续，则右侧数据肯定连续。因此需要把right指针改为mid，下一轮从mid的左侧区域开始查找。所以选C

第36题

4处应填（ ）

A.left + nums[0]

B.right + nums[0]

C.mid + nums[0]

D.right + 1

【答案】：A

【解析】

当退出while循环时，一定是left指针指向那个被移除的数前面一个数，用left+nums[0]就可以得到被移除的数，所以选A。

第37题

5处应填（ ）

A.nums[0] + n

B.nums[0] + n - 1

C.nums[0] + n + 1

D.nums[n-1]

【答案】：D

【解析】

题目描述中提到“除非被移除的是第一个或最后一个元素”，所以要打印“Sequence is consecutive”，只可能移除第一个或最后一个元素，4个选项D为最后一个元素，所以选D

（编辑距离）给定两个字符串， 每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符， 求将第一个字符串转换为第二个字符串所需要的最少操作次数。

试补全动态规划算法。

#include <iostream> #include <string> #include <vector> using namespace std; int min(int x, int y, int z) { return min(min(x, y), z); //三个整数求最小值 } int edit_dist_dp(string str1, string str2) { int m = str1.length(); //str1的长度 int n = str2.length(); //str2的长度 vector<vector<int>> dp(m + 1, vector<int>(n + 1)); //创建一个二维数组dp for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0) dp[i][j] = ①; else if (j == 0) dp[i][j] = ②; else if (③) dp[i][j] = ④; else dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤); } } return dp[m][n]; } int main() { string str1, str2; cin >> str1 >> str2; cout << "Minimum number of operations: " << edit_dist_dp(str1, str2) << endl; return 0; }

第38题

1处应填（ ）

A.j

B.i

C.m

D.n

【答案】：A

【解析】

dp[m][n]表示长度为m的字符串变成长度为n的字符串最少步数，那么dp[0][j]就应该表示str1长度为0的字符串变成长度为j的字符串最少步数。显然应该是添加j个字符，所以选A

第39题

2处应填（ ）

A.j

B.i

C.m

D.n

【答案】：B

【解析】

同39题，dp[m][n]表示长度为m的字符串变成长度为n的字符串最少步数，那么dp[i][0]就应该表示str1长度为i的字符串变成长度为0的字符串最少步数。显然应该是删除i个字符，所以选B

第40题

3处应填（ ）

A.str1[i - 1] == str2[j - 1]

B.str1[i] == str2[j]

C.str1[i - 1] != str2[j - 1]

D.stri[i] != str2[j]

【答案】：A

【解析】

因为第24行应该是判断str1和str2某个位置字符不相等时的处理，故这里就应该是字符相等的位置。str1和str2的第i个字符应该是str1[i-1]，选A

第41题

4处应填（ ）

A.dp[i - 1][j - 1] + 1

B.dp[i - 1][j - 1]

C.dp[i - 1][j]

D.dp[i][j - 1]

【答案】：B

【解析】

这里是动态规划的基本概念，如果两个字符相等，str1的i字符变成str2的j个字符最少步数，就等于str的i-1个字符变成str2的j-1个字符的最少步数。选B

第42题

5处应填（ ）

A.dp[i][j] + 1

B.dp[i - 1][j - 1] + 1

C.dp[i - 1][j - 1]

D.dp[i][j]

【答案】：C

【解析】

3个数字应该分别对应着插入、删除和替换。插入的话，就是相当于i比j多1，dp[i][j-1]就对应着插入。删除的话，就是相当于i比j少1，dp[i-1][j]就对应着删除。替换的话，i和j的数量相等，C选项满足要求。

5个空选出来后，可以带入abc和abd字符进行验算。打表如下：

i 0 1 2 3 j 0 0 1 2 3 1 1 0 1 2 2 2 1 0 1 3 3 2 1 1