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

• 分類：CSP-S 提高组
• 來源：https://lib.nbdp.net/paper/126.html

---

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

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

---

第 1 题 下列关于NOIP的说法，错误的是( )。

• A. NOIP中文名称为全国青少年信息学奥林匹克联赛，于2020年恢复举行
• B. 参加NOIP是参加NOI的必要条件，不参加NOIP将不具有参加NOI的资格
• C. NOIP竞赛全国前五十名将获得进人国家集训队的资格
• D. 在NOIP复赛中，NOI各省组织单位必须严格遵循CCF《关于NOIP数据提交格式的说明》的规范，在竞赛结束后规定时间内，向CCF提交本赛区所有参赛选手的程序

答案： C. NOIP竞赛全国前五十名将获得进人国家集训队的资格

---

第 2 题 二进制数001001与100101进行按位异或的结果为( ) 。

• A. 101000
• B. 100100
• C. 101101
• D. 101100

答案： D. 101100

---

第 3 题 在8位二进制补码中10101011 表示的数是十进制下的( )。

• A. 43
• B. -43
• C. -85
• D. -84

答案： C. -85

---

第 4 题 平衡树是计算机科学中的一类数据结构，为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离(即深度)，因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。下列数据结构中，不属于平衡树的为( )。

• A. 线段树
• B. Splay树
• C. 替罪羊树
• D. 红黑树

答案： A. 线段树

---

第 5 题 组合数C(n,k)为从n件有标号物品中选出k件物品的方案数,例如C(3,2)=3。已知$n,k \in N$，下列说法错误的是( )。

• A. C(n,k)=C(n-1,k)+(n-1,k-1)

答案： 3

B. C(2n,k) $(0 \leq k \leq 2n)$ 在k=n时取得最大值。

答案： 3

C. 卡特兰数 $C_n= C(2n,n)/n$

• D. 包含n个0和k个1，且没有两个1相邻的字符串的数量为C(n+1,k)

答案： 3

---

第 6 题 下列有关CPU的说法，正确的有( )。

• A. CPU的用途是将计算机系统所需要的显示信息进行转换驱动显示器
• B. CPU的性能和速度取决于时钟频率(一般以赫兹或千兆赫兹计算，即Hz与GHz)和每周期可处理的指令(IPC)，两者合并起来就是每秒可处理的指令(IPS)
• C. AMD是世界上最大的半导体公司，也是首家推出x86架构处理器的公司
• D. 目前的CPU一般都带有3D画面运算和图形加速功能，所以也叫做“图形加速器”或“3D加速器”

答案： B. CPU的性能和速度取决于时钟频率(一般以赫兹或千兆赫兹计算，即Hz与GHz)和每周期可处理的指令(IPC)，两者合并起来就是每秒可处理的指令(IPS)

---

第 7 题 下列算法中，没有用到贪心思想的算法为( )。

• A. 计算无向图最小生成树的Kruskal 算法
• B. 计算无向图点双连通分量的Tarjan算法
• C. 计算无向图单源最短路路径的Dijkstra算法
• D. 以上算法均使用了贪心的思想

答案： B. 计算无向图点双连通分量的Tarjan算法

---

第 8 题 在图G=(V,E)上用Bellman-Ford算法计算单源最短路径，最坏时间复杂度为( )。

• A. O(VE)
• B. O(VlogV)
• C. O(ElogE)
• D. O(E)

答案： A. O(VE)

---

第 9 题 若要使用g++编译器,开启-Ofast优化，且使用C++11标准，将源文件prog.cpp编译为可执行程序exec，且保留调试信息，则需要使用的编译命令为( )。

• A. g++ prog.cpp -Ofast exec-std=c++11 -debug
• B. g++ prog.cpp -Ofast exec-std=c++11 -g
• C. g++ prog.cpp -o exec -Ofast-std=c++11 -debug
• D. g++ prog.cpp -o exec -Ofast-std=c++11 -g

答案： D. g++ prog.cpp -o exec -Ofast-std=c++11 -g

---

第 10 题 已知袋子a中装有4张5元纸币和3张1元纸币，袋子b内装有2张10元纸币与3张1元纸币，袋子c中装有3张20元纸币与3张50元纸币。现在从每个袋子中随机选出2张纸币丢弃，记第i个袋子此时剩下的纸币面值之和为vi，则 va < vb < vc 的概率为( )。

• A. 8/35
• B. 9/35
• C. 11/35
• D. 12/35

答案： B. 9/35

---

第 11 题 Hackenbush 是一款老少皆宜的双人博弈游戏。该游戏双方分别被称为红方与蓝方。游戏的局面基于一些顶点和边 ，其中边分为红色、蓝色与绿色。一些顶点长在大地上(用虚线表示)，而另一些顶点将通过边直接与间接地与大地相连。每一局将从事先约定好的一方开始，每一方轮流选择属于自己颜色的边，然后将该边删除。特别地，对于绿色的边，红蓝双方都可以进行删除操作。如果删除后，某些顶点或边不再与大地联通,则这些顶点或边将自动被删除。如果轮到某一方时，属于他的颜色的所有的边都被删除了，那么他就输了整场游戏。

游戏的局面可以分为四种，分别为先手必胜局面、后手必胜局面、红方必胜局面、蓝方必胜局面。例如，图中第一、二个局面为蓝方必胜局面(无论蓝方先手后手,它只需要删除唯一的蓝色边，红方就无法操作了);第三个局面为红方必胜局面;第四、五个局面为先手必胜局面。下列说法正确的为( )。

• A. 若 Hackenbush 中不存在绿色边,则一定不 会出现先手必胜局面
• B. Hackenbush 中不存在后手必胜局面
• C. 即使不存在红色边与蓝色边，Hackenbush 问题仍是NP-Hard问题
• D. 若不存在绿色边，则Hackenbush问题是P类问题

答案： A. 若 Hackenbush 中不存在绿色边,则一定不 会出现先手必胜局面

---

第 12 题 记将n个有标号球，放到若干个无标号集合，每个集合可空的方案数为fn。{n,k}为第二类斯特林数，其表示将n个有标号球放到k个非空的无标号集合内的方案数。则下列说法: (1)$ fn = \sum_{k=0}^{n} { n,k } $ (2) $ fn = \sum_{k=0}^{n-1} ( n-1,k )fk $ (3)$ fn = [ \frac{x^n}{e!}] e^{e^x-1} $ 其中正确的是( )。

• A. ①②
• B. ①③
• C. ③
• D. ①②③

答案： D. ①②③

---

第 13 题 已知参数k，对于递归式 $T(n)=k\sqrt{n} T(\sqrt{n})+n$的说法，正确的是( )。

• A. 当k=1时，T(n) =O(n logn)
• B. 当k=1时，T(n) =O(n log^2 n)
• C. 当k=4时，T(n) =O(n log n)
• D. 当k=4时，T(n) =O(n log^2 n)

答案： D. 当k=4时，T(n) =O(n log^2 n)

---

第 14 题 对于图G=(V,E)中的边e∈E,我们记G-e表示将边e删除后得到的新图G'，G/e表示将e删除，并将e的两个端点合并为一个点后得到的新图(如图所示,G/(u,v)即为u,v合并为w后得到的图)。

需要注意的是，合并操作会保留所有的重边，即在上图操作后，w向外连边数为8而不是7。特别地，若u,v之间有多条重边，则G/(u,v)只会删去其中一条，其余的重边将构成新图中w指向自己的自环。

图G=(V,E)的Tutte多项式是一个关于变量x,y的多项式，满足:

①若E=φ,则T(G;x,y)= 1 ②若e是G的一个桥边,则T(G;x,y)=xT(G-e,x,y) ③若e是G的一个自环,则T=(G;x,y)=yT(G-e;x,y) ④若e既不是桥边，也不是自环，则T(G;x,y)=T(G-e;x,y)+T(G/e; x,y)

容易证明，一张图G的Tutte多项式是唯一的。设K4(V, E)为四阶完全图，e∈E,则K4-e的Tutte多项式可能是( )。

答案： 1

A. $x^3 +2x^2 +x+2xy+y+y^2$

答案： 1

B. $x^3+x^2 +x+2xy+y+y^2$

答案： 1

C. $x^3 +2x^2+2x+2xy+y+y^2$

答案： 1

D. $x^3+x^2 +2x+2xy+y+y^2$

---

第 15 题 满足$k!=\prod \limits_{i=0}^{n-1}(2^n-2^i)$的正整数对(k,n)的数量有( )个。

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

答案： B. 2

---

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

---

第 16 题 给定长为n的序列a，$a_i$的元素均为$[0,10^9]$内的整数。计算 $\sum_{i=1}^n[i \equiv 1(mod2)] \sum _{1 \leq j\leq n}^{i|j} a_j$ 对$10^9+7$取模后的值。其中[P]当命题P为真时值为1,否则值为0。

#include<cstdio>
#include <vector>

const int mod=1e9+7;
std::vector <int>vec;

inline int inc(int x,int y)
{ x+=y-mod;return x+(x>>31 & mod);}
inline int mul(int x,int y) {return 1ll*x*y%mod;}

int main()
{
	int n;
	scanf ("%d",&n);
	vec.push_back(0);
	for (int i=1;i<=n;++i)
	{
		int x;
		scanf ("%d",&x) ;
		vec.push_back(x);
	}
	int ans=0;
	for (int i=1;i<=n;++i)
		if(i&1)
			for (int j=i;j<=n;j+=i)
				ans=inc(ans,mul(vec[i],vec[j]));
	printf ("%d\n",ans);
	return 0;
}

判断题

第 16 题 (1分) vec.push_back(x)的含义为向容器vec的尾部插入元素x。( )

• A.正确
• B.错误

答案： A.正确

第 17 题 (1分) 对于0≤i≤2^31-1,语句 i&1 的含义与i mod 2等价。( )

• A.正确
• B.错误

答案： A.正确

第 18 题 该程序需要注意运算时可能超出int类型所能容纳的最大数据的风险。( )

• A.正确
• B.错误

答案： 2

第 19 题 inc(x，y)的含义为返回(x+y) mod(10*+7)的值(0≤x,y<10^9+7)。( )

• A.正确
• B.错误

答案： A.正确

第 20 题 (3分)该算法的时间复杂度为( )

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

答案： D. O(n log n)

第 21 题 下列说法错误的是( )。

• A. 该算法的空间复杂度为O(n)
• B. 在循环语句前执行vec.push_back(0) 是因为std::vector容器下标从0开始计数
• C. 若将inc函数接收的参数类型改为long long， 该函数仍将返回预期的结果
• D. 若要对x,y∈[0,10^9+7)进行运算(x-y)mod(10^9 +7),可以调用函数inc(x,mod-y)

答案： C. 若将inc函数接收的参数类型改为long long， 该函数仍将返回预期的结果

---

第 23 题

#include<bits/stdc++.h>
const int N=1e6+50;
int n, m, min[N],out[N],f[N],siz[N],ans;

struct edge
{
	int u, v, w;
} e[N];

inline int find(int x)
{
	while (x!=f[x])
		x=f[x]=f[f[x]];
	return x;
}

inline void merge(int x,int y)
{
	if (siz[x]>siz[y]) std::swap(x,y);
	f[x]=y;
}

int main()
{
	scanf ("%d%d", &n, &m);
	for (int i=1; i<=n; ++i)
	{
		f[i]=i,siz[i]=1;
	}
	for (int i=1; i<=m; ++i)
	{
		scanf ("%d%d%d", &e[i].u,&e[i].v,&e[i].w);
	}
	int components=n;
	while (components>1)
	{
		memset (min,0x3f,sizeof (min));
		for (int i=1; i<=m; ++i)
		{
			int u=find(e[i].u),v=find(e[i].v),w=e[i].w;
			if (u!=v)
			{
				if (w<min[u]) min[u]=w,out[u]=v;
				if (w<min[v]) min[v]=w,out[v]=u;
			}
		}
		for (int i=1; i<=n; ++i)
		{
			int x=find(i) ;
			if (out[x])
			{
				int y=find(out[x]);
				if (x!=y)
				{
					merge(x,y);
					--components;
					ans+=min[x];
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}

提示:该程序的输入为一张n个点m条边的连通无向图。输入格式为: 输入的第一行包含两个整数 n,m(1≤n≤m≤100)。 接下来一行，包含三个整数u,v,w(1≤u,v≤n,1≤w≤100)。

判断题

第 23 题 (1分)该程序实现了用于求无向图G=(V,E)的最小生成树的算法。( )

• A.正确
• B.错误

答案： A.正确

第 24 题 (1分)程序中使用了邻接矩阵来存储图G=(V,E)。( )

• A.正确
• B.错误

答案： 2

第 25 题 为了确保该算法的结果符合预期输入需要保证所有的w互不相同。( )

• A.正确
• B.错误

答案： 2

第 26 题 对于任意合法的输入，该程序一定会在有限步内返回结果。( )

• A.正确
• B.错误

答案： A.正确

第 27 题 变量components在运行过程中可达到的最小值为( )。

• A. 1
• B. 0

答案： A. 1

C. $ \frac{n}{2} $

• D. m-(n-1)

答案： 1

第 28 题 该程序的时间复杂度为( ) 。

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

答案： D. O(mlogn)

---

第 30 题

#include<bits/stdc++.h>
const int N=2e6+50;
int n, head[N], nxt[N], ver[N], dep[N],prv[N],suc[N],cnt;
inline void add(int u, int v)
{
	nxt[++cnt] =head[u], ver[cnt]=v, head[u]=cnt;
}
void dfs (int u, int fa)
{
	dep[u]=dep[fa]+1;
	for(int i=head[u]; i; i=nxt[i])
		if (ver[i] !=fa) dfs(ver[i],u);
}
void solve(int u,int fa,bool rv=false)
{
	int isLeaf=true,t=u;
	for (int i=head[u]; i; i=nxt[i])
	{
		int y=ver[i];
		if (y !=fa)
		{
			isLeaf= false;
			solve(y,u,rv ^ 1);
			if (rv)
			{
				int mp=prv[y];
				suc[t]=y,prv[y]=t,t=mp;
			}
			else
			{
				suc[t]=suc[y];
				prv[suc[y]]=t;
				suc[t=y]=0;
			}
		}
	}
	if (isLeaf) suc[u] =prv[u]=u;
	else suc[t]=u,prv[u]=t;
}
int main()
{
	scanf ("%d", &n) ;
	for (int i=1,u,v; i<n; ++i)
	{
		scanf ("%d%d",&u,&v);
		add(u,v) ;	add(v,u) ;
	}
	dfs (1,1) ;	solve(1,-1);
	printf("1 ");
	int p=1,v=suc[p];
	while (v !=p)
	{
		printf ("%d ",v) ;
		v=suc[v];
	}		
	return 0;
}

提示：该程序的输入为一张n个点的连通图。

判断题

第 30 题 (1分)由程序的建图方式，可以猜测输入的图G为一棵树。( )

• A.正确
• B.错误

答案： A.正确

第 31 题 函数dfs(int, int)用于计算每个节点的深度，并存储至数组dep[]。( )

• A.正确
• B.错误

答案： A.正确

第 32 题 函数solve()通过广度优先搜索，在树T上构造了一条路径。( )

• A.正确
• B.错误

答案： 2

第 33 题 (2分)程序将输出一个大小为n的排列。( )

• A.正确
• B.错误

答案： A.正确

第 34 题 该程序读入以下数据后，输出结果为( )。(\ 表示回车) 8 \1 2 \2 3 \3 4\4 5\4 6\4 7\7 8

• A. 1 3 8 7 5 6 4 2
• B. 1 3 7 8 6 5 4 2
• C. 1 3 8 7 5 6 2 4
• D. 1 3 7 8 6 5 2 4

答案： B. 1 3 7 8 6 5 4 2

第 35 题 (5分)该程序对于给定的图G，构造出另一个图G'，并在G'上构造某条特殊的路径。记dg(u,v)为图G中u,v两点的距离，则有关G'(V',E')的构造方法与找出的路径的说法,正确的为( )

• A. V'=V,E'={(u,v)|u,v∈V, dG(u,v)≤2},找出的路径为哈密顿路径
• B. V'=V,E'={(u,v)|u,v∈V, dG(u,v)≤2},找出的路径为欧拉路径
• C. V'=V,E'={(u,v)|u,v∈V, dG(u,v)≤3},找出的路径为哈密顿路径
• D. V'=V,E'={(u,v)|u,v∈V, dG(u,v)≤3},找出的路径为欧拉路径

答案： C. V'=V,E'={(u,v)|u,v∈V, dG(u,v)≤3},找出的路径为哈密顿路径

---

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

---

第 37 题 阅读下面一段程序,完成(1)-(5)五道小题。

对于图G=(V,E)，我们定义它的线图L(G)为一张|E|个点的无向图,满足: *原图G中的边e对应L(G)中的一个点u。 *L(G)中点u,v之间有连边，当且仅当G中u,v对应的边有公共的顶点。 下图展示了如何通过G构造出L(G)。

现在,给定一棵树T，你需要计算出它的k阶线图 L'(T) 的点数。 输入格式:输入的第一行包含两个整数n,k。接下来n-1行,每行两个整数u,v,描述树中的一条边。 输出格式:输出一行一个整数,表示答案。 数据范围:1≤k≤5,1≤n≤50。

#include<bits/stdc++.h>

const int N=5e3+7;
int n,k,d[N];
std::vector<int>p[N];
bool e[N][N];

int main() {
	scanf ("%d%d", &n,&k);
	--n;
	for (int i=1,x,y; i<=n; i++)
	{
		scanf ("%d%d",&x,&y);
		for (int j:p[x]) e[i][j]=e[j][i]=1;
		for (int j:p[y]) e[i][j]=e[j][i]=1;
		___(1)__;
	}
	int ans=0;
	if (k==2)
	{
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++)
				___(2)__;
		___(3)__;
	}
	else if (k==3)
	{
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++)
				d[i]+=e[i][j];
		for (int i=1; i<=n; i++)	___(4)__;
	}
	else if (k==4)
	{
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++) d[i]+=e[i][j];
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++)
				if (e[i][j])
					___(5)__;
		ans /=4;
	}
	else if (k==5)
	{
		for (int i=1; 1<=n; i++)
			for (int j=1; j<=n; j++) d[i]+=e[i][j];
		static int c[N][N];
		for (int i=1; 1<=n; i++) {

			int x1=0,x2=0;
			for (int j=1; j<=n; j++)
				if(e[i][j])
					c[i][j]=d[i]+d[j]-3, x1+=c[i][j],x2+=c[i][j]*c[i][j];
			for (int j=1; j<=n; j++)
				if (e[i][j])
					ans+=(d[i]-1)+c[i][j]+e[i][j], ans+-2*c[i][j]*(x1-c[i][j]),ans+=x2-c[i][j]*e[i][j], ans-=(d[i]-1)*c[i][j], ans-=x1-c[i][j];
		}
		ans /=4;
	}
	printf ("%d",ans);
	return 0;
}

第 37 题 ⑴处应填( )。

• A. p[x].push_back(i), p[y].push_back(i)
• B. p[x].push_back(y), p[y].push_back(x)
• C. p[i].push_back(x), p[i].push_back(y)
• D. p[x].push_back(y), p[i].push_back(x)

答案： A. p[x].push_back(i), p[y].push_back(i)

第 38 题 ⑵处应填( )。

• A. ans+=e[i][j]
• B. ans+=e[i][j]*2
• C. ans+=n-e[i][i]
• D. ans+=n-e[i][j]*2

答案： A. ans+=e[i][j]

第 39 题 ⑶处应填( )。

• A. ++ans
• B. –ans
• C. ans <≤ 1

答案： 4

=1" lay-filter="filter">

第 40 题 ⑷处应填( )。

• A. ans+=d[i] * (d[i]+1)/2
• B. ans+=d[i] *(d[i]-1)/2
• C. ans+=d[i]* (d[i]+1)
• D. ans+=d[i]*(d[i]-1)

答案： B. ans+=d[i] *(d[i]-1)/2

第 41 题 ⑸处应填( )。

• A. ans+=(d[i]+d[j]) * (d[i]+d[j]-1)
• B. ans+=(d[i]+d[j]-1) * (d[i]+d[j]-2)
• C. ans+=(d[i]+d[j]-2) * (d[i]+d[j]-3)
• D. ans+=(d[i]+d[j]-3) * (d[i]+d[j]-4)

答案： C. ans+=(d[i]+d[j]-2) * (d[i]+d[j]-3)

---

第 43 题 阅读下面一段程序,完成(1)-(5)五道小题。 给定n个区间[l1,r1],[l2,r2],…,[ln,rn]。你需要求出有多少种不同的方案，给每个区间涂上黑白两种颜色之一，使得任意同色区间两两交集为空集。 答案可能很大,因此要对998,244,353取模。 输入格式: 输入的第一行包含一个整数n。接下来n行，每行两个整数1, r。 输出格式:输出一行一个整数，表示答案。 数据范围:1≤n≤ 10^6, 1≤l≤r≤ 10^9。

#include<bits/stdc++.h>

const int N=5e6+50;
const int mod = 998244353;

int n, top, head[N], nxt[N],ver[N], col[N],cnt;
std::pair<int, int>stack[N];

struct seg
{
	int l,r;
} p[N];

inline void add(int u,int v)
{
	nxt[++cnt]=head[u], ver[cnt]=v, head[u]=cnt;
	nxt[++cnt]=head[v], ver[cnt]=u, head[v]=cnt;
}

//从x出发dfs,检测当前图是否为二分图
bool dfs(int x,int c)
{
	if (__(3)__) return co1[x]==c;
	col[x]=c;
	for (int i=head[x]; i; i=nxt[i])
		if (dfs (ver[1],c^1) - false)
			return false;
	return true;
}

int main()
{
	scanf ("%d", &n);
	for (int i=1; i<=n; ++i) scanf ("%d%d" ,&p[i].l,&p[i].r);
	std::sort(p+1,p+n+1,[] (seg u,seg v)
	{
		return __(1)__;
	});//将所有区间按照右端点从小到大排序
	for (int i=1; i<=n; ++i)
	{
		while (top>0 && __(2)__) //若区间有交,则进行建边
			add (stack[top--].second,i);
		stack[++top]=std::make_pair(p[i].r,i);
	}
	memset(col,-1,sizeof col);
	int ans=1;
	for (int i=1; i<=n; ++i)
		if (co1[1]==-1)
		{
			if (dfs(i,0)==false) return print("0"),0;//	若区间圈不是二分围,则无解
			ans=(__(4)__) %mod;
		}
	int mx[2];mx[0]=mx[1]=0;
	for (int i=1; i<=n; ++i)
	{
		if (__(5)__) return printf("0"),0;
		mx[col[i]]=p[i].r;
	}
	printf ("%d",ans);
	return 0;
}

第 43 题 ⑴处应填( )。

• A. u.l < v.l

答案： 3

v.l" lay-filter="filter">

• C. u.r < v.r

答案： C. u.r < v.r

v.r" lay-filter="filter">

第 44 题 ⑵处应填( )。

• A. stack[top].first < p[i].l

答案： 2

p[i].l" lay-filter="filter">

• C. stack[top].first < p[i].r

答案： 2

p[i].r" lay-filter="filter">

第 45 题 ⑶处应填( )。

• A. col[x] & 1
• B. col[x] │ 1
• C. !col[x]
• D. -col[x]

答案： D. -col[x]

第 46 题 ⑷处应填( )。

• A. ans+ 1
• B. ans*ans
• C. ans/2
• D. ans*2

答案： D. ans*2

第 47 题 ⑸处应填( )。

答案： 1

p[i].l" lay-filter="filter">

答案： 1

p[i].r" lay-filter="filter">

答案： 1

p[i].l" lay-filter="filter">

答案： 1

p[i].r" lay-filter="filter">

---