试卷查看

第 1 题关于机器翻译，下列选项中正确的是( )。

第 2 题以补码存储的8位有符号整数10100011的十进制表示为( ) 。

第 3 题关于网络协议，下面说法中正确的是( )。

第 4 题以下程序当执行完毕后。输出的值为( )。

int f(int n)
{
	if (n==2|n==1)
		return 1;//注意递归，验证，从最小的地方推
	else
		return f(n-1)+f(n-2);
}
cout << f(9);

第 5 题下列关键字序列中,哪一项是堆( )。

第 6 题对n个不同的排序码进行冒泡排序，在下列哪种情祝下比较的次数最多( )。

第 7 题 n为一个两位数，它的数码之和为a，当n分别各乘以3、5、7、9以后得到4个乘积，如果每一个积的数码之和都为a，那么这样的两位数n有( ) 个

第 8 题二叉树第10层的结点数的最大数目为( )。

第 9 题 100以内最大的素数是( ) 。

第 10 题 15张卡片，每张卡片上写有3个不同的汉字，任意2张上的汉字不完全相同;任意6张中，一定有2张，它们上面有共同的汉字。问:这15张卡片上最多有多少个不同的汉字?()。

第 11 题仅由数字1,2,3组成的七位数中，相邻数字均不相同的七位数的个数是()。

第 12 题有甲、乙、丙、丁四支球队参加的足球循环赛，每两队都要赛一场，胜得3分，负者将0分，如果踢平，两队各得1分。现在甲、乙、丙分别得了7分、1分和6分，已知甲和乙踢平，那么丁得( )分。

第 13 题若一组记录的排序码为(46,79,56,38,40,84)则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。

第 14 题一棵6节点二叉树的中序遍历为ABDGECF，先序遍历为DBACEGF，后序遍历为( )。

第 15 题下面哪种图不一定是树( )。

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

第 16 题

#include <bits/stdc++.h>
using namespace std;
const int N=2e5;
int a[N],s[N];
int main()
{
	int n, m;
	cin>>n>>m;
	memset (s,0, sizeof (s)) ;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
		s[i]=a[i]+s[i-1];
	}
	int l,r;
	while(cin>>l>>r)
	{
		cout<<s[r]-s[l-1]<<endl;
	}
	return 0;
}

判断题

第 16 题输出只能是正整数。( )

第 17 题将03行的2e5改为2e10输出结果不变。()。

第 18 题将第09行删除，程序运行结果不会改变。( )

第 19 题只要输入int数据类型的数据,输出结果就是正确的。( )

第 20 题如输入的5 3 1 2 3 4 5 2 4,则输出的结果为( )。

第 21 题本题涉及下列哪一项的数据范围偏小( )。

第 23 题

#include <cstdio>
bool pd(long long n)
{
	if(n==1)
		return false ;
	for(long long i=2; i<n; i++)
		if(n%i==0) return false;
	return true ;
}
int main()
{
	long long n,i,c=0;
	int	INF=1<<30;//1左移30位，把INF初始化为较大的数
	scanf("%d", &n) ;
	for(i=2; i<=INF; i++)
	{
		if (pd(i))
		{
			c++;
			if(c==n)
			{
				printf ("%d",i) ;
				return 0;
			}
		}
	}
	printf("\n over") ;
	return 0;
}

判断题

第 23 题上述代码中,将第13行修改为INF=1<<40,输出结果一定不变。()

第 24 题上述代码中,将第23行修改为break或continue这两种情况后，相同的输入,在这两种情况,输出结果也一定相同。( )

第 25 题上述代码中，将第23行修改为break后，相同的输入,变量c的值和未修改前一定相同。( )

第 26 题上述代码中，将第23行修改为break后，相同的输入，输出结果也一定相同。( )

第 27 题当输入为:8,输出为( ) 。

第 28 题上述代码中,将第06行的i

第 30 题

#include<bits/stdc++.h>
using namespace std;
int s[100001],a[100001],n,ans1, ans2;
int main()
{
	while (scanf ("%d", &a[++n])!=EOF) ;
	n--;
	for(int i=n; i>=1; i--) {
		s[i]=1;
		for (int j=i+1; j<=n; j++) {
			if(a[j]<=a[i]) {
				s[i] =max(s[i],s[j]+1);
			}
		}
		ans1 =max (ans1,s[i]);
	}
	for(int i=1; i<=n; i++) {
		s[i] =1;
		for(int j=1; j<=i; j++) {
			if(a[j]<a[i]) {
				s[i]=max(s[ i],s[j]+1);
			}
		}
		ans2 =max (ans2,s[i]) ;
	}
	printf ("%d%d", ans1,ans2) ;
	return 0;
}

判断题

第 30 题若输入的序列是一个单调递增序列,则ans1的值为1。( )

第 31 题若输入的序列是一个单调递减序列，则ans2的值为1。( )

第 32 题对输入序列数据处理中,ans1的值越大,ans2的值将会越小。( )

第 33 题输入的数值不能为负数。( )

第 34 题若输入389 207 155 300 299 170 158 65，输出第一个数为( )。

第 35 题若输入0 -1 0 -1，则输出( )。

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

第 37 题 (SPFA)给定一个有n个顶点(从1到n编号) ,m条边的有向图(其中某些边权可能为负，但保证没有负环)。请你计算从1号点到其他点的最短路。试补全程序。

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
const int inf=0x3f3f3f3f;
int h[N],e[N],ne[N],ret,w[N];
int dis[N];
bool st[N];
int n,m;
void add(int a,int b,int c) {
	e[ret]=b;
	w[ret]=c;
	ne[ret]=h[a];
	h[a]=ret++;
}
void spfa()
{
	memset (dis, inf,sizeof (dis));
	dis[1]=0;
	queue <int>q;
	q.push(1);
	st[1] = true;
	while(q.size()) {
		int t=q.front() ;
		q.pop();
		st[t]=false;
		for(int i=__(1)__;__(2)__; i=ne[i]) {
			int j=e[i];
			if (dis[j]>dis[t]+w[i])
			{
				__(3)__;
				if(!st[j]) {
					__(4)__;
					st[j]=true;
				}
			}
		}
	}
}
int main() {
	scanf ("%d%d", &n, &m) ;
	memset (h,-1, sizeof h) ;
	while (m--) {
		int a,b, c;
		scanf ("%d%d%d",&a, &b, &c) ;
		__(5)__;
	}
	spfa() ;
	for (int i=2; i<=n; ++i)
		printf ("%d\n",dis[i]) ;
	return 0 ;
}

第 37 题 ⑴处应填( )。

第 38 题 ⑵处应填( )。

第 39 题 ⑶处应填( )。

第 40 题 ⑷处应填( )。

第 41 题 ⑸处应填( )。

第 43 题 (01背包)在网友的国度中共有n种不同面额的货币，第i种货币的面额为a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为n、面额数组为a[1..n]的货币系统记作(n,a)。在一个完善的货币系统中，每一个非负整数的金额x都应该可以被表示出，即对每一个非负整数x，都存在n个非负整数t[i]满足a[i]*t[i]的和为x。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额x不能被该货币系统表示出。例如在货币系统n=3, a=[2,5,9]中，金额1,3就无法被表示出来。两个货币系统(n,a)和(m,b)是等价的,当且仅当对于任意非负整数x，它要么均可以被两个货币系统表示出，要么不能被其中任何一个表示出。现在网友们打算简化一下货币系统。他们希望找到一个货币系统(m,b),满足(m,b)与原来的货币系统(n,a)等价，且m尽可能的小。他们希望你来协助完成这个艰巨的任务:找到最小的m。

#include <bits/stdc++.h>
using namespace std;
int a[105],f[25005];
int main ()
{
	int T,n;
	scanf("%d", &T) ;
	while(__(1)__) {
		scanf ("%d", &n) ;
		for (int i=0; i<n; i++)
			scanf("%d",&a[i]);
		sort(a,a+n) ;
		
		int x=__(2)__;//x 代表a[i]的最大值
		memset (f,0xcf, sizeof (f) ) ;
		f[0]=__(3)__;
		for (int i=0; i<n; i++) {
			for (int j=a[i]; j<=x; j++) {
				f[j]=max(f[j],__(4)__);
			}
		}
		int res=0;
		for(int i=0; i<n; i++) {
			if(__(5)__)
				res++;
		}
		printf ("%d\n",res);
	}
	return 0;
}

第 43 题 ⑴处应填( )。

第 44 题 ⑵处应填( )。

第 45 题 ⑶处应填( )。

第 46 题 ⑷处应填( )。

第 47 题 ⑸处应填( )。

2022入门组 CSP-J 初赛模拟试题 (9)