CSP-J2020初赛试题及详细解析
请大家注意，CSP-J历年的试题，是分不同版本的卷子的，不同版本，题目一致，但选择题的选项顺序不同，本解析，是以下面发的试题的选项顺序作答的。
视频讲解请点击：CSP/NOIP初赛视频讲解
本篇题解，先发解析，再发试题，试题在解析下面。
一、单项选择题(共15题，每题2分，共计30分；每题有且仅有一个正确选项)
B
常识题
A
编译型：将源码直接转换为二进制代码，生成目标程序，然后将目标程序连接成可执行的程序。流程为：高级语言源码 —编译—> 目标程序 —连接—> 可执行程序。
3.C
与：∧ and &&
或：∨ or ||
非：¬ ! NOT
异或：^
优先级：括号 ＞ 非 ＞ 与 ＞ 异或,或，口诀：非与或
4.B
2048 * 1024 * 32 / 8 / 1024 /1024 MB
5.D
冒泡排序比较次数最少的情况：原本所有数字的顺序就是对的，一趟比较结束，所以是比较 n-1 次。
6.B
代码解析如下，分析代码可知，题目是求n个数的最小数：
int XYZ(int a[],int n)//n个元素 从下标 1 开始存储
{
if(n==1)
return a[1]；
else
{
int temp=XYZ(a,n-1);
return min(temp,a[n]);
}
}
7.B
可随机访问任一元素是线性表的特点。
8.C
n个顶点的无向图，至少需要n-1条边，才能连通。
9.C
按权展开，计算可得11。
10.D
捆绑法求解：A4/4 * A2/2 = 48
11.C
常识题
D
floor(log2n)+1 = 6
B
1949%10=9，因此是已
1949%12=5，因此是丑
14.B
插板法C6/9 = 84
D
先从5副手套选2副：C2/5
再从生下3副选2副，每副选1只：C2/3 * C1/2 * C1/2
因此答案 = C2/5 * C2/3 * C1/2 * C1/2 = 120
二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填√, 错误填×；除特殊说明外，判断题1.5分，选择题3分，共计40分)
1.
这个程序通过encoder,decoder两次转换产生一个乱序字符串，利用乱序字符串加密
encoder =“CSPABDEFGHIKLMNOQRTUVWXYZ”
decoder =“DEAFGHIKLMNOPQCRSBTUVWXYZ”
（1）√
因为数组大小为26，所以只能是大写字母，如果有小写字母会越界。
（2）×
根据decoder字符串的值，如果输入是T~Z之间的字母，输出是一样的。
（3）√
第12行是统计字符数，由于默认有3个字母，因此修改循环的值不影响统计结果。
（4）×
这里改了之后，decoder数组会少一段，影响输出。
（5）A
输出中有ABC，对应decoder[2]、decoder[18]、decoder[15],则输入的字符分别为字符C S P。
（6）D
输出中有ABC，对应decoder[15]、decoder[17]、decoder[13],则输入的字符分别为字符P R N。
代码的作用是十进制的 n 转换成 k 进制的数字，输出的ans为进位的次数,len为结果的长度。
（1）×
当k为1时，n为1，1进制的1，len 为2，所以错误。
（2）×
输入n为1且 k > 1 时，ans == n
（3）√
n转化为 len 位的 k 进制数字值 最大值为 k^len - 1 ，因此k^len>n。
（4）D
当输入的 k 为 1 时，会直接进位，len为2，但是后面触发不了len++的条件，结果就是，len一直是2，每次 d[0]++ 都会进位，输出 ans == n。
（5）A
第1位，每k次运算进位1次；
第2位，每k2次运算进位1次；
……
因此第1位，会产生330/3次进位，第2位会产生330/32次进位……最后一位，会产生1次进位。
因此答案 = 330 / 3 + 330/32 + … + 1
根据等比数列求和公式Sn = (a_1 (1-qn ))/(1-q) = (330 – 1) / (3 - 1)
（6）D
同上一问：
第1位进位次数 = 100010002000090 / 10次
第2位进位次数 = 100010002000090 / 100次
…
最后一位进位次数 = 1次
对上述数值求和可得D
每次将前两项合并，并清除一项，累计计算：a+x+abs(b-y)的和。
（1）×
输入 n 为0，什么都没做，结束程序。
（2）√
全是0，运算过程中所有 s 都是 0，ans 也是0
（3）×
这里减法，所以 ans 可能小于 输入的 d[ i ][ 1 ],例如
输入：
0 0
5 5
输出：
0
（4）C
第二列为0，可以忽略。
第1次合并：9+9=92
第2次合并：18+9=93
第3次合并：27+9=94
…
第19次合并：929
因此和 = 92 + 93 + … + 9 * 20 = 1881
（5）B
第1次合并：5-5=0
第2次合并：5+5-5=5=51
第3次合并：10+5-5=10=52
…
第29次合并：530-5=528
求和 = 5 * (1 + 2 + … + 28) = 2030
（6）D
对于第1列：
第1次合并 = 15+14
第2次合并 = 15+14+13
…
第14次合并 = 15+14+13+12+…+1
1514+1414+1313+…+11 = 1225
对于第2列：
第1次合并 = 15-14
第2次合并 = 15+14-13
第3次合并 = 15+14+13-12
……
第14次合并 = 15+14+13+12+…+2-1
1513+1412+…+3*1=1001，这里加上14个1
最终答案是：2240
三、完善程序（单选题，每小题3分，共计30分）
1.
（1）D
因子最小为2，所以 选 i = 2
（2）D
因子最大为 根号n 所以选 i * i
（3）D
由题目可知，一个因子可能被分解出好多次
（4）A
分解完成后，n 的值为 1 或者质数，判断剩余的是不是质数。
（5）D
不是 1 的 话需要单独输出
（1）C
按照区间起点进行排序
（2）C
基础的交换代码
（3）C
这里筛掉起点靠后同时终点靠前的区间，因为这样的区间完整的被前面选中的区间包含了。
（4）B
此时剩余的区间逐个选用，优先选用能和前一个区间连接的情况下，右端点更靠右的区间。
（5）B
更新r为当前选中区间的右端点的值。
视频讲解请点击：CSP/NOIP初赛视频讲解
本篇题解，先发解析，再发试题，试题在解析下面。
一、单项选择题(共15题，每题2分，共计30分；每题有且仅有一个正确选项)
B
常识题
A
编译型：将源码直接转换为二进制代码，生成目标程序，然后将目标程序连接成可执行的程序。流程为：高级语言源码 —编译—> 目标程序 —连接—> 可执行程序。
3.C
与：∧ and &&
或：∨ or ||
非：¬ ! NOT
异或：^
优先级：括号 ＞ 非 ＞ 与 ＞ 异或,或，口诀：非与或
4.B
2048 * 1024 * 32 / 8 / 1024 /1024 MB
5.D
冒泡排序比较次数最少的情况：原本所有数字的顺序就是对的，一趟比较结束，所以是比较 n-1 次。
6.B
代码解析如下，分析代码可知，题目是求n个数的最小数：
int XYZ(int a[],int n)//n个元素 从下标 1 开始存储
{
if(n==1)
return a[1]；
else
{
int temp=XYZ(a,n-1);
return min(temp,a[n]);
}
}
7.B
可随机访问任一元素是线性表的特点。
8.C
n个顶点的无向图，至少需要n-1条边，才能连通。
9.C
按权展开，计算可得11。
10.D
捆绑法求解：A4/4 * A2/2 = 48
11.C
常识题
D
floor(log2n)+1 = 6
B
1949%10=9，因此是已
1949%12=5，因此是丑
14.B
插板法C6/9 = 84
D
先从5副手套选2副：C2/5
再从生下3副选2副，每副选1只：C2/3 * C1/2 * C1/2
因此答案 = C2/5 * C2/3 * C1/2 * C1/2 = 120
二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填√, 错误填×；除特殊说明外，判断题1.5分，选择题3分，共计40分)
1.
这个程序通过encoder,decoder两次转换产生一个乱序字符串，利用乱序字符串加密
encoder =“CSPABDEFGHIKLMNOQRTUVWXYZ”
decoder =“DEAFGHIKLMNOPQCRSBTUVWXYZ”
（1）√
因为数组大小为26，所以只能是大写字母，如果有小写字母会越界。
（2）×
根据decoder字符串的值，如果输入是T~Z之间的字母，输出是一样的。
（3）√
第12行是统计字符数，由于默认有3个字母，因此修改循环的值不影响统计结果。
（4）×
这里改了之后，decoder数组会少一段，影响输出。
（5）A
输出中有ABC，对应decoder[2]、decoder[18]、decoder[15],则输入的字符分别为字符C S P。
（6）D
输出中有ABC，对应decoder[15]、decoder[17]、decoder[13],则输入的字符分别为字符P R N。
代码的作用是十进制的 n 转换成 k 进制的数字，输出的ans为进位的次数,len为结果的长度。
（1）×
当k为1时，n为1，1进制的1，len 为2，所以错误。
（2）×
输入n为1且 k > 1 时，ans == n
（3）√
n转化为 len 位的 k 进制数字值 最大值为 k^len - 1 ，因此k^len>n。
（4）D
当输入的 k 为 1 时，会直接进位，len为2，但是后面触发不了len++的条件，结果就是，len一直是2，每次 d[0]++ 都会进位，输出 ans == n。
（5）A
第1位，每k次运算进位1次；
第2位，每k2次运算进位1次；
……
因此第1位，会产生330/3次进位，第2位会产生330/32次进位……最后一位，会产生1次进位。
因此答案 = 330 / 3 + 330/32 + … + 1
根据等比数列求和公式Sn = (a_1 (1-qn ))/(1-q) = (330 – 1) / (3 - 1)
（6）D
同上一问：
第1位进位次数 = 100010002000090 / 10次
第2位进位次数 = 100010002000090 / 100次
…
最后一位进位次数 = 1次
对上述数值求和可得D
每次将前两项合并，并清除一项，累计计算：a+x+abs(b-y)的和。
（1）×
输入 n 为0，什么都没做，结束程序。
（2）√
全是0，运算过程中所有 s 都是 0，ans 也是0
（3）×
这里减法，所以 ans 可能小于 输入的 d[ i ][ 1 ],例如
输入：
0 0
5 5
输出：
0
（4）C
第二列为0，可以忽略。
第1次合并：9+9=92
第2次合并：18+9=93
第3次合并：27+9=94
…
第19次合并：929
因此和 = 92 + 93 + … + 9 * 20 = 1881
（5）B
第1次合并：5-5=0
第2次合并：5+5-5=5=51
第3次合并：10+5-5=10=52
…
第29次合并：530-5=528
求和 = 5 * (1 + 2 + … + 28) = 2030
（6）D
对于第1列：
第1次合并 = 15+14
第2次合并 = 15+14+13
…
第14次合并 = 15+14+13+12+…+1
1514+1414+1313+…+11 = 1225
对于第2列：
第1次合并 = 15-14
第2次合并 = 15+14-13
第3次合并 = 15+14+13-12
……
第14次合并 = 15+14+13+12+…+2-1
1513+1412+…+3*1=1001，这里加上14个1
最终答案是：2240
三、完善程序（单选题，每小题3分，共计30分）
1.
（1）D
因子最小为2，所以 选 i = 2
（2）D
因子最大为 根号n 所以选 i * i
（3）D
由题目可知，一个因子可能被分解出好多次
（4）A
分解完成后，n 的值为 1 或者质数，判断剩余的是不是质数。
（5）D
不是 1 的 话需要单独输出
（1）C
按照区间起点进行排序
（2）C
基础的交换代码
（3）C
这里筛掉起点靠后同时终点靠前的区间，因为这样的区间完整的被前面选中的区间包含了。
（4）B
此时剩余的区间逐个选用，优先选用能和前一个区间连接的情况下，右端点更靠右的区间。
（5）B
更新r为当前选中区间的右端点的值。
