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

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

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

适合人群：

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

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

单项选择题

第1题（系统结构）

在内存储器中每个存储单元都被赋予一个唯一的序号，称为（ ）。

A.地址

B.序号

C.下标

D.编号

【答案】：A

【解析】

数据存储在内存中，使用地址作为序号来查找

第2题（软件系统）

编译器的主要功能是（ ）。

A.将源程序翻译成机器指令代码

B.将源程序重新组合

C.将低级语言翻译成高级语言

D.将一种高级语言翻译成另一种高级语言

【答案】：A

【解析】

编译器的功能就是将高级语言转换为低级机器语言，如汇编语言，选A

第3题（应用数学）

设x=true，y=true， z=false，以下逻辑运算表达式值为真的是（ ）。

A.(y∨z)∧x∧z

B.x∧(z∨y)∧z

C.(x∧y)∧z

D.(x∧y)∨(z∨x)

【答案】：D

【解析】

∨表示逻辑或，∧表示逻辑与。A、B、C计算出来都是false，选D

第4题（信息编码）

现有一张分辨率为2048×1024像素的32位真彩色图像。请问要存储这张图像，需要多大的存储空间？（ ）。

A.16MB

B.4MB

C.8MB

D.32MB

【答案】：C

【解析】

(

2048

∗

1024

∗

32

)

/

(

8

∗

1024

)

=

8

(2048*1024*32) / (8*1024) = 8

(2048∗1024∗32)/(8∗1024)=8，选C

第5题（排序）

冒泡排序算法的伪代码如下：

输入：数组L，n≥1。输出：按非递减顺序排序的L。

算法BubbleSort：

1. FLAG ← n //标记被交换的最后元素位置
2. while FLAG > 1 do
3. k ← FLAG – 1
4. FLAG ← 1
5. for j=1 to k do
6. if L(j) > L(j+1) then do
7. L(j) ↔ L(j+1)
8. FLAG ← j

对n个数用以上冒泡排序算法进行排序，最少需要比较多少次？（ ）。

A.n²

B.n-2

C.n-1

D.n

【答案】：C

【解析】

第6行出现了比较，要算一共比较了多少次，就要判断双重循环一共执行了多少次。第4行将FLAG改为了1，所以while循环只会执行一次，故比较次数由for循环决定。for循环执行k次，k=n-1，所以选C

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

设A是n个实数的数组，考虑下面的递归算法：

XYZ(A[1..n])
1. if n=1 then return A[1]
2. else temp ← XYZ(A[1..n-1])
3. if temp<A[n]
4. then return temp
5. else return A[n]

请问算法XYZ的输出是什么？（ ）。

A.A数组的平均

B.A数组的最小值

C.A数组的中值

D.A数组的最大值

【答案】：B

【解析】

第1行n==1时，表示数组中只有1个数，就返回该数。否则就把前n-1的数赋值给temp，然后让temp与n（最后一个数）做比较，第3至5行表示每次比较后返回较小的那个数。所以选B，这个函数就是在求最小值。

第7题（线性表）

链表不具有的特点是（ ）。

A.可随机访问任一元素

B.不必事先估计存储空间

C.插入删除不需要移动元素

D.所需空间与线性表长度成正比

【答案】：A

【解析】

链表不能随机访问任一元素，选A。过去几年都有考过该题，建议机械记忆下来。

第8题（图）

有10个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。

A.9

B.10

C.11

D.12

【答案】：A

【解析】

例如3个点，需要2条边将其相连起来。

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

二进制数1011转换成十进制数是（ ）。

A.11

B.10

C.13

D.12

【答案】：A

【解析】

2³⁺²1+2^0 = 11

第10题（组合学）

五个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（ ）种不同排列方法?

A.48

B.36

C.24

D.72

【答案】：A

【解析】

双胞胎捆绑在一起看做一个整体。故4个小朋友排列，共

4

∗

3

∗

2

∗

1

=

24

4*3*2*1=24

4∗3∗2∗1=24 ， 双胞胎小朋友可以有2种排列方式，所以

24

∗

2

=

48

24*2=48

24∗2=48。也可以使用插空法，除双胞胎外的3个小朋友有

3

∗

2

∗

1

=

6

3*2*1=6

3∗2∗1=6种，周围4个空就有4种方式，最后双胞胎有2种排列方式，故

6

∗

4

∗

2

=

48

6*4*2=48

6∗4∗2=48。

第11题（栈和队列）

下图中所使用的数据结构是（ ）。

A.栈

B.队列

C.二叉树

D.哈希表

【答案】：A

【解析】

典型的堆栈压入和弹出示意图

第12题（树）

独根树的高度为1。具有61个结点的完全二叉树的高度为（ ）。

A.7

B.8

C.5

D.6

【答案】：D

【解析】

2^(n-1) -1 < 完全二叉树节点个数 < 2^n -1。由此计算出高度为6，选D

第13题（应用数学）

干支纪年法是中国传统的纪年方法，由10个天干和12个地支组合成60个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。

天干=(公历年份)除以10所得余数

地支=(公历年份)除以12所得余数

例如，今年是2020年，2020除以10余数为0，查表为“庚”；2020除以12，余数为4，查表为“子”，所以今年是庚子年。

请问1949年的天干地支是（ ）

A.己酉

B.己亥

C.己丑

D.己卯

【答案】：C

【解析】

1949 mod 10 = 9，1949 mod 12 = 5。所以为己丑，选C

第14题（组合学）

10个三好学生名额分配到7个班级，每个班级至少有一个名额，一共有（ ）种不同的分配方案。

A.84

B.72

C.56

D.504

【答案】：A

【解析】

使用插板法，有9个空插6块板子，

C

(

9

,

6

)

=

C

(

9

,

3

)

=

(

9

∗

8

∗

7

)

/

(

3

∗

2

∗

1

)

C(9,6) = C(9,3) = (9*8*7) / (3*2*1)

C(9,6)=C(9,3)=(9∗8∗7)/(3∗2∗1)

第15题（组合学）

有五副不同颜色的手套（共10只手套，每副手套左右手各1只），一次性从中取6只手套，请问恰好能配成两副手套的不同取法有（ ）种。

A.120

B.180

C.150

D.30

【答案】：A

【解析】

恰好配成两副手套，可以先从5副手套中挑出2副，C(5,2) = 10。剩下第5只有6种挑法，第6只有4种挑法，由于先挑哪只没有要求，所以需要除以2，得

6

∗

4

/

2

=

12

6*4/2 = 12

6∗4/2=12 。 最后*

10

∗

12

=

120

10*12=120

10∗12=120*。

阅读程序

#include <cstdlib>
#include <iostream>
using namespace std;

char encoder[26] = {'C', 'S', 'P', 0};
char decoder[26];

string st;

int main() {
int k = 0;
for (int i = 0; i < 26; ++i)
if (encoder[i] != 0) ++k; //k=3
for (char x = 'A'; x <= 'Z'; ++x) { //枚举每一个大写字符
bool flag = true;
for (int i = 0; i < 26; ++i)
if (encoder[i] == x) {
flag = false;
break;
}
if (flag) { //如果x未在encoder中出现
encoder[k] = x;
++k;
}
}
//循环结束encoder = [C,S,P,A,B,D,E,F…]
for (int i = 0; i < 26; ++i)
decoder[encoder[i] – 'A'] = i + 'A'; //d['C']='A' e['A']='C'
//循环结束decoder = [D,E,A,F,G,H,I,J…]
cin >> st;
for (int i = 0; i < st.length(); ++i)
st[i] = decoder[st[i] – 'A'];
cout << st;
return 0;
}

第16题

输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。（ ）

A.正确

B.错误

【答案】：A

【解析】

decoder的范围是0-26，30行是st[i]-‘A’，所以st[i]必须是大写字母。

第17题

若输入的字符串不是空串，则输入的字符串与输出的字符串一定不一样。（ ）

A.正确

B.错误

【答案】：B

【解析】

encoder = [C S P A B D E F G H I J K L M N O Q R T U V W X Y Z]

decoder = [D E A F G H I J K L M N O P Q C R S B T U V W X Y Z]

两个字符列表，从T以后加密和解密都是自己。所以是错误的

第18题

将第12行的“i < 26”改为“i < 16”，程序运行结果不会改变。（ ）

A.正确

B.错误

【答案】：A

【解析】

第13行的目的是求出k=3，改为i<16后，k还是等于3，所以结果不变

第19题

将第26行的“i < 26”改为“i < 16”，程序运行结果不会改变。（ ）

A.正确

B.错误

【答案】：B

【解析】

如果只求前16个，那后10的decoder的值就会发生变化

第20题

若输出的字符串为“ABCABCABCA”， 则下列说法正确的是（ ）

A.输入的字符串中既有Ｓ又有 P

B.输入的字符串中既有 S 又有 B

C.输入的字符串中既有 A 又有Ｐ

D.输入的字符串中既有 A 又有 B

【答案】：A

【解析】

输出（解密）的字符为A，那就是加密之前是A，输入的字符就应该是加密后的字符。

加密前 = [A B C D E F G H I J K L M N O P Q R S T U V W X Y Z]

加密后 = [C S P A B D E F G H I J K L M N O Q R T U V W X Y Z]

即encoder[A]=C，encoder[B]=S，encoder[C]=P

decoder[C]=A，decoder[S]=B，decoder[P]=C

第21题

若输出的字符串为“CSPCSPCSPCSP”，则下列说法正确的是（ ）

A.输入的字符串中既有Ｐ又有 K

B.输入的字符串中既有 J 又有 R

C.输入的字符串中既有 J 又有 K

D.输入的字符串中既有 P 又有 R

【答案】：D

【解析】

加密前 = [A B C D E F G H I J K L M N O P Q R S T U V W X Y Z]

加密后 = [C S P A B D E F G H I J K L M N O Q R T U V W X Y Z]

即encoder[C]=P，encoder[S]=R，encoder[P]=N

decoder[P]=C，decoder[R]=S，decoder[N]=P

#include <iostream>
using namespace std;

long long n, ans;
int k, len;
long long d[1000000];

int main() {
cin >> n >> k;
d[0] = 0;
len = 1;
ans = 0;
for (long long i = 0; i < n; ++i) {
++d[0];
for (int j = 0; j + 1 < len; ++j) {
if (d[j] == k) { //进位
d[j] = 0;
d[j + 1] += 1;
++ans; //只在进位时发生改变，记录进位次数
}
}
if (d[len – 1] == k) { //高精度加法，进位操作
d[len – 1] = 0;
d[len] = 1;
++len; //只在高位进位时发生改变，即记录数字长度
++ans;
}
}
cout << ans << endl;
return 0;
}

假设输入的n是不超过

2

62

2^{62}

262的正整数，k都是不超过10000的正整数，完成下面的判断题和单选题：

第22题

若k=1， 则输出ans时， len=n。（ ）

A.正确

B.错误

【答案】：B

【解析】

k=1时，len始终为2。所以错误

第23题

若k>1， 则输出ans时， len一定小于n。（ ）

A.正确

B.错误

【答案】：B

【解析】

n=1时，len等于1，所以错误

第24题

若k>1， 则输出ans时，$ k^{len}$一定大于n。（ ）

A.正确

B.错误

【答案】：A

【解析】

k进制下的2位数n（len=2），一定小于

k

2

k^2

k2。如10进制下的2位数，都是小于100的。2进制下的2位数，一定小于4。所以正确

第25题

若输入的n等于

10

15

10^{15}

1015，输入的k为1，则输出等于（ ）

A.1

B.

(

10

30

−

10

15

)

/

2

(10^{30}-10^{15})/2

(1030−1015)/2

C.

(

10

30

+

10

15

)

/

2

(10^{30}+10^{15})/2

(1030+1015)/2

D.

10

15

10^{15}

1015

【答案】：D

【解析】

k=1时，len=2，只会在低位（即d[1]）进位，所以进位数量和数字大小相同，选D

第26题

若输入的n等于205,891,132,094,649(即

3

30

3^{30}

330)，输入的k为3，则输出等于（ ）

A.

3

30

3^{30}

330

B.

(

3

30

−

1

)

/

2

(3^{30}-1)/2

(330−1)/2

C.3

30

−

1

^{30}-1

30−1

D.

(

3

30

+

1

)

/

2

(3^{30}+1)/2

(330+1)/2

【答案】：B

【解析】

d[0]向d[1]进位，每3次进一位，进位次数（ans）是

3

29

3^{29}

329

d[1]向d[2]进位，每9次进一位，进位次数（ans）是

3

28

3^{28}

328

d[2]向d[3]进位，每

3

3

3^3

33次进一位，进位次数（ans）是

3

27

3^{27}

327

…

d[29]向d[30]进位，进位次数（ans）是

3

0

3^0

30

求和就是

3

29

+

3

28

+

3

27

+

.

.

.

+

3

0

3^{29}+3^{28}+3^{27}+…+3^0

329+328+327+…+30，根据等比数列求和公式

S

n

=

(

k

n

−

1

)

k

−

1

S_n = \\frac{(k^n-1)}{k-1}

Sn​=k−1(kn−1)​，等于

(

3

30

−

1

)

/

2

(3^{30}-1)/2

(330−1)/2

第27题

若输入的n等于100,010,002,000,090，输入的k为10，则输出等于（ ）

A.11,112,222,444,543

B.11,122,222,444,453

C.11,122,222,444,543

D.11,112,222,444,453

【答案】：D

【解析】

d[0]向d[1]进位，进位次数为10001000200009

d[1]向d[2]进位，进位次数为1000100020000

d[2]向d[3]进位，进位次数为100010002000

d[3]向d[4]进位，进位次数为10001000200

d[4]向d[5]进位，进位次数为1000100020

d[5]向d[6]进位，进位次数为100010002

d[6]向d[7]进位，进位次数为10001000

d[7]向d[8]进位，进位次数为1000100

d[8]向d[9]进位，进位次数为100010

d[9]向d[10]进位，进位次数为10001

d[10]向d[11]进位，进位次数为1000

d[11]向d[12]进位，进位次数为100

d[12]向d[13]进位，进位次数为10

d[13]向d[14]进位，进位次数为1

最后计算为11112222444453

#include <algorithm>
#include <iostream>
using namespace std;

int n;
int d[50][2];
int ans;

void dfs(int n, int sum) {
if (n == 1) {
ans = max(sum, ans); //希望把n个合并到只剩一个时代价能够最大
return;
}
for (int i = 1; i < n; ++i) {
int a = d[i – 1][0], b = d[i – 1][1];
int x = d[i][0], y = d[i][1];
d[i – 1][0] = a + x; //枚举相邻的两个元素合并
d[i – 1][1] = b + y;
for (int j = i; j < n – 1; ++j) //抹去第i个元素
d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
int s = a + x + abs(b – y); //合并相邻两个元素的代价
dfs(n – 1, sum + s); //回溯法
for (int j = n – 1; j > i; –j) //还原第i个元素
d[j][0] = d[j – 1][0], d[j][1] = d[j – 1][1];
d[i – 1][0] = a, d[i – 1][1] = b;
d[i][0] = x, d[i][1] = y;
}
}

int main() {
cin >> n;
for (int i = 0; i < n; ++i) // 读2个数组
cin >> d[i][0];
for (int i = 0; i < n; ++i)
cin >> d[i][1];
ans = 0;
dfs(n, 0);
cout << ans << endl;
return 0;
}

假设输入的n是不超过50的正整数，d[i][0]、d[i][1]都是不超过10000的正整数，完成下面的判断题和单选题：

第28题

若输入n为0，此程序可能会死循环或发生运行错误。（ ）

A.正确

B.错误

【答案】：B

【解析】

n=0时，整个循环不会执行，不会发生错误

第29题

若输入n为20，接下来的输入全为0，则输出为0。（ ）

A.正确

B.错误

【答案】：A

【解析】

输入全为0时，s为0，sum也为0，所以ans也为0

第30题

输出的数一定不小于输入的d[i][0]和d[i][1]的任意一个。（ ）

A.正确

B.错误

【答案】：B

【解析】

n=1时，没有合并，ans为0，此时不管d数组中值为多少。ans都会小于等于d数组中的数字，所以错误。

第31题

若输入的n为20，接下来的输入是20个9和20个0，则输出为（ ）。

A.1890

B.1881

C.1908

D.1917

【答案】：B

【解析】

第一次合并的代价是18，第二次合并的代价是27，第三次合并的代价是36，…，最后一次合并的代价是9*20=180。

所以总的代价=

9

∗

2

+

9

∗

3

+

9

∗

4

+

.

.

.

+

9

∗

20

=

1881

9*2+9*3+9*4+…+9*20=1881

9∗2+9∗3+9∗4+…+9∗20=1881

第32题

若输入的n为30，接下来的输入是30个0和30个5，则输出为（ ）。

A.2000

B.2010

C.2030

D.2020

【答案】：C

【解析】

第一次合并的代价是0，第二次合并的代价是5（10-5），第三次合并的代价是10（15-5），…，最后一次合并的代价是28*5。

所有总的代价=

0

+

5

∗

1

+

5

∗

2

+

.

.

.

+

5

∗

28

=

2030

0+5*1+5*2+…+5*28=2030

0+5∗1+5∗2+…+5∗28=2030

第33题

若输入的n为15，接下来的输入是15到1，以及15到1，则输出为（ ）。

A.2440

B.2220

C.2240

D.2420

【答案】：C

【解析】

第一次合并的代价是30（15+14+15-14），第二次合并的代价是58，第三次合并的代价是84，第四次合并的代价是108，第五次合并的代价是130，第六次合并的代价是150，第七次合并的代价是168，第八次合并的代价是184，第九次合并的代价是198，第十次合并的代价是210，第十一次合并的代价是220，第十二次合并的代价是228，第十三次合并的代价是234，第十四次合并的代价是238。

所有总的代价=30+58+84+108+…+238=2240，选C

完善程序

（质因数分解）给出正整数n，请输出将n质因数分解的结果，结果从小到大输出。

例如：输入n=120，程序应该输出2 2 2 3 5，表示120=2×2×2×3×5.输入保证2≤n≤10^9。提示：先从小到大枚举变量i，然后用i不停试除n来寻找所有的质因子。

试补全程序。

#include <cstdio>
using namespace std;

int n, i;

int main() {
scanf("%d", &n);
for (i = __1__; __2__ < = n; i ++) {
__3__ {
printf("%d ", i);
n = n / i;
}
}
if(__4__)
printf("%d ", __5__);
return 0;
}

第34题

1处应填（ ）

A.1

B.n-1

C.2

D.0

【答案】：C

【解析】

从2开始的每个因数，拿来试除n，选C

第35题

2处应填（ ）

A.n / i

B.n / (i * i)

C.i * i

D.i * i * i

【答案】：C

【解析】

质因数分解只试除到小于等于

n

\\sqrt{n}

n

​的那些质因子，选C

第36题

3处应填（ ）

A.if (n % i == 0)

B.if (i * i <= n)

C.while (n % i == 0)

D.while (i * i <= n)

【答案】：C

【解析】

若n%i==0，则反复除，获得多个质因数，选C

第37题

4处应填（ ）

A.n > 1

B.n <= 1

C.i < n / i

D.i + i <= n

【答案】：A

【解析】

试除完所有小于等于√n的因子后，n还有剩（没有被除成1），说明这个此时n的值就是那个唯一大于√n的质因子

第38题

5处应填（ ）

A.2

B.n / i

C.n

D.i

【答案】：C

【解析】

参考第4题，此时就应该输出n。例如n=5时，输出5

（最小区间覆盖）给出n个区间，第i个区间的左右端点是[

a

i

a_i

ai​,

b

i

b_i

bi​]。现在要在这些区间中选出若干个，使得区间[0,m]被所选区间的并覆盖（即每一个

0

≤

i

≤

m

0\\le i\\le m

0≤i≤m都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数n和m

(

1

≤

n

≤

5000

,

1

≤

m

≤

10

9

)

(1\\le n\\le 5000, 1\\le m\\le 10^9)

(1≤n≤5000,1≤m≤109)。

接下来n行，每行两个整数

a

i

a_i

ai​，

b

i

(

0

≤

a

i

,

b

i

≤

m

)

b_i(0\\le a_i,b_i\\le m)

bi​(0≤ai​,bi​≤m)。

提示：使用贪心法解决这个问题。现有

O

(

n

2

)

O(n^2)

O(n2)的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

#include <iostream>

using namespace std;

const int MAXN = 5000;
int n, m;
struct segment {int a, b; } A[MAXN];

void sort() // 排序
{
for (int i=0; i<n; i++)
for (int j=1; j<n; j++)
if (__1__)
{
segment t = A[j];
__2__
}
}

int main()
{
cin >> n >> m;
for (int i=0; i<n; i++)
cin >> A[i].a >> A[i].b;
sort();
int p = 1;
for (int i=1; i<n; i++)
if (__3__)
A[p++] = A[i];
n = p;
int ans = 0, r = 0;
int q = 0;
while (r < m)
{
while (__4__)
q++;
__5__;
ans++;
}
cout << ans << endl;
return 0;
}

第39题

1处应填（ ）

A.A[j].b>A[j-1].b

B.A[j].a<A[j-1].a

C.A[j].a>A[j-1].a

D.A[j].b<A[j-1].b

【答案】：B

【解析】

冒泡排序，每次循环将左端点最大的线段排到最右边

第40题

2处应填（ ）

A.A[j+1]=A[j];A[j]=t;

B.A[j-1]=A[j];A[j]=t;

C.A[j]=A[j+1];A[j+1]=t;

D.A[j]=A[j-1];A[j-1]=t;

【答案】：D

【解析】

如果左侧线段的左端点更大，左右交换

第41题

3处应填（ ）

A.A[i].b>A[p-1].b

B.A[i].b<A[i-1].b

C.A[i].b>A[i-1].b

D.A[i].b<A[p-1].b

【答案】：A

【解析】

把被其他更大范围的线段覆盖的线段删除

第42题

4处应填（ ）

A.q+1<n&&A[q+1].a<=r

B.q+1<n&&A[q+1].b<=r

C.q<n&&A[q].a<=r

D.q<n&&A[q].b<=r

【答案】：A

【解析】

下下一个线段存在且左端点在已覆盖区间右边界左侧，则下个线段就被跳过。所以出while循环时，会保留最后一个线段左端点在已覆盖区间右边界左侧

第43题

5处应填（ ）

A.r=max(r,A[q+1].b)

B.r=max(r,A[q].b)

C.r=max(r,A[q+1].a)

D.q++

【答案】：B

【解析】

确定新的已覆盖区间右边界