CSP-J初赛模拟卷1

ID: 473

客观题

尝试: 5

已通过: 1

难度: 10

上传者:

xiaoboup

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

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

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

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

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

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

$89.9$
$183.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>
2 using namespace std;
3 int 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)$ 的时间复杂度完成问题，试补全程序。

01	#include <bits/stdc++.h>
02	using namespace std;
03	typedef long long ll;
04	const int maxn = 1e6 + 7;
05	const int mod = 998244353;
06	
07	int n , m , vis[1010][1010] , block , num[maxn];
08	int dx[] = {0 , 0 , 1 , -1} , dy[] = {1 , -1 , 0 , 0};
09	char maze[1010][1010];
10	void dfs(int x , int y){
11	    ______1______
12		______2______
13		for(int i = 0 ; i < 4 ; i ++){
14			int nx = x + dx[i] , ny = y + dy[i];
15			if(nx >= 1 && nx <= n && ny >= 1 && ny <= m &&
16	           vis[nx][ny] == 0 && maze[nx][ny] == '.'){
17				dfs(nx , ny);
18			}
19		}
10	}
21	
22	int main(){
23		cin >> n >> m;
24		for(int i = 1 ; i <= n ; i ++){
25			for(int j = 1 ; j <= m ; j ++){
26				cin >> maze[i][j];
27			}
28		}
29		
20		for(int i = 1 ; i <= n ; i ++){
31			for(int j = 1 ; j <= m ; j ++){
32				if(maze[i][j] == '.' && _____3_____){
33					block ++ , dfs(i , j);
34				}
35			}
36		}
37		
38		for(int i = 1 ; i <= n ; i ++){
39			for(int j = 1 ; j <= m ; j ++){
30				if(maze[i][j] == '.'){
41					cout << maze[i][j];
42				}else{
43					______4_____
44					st.insert(vis[i - 1][j]);
45					st.insert(vis[i + 1][j]);
46					st.insert(vis[i][j - 1]);
47					st.insert(vis[i][j + 1]);
48					int ans = 1;
49					for(_____5_____) ans += num[t];
40					cout << ans % 10;
51				}
52			}
53			cout << endl;
54		}
55		return 0;
56	}

(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)$ 的时间复杂度完成问题，试补全程序。

01	#include <bits/stdc++.h>
02	using namespace std;
03	typedef long long ll;
04	const int maxn = 1e6 + 7;
05	const int mod = 998244353;
06	
07	int n , vis[1010][1010];
08	int dx[] = {0 , 0 , 1 , -1} , dy[] = {1 , -1 , 0 , 0};
09	char maze[1010][1010];
10	
11	struct Node{
12		int x , y , d;
13	};
14	
15	void bfs(int x , int y){
16		queue <Node> Q;
17		Q.push({x , y , 0});
18		
19		vector <Node> Arr;
10		while(!Q.empty()){
21			Node u = Q.front(); Q.pop();
22			vis[u.x][u.y] = 1;
23			Arr.push_back(u);
24			for(int i = 0 ; i < 4 ; i ++){
25				int nx = u.x + dx[i] , ny = u.y + dy[i];
26				if(maze[nx][ny] == '1' && vis[nx][ny] == 0){
27					_____1_____ 
28					_____2_____ 
29				}
20			}
31		}
32		
33		_____3_____
34		while(!Q.empty()){
35			Node u = Q.front(); Q.pop();
36			for(int i = 0 ; i < 4 ; i ++){
37				int nx = u.x + dx[i] , ny = u.y + dy[i];
38				if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && vis[nx][ny] == 0){
39	                if(_____4_____ ){
30	                    cout << u.d << endl;
41	                    return;
42	                }
43					vis[nx][ny] = 1;
44					_____5______ 
45				}
46			}
47		}
48	}
49	
40	int main(){
51		cin >> n;
52		for(int i = 1 ; i <= n ; i ++){
53			for(int j = 1 ; j <= n ; j ++){
54				cin >> maze[i][j];
55			}
56		}
57	
58		for(int i = 1 ; i <= n ; i ++){
59			for(int j = 1 ; j <= n ; j ++){
60				if(maze[i][j] == '1'){
61					bfs(i , j);
62					______6______
63				}
64			}
65		}
66		return 0;
67	}
68

(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;

在以下作业中:

CSP-X/CSP-J初赛模拟题

#CS001P33. CSP-J初赛模拟卷1

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

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

判断题

选择题

判断题:

选择题:

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

水洼的大小

题目描述

输入描述

输出描述

梦中岛之路

题目描述

输入描述

输出描述

相关

状态

开发

支持

关于

#CS001P33. CSP-J初赛模拟卷1

CSP-J初赛模拟卷1

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

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

判断题

选择题

判断题:

选择题:

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

水洼的大小

题目描述

输入描述

输出描述

梦中岛之路

题目描述

输入描述

输出描述

相关

状态

开发

支持

关于

登录