信息学竞赛即将开始，在开始之前，我们需要总结一下历年真题，查漏补缺！
本篇文章，我们一起来回顾CSP-J2020真题。公众号回复CSP-J2020答案获取题目的答案。
1
CSP-J2020题目说明
1、题目类型与分值
CSP认证入门级第一轮总体来看，只有选择题和判断题两种形式。从题目类型来看，主要有三种题型：
单项选择题涉及到的知识点最多，题目数量也最多，但是每道题目的分值都比较小。单项选择题一共有15道题目，每道题目都是2分，共计30分。
阅读程序题一共有3道题目，每道题目有多个小题，小题分为判断题和单选题。一般来说，判断题是1.5分，选择题是3分，如果题目有特殊说明，那么分值会有所变化，总分40分不变。
完善程序题有两道题，一般来说，每道题都对应一个完整的功能，并且代码比较复杂，通常需要结合代码上下文及整体功能协助理解。完善程序题每道题都有5个空，每个空3分，共计30分。
因为CSP认证是从19年才开始，18年及以前主要都是NOIP，CSP认证和NOIP类型相似。CSP认证将NOIP中所有的题目形式都变成了选择或者填空。
2、知识板块
我喜欢把信息学初赛的题目分为五大板块：
信息学基本知识与理论
进制、编码与逻辑
程序设计基础
数据结构
数学与算法
一般来说，我们比较重视的是单项选择题的每一道题属于的板块，在单项选择题中，第三大板块考查的概率较低，因为第三大板块会结合第四大板块和第五大板块，在阅读程序题和完善程序题中出现，并且占据了70分的分值，足够考查程序设计基础了。所以在选择题中会更多考查另外四大板块的理论部分。
2020年的真题选择题分布如下：
信息学基本知识与理论：1、2、4
进制、编码与逻辑：3、9
程序设计基础
数据结构：7、8、11、12
数学与算法：5、6、10、13、14、15
如果大家感觉自己某一板块知识有遗漏，或者想整体复习，可以看下面的这些文章：
1、信息学基本知识与理论
信息学集训 | 02 信息学初赛必备计算机知识大串讲
2、进制、编码与逻辑
进制、编码与逻辑
位运算与进制初步
进制进阶与编码
if嵌套与逻辑运算符
3、程序设计基础
程序设计基础
只学C++，可以做哪些竞赛题
视频福利教程！只学C++，左老师带你入门信息学初赛
程序设计基础这里只是针对初赛做些讲解，真正的知识大家可以关注公众号，点击数学算法中的信息学：
查阅其中的编程基础部分进行学习。
4、数据结构
数据结构
顺序表基本理论
链表基本理论与信息学竞赛必考点
深入理解顺序表和链表的区别与应用
字符串进阶操作
栈理论与实战
队列理论与实战
树与二叉树必备基本理论（最全）
图论必备基本理论（最全）
赛前必看！信息学竞赛初赛中的树与图详细解析
上面的是以理论为主，下面还有树和图的相关实战，可能会出在后面的阅读程序或者完善程序中：
树与图实战
二叉树实战
并查集理论与实战详解
信息学复赛必备的图结构实现方式
5、数学与算法
往期推荐
算法及其复杂度
经典排序算法思想精讲1
经典排序算法思想精讲2
排序算法分析与sort函数详解
枚举算法理论与实战
贪心算法理论与实战
分治算法理论与实战
高精度算法理论与实现1
高精度算法理论与实现2
搜索与回溯——深度优先搜索算法与实例详解
广度优先搜索算法与实例详解
递推算法
初赛必备的递归算法答题方法详解
动态规划算法理论与实例详解
动态规划题型分析与实战
信息学必备初等数论知识总结
信息学必备组合数学知识总结
接下来让我们走进真题吧！
2
CSP-J2020真题
1、单项选择题
1、在内存储器中每个存储单元都被赋予一个唯一的序号，称为（）。
2、编译器的主要功能是（ ）。
A.将源程序翻译成机器指令代码
B.将一种高级语言翻译成另一种高级语言
C.将源程序重新组合
D.将低级语言翻译成高级语言
3、设 x=true, y=true, z=false，以下逻辑运算表达式值为真的是（ ）。
A.(x∧y) ∧z
B.x∧(z∨y) ∧z
C.(x∧y)∨(z∨x)
D.(y∨z)∧x∧z
4、现有一张分辨率为 2048×1024 像素的 32 位真彩色图像。请问要存储这张图像，需要多大的存储空间？（ ）。
5、冒泡排序算法的伪代码如下：
输入：数组L, n ≥ k。输出：按非递减顺序排序的 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 个数用以上冒泡排序算法进行排序，最少需要比较多少次?（ ）
6、设A是n个实数的数组，考虑下面的递归算法：
XYZ (A[1..n])
1. if n= 1 then return A[1]
2. else temp ← XYZ (A[l..n-1])
3. if temp < A[n]
4. then return temp
5. else return A[n]
请问算法XYZ的输出是什么？（）。
A.数组的平均
B.数组的最小值
C.数组的最大值
D.数组的中值
7、链表不具有的特点是（）。
A.插入删除不需要移动元素
B.可随机访问任一元素
C.不必事先估计存储空间
D.所需空间与线性表长度成正比
8、有 10 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。
9、二进制数 1011 转换成十进制数是（ ）。
10、5 个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（ ）种不同排列方法?
11、下图中所使用的数据结构是（ )。
12、独根树的高度为 1。具有 61 个结点的完全二叉树的高度为（ ）。
13、干支纪年法是中国传统的纪年方法，由10个天干和12个地支组合成60个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。
天干 =（公历年份）除以10所得余数
地支 =（公历年份）除以12所得余数
请问 1949 年的天干地支是（ ）。
14、10 个三好学生名额分配到 7 个班级，每个班级至少有一个名额，一共有（ ）种不同的分配方案。
15、有五副不同颜色的手套（共 10 只手套，每副手套左右手各 1 只），一次性从中取 6 只手套，请问恰好能配成两副手套的不同取法有（ ）种。
2、阅读程序题
1、第16题
#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;
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) {
encoder[k]= x;
++k;
}
}
for (int i = 0; i < 26; ++i)
decoder[encoder[i]- 'A'] = i + 'A';
cin >> st;
for (int i = 0; i < st.length( ); ++i)
st[i] = decoder[st[i] -'A'];
cout << st;
return 0;
}
判断题
1） 输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。（ ）
2） 若输入的字符串不是空串，则输入的字符串与输出的字符串一定不一样。（）
3） 将第 12 行的“i < 26”改为“i < 16”，程序运行结果不会改变。（ ）
4） 将第 26 行的"i < 26”改为“i < 16”，程序运行结果不会改变。（ ）
单选题
5） 若输出的字符串为“ABCABCABCA”，则下列说法正确的是（ ）。
A.输入的字符串中既有A又有P
B.输入的字符串中既有S又有B
C.输入的字符串中既有S又有P
D.输入的字符串中既有A又有B
6）若输出的字符串为“CSPCSPCSPCSP”，则下列说法正确的是（ ）。
A.输入的字符串中既有J又有R
B.输入的字符串中既有P又有K
C.输入的字符串中既有J又有K
D.输入的字符串中既有P又有R
2、第17题
#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 是不超过 的正整数，k都是不超过 10000 的正整数，完成下面的判断题和单选题：
判断题
1） 若 k=1，则输出 ans 时，len=n。（ ）
2） 若 k>1，则输出 ans 时，len —定小于 n。（）
3） 若 k>1，则输出 ans 时，
单选题
4） 若输入的n等于：
A.
B.
C. 1
D.
5） 若输入的 n 等于205,891,132,094,649（即 ），输入的 k 为 3，则输出等于（ ）。
A.
B.
C.
D.
6）若输入的 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
3、第18题
#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);
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)
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)
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)
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][i]都是不超过10000的正整数，完成下面的判断题和单选题：
判断题
1） 若输入 n 为 0,此程序可能会死循环或发生运行错误。（ ）
2） 若输入 n 为 20,接下来的输入全为 0，则输出为 0。（）
3） 输出的数一定不小于输入的 d[i][0] 和 d[i][l] 的任意一个。（ ）
单选题
4） 若输入的 n 为 20,接下来的输入是 20 个 9 和 20 个 0,则输出为。（ ）
5）若输入的 n 为 30,接下来的输入是 30 个 0 和 30 个 5,则输出为（ ）。
6）（4分）若输入的 n 为 15，接下来的输入是 15 到 1，以及 15到1，则输出为（ ）。
3、完善程序题
1、质因数分解
给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。例如：输入 n=120，程序应该输出 2 2 2 3 5，表示：120 = 2 × 2 × 2 × 3 × 5。输入保证
试补全程序。
#include <cstdio>
using namespace std;
int n, i;
int main() {
scanf("d", &n);
for(i = ①; ② <=n; i ++){
③{
printf("%d ", i);
n = n / i;
}
}
if(④)
printf("%d ", ⑤);
return 0;
}
1）①处应填（ ）
2）②处应填（ ）
A.n/i
B.n/(i*i)
C.i*i*i
D.i*i
3）③处应填（ )
A.if(i*i<=n)
B.if(n%i==0)
C.while(i*i<=n)
D.while(n%i==0)
4）④处应填（ ）
A.n>1
B.n<=1
C.i+i<=n
D.i<n/i
5）⑤处应填（ )
2、最小区间覆盖
给出 n 个区间，第 i 个区间的左右端点是
输入第一行包含两个整数 n 和 m （ ）
接下来 n 行，每行两个整数 ， （
提示：使用贪心法解决这个问题。先用
试补全程序。
#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 (①)
{
segment t = A[j];
②
}
}
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 (③)
A[p++] = A[i];
n = p;
int ans =0, r = 0;
int q = 0;
while (r < m)
{
while (④)
q++;
⑤;
ans++;
}
cout << ans << endl;
return 0;
}
1）①处应填（ ）
A.A[j].b<A[j-1].b
B.A[j].b>A[j-1].b
C.A[j].a<A[j-1].a
D.A[j].a>A[j-1].a
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;
3）③处应填（ )
A.A[i].b<A[p-1].b
B.A[i].b>A[i-1].b
C.A[i].b>A[p-1].b
D.A[i].b<A[i-1].b
4）④处应填（ ）
A.q+1<n&&A[q+1].b<=r
B.q+1<n&&A[q+1].a<=r
C.q<n&&A[q].a<=r
D.q<n&&A[q].b<=r
5）⑤处应填（ )
A.r=max(r,A[q+1].a)
B.r=max(r,A[q].b)
C.r=max(r,A[q+1].b)
D.q++
长按二维码关注
