#2406. 初赛模拟

初赛模拟

一、单项选择题（共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;

Statistics

Related

In following homework:

csp-j1

(9.6)周六1030作业

  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, 24ms
  4. Powered by Hydro v4.9.24 Community