CSP 2020 第一轮（初赛）模拟

第 1 题
十进制数114的相反数的8位二进制补码是：
A.10001110
B.10001101
C.01110010
D.01110011
正确答案： A
本题共 2 分

第 2 题
以下哪个网站不是Online Judge（在线程序判题系统）？Online Judge可以查看算法题目，提交自己编写的程序，然后可以获得评测机反馈的结果。
A.Luogu
B.Gitee
C.LeetCode
D.Codeforces
正确答案： B
本题共 2 分

第 3 题
小A用字母A表示1，B表示2，以此类推，用26表示Z。对于27以上的数字，可以用两位或者更长的字符串来对应，例如AA对应27，AB对应28，AZ对应52，AAA对应703……那么BYT字符串对应的数字是什么？
A.2018
B.2020
C.2022
D.2024
正确答案： C
本题共 2 分

第 4 题
UIM拍摄了一张照片，其分辨率是4096×2160，每一个像素都是24位真彩色。在没有压缩的情况下，这张图片占用空间接近以下哪个值？
A.8MB
B.25MB
C.200MB
D.200KB
正确答案： B
本题共 2 分

第 5 题
在一个长度为n的数组中找到第k大的数字，平均的算法时间复杂度最低的是：
A.O(n)
B.O(nk)
C.O(nlogn)
D.O(n2)
正确答案： A
本题共 2 分

第 6 题
对于“树”这种数据结构，正确的有： ①一个有n个顶点、n-1条边的图是树 ②一个树中的两个顶点之间有且只有一条简单路径 ③树中一定存在度数不大于1的顶点 ④树可能存在环
A.①②④
B.①②③
C.②③
D.①②
正确答案： C
本题共 2 分

第 7 题
博艾中学进行了一次信息学会考测试，其优、良、及格、不及格的试卷数量分别为10、13、14、5张。现在这些卷子混在一起，要将这些卷子按照等级分为4叠。分卷子的方法是，每次将一叠有不同等级答卷的卷子分为两堆，使得这两堆中没有相同等级的卷子，然后可以再分，直到分为4叠。要分完这些卷子，至少需要多少次“分卷子”的操作？将一堆数量为n的卷子分成两堆，就会产生n次分卷子的操作。
A.84
B.93
C.78
D.85
正确答案： A
本题共 2 分

第 8 题
一个二叉树的前序遍历是HGBDAFEC，中序遍历是BGHFAEDC，同时采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 1,若某结点的下标为i ，则其左孩子位于下标 2i处、右孩子位于下标2i+l处），则该数组的最大下标至少为（）
A.7
B.13
C.15
D.12
正确答案： B
本题共 2 分

第 9 题
在C++语言中，如果a=1;b=0;c=1;那么以下表达式中为1的是：
A.a&&b||b&&c
B.a+b>c||b
C.!(!c&&(!a||b)
D.a+b+c
正确答案： C
本题共 2 分

第 10 题
在一个初始长度为n的链表中连续进行k次操作，每次操作是读入两个数字ai和bi，在链表中找到元素为ai的结点（假设一定可以找到），然后将bi这个元素插入到这个结点前面。在最理想的情况下，链表访问的结点数量最少可能是多少（不算将要插入的结点）？
A.n次
B.k次
C.nk次
D.n+k次
正确答案： B
本题共 2 分

第 11 题
A班有5名风纪委员，B班有4名风纪委员，C班有3名风纪委员。现在需要这些同学中选取6名风纪委员巡逻，如果只关注各班派出的风纪委员人数，有几种不同的方案？
A.9
B.12
C.15
D.18
正确答案： D
本题共 2 分

第 12 题
以下哪种排序算法的时间复杂度是O(n2)？
A.计数排序
B.插入排序
C.希尔排序
D.归并排序
正确答案： B
本题共 2 分

第 13 题
已知rand()可以生成一个0到32767的随机整数，如果希望得到一个范围在[a,b)的随机整数，a和b均是不超过100的正整数且a<b，那么可行的表达式是什么？
A.(rand()%(b-a))+a
B.(rand()%(b-a+1))+a
C.(rand()%(b-a))+a+1
D.(rand()%(b-a+1))+a+1
正确答案： A
本题共 2 分

第 14 题
一个7个顶点的完全图需要至少删掉多少条边才能变为森林？
A.16
B.21
C.15
D.6
正确答案： C
本题共 2 分

第 15 题
2020年8月，第（）届全国青少年信息学奥林匹克竞赛在（）举行？
A.26，广州
B.26，长沙
C.37，广州
D.37，长沙
正确答案： D
本题共 2 分

第 16 题
二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×。除特殊说明外，判断题 2 分，选择题 3 分，共计 40 分)

#include<iostream>

using namespace std;

#define MAXN 20

int gu[MAXN][MAXN];

int luo(int n, int m) {

if(n <= 1 || m < 2)

return 1;

if(gu[n][m] != -1)

return gu[n][m];

int ans = 0;

for(int i = 0; i < m; i += 2)

ans += luo(n - 1, i);

gu[n][m] = ans;

return ans;

}

int main() {

int n, m;

cin >> n >> m;

for(int i = 0; i < MAXN; i++)

for(int j = 0; j < MAXN; j++)

gu[i][j] = -1;

cout << luo(n, m);

return 0;

}

?判断题

(1分)luo函数中，m的值不可能是奇数。（）
(1分)若将第11行的“<”改为“<=”，程序的输出结果可能会改变。（）
若将第8、9、13行删除，程序的运行的结果不变（）
在添加合适的头文件后，将第19到21行替换为“memset(gu,255,sizeof(gu));”可以起到相同的作用（）

?选择题

(4分)若输入数据为 4 8，则输出为（）。
最坏情况下，此程序的时间复杂度是（）。

1. A.正确 B.错误正确答案： B
2. A.正确 B.错误正确答案： A
3. A.正确 B.错误正确答案： A
4. A.正确 B.错误正确答案： A
5. A.7 B.8 C.15 D.16 正确答案： B
6. A.O(m^2n)O(m2n) B.O(nm!)O(nm!) C.O(n^2O(n2) D.O(n^2m)O(n2m) 正确答案： A

本题共 14 分

第 17 题

#include<bits/stdc++.h>

using namespace std;

int n, m;

int f[101][101];

int F[101][101];

int main() {

scanf("%d%d", &n, &m); // n的值在1到100之间

memset(f, -1, sizeof(f));

for(int i = 1; i <= m; i++) {

int u, v, w; // w的值在0到10000之间

scanf("%d%d%d", &u, &v, &w);

f[u][v] = f[v][u] = w;

}

for(int k = 1; k <= n; k++)

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

if(f[i][k] != -1 && f[k][j] != -1)

if(f[i][j] == -1||f[i][j]>f[k][j]+f[i][k])

f[i][j] = f[i][k] + f[k][j];

int ans = 2147483647;

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++) {

for(int x = 1; x <= n; x++)

for(int y = 1; y <= n; y++)

F[x][y] = f[x][y];

F[i][j] = F[j][i] = 0;

for(int x = 1; x <= n; x++)

for(int y = 1; y <= n; y++)

if(F[x][y]==-1||F[x][y]>F[x][i]+F[i][y])

F[x][y] = F[x][i] + F[i][y];

for(int x = 1; x <= n; x++)

for(int y = 1; y <= n; y++)

if(F[x][y]==-1||F[x][y]>F[x][j]+F[j][y])

F[x][y] = F[x][j] + F[j][y];

int res = 0;

for(int x = 1; x <= n; x++)

for(int y = 1; y < x; y++)

res += F[x][y];

ans = min(res, ans);

}

printf("%d\n", ans);

return 0;

}

?判断题

(1分)14到16行，将外层到内层的循环变量依次调整为i、j、k，程序的运行的结果不变。（）
这个程序的时间复杂度和m无关。（）
20行的ans如果初始化为107时，可能无法得到正确结果。（）
若将第27到30行的部分和31到34行的两个部分互换，程序的运行的结果不变。（）

?选择题

若输入数据为 4 5/1 2 3/1 3 6/2 3 4/2 4 7/3 4 2（其中“/”为换行符），则输出为（）。
这个程序使用了（）算法。

1. A.正确 B.错误正确答案： B
2. A.正确 B.错误正确答案： B
3. A.正确 B.错误正确答案： A
4. A.正确 B.错误正确答案： A
5. A.14 B.18 C.21 D.28 正确答案： A
6. A.Floyd B.Dijkstra C.Prim D.Kruskal 正确答案： A

第 18 题

#include<bits/stdc++.h>

using namespace std;

#define MOD 19260817

#define MAXN 1005

long long A[MAXN][MAXN] = {0}, sum[MAXN][MAXN] = {0};

int n, m, q;

int main() {

A[1][1] = A[1][0] = 1;

for(int i = 2; i <= 1000; i++) {

A[i][0] = 1;

for(int j = 1; j <= i; j++)

A[i][j] = (A[i - 1][j] + A[i - 1][j - 1]) % MOD;

}

for(int i = 1; i <= 1000; i++)

for(int j = 1; j <= 1000; j++)

sum[i][j] = (sum[i - 1][j] + sum[i][j - 1]

- sum[i - 1][j - 1] + A[i][j] + MOD) % MOD;

int q;

cin >> q;

while(q--) {

int n, m;

cin >> n >> m;

cout << sum[n][m] << endl;

}

return 0;

}

?判断题

(1分)当i<=j时，A[i][j]的值是0。（）
当i>j时，A[i][j]的值相当于从i个不同元素中取出j个元素的排列数。（）
sum[i][j]的值（1<j<i≤1000）不小于sum[i-1][j-1]的值。（）
若将第12行改为“A[i][j]=(A[i-1][j]+A[i-1][j-1]+MOD)%MOD;”，程序的运行的结果不变。（）

?选择题

(4分)A[i][j]（1≤i≤10，1≤j≤10）的所有元素中，最大值是（）。
若输入数据为 1/5 3（其中“/”为换行符），则输出为（）。

1. A.正确 B.错误正确答案： B
2. A.正确 B.错误正确答案： B
3. A.正确 B.错误正确答案： B
4. A.正确 B.错误正确答案： A
5. A.126 B.276 C.252 D.210 正确答案： C
6. A.10 B.35 C.50 D.24 正确答案： C

本题共 14 分

第 19 题
（封禁xxs）现有n个xxs（编号为1到n），每个xxs都有一个关注者，第i个xxs的关注者是ai。现在管理员要将其中的一些xxs的账号封禁，但需要注意的是如果封禁了第i个人，那么为了不打草惊蛇，就不能封禁他的关注者ai。现在想知道最多可以封禁多少个xxs。
输入第一行是一个不超过300000的整数n，第二行是n个1到n的整数表示ai。
输出一行，一个整数表示答案。

#include <cstdio>

using namespace std;

#define MAXN 300005

int n, ans = 0, a[MAXN], in[MAXN] = {0};

bool vis[MAXN] = {0};

void dfs(int cur, int w) {

if(vis[cur])

return;

vis[cur] = true;

if(w == 1) ans++;

①

if(②)

dfs(a[cur], ③);

}

int main() {

scanf("%d", &n);

for(int i = 1; i <= n; i++) {

scanf("%d", &a[i]);

in[a[i]]++;

}

for(int i = 1; i <= n; i++)

if(!in[i]) ④;

for(int i = 1; i <= n; i++)

if(⑤) dfs(i, 0);

printf("%d\n", ans);

return 0;

}

①处应填（）
②处应填（）
③处应填（）
④处应填（）
⑤处应填（）

1. A.a[cur]=cur; B.in[a[cur]]=0; C.in[a[cur]]–; D.in[cur]–; 正确答案： C
2. A.in[a[cur]]!=0||w==1 B.in[a[cur]]==0||w==0 C.in[a[cur]]!=0||w==0 D.in[a[cur]]==0||w==1 正确答案： D
3. A.0 B.1 C.w D.1-w 正确答案： D
4. A.dfs(i,1) B.dfs(i,0) C.dfs(a[i],1) D.dfs(a[i],0) 正确答案： A
5. A.!in[i] B.in[i] C.!vis[i] D.vis[i] 正确答案： C

本题共 15 分

第 20 题
（烧作业）某课作业布置了N（3≤N≤100000）个题目，第i题对应的得分是ai。作业的总得分的计算方式为去掉作业中得分最小的一个题，剩下其它所有题目得分的平均值。但很不幸小A遇到了一场火灾，前K（1≤K≤N-2）个题目被烧了，无法记录得分。小A想知道，K是多少时，可以得到最高的作业得分？作业被烧了前K页，这时的得分是从第K+1页到最后一页中，去除最小得分后取平均值。

输入第一行是整数N，第二行是n个不超过10000的非负整数表示ai。

输出一行，若干个整数表示答案。如果有多个K，请依次升序输出。

#include <cstdio>

#include <cmath>

#define min(a,b) (a<b?a:b)

#define MAXN 100002

using namespace std;

int n, k[MAXN], cnt = 0;

int s[MAXN], minScore, sum;

double maxAverage = 0, nowAverage;

int main() {

scanf("%d", &n);

for(int i = 1; i <= n; i++)

scanf("%d", &s[i]);

minScore = s[n];

①;

for(int i = n - 1; i >= 2; i--) {

minScore = min(minScore, s[i]);

②;

nowAverage = ③;

if(nowAverage > maxAverage) {

④

maxAverage = nowAverage;

} else if(fabs(nowAverage - maxAverage) < 1e-6)

⑤;

}

for(int i = cnt; i >= 1; i--)

printf("%d\n", k[i]);

return 0;

}

①处应填（）
②处应填（）
③处应填（）
④处应填（）
⑤处应填（）

1. A.sum=n B.sum=s[1] C.sum=s[n] D.sum=0 正确答案： C
2. A.sum=maxAverage*(n-i) B.sum+=s[i] C.sum+=s[n-i] D.sum=s[i]+minScore 正确答案： B
3. A.(double)(sum+minScore)/(n-i) B.sum*1.0/(n-i) C.(int)(sum-minScore)/(n-i) D.(double)(sum-minScore)/(n-i) 正确答案： D
4. A.k[++cnt]=i; B.k[cnt++]=i-1 C.cnt=1;k[cnt]=i-1; D.cnt=0;k[cnt]=i; 正确答案： C
5. A.k[cnt++]=i; B.k[++cnt]=i-1; C.k[cnt++]=n-i; D.k[cnt]=i; 正确答案： B

本题共 15 分

相关文章: