06_自習題庫_含參考答案2021提高组 CSP-S 初赛模拟试题 (9)

2021提高组 CSP-S 初赛模拟试题 (9)

2021提高组 CSP-S 初赛模拟试题 (9)

2021提高组 CSP-S 初赛模拟试题 (9)

一、单选题（每题 2 分，共 30 分） 查看答案

第 1 题 下列选项中最大的数是( )。

  • A. (504)10
  • B. (11111000)2
  • C. (770)8
  • D. (1FA)16

答案： D. (1FA)16

第 2 题 主机IP地址为194.32.6.22，掩码为255.255.255.192，子网地址是( )。

  • A. 194.32.6.22
  • B. 194.32.0.0
  • C. 0.0.0.22
  • D. 194.32.6.0

答案： D. 194.32.6.0

第 3 题 现代普通计算机的网关不能设置为( )。

  • A. 10.16.13.100
  • B. 127.0.0.1
  • C. 234.123.6.5
  • D. 168.10.7.100

答案： B. 127.0.0.1

第 4 题 2021个点的二叉树的叶子个数最大是( )

  • A. 1010
  • B. 1
  • C. 2020
  • D. 1011

答案： D. 1011

第 5 题 深度优先搜索时，一定需要用到的数据结构是( )。

  • A. 栈
  • B. 二叉树
  • C. 链式前向星
  • D. 队列

答案： A. 栈

第 6 题 2023的2023次方对5取模的结果为( ).

  • A. 1
  • B. 2
  • C. 3
  • D. 4

答案： B. 2

第 7 题 众所周知，希尔排序的复杂度与增量序列有着很密切的联系，下列增量序列中，( )在确保正确的前提下会使希尔排序的最坏时间复杂度最好。

  • A. {1,2,4,8,…}
  • B. {5,19,41,109,…}
  • C. {1,3,7,…,2^k-1}
  • D. {1,2,3,4,5,…}

答案： C. {1,3,7,…,2^k-1}

第 8 题 NP问题的讨论是计算机科学中一个重要的话题。以下问题中，( )在一般情况下仍有着关于输入规模n的多项式复杂度的确定性正确算法。

  • A. 0-1背包问题，n为物品个数
  • B. 数字的质因数分解，n为数字位数
  • C. 旅行商问题，n为点的个数
  • D. 求矩阵行列式，n为矩阵的行数

答案： D. 求矩阵行列式，n为矩阵的行数

第 9 题 表达式3*(1-2)+4的后缀形式为( )。

  • A. 3 1 2 - * 4 +
  • B. 3 1 - 2 * 4 +
  • C. + * 3 - 1 2 4
  • D. 3 1 * 2 - 4 +

答案： A. 3 1 2 - * 4 +

第 10 题 只采用路径压缩的并查集最坏平均复杂度为( )。

  • A. O(n)
  • B. O(na(n))
  • C. O(n log n)
  • D. O(n^2)

答案： B. O(na(n))

第 11 题 有以下程序段: const int N=1000, M = 10000; int h[N], tot, n, m;struct edge(double c; int nxt, v;} e[M << 1]; double d[N];其占用的静态空间大小约为( )。

  • A. 30000Bytes
  • B. 324KB
  • C. 3200KB
  • D. 3MB

答案： B. 324KB

第 12 题 下列表达式中，不论变量p,q如何取值，恒为真的只有( )。 (1) ((!p)&&q)||(p&&q) (2) ((!p)&&q)&&(p||q) (3) (!p)||q)&&(p||q))||p||(!q) (4) (p&&(!q)&.&)||(((!p)||q)&&(p||q))

  • A. (3)(4)
  • B. (1)(3)
  • C. (2)(4)
  • D. (3)

答案： D. (3)

第 13 题 定义一个数是“好的”:当且仅当这个数是个六位数(允许有前导零),并且里面含有数字9。“好的”数的个数是( )。

  • A. 1000000
  • B. 531441
  • C. 468559
  • D. 99999

答案： C. 468559

第 14 题 现在有20个人约定一起玩一局游戏。但是因为可能要补作业，所以每个人有50%的概率最终参加。他们认为一局游戏的有趣程度为参加人数的平方，则游戏有趣程度的期望为( )。

  • A. 425/4
  • B. 105
  • C. 110
  • D. 100

答案： B. 105

第 15 题 以下( )是 C++之父?

  • A. 本贾尼.斯特劳斯特卢普(Bjarne Stroustrup)
  • B. 图灵(Alan Turing)
  • C. 吉多.范罗苏姆(Guido van Rosum)
  • D. 姚期智

答案： A. 本贾尼.斯特劳斯特卢普(Bjarne Stroustrup)

二、判断题（每题 2 分，共 20 分）

第 16 题

# include<algorithm>
# include<iostream>
using namespace std ;
const int MAXN = 1000;
int a[MAXN], c[MAXN];

int main() {
	int n, x, y;
	cin>> n>> x>> y;
	int sum=(x^y)+((x&y)<<1);
	n=n<<3^5&3|2;
	for(int i=1; i<=n; ++i)
		cin >> a[i];
	int answer;
	answer = c[1] = max(a[1], 0);
	for (int i= 2; i<= n; ++i) {
		c[i] = max(c[i-1] + a[i],a[i]);
		if (c[i]<= 0)
			c[i] = 0;
		answer = max(answer, c[i]);
	}
	if (answer <= sum)
		puts("Good.");
	else
		puts("It's too sad.");
	return 0 ;
}

判断题

第 16 题 sum=x+y ( )

  • A.正确
  • B.错误

答案： A.正确

第 17 题 将程序18,19行删去后输出结果不变。( )

  • A.正确
  • B.错误

答案： A.正确

第 18 题 14行answer没赋初值可能会导致答案错误。( )

  • A.正确
  • B.错误

答案： 2

第 19 题 输入的n应小于等于125,否则会运行时错误。( )

  • A.正确
  • B.错误

答案： 2

第 20 题 若输入的n = 15,则程序12行以后的n的值为( )

  • A. 60
  • B. 123
  • C. 3
  • D. 30

答案： B. 123

第 21 题 若12行时n=11，且输入 a 数组元索依次是:5,12,-7,-11,-9,4,9,5,-6,11,-1,则程序运行到22行时answer是( )。

  • A. 23
  • B. 18
  • C. 17
  • D. 46

答案： A. 23

第 23 题

# include <cmath>
# include <cstring>
# include <iostream>

const int MAXN =1000000;
int n;
int f1[MAXN], f2[MAXN],f3[MAXN];

int calc_f1(int x) {
	int ans=1;
	int maxNum = sqrt(x);
	for (int i= 2; i<= maxNum; ++i)
		if(x%i==0) {
			ans=-ans;
			x/=i;
			if (x%i== 0)
				return 0;
		}
	if(x!=1)
		ans =-ans;
	return ans;
}

int calc_f2(int x) {
	return x;
}

void convolute( ) {
	memset(f3, 0, sizeof(f3));
	for (int i = 1; i<= n; ++i)
		for (int j= 1; j<= n/i; ++j)
			if(i*j<=n)
				f3[i*j]= f3[i* i]+ f1[i]*f2[j];
}
int main() {
	scanf("%d", &n);
	for (int i= 1; i<= n; ++i)
		f1[i] = calc_f1(i);
	for (int i= 1; i<= n; ++i)
		f2[i] - calc_f2(i);
	convolute();
	printf("% d\backslashn", f3[n]);
	return 0;
}

注:本题中你只需要考虑数组越界这一种未定义行为。

判断题

第 23 题 若将程序第31行的 n/i 改为n后运行，且已知程序可以安全地运行至第36行而不发生任何未定义行为，则程序依旧可以正常输出正确的答案。( )

  • A.正确
  • B.错误

答案： 2

第 24 题 去掉程序第3行，程序依然可以正常编译。()

  • A.正确
  • B.错误

答案： A.正确

第 25 题 该程序中,第30~33行运行的时间复杂度为( )。

  • A. O(n^2)
  • B. O(n)
  • C. O(nlogn)
  • D. O(nsqrt(n))

答案： C. O(nlogn)

第 26 题 若输入3，程序的输出为( )。

  • A. 2
  • B. 1
  • C. -1
  • D. 发生未定义行为

答案： A. 2

第 27 题 若输入1003，程序的输出为( )。

  • A. 1002
  • B. 928
  • C. 1
  • D. 发生未定义行为

答案： B. 928

第 28 题 若输入1000000,程序输出为( )。

  • A. 999999
  • B. 400000
  • C. 0
  • D. 发生未定义行为

答案： D. 发生未定义行为

第 30 题

#include <iostream>
using namespace std;

const int maxn =10000000;
int n,size ;
int prime[maxn+5];
bool vis[maxn+5];

int main() {
	cin >>n;
	size = 0;
	for (int i= 2; i<=n; ++i) {
		if (!vis[i]) {
			size = size + 1;
			prime[size]= i;
		}
		for (int j=1; i*prime[j]<=n; ++j) {
			vis[i * prime[j]]= 1;
			if (i % prime[j]==0)
				break ;
		}
	}
	int sum = 0;
	for (int i=1; i<=size; ++i)
		sum=sum + prime[i];
	cout<<sum<<endl;
	return 0;
}

判断题

第 30 题 n必须小于等于10000004，否则程序可能会运行时错误。

  • A.正确
  • B.错误

答案： A.正确

第 31 题 输出可能为1。( )

  • A.正确
  • B.错误

答案： 2

第 32 题 若输入为1000000，那么程序会输出小于等于1000000的质数之和。( )

  • A.正确
  • B.错误

答案： 2

第 33 题 该程序的输出含又是小于等于n的所有质数之和。()

  • A.正确
  • B.错误

答案： A.正确

第 34 题 若输入n为40,那么输出为( )。

  • A. 820
  • B. 197
  • C. 196
  • D. 217

答案： B. 197

第 35 题 (2.5分)若输出的答案在500000~500000之间，那么n的量级约为( )。

  • A. 100~1000
  • B. 1000~10000
  • C. 10000~100000
  • D. 100000~1000000

答案： C. 10000~100000

第 36 题 (2.5分)该程序的复杂度为( )

  • A. O(n)
  • B. O(n^2)
  • C. O(n log n)
  • D. O(n log log n)

答案： A. O(n)

三、编程题（每题 25 分，共 50 分）

第 38 题 1.(背包问题1)有一个质量上限为m的背包和n个物品。物品分三类，第一类物品有取的数量限制，第二类物品只能取一个,第三类物品可以无限取。 第i个物品的类别为tpi质量为w[i]，价值为c[i]，如果tp[i]=1 ，还会有一个a[0]表示这种物品最多只能取a[i]个。求这个背包可以装下的最大价值。 M≤1000,n ≤100,w[i],c[i]≤1000,a[i]<10,1≤tp[i]≤3。

试补全程序。

# include <iostream>
using namespace std;
int n, m, ans;
int f[100],a[101],tp[101],w[101],c[101];

int main() {
	cin>>m>>n;
	for(int i= 1; i<=n; ++i) {
		cin>> tp[i]>> w[i]>> c[i];
		if(tp[i] == 1) cin>> a[i];
	}
	f[0]= 0;
	for (int i= 1; i<= m; ++i)
		f[i]=___(1)___;
	for(int i= 1; i<=n; ++i) {
		if(tp[i]==1) {
			for (int j= 1; j<= a[i]; ++j)
				for(int v= m; v>=w[i]; --v)
					f[v] = max(f[v], ___(5)___ );
		}
		else if(tp[i]== ___(2)___) {
			for(int v=m; v>= ___(3)___ ; --v)
				f[v]=max(f[v], ___(5)___ );
		} 
		else {
			for( ___(4)___ )
				f[v]=max(f[v], ___(5)___ ) ;
		}
	}
	printf("%d", f[m]);
	return 0;
}

第 38 题 ⑴处应填( )。

  • A. 0
  • B. 1
  • C. -1
  • D. 2147483647

答案： A. 0

第 39 题 ⑵处应填( )。

  • A. 2
  • B. 0
  • C. 3
  • D. 1

答案： A. 2

第 40 题 ⑶处应填( )。

  • A. m
  • B. 0
  • C. w[i]
  • D. 1

答案： C. w[i]

第 41 题 ⑷处应填( )。

  • A. int v=0; v≤m; ++v
  • B. int v=w[i]; v≤m; ++v

答案： B. int v=w[i]; v≤m; ++v

=w[i]; –v" lay-filter="filter">

答案： 2

=0; –v" lay-filter="filter">

第 42 题 ⑸处应填( )。

  • A. w[i]
  • B. f[v-w[i]+c[i]
  • C. f[v-w[i]]
  • D. f[v-c[i]]+w[i]

答案： B. f[v-w[i]+c[i]

第 44 题 (背包问题2)有N(O<N≤50)个物品，第i个物品体积为vi，价值为wi。现有一个容量为V(0≤V≤10^18)的背包。你需要选择一些物品使 得体积之和不超过V且价值最大。求出最大价值及方案。如有多种方案，尽可能选择编号较大的方案(即尽量选第n个，仍有多组解选第n-1个，以此类推)。 提示:将物品按标号是否大于n/2分成两组，每组内枚举如何选择。再在两组间确定方案。 试补全程序。

#include <iostream>
using namespace std;

const long long inf=___(1)___;
long long v[41];
long long w[41];
struct Item {
	long long value, weight, choose;
} itm[2][1<<20];

bool cmp1(Item a, Item b) {
	return a.value < b.value||(a.value == b.value && a.choose < b.choose);
}
bool cmp2(Item a, Item b) {
	return a.value < b.value||(a. value == b.value && a.choose==b.choose);
}
int get_id(int n) {
	for(int i=0; ; ++i)
		if(!(n>>i)) return i-1;
	}

void sort(Item item[], int L, int R) {
	if(L>= R) return;
	int x=rand()%(R-L+1)+L;
	swap(item[L], item[x]);
	int a=L+1,b= R;
	while (a<b) {
		while (a<b&& cmp1(item[a], item[L]))
			++a;
		while(a< b&& ___(2)___)
			--b;
		swap(item[a],item[b]);
	}
	while (b<= R&& item[b].value == item[L].value)
		++b;
	if (item[a].value < item[L].value)
		swap(item[a],item[L]);
		     sort(item, L, a-1);
		     sort(item, b, R);
	}

int solve(int L, int R, Item item[]) {

	item[0].value=0;
	item[0].choose = 0;
	int len = ___(3)___;
	for (int i=1; i <= len; ++i) {
		int tmp= ___(4)___;
		item[i].value = item[i - tmp].value + v[L + get_id(tmp)];
		item[i].weight = item[i - tmp].weight + w[L + get_id(tmp)];
		if (item[i].value > inf) item[i].value = inf;
		item[i].choose = i;
	}
	sort(item, 0, len);
	return len;
}

int main() {
	int N;
	long long V, ans = 0;
	cin>>N>>V;
	for (int i = 1; i<= N; ++i)
		cin>> v[i] >> w[i];
	int len1 = solve(1,N/2, itm[0]);
	int len2 = solve(N/2 + 1, N, itm[1]);
	for (int i= 1; i<= len2; ++i)
		itm[1][i].value=max(itm[1][i].value, itm[1][i-1].value);
	long long choose = 0;
	for (int i= 0; i<= len1; ++i) {
		while (len2 >= 0 && itm[0][i].value + itm[1][len2].value>V)
			--len2;
		if(len2>=0) {
			long long new_value = itm[0][i].weight + itm[1][len2].weight;
			long long new_choose = ___(5)___ ;
			if (ans == new_value)
				choose = max( choose, new_choose);
			if (ans < new_value) {
				ans = new_value ;
				choose = new_choose ;
			}
		}
	}
	cout<<ans<<endl;
	for (int i= 0; i< N; i++)
		if (choose & (1LL<<i))
			cout<<i+1<<' ';
	cout << endl;
}

第 44 题 ⑴处应填( )。

  • A. 1000000000000000000LL
  • B. 0x3fffffffffffffffLL
  • C. 0x7fffffffffffffffLL
  • D. 0xffffffffffffffffLL

答案： B. 0x3fffffffffffffffLL

第 45 题 ⑵处应填( )。

  • A. cmp1(item[L], item[b])
  • B. cmp1(item[b], item[L])
  • C. cmp2(item[L], item[b])
  • D. cmp2(item[b], item[L])

答案： C. cmp2(item[L], item[b])

第 46 题 ⑶处应填( )。

  • A. (1 << R-L+1)-1
  • B. 1 << R-L+1
  • C. (1 << R)-1
  • D. 1 << R

答案： A. (1 << R-L+1)-1

第 47 题 ⑷处应填( )。

  • A. i
  • B. i&-i
  • C. i+(i&-i)
  • D. i-(i&-i)

答案： B. i&-i

第 48 题 ⑸处应填( )。

  • A. itm[0][i].choose │ itm[1][len2].choose
  • B. itm[0][i].choose │ (itm[1][len2].choose<< N / 2LL)
  • C. itm[0][i].choose │ (itm[1][len2].choose << N / 2)
  • D. itm[0][i].choose │ (itm[1][len2].choose << N)

答案： B. itm[0][i].choose │ (itm[1][len2].choose<< N / 2LL)

Links to this page:

  1. 自習題庫使用說明
Built with LogoFlowershow