#I. 初赛模拟

A B C D E F G H I
    Type: Objective

初赛模拟

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

  1. 十进制数 114 的相反数的 8 位二进制补码是()。

{{ select(1) }}

  • 10001110
  • 10001101
  • 01110010
  • 01110011

  1. 前缀表达式*+ab+cd的中缀形式是()。

    {{ select(2) }}

  • a+b*c+d
  • (a+b)*(c+d)
  • a*b+c*d
  • (d+c)*(b+a)
  1. 小A用字母A表示1，B 表示 2，以此类推，用 26 表示 Z。对于 27 以上的数字，可以用两位或者更长的字符串来对应，例如 AA 对应 27，AB 对应 28，AZ 对应 52，AAA 对应 703……那么 BYT 字符串对应的数字是什么?

{{ select(3) }}

  • 2018
  • 2020
  • 2022
  • 2024
  1. 拍摄了一张照片，其分辩率是 4096X2160，每一个像素都是 24 位真彩色。在没有压缩的情况下，这张图片占用空间接近以下哪个值?

{{ select(4) }}

  • 8MB
  • 25MB
  • 200MB
  • 200KB
  1. 在一个长度为n 的数组中找到第 k 大的数字，平均的算法时间复杂度最低的是:

{{ select(5) }}

  • O(n)
  • O(nk)
  • O(nlogn)
  • O(n2n^2)
  1. 对于“树”这种数据结构，正确的有:

①一个有 n 个顶点、n-1条边的图是树

②一个树中的两个顶点之间有且只有一条简单路径

③树中一定存在度数不大于 1 的顶点

④树可能存在环

{{ select(6) }}

  • ①②④
  • ①②③
  • ②③
  • ①②
  1. 设变量x为float 型且已赋值，则以下语句中能将 x 中的数值保留到小数点后两位，并将第三位四舍五入的是()。

{{ select(7) }}

  • x=(int)(x*100+0.5)/100.0
  • x=(x*100+0.5)/100.0
  • x=(x*100)+ 0.5/100.0
  • x=(x/100+0.5)*100.0
  1. 一个二叉树的前序遍历是 HGBDAFEC，中序遍历是 BGHFAEDC，同时采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 1，若某结点的下标为1 ，则其左孩子位于下标 2i 处、右孩子位于下标 2i+1 处），则该数组的最大下标至少为（）。

{{ select(8) }}

  • 7
  • 13
  • 15
  • 12
  1. 在 C++语言中，如果 a=1;b=0;c=1;那么以下表达式中为 1 的是:

{{ select(9) }}

  • a&&b||b&&c
  • a+b>c||b
  • !(!c&&(!a||b))
  • a+b+c
  1. 在一个初始长度为n 的链表中连续进行k 次操作，每次操作是读入两个数字aia_i和bib_i，在链表中找到元素为 aia_i的结点（假设一定可以找到），然后将 bib_i这个元素插入到这个结点前面。在最理想的情况下，链表访问的结点数量最少可能是多少（不算将要插入的结点）?

{{ select(10) }}

  • n 次
  • k 次
  • nk 次
  • n+k 次
  1. A班有5 名风纪委员，B 班有4名风纪委员,，C 班有 3 名风纪委员。现在需要这些同学中选取 6 名风纪委员巡逻，如果只关注各班派出的风纪委员人数，有几种不同的方案?

{{ select(11) }}

  • 9
  • 12
  • 15
  • 18
  1. 以下哪种排序算法的时间复杂度是 O(n) ?

{{ select(12) }}

  • 计数排序
  • 插入排序
  • 希尔排序
  • 归并排序
  1. 已知rand() 可以生成一个0到 32767 的随机整数，如果希望得到一个范围在[a,b) 的随机整数，a 和 b 均是不超过 100 的正整数且 a<b，那么可行的表达式是什么?

{{ select(13) }}

  • (rand()%(b-a) )+a
  • (rand()%(b-a+1) ) +a
  • (rand()%(b-a) ) +a+1
  • (rand ()%(b-a+1) ) +a+1
  1. 一个7个顶点的完全图需要至少删掉多少条边才能变为森林?

{{ select(14) }}

  • 16
  • 21
  • 15
  • 6
  1. 在计算机非专业级别软件能力认证 CSP-S 进行时，下列行为中被允许的是()。

{{ select(15) }}

  • 使用 SSH 协议远程登录其它计算机以获取试题等文件
  • 为方便与家长联系，携带关机状态的手机进入考场考试。
  • 使用 U 盘拷贝题目及下发文件或自己的代码供赛后复盘
  • 通过枚举输入文件的可能情况获得答案并写入源代码

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填T，错误填F；除特 殊说明外，判断题1.5分，选择题3分，共计40分）

（1）

#include<iostream>
using namespace std;
#define MAXN 20
int g[MAXN][MAXN];
int f(int n,int m) {
	if(n<=1 || m< 2)
		return 1;
	if(g[n][m]!= -1)
		return g[n][m];
	int ans =0;
	for(int i=0; i<m; i+= 2)
		ans +=f(n-1,i);
	g[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++)
			g[i][j] = -1;
	cout<< f(n,m);
	return 0;
}

判断题

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

选择题

  1. （4分）若输入数据为 4 8，则输出为 ( )。 {{ select(20) }}
  • A. 7
  • B. 8
  • C. 15
  • D. 16
  1. 最坏情况下，此程序的时间复杂度是( )。 {{ select(21) }}
  • A. O(m2n)O(m^2n)
  • B. O(nm!)O(nm!)
  • C. O(n2)O(n^2)
  • D. O(n2m)O(n^2m)

（2）

#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. （1分）14 到 16 行，将外层到内层的循环变量依次调整为 1、j、k，程序的运行的结果不变。 ( )

    {{ select(22) }}

  • V
  • X

  1. 这个程序的时间复杂度和nm无关。( )

    {{ select(23) }}

  • V
  • X
  1. 20 行的 ans 如果初始化为 10' 时，可能无法得到正确结果。( ) {{ select(24) }}
  • V
  • X
  1. 车将第 27 到 30 行的部分和 31 到 34 行的两个部分互换，程序的运行的 结果不变。 ( ) {{ select(25) }}
  • V
  • X

选择题

  1. 若输入数据为 4 5/1 2 3/1 3 6/2 3 4/2 4 7/3 4 2（其中“/”为换行符），则输出为（ ） {{ select(26) }}
  • A. 14
  • B. 18
  • C. 2
  • D. 28
  1. 这个程序使用了 ( ) 算法。 {{ select(27) }}
  • A. Floyd
  • B. Dijkstra
  • C. Prim
  • D. Kruskal

（3）

#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. （1分)当 i=j 时，A[i][j] 的值是0。( ) {{ select(28) }}
  • V
  • X
  1. 当 i>j 时，A[i][j] 的值相当于从 i 个不同元素中取出 j 个元素的排列 数。( ) {{ select(29) }}
  • V
  • X
  1. sum[i][j] 的值 (当 i>=j 时) 不小于 sun[i-1][j-1] 的值。( ) {{ select(30) }}
  • V
  • X
  1. 若将第 12 行改为“A[i][j]=(A[i-1][j]+A[i-1][j-1]+MOD)%MOD;” 程 序的运行的结果不变。( ) {{ select(31) }}
  • V
  • X

选择题

  1. (4分)A[i][j] (当 i<=10，j<=10) 的所有元素中，最大值是( )。 {{ select(32) }}
  • A. 126
  • B. 276
  • C. 252
  • D. 210
  1. 若输入数据为 1/5 3 (其中“/ ”为换行符)，则输出为( )。 {{ select(33) }}
  • A. 10
  • B. 35
  • C. 50
  • D. 24

三、完善程序（单选题，每小题3分，共计30分）

（1）（封禁 xxs）现有 n 个 xxs（编号为 1 到 n），每个 xxs 都有一个关注者，第 i 个 xxs 的关注者是 aia_i。现在管理员要将其中的一些 xxs 的账号封禁，但需要注意的是如果封禁了第 i 个人，那么为了不打草惊蛇，就不能封禁他的关注者 aia_i。现在想知道最多可以封禁多少个 xxs。

输入第一行是一个不超过 300000 的整数 n，第二行是 n 个 1 到 n 的整数表示 aia_i。

输出一行，一个整数表示答案。

#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. ①处应填( ) {{ select(34) }}
  • a[cur]=cur;
  • in[a[cur]]=0;
  • in[a[cur]]--;
  • in[cur]--;
  1. ②处应填 人 ) {{ select(35) }}
  • in[a[cur]]!=0||w==1
  • in[a[cur]]==0||w==0
  • in[a[cur]]!=0||w==0
  • in[a[cur]]==0||w==1
  1. ③处应填( ) {{ select(36) }}
  • 0
  • 1
  • w
  • 1-w
  1. ④处应填( ) {{ select(37) }}
  • dfs(i,1)
  • dfs(i,0)
  • dfs(a[i],1)
  • dfs(a[i],0)
  1. ⑤处应填( ) {{ select(38) }}
  • !in[i]
  • in[i]
  • !vis[i]
  • vis[i]

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

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

输出一行，若干个整数表示答案。如果有多个 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. ①处应填（ ） {{ select(39) }}
  • sum=n
  • sum=s[1]
  • sum=s[n]
  • sum=0

  1. ②处应填（ ）

    {{ select(40) }}

  • sum=maxAverage*(n-i)
  • sum+=s[i]
  • sum+=s[n-i]
  • sum=s[i]+minScore
  1. ③处应填（ ） {{ select(41) }}
  • (double)(sum+minScore)/(n-i)
  • sum*1.0/(n-i)
  • (int)(sum-minScore)/(n-i)
  • (double)(sum-minScore)/(n-i)
  1. ④处应填（ ）

{{ select(42) }}

  • k[++cnt]=i;
  • k[cnt++]=i-1
  • cnt=1;k[cnt]=i-1;
  • cnt=0;k[cnt]=i;
  1. ⑤处应填（ ） {{ select(43) }}
  • k[cnt++]=i;
  • k[++cnt]=i-1;
  • k[cnt++]=n-i;
  • k[cnt]=i;

csp-j1

Not Claimed
Status
Done
Problem
9
Open Since
2024-8-20 0:00
Deadline
2024-9-20 23:59
Extension
24 hour(s)
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 滇ICP备18000821号 战码少年 qucode.cn 战码青少年编程 云南-昆明-专业青少年编程训练
  3. Worker 0, 17ms
  4. Powered by Hydro v4.9.24 Community