ID: 1437

客观题

难度: 9

上传者:

xiaoboup

2023年图灵编程CSP-J初赛模拟卷1

一、单项选择题(共15题，每题2分，共计30分）

1.计算机系统中的存储器系统是指( )。 {{ select(1) }}

RAM存储器
ROM存储器
主存储器
主存储器和外存储器

2.从未排序序列元素中挑选元素，并将其放入已排序序列(初始时为空)的一端，这种排序方法称为( ){{ select(2) }}

插入排序
选择排序
冒泡排序
快速排序

3.若十进制数据为 $123.5$ 则其八进制数为( ) {{ select(3) }}

$89.9$
$1.4$
$173.4$
$1011111.101$

4.图灵编程教育派朱、刘、鲍、张、卞五人出国学习，选派条件是

1).若朱去，刘也去

2).张、卞两人必有一人去

3).如卞去，则朱、刘也同去

4).鲍、张二人同去或同不去

如何选他们出国?( ){{ select(4) }}

鲍、朱、卞去
朱、刘、卞去
张、卞、鲍去
刘、鲍去

5.国际标准化组织ISO制定的开放系统互连基本参考模型有( ){{ select(5) }}

3层
5层
6层
7层

6.若定义int x=3;，则执行下列语句后的输出结果是( )

do{ 
    printf("%d",x+=1);
}while(--x);

444
44
4
死循环

7.若 $x_补=0.1101010,则x_原=$ （）。{{ select(7) }}

$1.0010101$
$1.0010110$
$0.0010110$
$0.1101010$

8.小朱有7个好朋友，他让好朋友们在圆桌上排成一圈，小朱在圆桌中间为他们表演，请问有几种排法。（）{{ select(8) }}

9.存储一幅分辨率为 $1024\times 768$ 像素的 $256$ 色位图图像所需要的存储空间约为多少KB？( ){{ select(9) }}

768
1024
96
256

10.表达式 $a*(b+c)*d$ 的后缀表达式为( )，其中" $*$ "和" $+$ "是运算符。{{ select(10) }}

**a+bcd*
abc+*d*
abc*d+*
*a*+bcd

11.在长度为n的顺序表的表尾插入一个新元素的时间复杂度为( )。{{ select(11) }}

$O(n)$
$O(1)$
$O(n^2)$
$O(logn)$

12.在具有2n个结点的完全二叉树中，叶子结点个数为( ){{ select(12) }}

13.下列说法中正确的是（）。{{ select(13) }}

一个图的邻接矩阵表示是唯一的，邻接表表示也唯一
一个图的邻接矩阵表示是唯一的，邻接表表示不唯一
一个图的邻接矩阵表示不唯一，邻接表表示唯一
一个图的邻接矩阵表示不唯一，邻接表表示也不唯一

14.已知一个栈的进栈序列为1，2，3，…，n，其输出序列的第一个元素是i，则第j个出栈元素是（）。{{ select(14) }}

j-1
n-i
j-i+1
不确定

15.小博的手里有200个键盘，其中有160个无线键盘，小朱手中有240个鼠标，其中有180个无线鼠标。现在从小博、小朱手中各任取一个，则能配成无线外设(无线键盘+无线鼠标)的概率为多少？（）{{ select(15) }}

$\frac 1{20}$
$\frac {19}{20}$
$\frac35$
$\frac{15}{16}$

二、阅读程序(判断题每题2分，选择题每题3分，共28分)

(1)

1#include <bits/stdc++.h>
2using namespace std;
3
4int main(){
5	 int a[51]={0};
6	 int i,j,t,t2,n = 50;
7	 for(i = 2;i<=sqrt(n);i++){
8  		if(a[i] == 0){
9   			t2 = n/i;
10   			for(j = 2;j<=t2;j++)
11    			a[i*j] = 1;
12  		 }
13 	 }
14 	 t = 0;
15 	 for(i = 2;i<=n;i++){
16 		 if(a[i] == 0){
17   			cout <<" "<<i;
18   			t++;
19   			if(t%10 == 0) cout <<endl;
20  		 }
21 	 }
22  	 cout << endl;
23  	 return 0;
24}

判断题

16.若把06行n改为51，程序可能发生运行时错误。( ){{ select(16) }}

正确
错误

17.若去掉第05行的"={0}"，则程序运行结果不会改变。( ){{ select(17) }}

正确
错误

18.若把第07行的<=sqrt(n)该为<=n，则程序会发生运行时错误。( ){{ select(18) }}

正确
错误

19.这个程序输出了16个数字。( ){{ select(19) }}

正确
错误

20.输出的第11个数为31。( ){{ select(20) }}

正确
错误

选择题

21.程序的时间复杂度为( ){{ select(21) }}

$O(1)$
$O(n)$
$O(nlogn)$
$O(nloglogn)$

22.输出的第15个数为( ){{ select(22) }}

(2)

1#include<bits/stdc++.h>
2using namespace std;
3int main(){
4 	int n, x;
5	cin >> n;
6 	for(int i = 1; i <= n; i++) {
7		cin >> x;
8  		int cnt = 0;
9  		while(x) {
10  			if(x & 1) cnt++;
11 			x /= 2;
12		}
13  		cout << cnt << endl;
14 	}
15	return 0;
16}

判断题:

23.若去掉第08行的"=0"，则程序运行结果不会改变。(){{ select(23) }}

正确
错误

24.若把第10行的x&1改为x^0,则程序运行结果不会改变。(){{ select(24) }}

正确
错误

25.若把第11行x/=2改为x>>=1 ，程序结果不变。(){{ select(25) }}

正确
错误

选择题:

26.输入3 15 1 22，输出的结果为:( ){{ select(26) }}

3
2
4
4
1
3
5
1
3
4
2
3

27.输入1 127，输出的结果为:( ){{ select(27) }}

三、完善程序（28题2分，其余四分，共42分）

水洼的大小

题目描述

在一个 $n\times m$ 的地图里面，有水和空地。水用'.'表示，空地用'*'表示。有些位置水与上下左右相邻的水连成一片的，叫做水洼，'.'的数量表示水洼的大小。现在我们希望把空地变成水，对于给出的地图，输出把每块空地变成水后（每次只改变这一个位置，其他位置保持地图原来的状态），连通的整个水洼的大小。

输入描述

第一行： $2$ 个数 $n$ ， $m$ ，中间用空格分隔，表示地图的大小（ $1 \le m, n \le 1000$ ）。后面 $n$ 行：每行 $m$ 个字符，对应地图中的位置是水还是空地。

输出描述

对应原地图中的空地，输出将该位置改为水后，所处水洼的大小。结果 $Mod\ 10$ 。

下面的程序是以 $O(n*m)$ 的时间复杂度完成问题，试补全程序。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
const int mod = 998244353;

int n , m , vis[1010][1010] , block , num[maxn];
int dx[] = {0 , 0 , 1 , -1} , dy[] = {1 , -1 , 0 , 0};
char maze[1010][1010];
void dfs(int x , int y){
    ______1______ 
	______2______ 
	for(int i = 0 ; i < 4 ; i ++){
		int nx = x + dx[i] , ny = y + dy[i];
		if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && 
           vis[nx][ny] == 0 && maze[nx][ny] == '.'){
			dfs(nx , ny);
		}
	}
}

int main(){
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			cin >> maze[i][j];
		}
	}
	
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			if(maze[i][j] == '.' && _____3_____){
				block ++ , dfs(i , j);
			}
		}
	}
	
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			if(maze[i][j] == '.'){
				cout << maze[i][j];
			}else{
				______4_____
				st.insert(vis[i - 1][j]);
				st.insert(vis[i + 1][j]);
				st.insert(vis[i][j - 1]);
				st.insert(vis[i][j + 1]);
				int ans = 1;
				for(_____5_____) ans += num[t];
				cout << ans % 10;
			}
		}
		cout << endl;
	}
	return 0;
}

(1)处填写的代码为{{ select(28) }}

num[x][y] ++;
num[vis[x][y]] ++;
num[block] ++;
num[cnt] ++;

29.(2)处填写的代码为{{ select(29) }}

vis[x][y] ++;
vis[x][y] = block;
vis[x][y] = cnt;
vis[x][y] = num[block];

30.(3)处填写的代码为{{ select(30) }}

vis[i][j] == 0;
vis[i][j];
num[block];
num[block] == 0;

31.(4)处填写的代码为{{ select(31) }}

vector <int> st;
set <int> st;
map <int> st;
priority_queue <int> st;

32.(5)处填写的代码为{{ select(32) }}

auto t = st.begin() ; t != st.end() ; t ++
int t : st
int t = 0 ; t < st.size() ; t ++
auto t = st ; ;

梦中岛之路

题目描述

小 $S$ 上课摸鱼睡着了，梦里，他在一座岛上，因为是梦，所以他有上帝视角，他看到另一座岛上有宝藏，但是两座岛不相连，于是乎他现在要把一些海水变成路使得两座岛连通。

由于小 $S$ 想省力，所以他会把尽量少的海水变成路，不过小 $Y$ 作为一个计算机的学生，他已经做到看山不是山看水不是水，他现在眼中的岛是二位数组里的 $1$ ，他眼中的水是二维数组里的 $0$ ，那么刚才的问题就变成了，给你一个只包含 $01$ 的二维数组，且岛是一个由 $1$ 组成的四联通的块， $0$ 则是水，现在要求你把最少的 $0$ 变成 $1$ ，使得二维数组里有且仅有的两座岛相连。

输入描述

第一行一个整数 $N$ 表示二维数组有 $N$ 行 $N$ 列接下来 $N$ 行，每行 $N$ 个数字 $0$ 或 $1$ ， $0$ 代表水， $1$ 代表岛 $1\le N\le 1000$

输出描述

一个整数表示最少的需要把 $0$ 变成 $1$ 的数量

思路：先考虑找到第一个连通块，然后通过第一个连通块去bfs，找到和第二个连通块的最短距离。

下面的程序是以 $O(n^2)$ 的时间复杂度完成问题，试补全程序。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
const int mod = 998244353;

int n , vis[1010][1010];
int dx[] = {0 , 0 , 1 , -1} , dy[] = {1 , -1 , 0 , 0};
char maze[1010][1010];

struct Node{
	int x , y , d;
};

void bfs(int x , int y){
	queue <Node> Q;
	Q.push({x , y , 0});
	
	vector <Node> Arr;
	while(!Q.empty()){
		Node u = Q.front(); Q.pop();
		vis[u.x][u.y] = 1;
		Arr.push_back(u);
		for(int i = 0 ; i < 4 ; i ++){
			int nx = u.x + dx[i] , ny = u.y + dy[i];
			if(maze[nx][ny] == '1' && vis[nx][ny] == 0){
				_____1_____ 
				_____2_____ 
			}
		}
	}
	
	_____3_____
	while(!Q.empty()){
		Node u = Q.front(); Q.pop();
		for(int i = 0 ; i < 4 ; i ++){
			int nx = u.x + dx[i] , ny = u.y + dy[i];
			if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && vis[nx][ny] == 0){
                if(_____4_____ ){
                    cout << u.d << endl;
                    return;
                }
				vis[nx][ny] = 1;
				_____5______ 
			}
		}
	}
}

int main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			cin >> maze[i][j];
		}
	}

	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			if(maze[i][j] == '1'){
				bfs(i , j);
				______6______
			}
		}
	}
	return 0;
}

(1)处填写的代码为{{ select(33) }}

vis[u.x][u.y] = 1;
vis[nx][ny] = 0;
vis[nx][ny] = 1;
vis[u.x][u.y] = 0;

34.(2)处填写的代码为{{ select(34) }}

Q.push({u.x , u.y , 0});
Q.push({nx , ny , u.d + 1});
Q.push({nx , ny , 0});
Q.push({u.x , u.y , u.d + 1});

35.(3)处填写的代码为{{ select(35) }}

for(int u = 0 ; u < Arr.size() ; u ++) Q.push(u);
for(auto u : Arr) Q.push(Arr[u]);
for(auto u = Arr.begin() ; u != Arr.end() ; u ++) Q.push(u);
for(Node u : Arr) Q.push(u);

36.(4)处填写的代码为{{ select(36) }}

maze[nx][ny] == '0';
maze[nx][ny] == 0;
maze[nx][ny] == '1';
maze[nx][ny] == 1;

37.(5)处填写的代码为{{ select(37) }}

Q.push({u.x , u.y , 0});
Q.push({nx , ny , u.d + 1});
Q.push({nx , ny , 0});
Q.push({u.x , u.y , u.d + 1});

38.(6)处填写的代码为{{ select(38) }}

continue;
break;
return 0;
return;

在以下作业中:

初赛模拟试卷及阅读完善练习

#C0001. 2023年图灵编程CSP-J初赛模拟卷1

2023年图灵编程CSP-J初赛模拟卷1

2023年图灵编程CSP-J初赛模拟卷1

一、单项选择题(共15题，每题2分，共计30分）

二、阅读程序(判断题每题2分，选择题每题3分，共28分)

判断题

选择题

判断题:

选择题:

三、完善程序（28题2分，其余四分，共42分）

水洼的大小

题目描述

输入描述

输出描述

梦中岛之路

题目描述

输入描述

输出描述

相关

状态

开发

支持

#C0001. 2023年图灵编程CSP-J初赛模拟卷1

2023年图灵编程CSP-J初赛模拟卷1

2023年图灵编程CSP-J初赛模拟卷1

一、单项选择题(共15题，每题2分，共计30分）

二、阅读程序(判断题每题2分，选择题每题3分，共28分)

判断题

选择题

判断题:

选择题:

三、完善程序（28题2分，其余四分，共42分）

水洼的大小

题目描述

输入描述

输出描述

梦中岛之路

题目描述

输入描述

输出描述

相关

状态

开发

支持

还没有账户？

登录