历年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题（信息编码）
现有一张分辨率为2048x1024像素的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请问算法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
【解析】
23+21+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
#include
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
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 = rac{(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
#include
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
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 0le ile m 0≤i≤m都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。
输入第一行包含两个整数n和m ( 1 ≤ n ≤ 5000 , 1 ≤ m ≤ 10 9 ) (1le nle 5000, 1le mle 10^9) (1≤n≤5000,1≤m≤109)。
接下来n行，每行两个整数 a i a_i ai， b i ( 0 ≤ a i , b i ≤ m ) b_i(0le a_i,b_ile m) bi(0≤ai,bi≤m)。
提示：使用贪心法解决这个问题。现有 O ( n 2 ) O(n^2) O(n2)的时间复杂度排序，然后贪心选择这些区间。
试补全程序。
#include 第39题
1处应填（ ）
A.A[j].b>A[j-1].b
B.A[j].a
C.A[j].a>A[j-1].a
D.A[j].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
C.A[i].b>A[i-1].b
D.A[i].b
【答案】：A
【解析】
把被其他更大范围的线段覆盖的线段删除
第42题
4处应填（ ）
A.q+1 B.q+1 C.q D.q 【答案】：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 【解析】 确定新的已覆盖区间右边界
