2023CCF 提高级 CSP-S 初赛

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

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

第 1 题在Linux系统终端中，以下那个命令用于创建一个新的目录？( )

A. newdir
B. mkdir
C. create
D. mkfold

答案： B. mkdir

第 2 题由0,1,2,3,4中选取4个数字，能组成( )个不同四位数注:最小的四位数是1000最大的四位数是9999)

A. 96
B. 18
C. 120
D. 84

答案： A. 96

第 3 题假设n 是图的顶点的个数,m 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法对于m=O(n)的稀疏图而言下面的四个选项，哪一项的渐近时间复杂度最小。( )

答案： 1

A. $O(m*\sqrt{\log n *\log \log n})$

答案： 1

B. $O(n^2+m)$

答案： 1

C. $O(n^2/\log m+m \log n)$

答案： 1

D. $O(m+n \log n)$

第 4 题假设有n 根柱子，需要按照以下规则依次放置编号为1、2、3、…的圆环:每根柱子的底部固定，顶部可以放入圆环，每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有4根柱子时，最多可以放置( )个圆环。

A. 7
B. 9
C. 11
D. 5

答案： C. 11

第 5 题以下对数据结构的表述不恰当的一项是：( )

A. 队列是一种先进先出(FIFO)的线性结构
B. 哈夫曼树的构造过程主要是为了实现图的深度优先搜索
C. 散列表是一种通过散列函数将关键字映射到存储位置的数据结构
D. 二又树是一种每个结点最多有两个子结点的树结构

答案： B. 哈夫曼树的构造过程主要是为了实现图的深度优先搜索

第 6 题以下连通无向图中，( )一定可以用不超过两种颜色进行染色

A. 完全三叉树
B. 平面图
C. 边双连通图
D. 欧拉图

答案： A. 完全三叉树

第 7 题最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下:给定两个序列X={x1,x2,x3,…xm}和Y={y1,y2,y3…yn},最长公共子序列(LCS)问题的目标是找到一个最长的新序列Z= {z1,z2,z3…zk},使得序列既是序列X 的子序列，又是序列Y的子序列，且序列Z的长度k 在满足上述条件的序列里是最大的。(注:序列A 是序列B 的子序列，当且仅当在保持序列B 元素顺序的情况下，从序列B中删除若千个元素，可以使得剩余的元素构成序列A。测序列“ABCAAAABA”和“ABABCBABA”的最长公共子序列长度为( )

A. 4
B. 5
C. 6
D. 7

答案： C. 6

第 8 题一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下:玩家第一次掷出x点，得到2x元;第二次掷出y点，当y=x 时玩家会失去之前得到的2x元而当y!=x时玩家能保住第一次获得的2x元。上述x,y∈[1,2,3,4,5,6]。例如:玩家第一次掷出3点得到6元后，但第二次再次掷出3点，会失去之前得到的6元，玩家最终收益为0元:如果玩家第一次掷出3点第二次掷出4点，则最终收益是6元。假设骰子挑出任意一点的概率均为1/6,玩家连续掷两次般子后所有可能情形下收益的平均值是多少?

A. 7
B. 35/6
C. 16/3
D. 19/3

答案： B. 35/6

第 9 题假设我们有以下的C++代码:

int a=5,b=3,c=4; bool res= a&b||c^b && a|c 请问，res的值是什么？（）提示:在 C++中，逻辑运算的优先级从高到低依次为: 逻辑非(!)逻辑与(&&)、逻辑或(||)。位运算的优先级从高到低依次为: 位非(~)、位与(&)、位异或(^)、位或(|)。同时，双目位运算的优先级高于双目逻辑运算:逻辑非和位非优先级相同，且高于所有双目运算符

A. true
B. false
C. 1
D. 0

答案： A. true

第 10 题假设快速排序算法的输入是一个长度为n的已排序数组，且该快速排序算法在分治过程总是选择第1个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?( )

A. 快速排序对于此类输入的表现最好因为数组已经排序
B. 快速排序对于此类输入的时间复杂度是O(nlogn)。
C. 快速排序对于此类输入的时间复杂度是O(n^2)
D. 快速排序无法对此类数组进行排序因为数组已经排序

答案： C. 快速排序对于此类输入的时间复杂度是O(n^2)

第 11 题以下哪个命令，能将一个名为“main.cpp”的 C++源文件，编译并生成一个名为"main“的可执行文件? ( )

A. g++ -o main main.cpp
B. g++ -o main.cpp main
C. g++ main -o main.cpp
D. g++ main.cpp -o main.cpp

答案： A. g++ -o main main.cpp

第 12 题在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心( )

A. 4个结点的树
B. 6个结点的树
C. 7个结点的树
D. 8个结点的树

答案： C. 7个结点的树

第 13 题如图是一张包含6个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这6个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边?

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

答案： C. 3

第 14 题若 $n=\sum_{i=0}^k 16^i*X_i$ ，定义 $f(n)=\sum_{i=1}^k x_i$ ;其中 $x_i\to{0,1,...,15}$ 。对于给定自然数 $n_0$ ，存在序列 $n_0,n_1,..., n_m$ ,其中对于 $1≤i≤m$ 都有 $n_i=f(n_{i-1})$ ，且 $n_m = n_{m-1}$ ，称 $n_m$ 为 $n_0$ 关于 $f$ 的不动点。问在 $100_{16}$ 至 $1A0_{16}$ 中，关于f的不动点为9的自然数个数为( )。

A. 10
B. 11
C. 12
D. 13

答案： B. 11

第 15 题现在用如下代码来计算x^n，其时间复杂度为( )

double quick_power(double x,unsigned int n){
    if (n==0) return 1;
	if (n==1) return x;
	return quick_power(x,n/2)*quick_power(x,n/2)*((n&1)?x:1);
}

A. O(n)
B. O(1)
C. O(logn)
D. O(nlogn)

答案： A. O(n)

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

第 16 题

#include <iostream>
using namespace std;

unsigned short f(unsigned short x) {
	x ^=x << 6;
	x ^=x >> 8;
	return x;
}

int main() {
	unsigned short x;
	cin >> x;
	unsigned short y = f(x);
	cout << y << endl;
	return 0;
}

假设输入的x是不超过65535的自然数，完成下面的判断题和单选题

判断题

第 16 题当输入非零时，输出一定不为零（）

A.正确
B.错误

答案： A.正确

第 17 题将f函数的输入参数的类型改为unsigned int，程序的输出不变（）

A.正确
B.错误

答案： 2

第 18 题当输入为“65535”时，输出为“63”（）

A.正确
B.错误

答案： A.正确

第 19 题当输入为“1”时，输山为“64”。

A.正确
B.错误

答案： 2

第 20 题当输入为“512”时，输出为( )

A. “33280”
B. “33410”
C. “33106”
D. “33346”

答案： B. “33410”

第 21 题当输入为“64”时，执行完第5行后x的值为( )

A. “8256”
B. “4130”
C. “4128”
D. “4160”

答案： D. “4160”

第 23 题

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

long long solve1(int n) {
	vector<bool> p(n+1, true);
	vector<long long> f(n+1,0),g(n+1,0);
	f[1] = 1;
	for (int i= 2; i*i<= n; i++) {
		if (p[i]) {
			vector<int> d;
			for (int k=i; k <= n; k *= i) d.push_back(k);
			reverse(d.begin(),d.end());
			for (int k : d) {
				for (int j= k; j<= n; j+= k) {
					if (p[j]) {
						p[j] = false;
						f[j] = i;
						g[j] = k;
					}
				}
			}
		}
	}
	for (int i= sqrt(n) + 1; i<= n; i++) {
		if (p[i]) {
			f[i] = i;
			g[i] = i;
		}
	}
	long long sum = 1;
	for (int i=2; i<= n; i++) {
		f[i]=f[i / g[i]]*(g[i]*f[i]-1) / (f[i]-1);
		sum += f[i];
	}
	return sum;
}

long long solve2(int n) {
	long long sum = 0;
	for (int i= 1; i <= n; i++) {
		sum +=i*(n /i);
	}
	return sum;
}

int main() {
	int n;
	cin >>n;
	cout << solve1(n)<< endl;
	cout << solve2(n)<< endl;
	return 0;
}

假设输入的x是不超过65535的自然数，完成下面的判断题和单选题

判断题

第 23 题将第15 行删去，输出不变（）

A.正确
B.错误

答案： 2

第 24 题当输入为“10”时，输出的第一行大于第二行。（）

A.正确
B.错误

答案： 2

第 25 题当输入为“1000”时，输出的第一行与第二行相等（）

A.正确
B.错误

答案： A.正确

第 26 题 solve1(n)的时间复杂度为（）

答案： 4

A. $O(nlog2n)$

答案： 4

B. $O(n)$

答案： 4

C. $O(nlogn)$

答案： 4

D. $O(nloglogn)$

第 27 题 solve2(n)的时间复杂度为（）

答案： 2

A. $O(n^2)$

答案： 2

B. $O(n)$

答案： 2

C. $O(nlogn)$

答案： 2

D. $O(n\sqrt(n))$

第 28 题输入为“5”时，输出的第二行为( )

A. 20
B. 21
C. 22
D. 23

答案： B. 21

第 30 题

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool f0(vector<int>& a, int m,int k) {
	int s = 0;
	for (int i=0,j=0; i< a.size(); i++) {
		while (a[i]- a[j]> m) j++;
		s+= i-j;
	}
	return s >= k;
}

int f(vector<int>& a,int k) {
	sort(a.begin(), a.end());

	int g = 0;
	int h = a.back()- a[0];
	while (g <h) {
		int m=g+(h-g)/2;
		if(f0(a,m,k)) {
			h=m;
		} else {
			g=m+1;
		}
	}

	return g;
}

int main() {
	int n, k;
	cin >> n>> k;
	vector<int> a(n,0);
	for (int i=0; i<n; i++) {
		cin >>a[i];
	}
	cout << f(a,k) << endl;
	return 0;
}

假设输入总是合法的且 $|a[i]| \le 10^8、n \le 1000$ 和 $1 \le k \le n(n-1)/2$ ，完成下面的判断题和单选题：

判断题

第 30 题将第24行的“m”改为“m-1”，输出有可能不变，而剩下情况为少1。（）

A.正确
B.错误

答案： A.正确

第 31 题将第22行的“g +(h-g)/2”改为“(h+g)>>1”，输出不变。（）

A.正确
B.错误

答案： A.正确

第 32 题当输入为“5 7 2 -4 5 1 -3”，输出为”5”。（）

A.正确
B.错误

答案： A.正确

第 33 题设a数组中最大值减最小值加1为A，则f函数的时间复杂度为（）

A. O(nlogA)
B. O(n^2logA)
C. O(nlog(nA))
D. O(nlogn)

答案： C. O(nlog(nA))

第 34 题将第10行中的“>”替换为“>=”，那么原输出与现输出的大小关系为（）

A. 一定小于
B. 一定小于等于且不一定小于
C. 一定大于等于且不一定大于
D. 以上三种情况都不对

答案： B. 一定小于等于且不一定小于

第 35 题当输入为“5 8 2 -5 3 8 -1 2”时，输出为（）

A. “13”
B. “14”
C. “8”
D. “15”

答案： B. “14”

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

第 37 题第k小路径

给定一张n个点 m 条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第k小的路径。保证存在至少 k条路径，上述参数满足1≤n,m≤10^5 和1≤k≤10^18表示。在程序中，我们求出从每个点出发的路径数量。超过10^18的数都用 10^18表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。

试补全程序。

#include <iostream>
#include <algorithm>
#include <vector>

const int MAXN = 100000;
const long long LIM =1000000000000000000ll;

int n,m,deg[MAXN];
std::vector<int> E[MAXN];
long long k, f[MAXN];

int next(std::vector<int> cand, long long &k) {
	std::sort(cand.begin(), cand.end());
	for (int u : cand) {
		if ( __(1)__ ) return u;
			k -= f[u];
	}
	return -1;
}

int main() {
	std::cin >>n>> m >> k;
	for (int i=0;i<m; ++i){
		int u, v;
		std::cin >> u>> v;
		E[u].push_back(v);
		++deg[v];
		}
	std::vector<int> Q;
	for (int i= 0;i<n; ++i)
		if (!deg[i]) Q.push_back(i);
	for (int i=0;i<n;++i){
		int u= Q[i];
		for (int v :E[u]){
			if (  __(2)__ ) Q.push_back(v);
			--deg[v];
		}
	}
		std::reverse(Q.begin(), Q.end());
	for (int u:Q){
		f[u] = 1;
		for (int v : E[u]) f[u] = __(3)__ ;		 
	}
	int u= next(Q,k);
	std::cout << u << std::endl;
	while ( __(4)__ ) {
		__(5)__ ;
		u= next(E[u], k);
		std::cout << u << std::end1;
	}
	return 0;
}

第 37 题 ⑴处应填( )。

答案： 2

=f[u]" lay-filter="filter">

B. k≤f[u]

答案： B. k≤f[u]

f[u]" lay-filter="filter">

D. k<f[u]

答案： 2

第 38 题 ⑵处应填( )。

A. deg[v]==1
B. deg[v]==0

答案： A. deg[v]==1

1" lay-filter="filter">

答案： 1

0" lay-filter="filter">

第 39 题 ⑶处应填( )。

A. std::min(f[u]+f[v],LIM)
B. std::min(f[u]+f[v]+1,LIM)
C. std::min(f[u]*f[v],LIM)
D. std::min(f[u]*(f[v]+1),LIM)

答案： A. std::min(f[u]+f[v],LIM)

第 40 题 ⑷处应填( )。

A. u!=1
B. !E[u].empty()

答案： 4

0" lay-filter="filter">

答案： 4

1" lay-filter="filter">

第 41 题 ⑸处应填( )。

A. k+=f[u]
B. k-=f[u]
C. –k
D. ++k

答案： C. –k

第 43 题（最大值之和）给定整数序列 a0…an-1，求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤10^5 和 1≤ai≤10^8 一个序列的非空连续子序列可以用两个下标l和r(其中0 ≤l≤r≤n)表示，对应的序列为al,al+1,…ar。两个非空连续子序列不同，当且仅当下标不同。例如，当原序列为[1,2,1,2] 时，要计算子序列[1]、[2]、[1]、[2]、[1,2]、[2,1]、[1,2]、[1,2,1]、[2,1,2]、[1,2,1,2] 的最大值之和，答案为 18。注意[1,1]和[2,2] 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。解决该问题有许多算法，以下程序使用分治算法时间复杂度 O(nlogn)。

试补全程序

#include <iostream>
#include<algorithm>
#include <vector>

const int MAXN = 100000;

int n;
int a[MAXN];
long long ans;

void solve(int l, int r) {
	if(l+1==r) {
		ans += a[l];
		return;
	}
	int mid=(l+r)>>1;
	std::vector<int> pre(a + mid,a+r);
	for (int i=l; i<r-mid; ++i)   __(1)__ ;
		std::vector<long long> sum(r - mid + 1);
	for (int i=0; i<r-mid; ++i) sum[i+1]= sum[i]+ pre[i];
	for (int i=mid-1,j=mid,max = 0; i>= l; --i) {
		while (j<r &&  __(2)__ ) ++j;
		max = std::max(max,a[i]);
		ans += __(3)__;
		ans += __(4)__;
	}
	solve(l, mid);
	solve(mid, r);
}

int main() {
	std::cin >> n;
	for (int i=0; i<n; ++i) std::cin >> a[i];
	__(5)__ ;
	std::cout << ans << std::endl;
	return 0;
}

第 43 题 ⑴处应填( )。

A. pre[i]= std::max(pre[i - 1],a[i - 1])
B. pre[i + 1]= std::max(pre[il,pre[i+ 1])
C. pre[i]=std::max(pre[i - 1],a[i])
D. pre[i]= std::max(pre[i],pre[i - 1])

答案： D. pre[i]= std::max(pre[i],pre[i - 1])

第 44 题 ⑵处应填( )。

A. a[j]< max
B. a[j]< a[i]
C. pre[j - mid]< max

答案： B. a[j]< a[i]

max" lay-filter="filter">

第 45 题 ⑶处应填( )。

A. (long long)(j - mid)* max
B. (long long)(j - mid) * (i - l)* max
C. sum[j - mid]
D. sum[j - mid]*(i- l)

答案： A. (long long)(j - mid)* max

第 46 题 ⑷处应填( )。

A. (long long)(r -j)* max
B. (long long)(r -j)i(mid -i)*max
C. sum[r - mid] - sum[j - mid]
D. (sum[r - mid] - sum[j - mid])* (mid - i)

答案： C. sum[r - mid] - sum[j - mid]

第 47 题 ⑸处应填( )。

A. solve(0,n)
B. solve(0,n - 1)
C. solve(1,1)
D. solve(1,n - 1)

答案： A. solve(0,n)

2023CCF 提高级 CSP-S 初赛

Links to this page: