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

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

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

适合人群：

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

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

单项选择题

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

以下哪种功能没有涉及C++语言的面向对象特性支持：（ ）。

A.C++中调用printf函数

B.C++中调用用户定义的类成员函数

C.C++中构造一个class或struct

D.C++中构造来源于同一基类的多个派生类

【答案】：A

【解析】

A：printf是C语言中的函数，C语言是面向过程语言

B/C/D选项中均有class，所以涉及面向对象特性

第2题（栈）

有6个元素，按照6、5、4、3、2、1的顺序进入栈S，请问下列哪个出栈序列是非法的（ ）。

A.543612

B.453126

C.346521

D.234156

【答案】：C

【解析】

A/B/D按照6、5、4、3、2、1顺序进栈，可以实现该顺序出栈

C：需要6出栈时，6不是栈顶，而是5，所以无法出栈

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

运行以下代码片段的行为是（ ）。

int x = 101; int y = 201; int *p = &x; int *q = &y; p = q;

A.将x的值赋为201

B.将y的值赋为101

C.将q指向x的地址

D.将p指向y的地址

【答案】：D

【解析】

D：p = q，将p也指向y的地址

第4题（线性表）

链表和数组的区别包括（ ）。

A.数组不能排序，链表可以

B.链表比数组能存储更多的信息

C.数组大小固定，链表大小可动态调整

D.以上均正确

【答案】：C

【解析】

A：数组可以排序

B：不一定，数组也可以是结构体数组，可以放任意多的信息

C：数组使用过程中，大小不能调整；链表每次申请一块内存，用这块内存去存一个内容，大小可以动态调整

第5题（栈和队列）

对假设栈S和队列Q的初始状态为空。存在e1~e6六个互不相同的数据，每个数据按照进栈S、出栈S、进队列Q、出队列Q的顺序操作，不同数据间的操作可能会交错。已知栈S中依次有数据e1、e2、e3、e4、e5和e6进栈，队列Q依次有数据e2、e4、e3、e6、e5和e1出队列。则栈S的容量至少是（ ）个数据。

A.2

B.3

C.4

D.6

【答案】：B

【解析】

依次有e2、e4、e3、e6、e5和e1出队列，即表示有e2、e4、e3、e6、e5、e1顺序出栈。

栈S最大容量为3，即存放e1、e3、e4或e1、e5、e6时需要（从栈底到栈顶）

第6题（栈和队列）

对表达式a+(b-c)*d的前缀表达式为（ ），其中+、-、*是运算符。

A.*+a-bcd

B.+a*-bcd

C.abc-d*+

D.abc-+d

【答案】：B

【解析】

a+(b-c)*d是常见的中缀表达式，中缀表达式转为前缀表达式，可以使用

1.加括号：a+(b-c)*d --> (a+((b-c)*d))

2.将运算符移到每对运算式的左边：+(a(*(-bc)d))

3.去括号：+a*-bcd

第7题（树）

假设字母表{a, b, c, d, e}在字符串出现的频率分别为10%，15%，30%，16%，29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母d的编码长度为（ ）位。

A.1

B.2

C.2或3

D.3

【答案】：B

【解析】

哈夫曼编码每次就是选择两个最小的频率合成出一个新的数，依次往复，构成一棵树。

此题先用10和15合成25，再选16和25合成41，再选29和30合成59，最后把41和59合成100。

构建哈夫曼树后，往左走的都是0，往右走的都是1，d的编码长度为2位，编码为00。

第8题（树）

一棵有n个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第1个位置。若存储在数组第9个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。

A.8、18

B.10、18

C.8、19

D.10、19

【答案】：C

【解析】

完全二叉树在数组中存放的形式为[1,2,3,4,5,6,7,8,9,…]。

9为奇数，即右节点，其兄弟节点是8，其右子节点是n*2+1，即19。

第9题（图）

考虑由N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。

A.N-1

B.N

C.N+1

D.N 2 N^2N2

【答案】：B

【解析】

可以举一个简单的有向连通图，1->2->3->4->1。n个顶点需要n条边连接。

构成二维矩阵时（行编号依次为1234，列编号依次为1234），有4个非零元素。

第10题（栈和队列）

以下对数据结构的表述不恰当的一项为：（ ）。

A.图的深度优先遍历算法常使用的数据结构为栈。

B.栈的访问原则为后进先出，队列的访问原则是先进先出。

C.队列常常被用于广度优先搜索算法。

D.栈与队列存在本质不同，无法用栈实现队列。

【答案】：D

【解析】

D：可以用两个栈去实现队列的功能

第11题（线性表）

以下哪组操作能完成在双向循环链表结点p之后插入结点s的效果（其中，next域为结点的直接后继，prev域为结点的直接前驱) ：（ ）。

A.p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;

B.p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;

C.s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;

D.s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

【答案】：D

【解析】

先将s节点与p的next节点连接起来，即s->next = p->next; p->next->prev = s。

然后再将p与s相连，s->prev = p; p->next = s;

所以选择D

第12题（排序）

以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。

A.冒泡排序算法是稳定的

B.简单选择排序是稳定的

C.简单插入排序是稳定的

D.归并排序算法是稳定的

【答案】：B

【解析】

排序算法是否稳定，就是看相同的元素在排序前和排序后，相对位置是否稳定。如两个2排序，排序后第1个2必须还是在第2个2前面。

简单记忆规则如下：

1.选择、冒泡、插入排序算法中选择不稳定

2.归并、堆排序算法中堆不稳定

3.快排、希尔排序算法，两个都不稳定

4.基数、桶、计数排序算法，都稳定

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

八进制数32.1对应的十进制数是（ ）。

A.24.125

B.24.250

C.26.125

D.26.250

【答案】：C

【解析】

其他进制转十进制的方法为按权展开求和。

3 ∗ 8 1 + 2 ∗ 8 0 + 1 ∗ 8 − 1 = 26.125 3*8^1+2*8^0+1*8^{-1}=26.1253∗81+2∗80+1∗8−1=26.125

第14题（组合学）

一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串abcab有（ ）个内容互不相同的子串。

A.12

B.13

C.14

D.15

【答案】：B

【解析】

一种方法就是列出所有的子串，注意需要包括空串。另一种可以按插空法计算。

左端点有6种选择方式，右端点有5种选择方式，所以共6*5=30种，此时没有考虑右端点小于左端点，所以需要30/2=15种，再加上1个空串，共16种

相同子串中，ab有2个，a有2个，b有2个，相同的子串可以只算1个，所以需要16-3=13种，选B。

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

以下对递归方法的描述中，正确的是：（ ）

A.递归是允许使用多组参数调用函数的编程技术

B.递归是通过调用自身来求解问题的编程技术

C.递归是面向对象和数据而不是功能和逻辑的编程语言模型

D.递归是将用某种高级语言转换为机器代码的编程技术

【答案】：B

【解析】

递归就是通过调用自身来解决问题的一种编程技术

阅读程序

#include <iostream> using namespace std; int main() { unsigned short x, y; //short占2字节，unsigned short范围为0~65535 cin >> x >> y; x = (x | x << 2) & 0x33; //x << 2 表示转为二进制后左移2位 x = (x | x << 1) & 0x55; //x << 1 表示转为二进制后左移1位 y = (y | y << 2) & 0x33; y = (y | y << 1) & 0x55; unsigned short z = x | y << 1; cout << z << endl; return 0; }

假设输入的x、y均是不超过15的自然数，完成下面的判断题和单选题：

第16题

删去第7行与第13行的unsigned，程序行为不变。（ ）

A.正确

B.错误

【答案】：A

【解析】

设x=abcd，y=efgh

如果删除unsgined，则范围变为-32768 ~ 32767，而输入x和y都是不超过15的自然数（半个字节），左移2位也最多乘4（1个字节），不会超过范围，所以不会改变。

第17题

将第7行与第13行的short均改为char，程序行为不变。（ ）

A.正确

B.错误

【答案】：B

【解析】

改为char，cin会按照字符读入，做位运算会按照ASCII码进行运算，程序行为会发生变化。

第18题

程序总是输出一个整数“0”。（ ）

A.正确

B.错误

【答案】：B

【解析】

可以同19和20题一起做，输入2和2，输出为12。

第19题

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

A.正确

B.错误

【答案】：B

【解析】

输入2和2，x=0010，y=0010，a=b=d=0，c=1，e=f=h=0，g=1。eafbgchd=00001100，输出为12。注意优先级关系为：左移/右移 > 按位与 > 按位或 > 与或非

第20题

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

A.正确

B.错误

【答案】：B

【解析】

同19题，输出为12。

第21题

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

A.“0”

B.“209”

C.“197”

D.“226”

【答案】：B

【解析】

同19题，输入13和8计算，输出209

#include <algorithm> #include <iostream> #include <limits> using namespace std; const int MAXN = 105; const int MAXK = 105; int h[MAXN][MAXK]; int f(int n, int m) { if (m == 1) return n; if (n == 0) return 0; int ret = numeric_limits<int>::max(); //返回编译器允许的int型数最大值。2^31-1，2148473647 for (int i=1; i<=n; i++) ret = min(ret, max(f(n-i, m), f(i-1, m-1)) + 1); return ret; } int g(int n, int m) //g函数与f函数实现功能一致，f函数使用递归实现，g函数使用递推实现 { for (int i=1; i<=n; i++) h[i][1] = i; for (int j=1; j<=m; j++) h[0][j] = 0; for (int i=1; i<=n; i++) { for (int j=2; j<=m; j++) { h[i][j] = numeric_limits<int>::max(); for (int k = 1; k<=i; k++) h[i][j] = min( h[i][j], max(h[i-k][j], h[k-1][j-1]) + 1); } } return h[n][m]; } int main() { int n, m; cin >> n >> m; cout << f(n, m) << endl << g(n, m) << endl; return 0; }

假设输入的n、m均是不超过100的正整数，完成下面的判断题和单选题：

第22题

当输入为“7 3”时，第19行用来取最小值的min函数执行了449次。（ ）

A.正确

B.错误

【答案】：B

【解析】

尝试打表理解题意。h[3][2]是求出交叉单元格的极大值之后的极小值

设g[][]记录计算次数，n=1,m=2，ret = min(ret, max(f[0][2],f[0][1])+1)， 则g[1][2]=1+g[0][2]+g[0][1]=1

n=2,m=2，

i=1：ret = min(ret, max(f[1][2],f[0][1])+1)

i=2：ret = min(ret, max(f[0][2],f[1][1])+1)

则g[2][3]=2+g[1][2]+g[0][2]+g[0][2]+g[1][2]=3

同理，g[3][2]=7，g[3][3]=12，g[4][2]=15，g[4][3]=32，发现n行第2列的g[i][2]=2 i 2^i2i-1。

最后计算g[4][3]=32,g[5][3]=80,g[6][3]=192,g[7][3]=448

第23题

输出的两行整数总是相同的。（ ）

A.正确

B.错误

【答案】：A

【解析】

f和g函数，初值、递归/递推形式完全一致，所以结果也相同。

第24题

当m为1时，输出的第一行总为n。（ ）

A.正确

B.错误

【答案】：A

【解析】

第14行，m==1时return n

第25题

算法g(n, m)最为准确的时间复杂度分析结果为（ ）。

A.O ( n 3 / 2 m ) O(n^{3/2}m)O(n3/2m)

B.O ( n m ) O(nm)O(nm)

C.O ( n 2 m ) O(n^2m)O(n2m)

D.O ( n m 2 ) O(nm^2)O(nm2)

【答案】：C

【解析】

i从1到n，j从1到m，k从1到i，n ∗ m ∗ n = n 2 ∗ m n * m * n = n^2 * mn∗m∗n=n2∗m

第26题

当输入为“20 2”时，输出的第一行为（ ）。

A.“4”

B.“5”

C.“6”

D.“20”

【答案】：C

【解析】

画二维矩阵表计算，行i表示n，列j表示m，通过i、j、k代入运算可以发现规律为前i-1行第1列和第2列的数字交叉取最大值，取出最大值后再取其中的最小值，并将该值加1。

列j为2时，可以看出规律为1个1，2个2，3个3，4个4，5个5，6个6…，所以i为20时，j为6。

第27题

当输入为“100 100”时，输出的第一行为（ ）。

A.“6”

B.“7”

C.“8”

D.“9”

【答案】：B

【解析】

100楼层，扔7次就可以测出最高的扔鸡蛋不碎的楼层。7个鸡蛋就够用。最坏情况下6次不一定测得出来，7次一定测得出来。

如果用暴力枚举，列j为3时，可以看出规律为1个1，2个2，4个3，8个4，16个5，32个6，64个7。

列j为4时，发现规律同列3，因为列3和列4数字相同，所以即使到列100，规律也同列3。所以i为100时，j为7种。

#include <iostream> using namespace std; int n, k; int solve1() //返回使得x²≤n的最大整数x { int l = 0, r = n; while (l<=r) { int mid = (l+r)/2; if (mid * mid <= n) l = mid+1; else r = mid -1; } return l-1; //l-1是满足(l-1)²≤n的最大数 } double solve2(double x) { if (x == 0) return x; for (int i=0; i<k; i++) x = (x + n/x) / 2; //假设x数列有极限A，随着k增加，xi会越来越接近√n。牛顿迭代法求平方根，边长x最后趋向于根号n return x; } int main() { cin >> n >> k; double ans = solve2(solve1()); cout << ans << ' ' << (ans * ans == n) << endl; return 0; }

假设int为32位有符号整数类型，输入的n是不超过47000的自然数、k是不超过int表示范围的自然数，完成下面的判断题和单选题：

第28题

该算法最准确的时间复杂度分析结果为O(logn+k) 。（ ）

A.正确

B.错误

【答案】：A

【解析】

solve1的时间复杂度是logn，solve2的时间复杂度是k

第29题

当输入为“9801 1”时，输出的第一个数为“99”。（ ）

A.正确

B.错误

【答案】：A

【解析】

sovle1的作用就是求n的平方根，n=9801时，n的平方根就是99

第30题

对于任意输入的n，随着所输入k的增大，输出的第二个数会变成“1”。（ ）

A.正确

B.错误

【答案】：B

【解析】

如果n不是整数的平方，由于舍入误差的原因，ans会接近n \sqrt nn​，但不会等于n \sqrt nn​。原因就是double类型在运算过程中会发生截断误差。例如输入“3 10”，循环到后面，x是不变的

第31题

该程序有存在缺陷。当输入的n过大时，第12行的乘法有可能溢出，因此应当将mid强制转换为64位整数再计算。（ ）

A.正确

B.错误

【答案】：B

【解析】

最大值是(47000/2)^2，mid = (0+47000)/2 = 23500，不超过int的最大值2147483647

第32题

当输入为“2 1”时，输出的第一个数最接近（ ）。

A.1

B.1.414

C.1.5

D.2

【答案】：C

【解析】

代入计算，得到1.5

第33题

当输入为“3 10”时，输出的第一个数最接近（ ）。

A.1.7

B.1.732

C.1.75

D.2

【答案】：B

【解析】

代入计算，得到3 \sqrt 33​。solve2几次循环后就会发现x的数值不再发生改变

第34题

当输入为“256 11”时，输出的第一个数（ ）。

A.等于16

B.接近但小于16

C.接近但大于16

D.前三种情况都有可能

【答案】：A

【解析】

同29题，结果等于16

完善程序

从小到大打印正整数n的所有正因数。

试补全枚举程序。

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int>fac; fac.reserve((int)ceil(sqrt(n))); //为fac申请一片内存空间，对程序理解无影响 int i; for (i=1; i*i<n; ++i) { //此循环是将小于√n的所有因数放入到fac中 if (__1__) { fac.push_back(i); } } for (int k=0; k<fac.size(); ++k) { //将fac中已经存放的数据打印出来 cout << __2__ << ""; } if (__3__) { //如果不能理解可以先跳过3、4直接看第5个空。这里用来处理i*i=n的数 cout << __4__ << ""; } for (int k=fac.size()-1; k>=0; --k) { //逆序枚举fac cout << __5__ << ""; } }

第35题

1处应填（ ）

A.n % i == 0

B.n % i == 1

C.n % (i-1) == 0

D.n % (i-1) == 1

【答案】：A

【解析】

题目是求n的因数，所以此处为n的因数时，放到fac中。所以选A

第36题

2处应填（ ）

A.n / fac[k]

B.fac[k]

C.fac[k]-1

D.n / (fac[k]-1)

【答案】：B

【解析】

将已经放入fac中的小鱼n \sqrt nn​的因数打印出来

第37题

3处应填（ ）

A.(i-1) * (i-1) == n

B.(i-1) * i == n

C.i * i == n

D.i * (i-1) == n

【答案】：C

【解析】

如果n=9，16行之前输出的内容是1，24到26行输出的是9，还缺个3，所以3、4空合起来应该是要能输出3。因为3*3=9，所以倒推出来选C

第38题

4处应填（ ）

A.n-i

B.n-i+1

C.i-1

D.i

【答案】：D

【解析】

同37题，输出这个i，即n \sqrt nn​

第39题

5处应填（ ）

A.n / fac[k]

B.fac[k]

C.fac[k]-1

D.n / (fac[k]-1)

【答案】：A

【解析】

如果n=6，其正因数有1、2、3、6，16行之前fac中存放到是1和2，而3和6可通过n/fac[k]得到，所以选A

（洪水填充）现有用字符标记像素颜色的8x8图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。

试补全程序。

#include <bits/stdc++.h> using namespace std; const int ROWS = 8; const int COLS = 8; struct Point { int r, c; Point(int r, int c): r(r), c(c) {} //构造函数 }; bool is_valid(char image[ROWS][COLS], Point pt, int prev_color, int new_color) { int r = pt.r; int c = pt.c; return (0<=r && r<ROWS && 0<=c && c<COLS && //判断r和c在图像中 __1__&& image[r][c] != new_color); //image[r][c]!=new_color表示颜色没有被修改过 } void flood_fill(char image[ROWS][COLS], Point cur, int new_color) { //cur是[4,4]，new_color是y queue<Point> queue; queue.push(cur); int prev_color = image[cur.r][cur.c]; //prev_color = b __2__; while (!queue.empty()) { Point pt = queue.front(); queue.pop(); Point points[4] = {__3__, Point(pt.r - 1, pt.c), Point(pt.r, pt.c + 1), Point(pt.r, pt.c -1)}; for (auto p:points) { //基于范围的枚举，会从points中的4个位置依次枚举 if (is_valid(image, p, prev_color, new_color)) { __4__; __5__; } } } } int main() { char image[ROWS][COLS] = {{'g','g','g','g','g','g','g','g'}, {'g','g','g','g','g','g','r','r'}, {'g','r','r','g','g','r','g','g'}, {'g','b','b','b','b','r','g','r'}, {'g','g','g','b','b','r','g','r'}, {'g','g','g','b','b','b','b','r'}, {'g','g','g','g','g','b','g','g'}, {'g','g','g','g','g','b','b','g'}}; Point cur(4, 4); //相当于cur.r=4，cur.c=4 char new_color = 'y'; flood_fill(image, cur, new_color); //将[4,4]位置的b及可达的b都换成y for (int r=0; r<ROWS; r++) { for (int c=0; c<COLS; c++) { cout << image[r][c] << " "; } cout << endl; } // 输出： // g g g g g g g g // g g g g g g r r // g r r g g r g g // g y y y y r g r // g g g y y r g r // g g g y y y y r // g g g g g y g g // g g g g g y y g return 0; }

第40题

1处应填（ ）

A.image[r][c] == prev_color

B.image[r][c] != prev_color

C.image[r][c] == new_color

D.image[r][c] != new_color

【答案】：A

【解析】

该位置上下左右的颜色要与原来的原色相同，才可以灌溉。所以选A

第41题

2处应填（ ）

A.image[cur.r+1][cur.c] = new_color

B.image[cur.r][cur.c] = new_color

C.image[cur.r][cur.c+1] = new_color

D.image[cur.r][cur.c] = prev_color

【答案】：B

【解析】

上一句是将之前的颜色保存至prev_color中，所以此行应该是要把新的颜色赋予当前的位置，即[cur.r][cur.c]

第42题

3处应填（ ）

A.Point(pt.r, pt.c)

B.Point(pt.r, pt.c+1)

C.Point(pt.r+1, pt.c)

D.Point(pt.r+1, pt.c+1)

【答案】：C

【解析】

通过其他三个位置变换，可以推测出此行的目的是获得原有坐标的上下左右位置

第43题

4处应填（ ）

A.prev_color = image[p.r][p.c]

B.new_color = image[p.r][p.c]

C.image[p.r][p.c] = prev_color

D.image[p.r][p.c] = new_color

【答案】：D

【解析】

如果判断该位置可以灌溉，需要把新的颜色赋值给该位置，选D

第44题

5处应填（ ）

A.queue.push§

B.queue.push(pt)

C.queue.push(cur)

D.queue.push(Point(ROWS, COLS))

【答案】：A

【解析】

需要把新的位置p放入到队列中，所以选A