历年CSP-J初赛真题解析 | 2021年CSP-J初赛-平芜编程栈

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

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

适合人群：

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

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

单项选择题

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

以下不属于面向对象程序设计语言的是（）。

A.C++

B.Python

C.Java

D.C

【答案】：D

【解析】

C语言面向过程，不面向对象

第2题（基本常识）

以下奖项与计算机领域最相关的是（）。

A.奥斯卡奖

B.图灵奖

C.诺贝尔奖

D.普利策奖

【答案】：B

【解析】

奥斯卡奖是电影界的，普利策奖是摄影方面的

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

目前主流的计算机储存数据最终都是转换成（）数据进行储存。

A.二进制

B.十进制

C.八进制

D.十六进制

【答案】：A

【解析】

主流计算机都是将数据转换为二进制进行存储的，因为二进制最容易实现，利用高低电平就可以体现0和1。ENIAC是十进制计算机

第4题（排序）

以比较作为基本运算，在N个数中找出最大数，最坏情况下所需要的最少的比较次数为（）。

A.N^2

B.N

C.N-1

D.N+1

【答案】：C

【解析】

最坏的情况需要进行相邻比较，如1与2、1与3、1与4…、1与n，即N-1次

第5题（栈和队列）

对于入栈顺序为a，b，c，d，e的序列，下列（）不是合法的出栈序列。

A.a，b，c，d，e

B.e，d，c，b，a

C.b，a，c，d，e

D.c，d，a，e，b

【答案】：D

【解析】

A是合法的，如进入栈后就出来

B是合法的，就是5个元素全部入栈后再依次出来

C是合法的，可以模拟出来

D是非法的，a出不来，因为此时栈顶为b

出栈序列中的每个数的序号后面的序号比它小的数，是按递减排列的（可将a/b/c/d/e转为1/2/3/4/5后检查）

第6题（树）

对于有n个顶点、m条边的无向连通图（m>n），需要删掉（）条边才能使其成为一棵树。

A.n-1

B.m-n

C.m-n-1

D.m-n+1

【答案】：D

【解析】

n个节点的树有n-1条边，所以需要删除m-(n-1)条边，选D

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

二进制数101.11对应的十进制数是（）。

A.6.5

B.5.5

C.5.75

D.5.25

【答案】：C

【解析】

1 ∗ 2 2 + 0 ∗ 2 1 + 1 ∗ 2 0 + 1 ∗ 2 − 1 + 1 ∗ 2 − 2 = 5.75 1*2^2+0*2^1+1*2^0+1*2^{-1}+1*2^{-2} = 5.751∗22+0∗21+1∗20+1∗2−1+1∗2−2=5.75

第8题（树）

如果一棵二叉树只有根结点，那么这棵二叉树高度为1。请问高度为5的完全二叉树有（）种不同的形态？

A.16

B.15

C.17

D.32

【答案】：A

【解析】

去掉满二叉树右下角的节点后的树就是完全二叉树，即若给所有节点编号，完全二叉树中逐层遍历的所有节点的编号是连续的。高度为5时，第5层可以有16个叶子节点，可以删除0-15个叶子节点，共16种形态

第9题（栈和队列）

表达式a*(b+c)*d的后缀表达式为（），其中“*”和“+”是运算符。

A.**a+bcd

B.abc+*d*

C.abc+d**

D.*a*+bcd

【答案】：B

【解析】

中缀表达式转为后缀表达式，可以使用

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

2.将运算符移到每对运算式的右边：( ( a ( b c ) + ) ∗ d ) ∗ ((a(bc)+)*d)*((a(bc)+)∗d)∗

3.去括号：a b c + ∗ d ∗ abc+*d*abc+∗d∗

第10题（组合学）

6个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有（）种。

A.10

B.15

C.30

D.20

【答案】：B

【解析】

第一队，从6人中挑2人，C(6,2) = 6*5/2 = 15

第二队，从4人中挑2人，C(4,2) = 4*3/2 = 6

第三队，从2人中挑2人，C(2,2) = 2*1/2 = 1

如果15 * 6 * 1 = 90，则是有顺序的挑法，所以需要去掉3支队伍的不同排列数A(3,3)，所以90 / A(3,3) = 15

第11题（树）

在数据压缩编码中的哈夫曼编码方法，在本质上是一种（）的策略。

A.枚举

B.贪心

C.递归

D.动态规划

【答案】：B

【解析】

哈夫曼编码本质上是哈夫曼树的一个应用。哈夫曼树构造就是给定N个带权值的叶子节点，构造出一个带权路径长度最小的二叉树。如果想要带权路径长度最小，我们应该将权值越小的节点放在越底层，因为这些节点路径长度比较长，权值小点，这样计算出来的带权路径长度就较小。这个其实就是基于贪心的策略。

第12题（组合学）

由1，1，2，2，3这五个数字组成不同的三位数有（）种。

A.18

B.15

C.12

D.24

【答案】：A

【解析】

假设三位数是abc，按照如下计算，共18种不同的数字

a=1 b=1 c=2/3 2种； b=2 c=1/2/3 3种； b=3 c=1/2 2种； a=2 b=1 c=1/2/3 3种； b=2 c=1/3 2种； b=3 c=1/2 2种； a=3 b=1 c=1/2 2种； b=2 c=1/2 2种；

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

考虑如下递归算法

solve(n) if n<=1 return 1 else if n>=5 return n*solve(n-2) else return n*solve(n-1)

则调用solve(7) 得到的返回结果为（）。

A.105

B.840

C.210

D.420

【答案】：C

【解析】

列出递推矩阵，得到结果为210，选C

i 0 1 2 3 4 5 6 7 f(i) 1 1 2*f(1)=2 3*f(2)=6 4*f(3)=24 5*f(3)=30 6*f(4)=144 7*f(5)=210

第14题（图）

以a为起点，对右边的无向图进行深度优先遍历，则b、c、d、e四个点中有可能作为最后一个遍历到的点的个数为（）。

A.1

B.2

C.3

D.4

【答案】：B

【解析】

列出所有深度优先遍历的结果：

abdce

acdbe

acedb

所以作为最后一个遍历到的点的个数有2个，分别是b和e

第15题（应用数学）

有四个人要从A点坐一条船过河到B点，船一开始在A点。该船一次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为1，2，4，8，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短（）时间可以让四个人都过河到B点（包括从B点把船开回A点的时间）

A.14

B.15

C.16

D.17

【答案】：B

【解析】

使用贪心策略，第一条就是希望过河时间最长的人少来回，过去后就不要再回来了。第二条就是希望把船开回来的人的时间尽可能短。画个模拟图

1&2&4&8 A --------- B 4&8 A ---1&2---> B 4&8 A <---1---- B 2 1 A ---4&8---> B 2 1 A <---2---- B 4&8 A ---1&2---> B 4&8

最短的时间=2+1+8+2+2=15

阅读程序

#include <iostream> using namespace std; int n; int a[1000]; int f(int x) //统计x转为二进制后1的个数 { int ret = 0; for (; x; x &= x - 1) ret++; return ret; } int g(int x) //获取x转为二进制后1的最低位 { return x & -x; } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cout << f(a[i]) + g(a[i]) << ' '; cout << endl; return 0; }

第16题

输入的n等于1001时，程序不会发生下标越界。（）

A.正确

B.错误

【答案】：B

【解析】

a[1000]的下标范围为a[0] - a[999]，所以a[1000]会导致越界

第17题

输入的a[i]必须全为正整数，否则程序将陷入死循环。（）

A.正确

B.错误

【答案】：B

【解析】

尝试将一个负数带入运算，f函数的二进制运算逻辑没有发生变化，也不会陷入死循环。另外第21题就有负数输入

第18题

当输入为“5 2 11 9 16 10”时，输出为“3 4 3 17 5”。（）

A.正确

B.错误

【答案】：B

【解析】

输入数据后逐个计算，输出为3 4 3 17 4

第19题

当输入为“1 511998”时，输出为“18”。（）

A.正确

B.错误

【答案】：A

【解析】

511998转为二进制后为0111 1100 1111 1111 1110，计算的结果为18，所以是对的

第20题

将源代码中g函数的定义（14-17行）移到main函数的后面，程序可以正常编译运行。（）

A.正确

B.错误

【答案】：B

【解析】

运行main函数时，如果g函数未被声明，是无法调用的

第21题

当输入为“2 -65536 2147483647”时，输出为（）。

A.“65532 33”

B.“65552 32”

C.“65535 34”

D.“65554 33”

【答案】：B

【解析】

2147483647换算为二进制后，是2^31-1，即有31个1，所以输出为32，选B

#include <iostream> #include <string> using namespace std; char base[64]; char table[256]; void init() { for (int i=0; i<26; i++) base[i] = 'A' + i; //10-13行，是为了给每个字符标记一个唯一的数字 for (int i=0; i<26; i++) base[26+i] = 'a' + i; for (int i=0; i<10; i++) base[52+i] = '0' + i; base[62] = '+', base[63] = '/'; for (int i=0; i<256; i++) table[i] = 0xff; for (int i=0; i<64; i++) table[base[i]] = i; table['='] = 0; } string decode(string str) { string ret; int i; for (i=0; i<str.size(); i+=4) { //将4个6位二进制变成3个8位二进制 ret += table[str[i]] << 2 | table[str[i+1]] >> 4; //i的6位 + i+1的前2位 if (str[i+2] != '=') ret += (table[str[i+1]] & 0x0f) << 4 | table[str[i+2]] >> 2; //i+1的后4位 + i+2的前4位 if (str[i+3] != '=') ret += table[str[i+2]] << 6 | table[str[i+3]]; //i+2的后2位 + i+3的6位 } return ret; } int main() { init(); cout << int(table[0]) << endl; string str; cin >> str; cout << decode(str) << endl; return 0; }

第22题

输出的第二行一定是由小写字母、大写字母、数字和“+”、“/”、“=”构成的字符串。（）

A.正确

B.错误

【答案】：B

【解析】

算出来的结果可以是256(2^8)以内的任何一个值，有可能为空格

第23题

可能存在输入不同，但输出的第二行相同的情形。（）

A.正确

B.错误

【答案】：A

【解析】

超出ASCII集后可能会重复

第24题

输出的第一行为“-1”。（）

A.正确

B.错误

【答案】：A

【解析】

11111111在char中就是-1，强转成int，还是-1

第25题

设输入字符串长度为n，decode函数的时间复杂度为（）

A.O(n^(1/2))

B.O(n)

C.O(nlogn)

D.O(n^2)

【答案】：B

【解析】

只有一层循环，从0循环到n-1

第26题

当输入为“Y3Nx”时，输出的第二行为（）。

A.“csp”

B.“csq”

C.“CSP”

D.“Csp”

【答案】：B

【解析】

把字符带进去硬算，最后需要截断后8位为113，即q

第27题

当输入为“Y2NmIDIwMjE=”时，输出的第二行为（）。

A.“ccf2021”

B.“ccf2022”

C.“ccf 2021”

D.“ccf 2022”

【答案】：C

【解析】

每4个字符转成3个字符，Y2Nm转成ccf，IDIw转成 20，MjE中M和j转成1个字符2，j和E转成1个字符1。合并起来就是“ccf 2021” ，选C

#include <iostream> using namespace std; const int n = 100000; const int N = n + 1; int m; int a[N], b[N], c[N], d[N]; //a[N]标记一个数是不是质数，b[N]用来存质数，c[N]用来存i的最小质因数的个数，d[N]是g[x]连乘积中去除最小质因子连乘积的部分，p指最大质因子 int f[N], g[N]; //f[N]用来存i的约数个数，g[N]用来存所有约数之和 void init() { f[1] = g[1] = 1; for (int i=2; i<=n; i++) { //枚举i if (!a[i]) { // i是质数 b[m++] = i; //使用数组b存放地i个质数 c[i] = 1, f[i] = 2; //i的最小质因数数i，个数1个。i的约数2个：1和i d[i] = 1, g[i] = i + 1; } for (int j=0; j<m&&b[j]*i<=n; j++) { int k = b[j]; //k为当前的质数 a[i*k] = 1; //标记质数k的i倍为合数 if (i%k==0) { //k是i*k的最小质因子，i包括最小质因子k，c[i]是k的个数 c[i*k] = c[i] + 1; // 在c[i]最小质因子k的个数基础上加1 f[i*k] = f[i] / c[i*k] * (c[i*k]+1); //f[i*k]的最小质因子k比f[i]多1个，如2^2变为2^3，那么先除以3，再乘以4 d[i*k] = d[i]; //根据定义，连乘积中不包括k连乘积的部分 g[i*k] = g[i] * k + d[i]; break; } else { // i不能整除k c[i*k] = 1; // i不包括最小质因子k，i*k的最小质因子k的个数1 f[i*k] = 2 * f[i]; // f[i*k]的质因子比f[i]多一个k，且个数1，所以因数个数为f[i]*(1+1) d[i*k] = g[i]; // i*k比i多一个质因子k，d[i*k]是g[i*k]中不包括k连乘积的部分 g[i*k] = g[i] * (k+1); // 约数和公式 } } } } int main() { init(); int x; cin >> x; cout << f[x] << ' ' << g[x] << endl; return 0; }

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

第28题

若输入不为“1”，把第13行删去不会影响输出的结果。（）

A.正确

B.错误

【答案】：A

【解析】

对代码中所有数组进行暴力打表，猜测其作用：

i	2	3	4	5	6	7	8	9	10
a[ ]	0	0	1	0	1	0	1	1	1
b[ ]	2	3	5	7	11	13	19	23	29
c[ ]	1	1	2	1	1	1	3	2	1
d[ ]	1	1	1	1	4	1	1	1	6
f[ ]	2	2	3	2	4	2	4	3	4
g[ ]	3	4	7	6	12	8	15	13	18

13行对1进行预处理，枚举是从2开始，全程没有与1相关的数据输出，如果输入从2开始，就没有影响

第29题

第25行的“f[i]/c[i*k]”可能存在无法整除而向下取整的情况。（）

A.正确

B.错误

【答案】：B

【解析】

f[i]表示i的质因数个数，c[i * k]表示i * k的最小质因数个数，f[i]=(num1+1)(num2+1)…(numn+1)，其中numx为质因数，c[i * k]=c[i]+1（见代码）=num1+1，这两个数之间一定是倍数的关系

第30题

在执行完init() 后，f数组不是单调递增的，但g数组是单调递增的。（）

A.正确

B.错误

【答案】：B

【解析】

约数和不一定是单调递增，如g[8]=1+2+4+8=15，g[9]=1+3+9=13

第31题

init函数的时间复杂度为（）

A.O(n)

B.O(nlogn)

C.O(n*n^(1/2))

D.O(n^2)

【答案】：A

【解析】

欧拉线性筛的特点

第32题

在执行完init() 后，f[1] ，f[2] ，f[3] … f[100] 中有（）个等于2。

A.23

B.24

C.25

D.26

【答案】：C

【解析】

只有质数的约数个数为2，所以也就是求1-100中有多少个质数，有25个，选C

第33题

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

A.“15 1340”

B.“15 2340”

C.“16 2340”

D.“16 1340”

【答案】：C

【解析】

1000=2³⁺⁵3，约数个数=(3+1)*(3+1)=16。有1000和500两个约数，肯定超过1340，所以选C

完善程序

有n个人围成一个圈，依次标号0至n-1。从0号开始，依次，0,1,0,1,…交替报数，报到1的人会离开，直至圈中只剩一个人。求最后剩下人的编号。

试补全模拟程序。

#include <iostream> using namespace std; const int MAXN = 1000000; int F[MAXN]; int main() { int n; cin >> n; int i = 0, p = 0, c = 0; //i是人的编号，c是已出队的人数，p表示当前要报的数 while (__1__) { if (F[i] == 0) { //表示i在队中 if (__2__) { //报了1 F[i] = 1; //i出队 __3__; } __4__; } __5__; } int ans = -1; for (i=0; i<n; i++) if (F[i] == 0) //编号为i这个人在队中 ans = i; cout << ans << endl; return 0; }

第34题

1处应填（）

A.i<n

B.c<n

C.i<n-1

D.c<n-1

【答案】：D

【解析】

题目要求只剩1个人为止，反过来说就是还剩大于1个人就继续循环。所以若作为出队人数的c小于n-1人，就继续循环。选D

第35题

2处应填（）

A.i % 2 == 0

B.i % 2 == 1

C.p

D.!p

【答案】：C

【解析】

报了1这个数就要出队，而p表示当前要报的数，所以选C

第36题

3处应填（）

A.i++

B.i = (i + 1) % n

C.c++

D.p ^= 1

【答案】：C

【解析】

上一行表示出队，所以这里应该是出队人数+1，所以选C

第37题

4处应填（）

A.i++

B.i = (i + 1) % n

C.c++

D.p ^= 1

【答案】：D

【解析】

报完数后应该就是要处理下一个要报的数，只有D选项是对p（要报的数）进行操作。1^1=0，01=1，选D

第38题

5处应填（）

A.i++

B.i = (i + 1) % n

C.c++

D.p ^= 1

【答案】：B

【解析】

这个是要处理下一个要报数的人i，i走到n-1后，再加1需要通过mod运算变为0。所以选B

（矩形计数）平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只记一次。

试补全枚举算法。

#include <iostream> using namespace std; struct point { int x, y, id; }; bool equals(point a, point b) { return a.x == b.x && a.y == b.y; } bool cmp(point a, point b) { //相当于a<b return __1__; } void sort(point A[], int n) { //将关键点的集合按照从小到大方式排序 for ( int i=0; i<n; i++) for (int j=1; j<n; j++) if (cmp(A[j], A[j-1])) { point t = A[j]; A[j] = A[j-1]; A[j-1] = t; } } int unique(point A[], int n) { //unique为去重 int t = 0; for (int i=0; i<n; i++) if (__2__) A[t++] = A[i]; return t; } bool binary_search(point A[], int n, int x, int y) { //二分搜索，判断p是否在A[0]-A[n-1]中 point p; p.x = x; p.y = y; p.id = n; int a = 0, b = n - 1; while (a<b) { int mid = __3__; if (__4__) a = mid + 1; else b = mid; } return equals(A[a], p); } const int MAXN = 1000; point A[MAXN]; int main() { int n; cin >> n; for (int i=0; i<n; i++) { cin >> A[i].x >> A[i].y; A[i].id = i; } sort(A, n); n = unique(A,n); int ans = 0; for (int i=0; i<n; i++) for (int j=0; i<n; j++) if (__5__ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) { ans ++; } cout << ans << endl; return 0; }

第39题

①处应填（）

A.a.x != b.x ? a.x < b.x : a.id < b.id

B.a.x != b.x ? a.x < b.x : a.y < b.y

C.equals(a, b) ? a.id < b.id : a.x < b.x

D.equals(a, b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)

【答案】：B

【解析】

因为equals是比坐标，cmp也只能比坐标，所有带id的选项都不能选，所以只能选B。优先级是先比较x再比较y。

第40题

②处应填（）

A.i == 0 || cmp(A[i], A[i-1])

B.t == 0 || equals(A[i], A[t-1])

C.i == 0 || !cmp(A[i], A[i-1])

D.t == 0 || !equals(A[i], A[t-1])

【答案】：D

【解析】

当A[t-1]不等于A[i]，就把A[i]放到A[t]的位置，然后t++。选D

第41题

③处应填（）

A.b - (b - a) / 2 +1

B.(a + b + 1) >> 1

C.(a + b) >> 1

D.a + (b - a + 1) / 2

【答案】：C

【解析】

二分查找方法有很多种，没有必要背下来，唯一的标准是不能死循环，死循环就是发生在a与b最接近时（a与b的差值为1），即区间为[a, a+1]。此时需要拆为[a]和[a+1]这两个区间，而二分查找拆成的区间就是[a, mid]，[mid+1, a+1]，那么推断出mid的值要等于a。可以将b=a+1代入，选C。右移一位相当于除2。

第42题

④处应填（）

A.!cmp(A[mid], p)

B.cmp(A[mid], p)

C.cmp(p, A[mid])

D.!cmp(p, A[mid])

【答案】：B

【解析】

目的是要淘汰不等于p的部分，4个选项，只有B选项成立时，A[0] … A[mid]不可能等于p，因为此处是A[0] … A[mid]小于p

第43题

⑤处应填（）

A.A[i].x == A[j].x