试卷查看

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

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

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

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

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

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

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

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

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

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

第 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];其占用的静态空间大小约为( )。

第 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))

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

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

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

二、判断题（每题 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 ( )

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

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

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

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

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

第 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行而不发生任何未定义行为，则程序依旧可以正常输出正确的答案。( )

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

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

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

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

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

第 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，否则程序可能会运行时错误。

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

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

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

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

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

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

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

第 38 题 1.(背包问题1)有一个质量上限为m的背包和n个物品。物品分三类，第一类物品有取的数量限制，第二类物品只能取一个,第三类物品可以无限取。第i个物品的类别为tp[i](tp[i]∈[1,2,3])质量为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 题 ⑴处应填( )。

第 39 题 ⑵处应填( )。

第 40 题 ⑶处应填( )。

第 41 题 ⑷处应填( )。

第 42 题 ⑸处应填( )。

第 44 题 (背包问题2)有N(O

#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 题 ⑴处应填( )。

第 45 题 ⑵处应填( )。

第 46 题 ⑶处应填( )。

第 47 题 ⑷处应填( )。

第 48 题 ⑸处应填( )。

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