全国提高组 CSP-S 初赛模拟试题 (5) [2021年]

1. 表达式a×(b+c)-d/f转后缀表达式的结果是( )。

2. 以下字符串中，字典序最小的是( )。

3. 在C++中,表达式('O'-'I')^13%9+5 的值是( )。

4. 在8个数中，找出这组数的最小值与最大值，最坏情况下最少需要比较( )次。

5. 在 TCP/IP协议族中，最核心的网络协议是( )。

6. 应用快速排序的分治思想可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法期望时间复杂度为( )。

7. 在解决计算机主机与外设之间速度不匹配时通常设置一个缓冲池，主要将计算机输出的数据依次写入该缓冲区，而外设从该缓冲区池中取出数据。该缓冲池应该是一个( )结构。

8. (1E34)16-(676)8的结果是( )。

9. 一棵二叉树前序遍历为ABDECFGH，后序遍历为EDBGFHCA，以下不是可能的中序遍历的是( )。

10. 一个栈的输入顺序为1,2,3,4,5，下列序列中不可能是栈的输出序列的是( )。

11. Linux是一个用C语言写成的开源电脑操作系统内核，有大量的操作系统是基于Linux内核创建的。以下操作系统使用的不是Linux内核的是( )。

12. 在下列关于计算机算法的说法中，正确的是( )。

13. 以下关于二叉树性质中，正确的描述的个数有( )。 a.包含n个结点的二叉树的高度至少为log2n; b.在任意一棵非空二叉树中，若叶子结点的个数为n0，度为2的结点数为n2，则 n0=n2+1; c.深度为k的二叉树至多有2^k个结点 d.没有一棵二叉树的前序遍历序列与后序遍历序列相同 e.具有n个结点的完全二叉树的深度为[log2[(n+1)]

14. 排序算法是稳定的，这句话的意思是关键码相同的记录排序前后相对位置不发生改变，以下排序算法不稳定的是( )。

15. 给定m种颜色和有n个点的手环，要求用这个m种颜色给这条手环染色，其中旋转和翻转能够互相得到的算同一种染色方案，如对于3个点的手环，ABC的染色方法与BCA(旋转)、ACB(翻转)是相同的。当m=2,n=2 时，一共有三种染色方案，分别为AA、AB、BB，那么当m=5,n=4时，一共有( )种染色方案。

1.

#include <iostream>

using namespace std;



unsigned short tot;

void Hanoi(int n, char A, char B, char C) {

	++tot;

	if(n==1) {

		cout<<A<<"->"<<C<<'/';

		return;

	}

	Hanoi(n-1,A,C,B);

	cout<<A<<"->"<<C<<'/';

	Hanoi(n-1,B,A,C);

}



int main() {

	int n;

	cin>> n;

	Hanoi(n,'A','B','C');

	cout<<'\n'<<tot<<'\n';

	

	return 0;

}

判断题

选择题

2.

#include <iostream>

#include <iomanip>

#include <cstring>

using namespace std;

const int N = 105;

int a[N][N];

int main() {

	int n, x, y,count;

	cin>> n;

	memset(a,0,sizeof(a));

	count=a[x=0][y=n-1]=1;

	while (count<n*n) {

		while (x+1<n && !a[x+1][y]) a[++x][y]= ++count;

		while (y-1>=0&&!a[x][y- 1]) a[x][--y]= ++count;

		while (x-1>=0&&!a[x-1][y])  a[--x][y]= ++count;

		while (y+1<n &&!a[x][y+1])  a[x][++y]= ++count;

	}

for (x=0; x<n; x++) {

		for (y=0; y<n; y++) {

			cout<<setw(5)<<a[x][y];

		}

		cout<<endl;

	}

	return 0;

}

判断题

选择题

3.

#include <iostream>

#include <iomanip>

#include <cstring>

using namespace std;

string s;

int main() {

	int k;//限制输入0<=k<26

	cin>>k>>s;

	int n=s.length();

	for (int i=0; i<n; i++) {

		if (s[i]<='Z'&&s[i]+k>'Z')

			s[i]=(s[i]+k)%'Z'+'A'-1;

		else if ('A'<=s[i]&&s[i] <='Z')

			s[i]+=k;

	}

	char pre;

	int st=-1;

	for (int i=0; i<n; i++) {

		if(s[i]<'A'||s[i]>'Z') {

			if (st==-1) {

				st=i;

				pre=s[i];

			} else {

				char tmp=s[i];

				s[i]=pre;

				pre=tmp;

			}

		}

	}

	if(st !=-1)

		s[st]=pre;

	cout<<s<<endl;

	return 0;

}

判断题

选择题

1. (拓扑排序)
在我们所学的课程中，部分课程之间可能存在依赖关系，如我们在学习图论知识之前，需要先学习离散数学中的基础知识。一门课可能有若干先修课程。现在李老师需要安排一些课程的授课计划，排课需要遵从一定的规则,即只有修习完某课程的全部课程后，才能修习该课程。
在本例中,用1~n表示n个课程,用x y表示x是y的先修课程，输入数据保证图中没有环与重边。要求输出任意一个可行的授课顺序。图用邻接矩阵方法储存。

#include <iostream>

#include <cstring>

# include <queue>

using namespace std;

const int N=105;

int a[N][N];

int in[N],s[N];

int n,m,u,v;

void Topo() {

	queue<int> q;

	int cnt;

	for(int i=1; i<=n; i++)

		if(___(1)___)

			q.push(i);

	while(!q.empty()) {

		int cur = q.front();

		q.pop();

		s[cnt++]=___(2)___;

		for (int i=1; i<=n; i++) {

			if (___(3)___) {

				___(4)___;

				if (in[i]==0)

					q.push(i);

			}

		}

	}

}

int main() {

	memset(in,0,sizeof(in));

	memset(a, 0,sizeof(a));

	cin>>n>>m;

	for (int i=0; i<m; i++) {

		cin>>u>>v;

		in[v]++;

		___(5)___;

	}

	Topo();

	for (int i=0; i<n; i++) {

		if (i)

			cout<<' ';

		cout<<s[i];

	}

	cout<<endl;

	return 0;

}

选择题

2. (8一皇后问题)要求用回溯法求解8-皇后问题，使放置在8*8棋盘上的8个皇后彼此不受攻击，即:任何两个皇后都不在同一行、同一列或同一斜线上。请输出8皇后问题的所有可行解。

#include <iostream>

#include<cmath>

using namespace std ;



bool Place(int k,int i,int * x) {

	for (int j=0; j<k; j++)

		if ((x[j]==i)||___(1)___)

			return false;

	return true;

}



void NQueens(int k, int n, int *x) {

	for (int i=0; i<n; i++) {

		if (Place(k,i,x)) {

			___(2)___;

			if(___(3)___) {

				for (int j=0; j<n; j++) cout<<x[j]<<" ";

				cout<< endl;

			}

			else {

				___(4)___;

			}

		}

	}

}

int main() {

	int x[8];

	for (int i=0; i<8; i++)x[i]=-1;

	___(5)___;

	return 0;

}

选择题