2021CCF 提高级 CSP-S 初赛

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

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

第 1 题在Linux系统终端中，用于列出当前目录下所含的文件和子目录的命令为( )。

A. ls
B. cd
C. cp
D. all

答案： A. ls

第 2 题二进制数00101010(2)和00010110(2)的和为( )。

A. 00111100(2)
B. 01000000(2)
C. 00111100(2)
D. 01008010(2)

答案： B. 01000000(2)

第 3 题在程序运行过程中，如果递归调用的层数过多，可能会由于( )引发错误。

A. 系统分配的栈空间溢出
B. 系统分配的队列空间溢出
C. 系统分配的链表空间溢出
D. 系统分配的堆空间溢出

答案： A. 系统分配的栈空间溢出

第 4 题以下排序方法中，(）是不稳定的。

A. 插入排序
B. 冒泡排序
C. 堆排序
D. 归并排序

答案： C. 堆排序

第 5 题以比较为基本运算，对于2n个数，同时找到最大值和最小值，最坏情况下需要的最小的比较次数为( ) 。

A. 4n-2
B. 3n+1
C. 3n-2
D. 2n+1

答案： C. 3n-2

第 6 题现有一个地址区间为0~10的哈希表，对于出现冲突情况，会往后找第一个空的地址存储（到10冲突了就从0开始往后），现在要依次存储(0, 1, 2, 3, 4, 5, 6, 7)，哈希函数为h(x)=x^2 mod 11。请问7存储在哈希表哪个地址中( )。

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

答案： C. 7

第 7 题 G是一个非连通简单无向图（没有自环和重边），共有36条边，则该图至少有( )个点。

A. 8
B. 9
C. 10
D. 11

答案： C. 10

第 8 题令根结点的高度为1,则一棵含有2021个结点的二叉树的高度至少为( )。

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

答案： B. 11

第 9 题前序遍历和中序遍历相同的二叉树为且仅为( )。

A. 只有1个点的二叉树
B. 根结点没有左子树的二叉树
C. 非叶子结点只有左子树的二叉树
D. 非叶子结点只有右子树的二叉树

答案： D. 非叶子结点只有右子树的二叉树

第 10 题定义一种字符串操作为交换相邻两个字符。将“DACFEB”变为“ABCDEF”最少需要( )次上述操作。

A. 7
B. 8
C. 9
D. 6

答案： A. 7

第 11 题有如下递归代码 solve(t,n): if t=1 return 1 else return 5*solve(t-1,n) mod n 则solve(23, 23)的结果为( ) 。

A. 1
B. 7
C. 12
D. 22

答案： A. 1

第 12 题斐波那契数列的定义为：F1=1,F2=1,Fn=Fn-1+Fn-2 (n>=3)。现在用如下程序来计算斐波那契数列的第n项，其时间复杂度为( ). F(n) : if n ≤2 return 1 else return F(n-1) +F(n-2)

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

答案： C. O(2^n)

第 13 题有8个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两个苹果，一共有( )种方案。

A. 36
B. 48
C. 54
D. 64

答案： C. 54

第 14 题设一个三位数n=abc,a,b,c均为1~9之间的整数，若以a、b、c作为三角形的三条边可以构成等腰三角形（包括等边），则这样的n有( )个。

A. 81
B. 120
C. 165
D. 216

答案： C. 165

第 15 题有如下的有向图，节点为A,B,…,J,其中每条边的长度都标在图中。则节点A到节点J的最短路径长度为（）。

A. 16
B. 19
C. 20
D. 22

答案： B. 19

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

第 16 题

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

const double r = acos(0.5) ;

int a1, b1, c1, d1;
int a2, b2, c2, d2;

inline int sq(const int x) {return x * x;}
inline int cu(const int x) {return x*x *x;}

int main (  )
{
	cout.flags(ios::fixed) ;
	cout.precision(4) ;
	
	cin >> a1 >> b1 >> c1 >> d1;
	cin >> a2 >> b2 >> c2 >> d2;
	
	int t= sq (a1-a2) +sq (b1-b2) +sq (c1-c2) ;
	
	if (t <= sq(d2-d1)) cout << cu(min(d1,d2))*r*4;	
	else if (t >=sq (d2+d1)) cout << 0;
	else {
		double x=d1-(sq (d1) - sq (d2) +t) / sqrt (t) / 2;
		double y=d2-(sq (d2) - sq (d1) +t) / sqrt (t) /2;
		cout << (x*x* (3*d1-x) +y*y* (3*d2-y)) *r;
	}
	cout << endl;
	return 0;
}

假设输入的所有数的绝对值都不超过1000,完成下面的判断题和单选题：

判断题

第 16 题将第21行中t的类型声明从int改为double，不会影响程序运行的结果。( )

A.正确
B.错误

答案： A.正确

第 17 题将第26、27行中的“／sqrt(t)/2”替换为“／2/sqrt(t)”，不会影响程序运行的结果。( )

A.正确
B.错误

答案： 2

第 18 题将第28行中的“xx”改成“sq(x)”、“yy”改成“sq(y)”，不会影响程序运行的结果。( )

A.正确
B.错误

答案： 2

第 19 题 (2分)当输入为“00011001”时，输出为“1.3090”。( )

A.正确
B.错误

答案： A.正确

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

A. “3.1416”
B. “6.2832”
C. “4.7124”
D. “4.1888”

答案： D. “4.1888”

第 21 题 (2.5分) 这段代码的含义为( )。

A. 求圆的面积并
B. 求球的体积交
C. 求球的体积并
D. 求椭球的体积并

答案： C. 求球的体积并

第 23 题

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

int n,a[1005] ;

struct Node
{
	int h, j, m, w;
	
	Node (const int _h, const int _j, const int _m, const int _w) :
		h (_h) , j (_j) , m (_m) ,w (_w)
	{}
		
	Node operator+ (const Node &o) const
	{
		return Node(
			max(h,w+o.h) ,
		    max(max (j,o.j) ,m +o.h) ,
		    max(m+o.w,o.m) ,
		    w+o.w) ;
	}
} ;

Node solve1 (int h,int m)
{
	if (h>m)
		return Node (-1, -1, -1, -1) ;
	if (h==m)
		return Node(max(a[h], 0) , max(a[h], 0) , max(a[h], 0) ,a[h]) ;
	int j= (h + m) >> 1;
	return solve1 (h, j) + solve1(j+1, m);
}

int solve2 (int h, int m)
{
	if (h>m)
		return -1;
	if (h==m)
		return max(a[h], 0) ;
	int j= (h+m) >> 1;
	int wh=0,wm =0;
	int wht=0,wmt=0;
	for (int i = j; i >= h; i--) {
		wht +=a[i] ;
		wh =max(wh,wht) ;
	}
	for (int i = j+1; i <= m; i++){
		wmt +=a[i] ;
		wm=max(wm,wmt) ;
	}		
	return max (max(solve2(h, j), solve2(j+1,m)) ,wh + wm) ;
}

int main (  )
{
	cin >> n;
	for (int i=1; i <= n; i++) cin >> a[i];
	cout << solve1(1, n).j << endl;
	cout << solve2(1, n) << endl;
	return 0;
}

假设输入的所有数的绝对值都不超过1000,完成下面的判断题和单选题：

判断题

第 23 题程序总是会正常执行并输出两行两个相等的数。( )

A.正确
B.错误

答案： A.正确

第 24 题第28行与第38行分别有可能执行两次及以上。( )

A.正确
B.错误

答案： 2

第 25 题当输入为“5-10 11-95-7”时，输出的第二行为“7”。( )

A.正确
B.错误

答案： 2

第 26 题 solve1(1, n)的时间复杂度为( )。

答案： 2

A. $Θ(logn)$

答案： 2

B. $Θ(n)$

答案： 2

C. $(Θnlogn)$

答案： 2

D. $Θ(n^2)$

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

答案： 3

A. $Θ(logn)$

答案： 3

B. $Θ(n)$

答案： 3

C. $Θ(nlogn)$

答案： 3

D. $Θ(n^2)$

第 28 题当输入为“10 -3 2 10 0 -8 9 -4 -5 9 4”时，输出的第一行为( )。

A. “13”
B. “17”
C. “24”
D. “12”

答案： B. “17”

第 30 题

#include <iostream>
#include <string>
using namespace std;

char base [64] ;
char table [256] ;

void init ()
{
	for (int i=0; i < 26; i++) base[i] = 'A' + i;
	for (int i=0; i < 26; i++) base[26 + i] = 'a' + i;
	for (int i=0; i < 10; i++) base[52 + i] = '0' + i;
	base [62] = '+', base[63] = '/';
	
	for (int i = 0; i < 256; i++) table[i] = 0xff;
	for (int i = 0; i < 64; i++) table[base[i]]= i;
	table ['='] =0;	
}

string encode (string str)
{
	string ret;
	int i;
	for (i=0; i + 3 <= str.size(); i+=3){		
		ret +=base [str [i] >> 2] ;
		ret +=base [ (str [i] &0x03) <<4|str[i+1]>> 4];
		ret +=base [ (str [i +1] &0x0f) <<2|str[i+2]>> 6];
		ret += base [str [i+2] & 0x3f] ;
	}
	if (i < str.size()){
		ret +=base [str [i] >> 2];
		if (i+1==str.size () ) {			
			ret +=base [ (str [i] &0x03) <<4];
			ret +="==";
		}
		else{		
			ret += base [ (str [i] & 0x03) <<4|str[i+1] >> 4];
			ret += base [ (str [i +1] & 0x0f) << 2];
			ret +="=";
		}
	}
	return ret;
}

string decode (string str)
{
	string ret;
	int i;	
	for (i=0; i < str.size(); i +=4){
	ret +=table [str [i] ] <<2|table[str[i+1]]>>4;
	if (str[i + 2] != '=')
		ret += (table[str[i+1]]& 0x0f) << 4|table[str[i+2]] >> 2;
	if (str[i+3] != '=')
		ret += table [str [i + 2] ] << 6|table[str[i +3]];
	}
	return ret;
}

int main ()
{
	init () ;
	cout << int(table[0])<< endl;
	int opt;
	string str;
	cin >> opt >> str;
	cout << (opt ? decode(str) : encode(str))<< endl;
	return 0;
}

假设输入总是合法的（一个整数和一个不含空白字符的字符串，用空格隔开），完成下面的判断题和单选题：

判断题

第 30 题程序总是先输出一行一个整数，再输出一行一个字符串。( )

A.正确
B.错误

答案： 2

第 31 题对于任意不含空白字符的字符串str1,先执行程序输入“0 str1”，得到输出的第二行记为str2;再执行程序输入“1 str2”，输出的第二行必为str1.( )

A.正确
B.错误

答案： A.正确

第 32 题当输入为“1 SGVsbG93b3JsZA==”时，输出的第二行为“HelloWorld”。( )

A.正确
B.错误

答案： 2

第 33 题设输入字符串长度为 n,encode 函数的时间复杂度为( ).

答案： 2

A. $Θ(\sqrt{n})$

答案： 2

B. $Θ(n)$

答案： 2

C. $Θ(nlogn)$

答案： 2

D. $Θ(n^2)$

第 34 题输出的第一行为( )。

A. “0xff”
B. “255”
C. “0xFF”
D. “-1”

答案： D. “-1”

第 35 题 (4分）当输入为“0 CSP2021csp”时，输出的第二行为( )。

A. “Q1NQMjAyMWNzcAv=”
B. “Q1NQMjAyMGNzcA==”
C. “Q1NQMjAyMGNzcAv=”
D. “Q1NQMjAyMWNzcA==”

答案： D. “Q1NQMjAyMWNzcA==”

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

第 37 题 (魔法数字）小H的魔法数字是 4。给定 n,他希望用若干个 4 进行若干次加法、减法和整除运算得到n。但由于小H计算能力有限，计算过程中只能出现不超过M=10000的正整数。求至少可能用到多少个 4。

例如，当n=2时，有2=(4+4)/4,用到了3个4，是最优方案。

试补全程序。

#include <iostream>
#include <cstdlib>
#include <climits>

using namespace std;

const int M=10000;
bool Vis[M+1] ;
int F[M+1] ;

void update (int &x, int y) {
	if (y<x)
		x=y;
}

int main () {
	int n;
	cin >> n;
	for (int i = 0; i <=M; i++)
		F[i]= INT_MAX;
	___(1)___;
	int r=0;
	while (___(2)___) {
		r++;
		int x=0;
		for (int i = 1; i <= M; i++)
			if (___(3)___)
				x=i;
		Vis[x]=1;
		for (int i = 1; i <= M; i++)
			if (___(4)___) {
				int t=F[i] +F[x] ;
				if (i+x <=M)
					update (F[i+x] ,t) ;
				if (i!=x)
					update (F[abs (i-x)] ,t) ;
				if (i%x==0)
					update (F[i/x] ,t) ;
				if (x%i==0)
					update (F[x/i] ,t) ;
			}
	}
	cout <<F[n] << endl;
	return 0;
}

第 37 题 ⑴处应填( )。

A. F[4]=0
B. F[1]=4
C. F[1]=2
D. F[4]=1

答案： D. F[4]=1

第 38 题 ⑵处应填( )。

A. !Vis[n]
B. r <n
C. F[M]==INT_MAX
D. F[n]==INT_MAX

答案： A. !Vis[n]

第 39 题 ⑶处应填( )。

A. F[i]==r
B. !Vis[i] &&F[i] ==r
C. F[i]<F[x]
D. !Vis[i] &&F[i] <F[x]

答案： D. !Vis[i] &&F[i] <F[x]

第 40 题 ⑷处应填( )。

A. F[i]<F[x]
B. F[i]≤r
C. Vis[i]
D. i ≤x

答案： C. Vis[i]

第 42 题 (RMQ 区间最值问题）给定序列 $a_0,\cdots,a_{n-1}$ ,和 $m$ 次询问，每次询问给定 $l,r$ ,求 $\max \{a_l, \cdots ,a_r\}$ 。

为了解决该问题，有一个算法叫 the Method of Four Russians,其时间复杂度为 $O(n+m)$ ,步骤如下：

建立 Cartesian(笛卡尔)树，将问题转化为树上的 LCA(最近公共祖先)问题。
对于 LCA 问题，可以考虑其 Euler序（即按照 DFS 过程，经过所有点，环游回根的序列），即求 Euler 序列上两点间一个新的 RMQ 问题。
注意新的问题为 ±1 RMQ,即相邻两点的深度差一定为1。下面解决这个±1 RMQ 问题，“序列” 指 Euler 序列：
设t为Euler 序列长度。取 $b=\lceil \frac{log_{2}{t}}{2} x \rceil$ 。将序列每b个分为一大块，使用ST表（倍增表）处理大块间的 RMQ 问题，复杂度 $O(\frac{t}{b}logt)=O(n)$ 。
（重点）对于一个块内的 RMQ问题，也需要O(1)的算法。由于差分数组 $2^{b-1}$ 种，可以预处理出所有情况下的最值位置，预处理复杂度 $O(b2^b)$ ,不超过 $O(n)$ 。
最终，对于一个查询，可以转化为中间整的大块的 RMQ问题，以及两端块内的 RMQ 问题。试补全程序。

#include <iostream>
#include <cmath>

using namespace std;

const int MAXN=100000, MAXT=MAXN << 1;
const int MAXL = 18, MAXB = 9, MAXC =MAXT/MAXB;

struct node {
	int val;
	int dep, dfn, end;
	node *son[2];//son[0],son[1]分别表示左右儿子
} T[MAXN] ;

int n,t,b,c, Log2 [MAXC+1] ;
int Pos [(1 << (MAXB-1))+5],Dif[MAXC + 1];
node *root, *A[MAXT] , *Min[MAXL][MAXC];

void build(  ) { //建立 Cartesian 树
	static node *S [MAXN +1] ;
	int top=0;
	for (int i=0; i<n; i++) {
		node *p=&T [i] ;
		while (top &&S[top]->val<p->val)
			___(1)___;
		if (top)
			___(2)___;
		S [++top] =p;
	}
	root=S[1] ;
}

void DFS(node *p) { //构建 Euler 序列
	A [p-> dfn = t++] =p;
	for (int i =0; i < 2; i++)
		if (p->son[i]) {
			p->son[i]->dep = p->dep +1;
			DFS(p->son[i]) ;
			A [t++] =p;
		}
	p->end =t - 1;
}

node *min (node *x,node *y) {
	return ___(3)___?x:y;
}

void ST_init() {
	b= (int) (ceil(log2(t)/2));
	c=t/b;
	Log2 [1] =0;
	for (int i =2; i <=c; i++)
		Log2 [i] =Log2[i>>1] +1;
	for (int i = 0; i < c; i++) {
		Min[0][i]=A[i*b];
		for (int j=1; j< b; j++)
			Min[0][i] = min(Min[0][i],A[i*b+j]);
	}
	for (int i=1,l=2; l<= c; i++, l<<= 1)
		for (int j=0; j+1 <= c; j++)
			Min[i][j] = min(Min[i-1][j], Min[i-1][j+(l>>1)]) ;
}

void small_init(  ) { //块内预处理
	for (int i=0; i <=c; i++)
		for (int j = 1; j<b&& i *b+j<t; j++)
			if (___(4)___)
				Dif [i]|=1 << (j-1);
	for (int S =0; S<(1<<(b-1)); S++) {
		int mx=0,v=0;
		for (int i=1; i<b; i++) {
			___(5)___;
			if (v <mx) {
				mx=v;
				Pos [S] =i;
			}
		}
	}
}

node *ST_query (int l, int r) {
	int g=Log2 [r-1+1] ;
	return min (Min[g][1],Min[g][r-(1<<g)+1]);
}

node *small_query(int l,int r) { //块内查询
	int p=1/b;
	int S=6;
	return A[1+Pos[S]] ;
}

node *query (int l,int r) {
	if (l>r)
		return query (r, 1) ;
	int pl=l/b,pr =r/b;
	if (pl ==pr) {
		return small_query (l,r) ;
	} else {
		node *s = min(small_query (l, pl*b+b-1),small_query (pr*b,r) ) ;
		if (pl+1<=pr-1)
			s = min (s, ST_query(pl+1,pr-1));
		return s;
	}
}

int main () {
	int m;
	cin >>n>>m;
	for (int i=0; i<n; i++)
		cin >> T[i].val;
	build () ;
	DFS (root) ;
	ST_init () ;
	small_init () ;
	while (m--) {
		int l,r;
		cin >>l>>r;
		cout << query(T[1].dfn, T[r].dfn)->val << endl;
	}
	return 0;
}

第 42 题 ⑴处应填( )。

答案： 1

son[0] =S[top–]" lay-filter="filter">

答案： 1

son[1] =S[top–]" lay-filter="filter">

答案： 1

son[0]=p" lay-filter="filter">

答案： 1

son[1] =p" lay-filter="filter">

第 43 题 ⑵处应填( )。

答案： 4

son[0] =S[top]" lay-filter="filter">

答案： 4

son[1] =S[top]" lay-filter="filter">

答案： 4

son[0] =p" lay-filter="filter">

答案： 4

son[1] =p" lay-filter="filter">

第 44 题 ⑶处应填( )。

答案： 1

dep < y->dep" lay-filter="filter">

B. x<y

答案： 1

dep > y->dep" lay-filter="filter">

答案： 1

val < y->val" lay-filter="filter">

第 45 题 ⑷处应填( )。

答案： 4

son[0]" lay-filter="filter">

答案： 4

val < A[i*b+j-1]->val" lay-filter="filter">

答案： 4

son[1]" lay-filter="filter">

答案： 4

dep < A[i*b+j-1]->dep" lay-filter="filter">

第 46 题 ⑸处应填( )。

答案： 4

i &1)?-1:1" lay-filter="filter">

答案： 4

i &1)?1:-1" lay-filter="filter">

答案： 4

(i-1)&1)?1:-1" lay-filter="filter">

答案： 4

(i-1) &1)?-1:1" lay-filter="filter">

第 47 题 ⑹处应填( )。

答案： 3

(r-p*b))&((1<<(r-l))-1)" lay-filter="filter">

B. Dif[p]

答案： 3

(l-p*b))&((1<(r-l))-1)" lay-filter="filter">

答案： 3

((p+1)*b-r))&((1<<(r-l+1))-1)" lay-filter="filter">

2021CCF 提高级 CSP-S 初赛

Links to this page: