06_自習題庫_含參考答案2021提高组 CSP-S 初赛模拟试题 (5)

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

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

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

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

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

  • A. abc×+df-/
  • B. abc+×df/-
  • C. bc+a×df/-
  • D. abc+×-df/

答案： B. abc+×df/-

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

  • A. NOIP2017
  • B. NOIPC
  • C. NOIPC++
  • D. NOIPP

答案： A. NOIP2017

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

  • A. 7
  • B. 8
  • C. 14
  • D. 15

答案： D. 15

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

  • A. 9
  • B. 10
  • C. 12
  • D. 13

答案： B. 10

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

  • A. UDP
  • B. HTTP
  • C. TCP
  • D. IP

答案： D. IP

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

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

答案： C. O(n)

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

  • A. 堆栈
  • B. 队列
  • C. 二叉树
  • D. 链表

答案： B. 队列

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

  • A. (1110001111110)2
  • B. (7276)10
  • C. (1C6C)16
  • D. (16166)8

答案： D. (16166)8

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

  • A. DEBAFGCH
  • B. EDBAGFCH
  • C. DBEAFGCH
  • D. BEDAFGCH

答案： B. EDBAGFCH

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

  • A. 54321
  • B. 24135
  • C. 32541
  • D. 13542

答案： B. 24135

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

  • A. Android
  • B. CentOS
  • C. Windows
  • D. Ubuntu

答案： C. Windows

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

  • A. 对于一个问题，我们能通过优化算法，不断降低其算法复杂度
  • B. 判断一个算法的好坏，主要依据它在某台计算机上具体实现时的运行时间
  • C. 一个算法必须至少有一个输入
  • D. 算法复杂度理论中，P/NP问题(NP完全问题)仍是一个未解之谜

答案： D. 算法复杂度理论中，P/NP问题(NP完全问题)仍是一个未解之谜

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

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

答案： B. 1

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

  • A. 直接插入排序
  • B. 快速排序
  • C. 冒泡排序
  • D. 归并排序

答案： B. 快速排序

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

  • A. 625
  • B. 160
  • C. 60
  • D. 120

答案： D. 120

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

第 16 题

#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;
}

判断题

第 16 题 (1分)将第6行移到13行和14行之间，输出结果不会变化。( )

  • A.正确
  • B.错误

答案： 2

第 17 题 当输入的n=2时，输出的第一行为A->B/B->C/A->C/。( )

  • A.正确
  • B.错误

答案： 2

第 18 题 当输入的n=3时，输出的第二行为8。( )

  • A.正确
  • B.错误

答案： 2

第 19 题 本程序的含义可以是:有三根柱子，第一根柱子从上到下依次套有编号分别为1~n的圆环，现在每次可以移动某个柱子顶部的圆环到另一个桂子的顶部上，并且要求编号较大的圆环要始终不能在编号较小的上面，输出一种操作次数最少的方案以及对应的操作次数。( )

  • A.正确
  • B.错误

答案： A.正确

第 20 题 当输入的n=3时，输出的第一行的第21个字符是( )。

  • A. A
  • B. B
  • C. C
  • D. /

答案： B. B

第 21 题 (5分)当n=17时,程序输出的第二行为( )。

  • A. -1
  • B. 131071
  • C. 131072
  • D. 65535

答案： D. 65535

第 23 题

#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;
}

判断题

第 23 题 (1分)删除第10行,不影响程序运行结果。()

  • A.正确
  • B.错误

答案： A.正确

第 24 题 将第12行改为“while (count≤ n*n){”,不影响程序运行结果。()

  • A.正确
  • B.错误

答案： 2

第 25 题 当输入的n=4时,程序输出的a[3][2]的值为15。()

  • A.正确
  • B.错误

答案： 2

第 26 题 (3分)本题的时间复杂度为()。

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

答案： B. O(n^2)

第 27 题 当输入的n=100 时,a[33][66]的值为()。

  • A. 8779
  • B. 8707
  • C. 10957
  • D. 8845

答案： D. 8845

第 29 题

#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;
}

判断题

第 29 题 (1分)删除第30行和第31行，不影响程序运行结果。( )

  • A.正确
  • B.错误

答案： 2

第 30 题 如果输入的s不含大写字母，则输出结果与k的值无关。( )

  • A.正确
  • B.错误

答案： A.正确

第 31 题 如果知道输出结果，能够反推出唯一的输入结果。( )

  • A.正确
  • B.错误

答案： 2

第 32 题 当k的值确定时，不存在两个不同的输入使得输出相同。( )

  • A.正确
  • B.错误

答案： A.正确

第 33 题 如果输入是6 KU96APY5,则输出为( )。

  • A. QB96GWE5
  • B. QA59GVE6
  • C. PA59GWF6
  • D. PB96GWE5

答案： B. QA59GVE6

第 34 题 (5分)如果输出是ab1287F2Tguz,则输入可能为( )。

  • A. 0 ab1287F2Tguz
  • B. 3 b1287BgTuza
  • C. 16 b12872PgDuza
  • D. 13 b12872MgAuza

答案： C. 16 b12872PgDuza

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

第 36 题 (拓扑排序) 在我们所学的课程中，部分课程之间可能存在依赖关系，如我们在学习图论知识之前，需要先学习离散数学中的基础知识。一门课可能有若干先修课程。现在李老师需要安排一些课程的授课计划，排课需要遵从一定的规则,即只有修习完某课程的全部课程后，才能修习该课程。 在本例中,用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;
}

第 36 题 ①处应填( )

  • A. in[i]==0
  • B. in[i]==1
  • C. a[1][u]==0
  • D. a[1][u]==1

答案： A. in[i]==0

第 37 题 ②处应填( )

  • A. q.front()
  • B. cur
  • C. q.back()
  • D. s[cur]

答案： B. cur

第 38 题 ③处应填( )

  • A. !–in[i]
  • B. a[u][v]==1
  • C. a[cur][i]==1
  • D. !in[i]

答案： C. a[cur][i]==1

第 39 题 ④处应填( )

  • A. in[i]++
  • B. in[i]–
  • C. q.pop()
  • D. q.push(cur)

答案： B. in[i]–

第 40 题 ⑤处应填( )

  • A. in[u]++
  • B. in[u]–
  • C. a[u][v]=1
  • D. a[v][u]=1

答案： C. a[u][v]=1

第 42 题 (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;
}

第 42 题 ①处应填( )

  • A. x[j]==i-1
  • B. abs(x[j]-i)≤1
  • C. abs(x[j]-k)==i-j
  • D. abs(x[j]-i)==k-j

答案： D. abs(x[j]-i)==k-j

第 43 题 ②处应填( )

  • A. x[i]=k
  • B. x[k]=n-i
  • C. x[k]=i
  • D. x[i]=x[k]

答案： C. x[k]=i

第 44 题 ③处应填( )

答案： 2

n-1" lay-filter="filter">

答案： 2

= n-1" lay-filter="filter">

  • C. k == n

答案： 2

n" lay-filter="filter">

第 45 题 ④处应填( )

  • A. NQueens(k,n-1,x)
  • B. NQueens(k+1,n,x)
  • C. NQueens(k+1,n-1,x)
  • D. cout << x[k] << ' '

答案： B. NQueens(k+1,n,x)

第 46 题 ⑤处应填( )

  • A. NQueens(1,8,x)
  • B. NQueens(0,7,x+1)
  • C. NQueens(0,8,x)
  • D. NQueens(1,8,x+1)

答案： C. NQueens(0,8,x)

Links to this page:

  1. 自習題庫使用說明
Built with LogoFlowershow