全国提高组 CSP-S 初赛模拟试题 (8)

不是VIP会员，不能显示答案，请在后台“我的信息” 在线升级 VIP 。

一、单项选择题(共15题，每题2分，共计30分；每题有且仅有一个正确选项)

1. 以下属于系统软件的是( )。

A.c++编译器
B.腾讯QQ
C.CAD
D.游戏软件

查看

2. 如果用一个字节来表示整数，最高位用作符号位，其他位表示数值。例如:0000000表示1，10000001表示-1，试问这样表示法的整数A的范围应该是( )。

A.-127≤A≤127
B.-128≤A≤128
C.-128≤A< 128
D.-128

查看

3. 一篇文章有200个中文字符，50个英文字符，20个半角空格，如果只考虑存储这些文字本身需要( )个字节。

A.270字节
B.320字节
C.470字节
D.400字节

查看

4. 下列属于网络模型的名称是( )。

A.LAN
B.TCP/IP
C.FTP
D.SMTP

查看

5. 深度优先搜索时，如果不使用递归程序，一般需要用到的数据结构是( )。

A.链表
B.队列
C.栈
D.散列表

查看

6. 学号为1到30的小朋友顺时针排成一圈，从1号小朋友开始顺时针报数，从数字1开始数下去:1,2,3,...,28,29,30,31,32...一圈又一圈，当数到数字n时，所在的小朋友的学号是( )。

A.(n-1)%30
B.1+(n-1)%30
C.(n+1)%30-1
D.(n+1)%30

查看

7. 一棵完全二叉树的结点总数为41,其叶结点数为( )。

A.18个
B.19个
C.20个
D.21个

查看

8. 给出3种排序:插入排序、冒泡排序、选择排序。这3种排序的时间代价分别是( )。

A.O(n)、O(n^2)、O(log(n))
B.O(log(n))、O(n)、O(n^)
C.O(n^2)、O(n)、O(n)
D.O(n^2)、O(n^2)、O(n^2)

查看

9. 对以下关键字序列用快速排序法进行从小到大排序，速度最慢的情况是( )。

A.{19,23,3,15,7,21,8}
B.{23,21,28,15,19,3,7}
C.{19,7,15,28,23,21,3}
D.{3,7,15,19,21,23,28}

查看

10. 算法是指( )。

A.为解决问题面编写的计算机程序
B.为解决问题而采取的方法与步骤
C.为解决问题而需要采用的计算机语言
D.为解决问题而采用的计算方法

查看

11. 以下关于图的不正确说法是( )。

A.所有顶点的度数之和等于边数的2倍
B.所有顶点的度数之和不一定等于边数的2倍
C.任意一个图一定有偶数个奇点
D.在有向图中顶点的入度之和等于出度之和

查看

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

A.堆栈
B.数组
C.队列
D.链表

查看

13. 6个人分乘两辆不同的汽车，每辆车最多坐4人，则不同的乘车方法数为( )。

A.40
B.50
C.60
D.70

查看

14. 为了实现两数交换,代码如下: void swapAB(int &a,int &b){_____;b=a-b;a=a-b;} 则空格内要填人的语句是( )。

A.a=a+b
B.a=a*b;
C.a=a-b;
D.a=a&b;

查看

15. 某数列有1000个各不相同的数，由低到高按序排列，现要对该数列进行二分法检索，在最坏的情况下，需要检索( )个数据。

A.1000
B.10
C.100
D.500

查看

二、阅读程序(程序输入不超过数组或字符串定义的范围;除特殊说明外，判断题1.5分，选择题3分，共计40分)

#include<bits/stdc++.h>

using namespace std;

int n;

int a[1005],f[1005];

int main() {

	int i, j;

	cin>> n; int ans=0;

	for (i=0; i<n; i++)cin>>a[i];

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

		f[i] = 1;

		for(j= i-1; j>=0; --j)

			if(a[i]>a[j])f[i]= max(f[i],f[j]+1);

		ans =max(ans,f[i]);

	}

	cout<< ans<<"\n";

	return 0;

}

输入保证是正整数n以及一个长度为n的数组，且相邻元素之间没有空格。如下例:

判断题

1) 若将第6行的“int i,j”改为“int i;”,则程序会出现编译错误。( )

2) 若将第12行的a[i]>a[j]改为a[i]<a[j]，运行结果不变。( )

3) f[i]表示以i结尾的最长不下降子序列长度。( )

4) 若把第9行的"i=0;"换成"i=1;"，则程序运行结果不变。( )

选择题

5) 若n= 100,则ans的最大值是( )。

6) 若n=15,a= {5,7,6,8,1,3,5,4,2,9,14,11,12,8,7}，则ans的值为( )

查看

# include <iostream>

using namespace std;

const int maxn=100005;

int n;

int a[maxn];

int b[maxn];

void solve(int l, int r)

{

	if (l==r) return ;

	int mid=(l+r)/2;

	solve(l, mid); solve(mid+1,r);

	int i=1,j=mid+1,k=1;

	while(i<=mid &&j<=r)

	{

		if (a[i]<=a[j]) b[k++]=a[i++];

		else b[k++]=a[j++]; 

	}

	while(i<=mid) b[k++]=a[i++];

	while(j<=r) b[k++]=a[j++];

	for (int i=l; i<=r; i++) a[i]=b[i]; 

}

int main(){

	cin>>n;

	for (int i=1; i<=n; i++) cin>>a[i];

	solve(1,n);

	int ans=0;

	for (int i=1; i<=n; i++) ans=ans+a[i]*i;

	cout<<ans<<endl;

	return 0;

}

判断题

1) 即使a中有重复的数字，该程序仍能正常运行并输出正确答案。( )

2) 当运行完25行后，a数组单调不增。( )

选择题

3) 当输入如下时，n 1 2 3.....n 输出答案为( )。

4) 该程序最坏情况下的时间复杂度为( )。

5) 当输入如下时，5 50 60 30 40 50,输出为( )。

6) 列各组输入获得的答案最大的是( )。

查看

#include <stdio.h>

char c[200][200];

int s[200], m, n;

void numara() {

	int i,j, cod, nr;

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

		nr=0; cod=1;

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

			if(c[i][j]=='1') {

				if(!cod) {cod=1;s[nr]++;nr=0;}

			}

			else {

				if (cod) {nr=1;cod=0;} 

				else nr++;

			}

		}

		if(!cod) s[nr]++;

	}

}

int main() {

	int i,j;

	scanf("%d %d\n", &m, &n);

	for(i= 0; i<m; i++) gets(c[i]);

	numara();

	for(i=1; i<=m; i++)

		if(s[i]!= 0) printf("%d %d",i, s[i]);

	return 0;

}

输入保证是正整数m和n以及一个m*n的01矩阵，且相邻元素之间没有空格。如
下例:
2 4
0101
1000

判断题

1) 若将第21行的“int i,j;”改为“int i;”,则程序会出现编译错误。()

2) 程序最少输出0个数,最多输出2*m个数。()

3) s[i]表示矩阵中有s[i]个列有i个0。( )

4) 若把第10行的“cod=1;”和第13行的“cod=0;”全部换成“cod^=1;”，则程序运行结果不变。( )

选择题

5) 若m=100,n=100,则s[1]的最大值是( )。

6) 若m=95,n=95,则s[5]的最大值是( )。

查看

三、完善程序(单选题，每题3分，共计30分)

1. (YY的树)题目给出m颗非空有根(根节点编号为1)区分左右儿子的二叉树。
将某一棵给出二叉树的叶子节点换成任意一棵二叉树称为一次变换，即给出的二叉树变换到新二叉树。
同一棵二叉树进行多次变换是指在每次变换后得到的新二叉树上继续进行变换。
若任意一棵大小超过1的二叉树都可以由给出的某一棵给出的二叉树通过有限次变换得到，则输出“Almost Complete”，否则输出“No”。
题目第一行首先读入一个数m，表示二叉树的棵数。
接下来进行m次这样的操作。
读入一个数n，接下来n行每行2个数li和ri分别表示这棵二叉树第i个点的左右儿子编号，若没有左儿子，则li=0，若没有右儿子，则ri=0。

#include<bits/stdc++.h>

using namespace std;

const int N=2e6+5;

int n, m, tot;

vector <int> t;

int lc[N], rc[N];

inline bool isleaf(int u) { ___(1)___;}

inline bool solve(vector <int> t) {

	if (t.empty()) return false;

	for (auto o : t) if (isleaf(o)) return true;

	vector<int> t1,t2,t3,t4;

	for (auto o : t) {

		if(!lc[o]) t2.push_back(rc[o]);

		if(!rc[o]) t1.push_back(lc[o]);

		if( ___(2)___ ) {

			if (isleaf(lc[o])) t3.push_back(rc[o]);

			if (isleaf(rc[o])) t4.push_back(lc[o]);

		}

	}

	___(3)___;

}

int main() {

	scanf("%d", &m);

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

		int n;	scanf("%d" ,&n);___(4)___;

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

			scanf("%d", &lc[tot+j]); if (lc[tot+j]) lc[tot+j] += tot;

			scanf("%d", &rc[tot+j]); if (rc[tot+j]) rc[tot+j] += tot;

		}

		___(5)___;

	}

	if (solve(t)) printf("Almost Complete\n");

	else printf("No\n");

	return 0;

}

选择题

1) ⑴处应填( )。

2) ⑵处应填( )。

3) ⑶处应填( )。

4) ⑷处应填( )。

5) ⑸处应填( )。

查看

2. 逻辑游戏
题目描述:
一个同学给了我一个逻辑游戏。他给了我图1，在这个图上，每一段边界都已经进行了编号。我的任务是在图中画一条连续的曲线，使得这条曲线穿过每一个边界一次且仅穿过一次，而且曲线的起点和终点都在这整个区域的外面。这条曲线是容许自交的。
对于图1，我的同学告诉我画出这样的一条曲线（图2）是不可能的，但是对于有的图形（比如图3），画出这样一条曲线是可行的。对于给定的一个图，我想知道是否可以画出满足要求的曲线。

输入:
输入的图形用一个n×n的矩阵表示的。矩阵的每一个单元里有一个0到255之间（包括0和255）的整数。处于同一个区域的单元里的数相同，相邻区域的数不同（但是不相邻的区域里的数可能相同）。
输入的第一行是n（0<n<100）。以下的n行每行包括n个整数，分别给出对应的单元里的整数（这n个整数之间用空格分开）。图4给出了输入样例对应的图形。
输出:
当可以画出满足题意的曲线的时候，输出“YES”；否则，输出“NO”。
输入样例:
3
1 1 2
1 2 2
1 1 2
输出样例:
YES
程序：

#include <stdio.h>

#include <math.h>

int orig, n, ns, a [102][102], bun;

int d[]= {1,0,-1,0,0,1,___(1)___};

void plimba(int x, int y) {

	int i,xx, yy;

	a[x][y]=-a[x][y] ;

	if(abs(a[x-1][y]) !=orig&&( ___(2)___  !=a[x-1][y]||abs(a[x][y-1]) !=orig))	ns++;

	if(abs(a[x+1][y]) !=orig&& (a[x+1][y-1]!=a[x+1][y]||abs(a[x][y-1]) !=orig))	ns++;

	if(abs(a[x][y-1]) !=orig&&( ___(3)___  !=a[x][y-1]||abs(a[x-1][y]) !=orig))	ns++;

	if(abs(a[x][y+1]) !=orig&&(a[x-1][y+1] !=a[x][y+1]||abs(a[x-1][y]) !=orig))	ns++;

	for(i=0; i<4 ; i++) {

		xx=x+d[2*i]; yy=y+___(4)___;

		if(xx>=1&&xx<=n&&yy>=1&&yy<=n&& ___(5)___ )plimba(xx,yy);

	}

}

int main () {

	int i,j;

	bun=1;

	scanf("%d",&n);

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

	for (j=0; j<=n+1; j++)	a[i][j]=0;

	a[0][0]=-1;	a[n+1][0]=-1;

	a[0][n+1]=-1;	a[n+1][n+1]=-1;

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

	for (j=1; j<=n; j++) scanf("%d",&a[i][j]);

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

		for(j=1; j<=n; j++) {

			if(a[i][j]>-1) {

				ns=0; ___(6)___;				

				plimba (i,j);

				if(ns%2==1) bun=0;

			}

		}

	if (bun)printf("YES\n");else printf("NO\n");

	return 0;

}

选择题