#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_ibib_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;