试卷查看

第 1 题关于CPU下面哪些说法是正确的? ()

第 2 题在字长为16位的系统环境下，一个16位带附号整数的进制补码为1111111111101101其对应的十进制整数应该是( )

第 3 题在计算机内部，用来传送、存储、加工处理的数据或指令(命令)都是以( )形式进行的。

第 4 题排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法不是稳定的? ( )

第 5 题一棵6节点二叉树的中序遍历为DBAGECF，先序遍历为ABDCEGF，后序遍历为( )

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

第 7 题若3个顶点的无权图G的邻接矩阵用数组存储为{{0,1,1),{1,0,1),{0,1,0)}，假定在具体存储中顶点依次为:V1,V2,V3。关于该图，下面的说法哪个是错误的? ( )

第 8 题 2019年10月14 日是星期一，1978年10月14日是( )

第 9 题表达式a*(b+c) d的后缀表达式是( )。

第 10 题某算法计算时间表示为递推关系式:T(N)=N+T(N/2)，该算法时间复杂度为()。

第 11 题如果根结点的深度记为1，则一棵恰有201个叶子结点的二又树的深度不可能是( )。

第 12 题对于序列“7,5,1,9,3,6,8,4",在不改变顺序的情况下，去掉( )会使逆序对的个数减少3。

第 13 题某班有50名学生，每位学生发一张调查卡，上写a、b、c三本书的书名，将读过的书打V，结果统计数字如下:只读a者8人;只读b者4人;只读c者3人;全部读过的有2人;读过a，b两本书的有4人;读过a、c两本书的有2人;读过b,c两本书的有3人，则读过a的人数是( )。

第 14 题一家3三口人，恰有两个人生日在同一天的概率是() . (假设每年都是365天)

第 15 题字符申"abeab"本质不同的子串(不包含空串)个数( )

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

第 16 题

#include <bits/stdc++.h>
using namespace std;
int main() {
	int a[4], b[4];
	int i, j, tmp;
	for(i=0; i<4; i++)
		scanf("%d", &b[i]);
	for(i=0; i<4; i++) {
		a[i]= 0;
		for(j=0; j<=i; j++) {
			a[i] += b[i];
			b[a[i]%4] += a[j];
		}
	}
	tmp= 1;
	for(i=0; i<4; i++) {
		a[i]%= 10;
		b[i]%= 10;
		tmp *= a[i]+b[i];
	}
	printf("%d\n",tmp);
	return 0;
}

判断题

第 16 题若输入的b数组都是奇数，程序运行到第15行时，b[2]没有发生变化。( )

第 17 题若将第11行和第12行交换，程序的结果可能发生变化。( )

第 18 题当程序运行到第15行时，此时a数组的值等于b数组的值。( )

第 19 题若输入b数组都是偶数，当程序运行到第15行时，a数组中的值也全部为偶数。( )

第 20 题该程序能输出的最大结果为( )。

第 21 题若输入2 3 5 7,输出的结果为( )。

第 23 题

#include <ctype.h>
#include <stdio.h>
void expand(char s1[], char s2[])
{
	int i,j,a,b,c;
	j=0;
	for(i=0; (c=s1[1])!='\0'; i++)
		if (c=='-')
		{
			a=s1[i-1];b=s1[i+1];
			if (isalpha(a) && isalpha(b)||isdigit(a) && isdigit(b))
			{
				j--;
				do
					s2[j++]= a++;
				while (tolower(a) <tolower(s1[i+1]));
			}
			else s2[j++]=c;
		}	else s2[j++]=c;
	s2[j] = '\0';
}
main()
{
	char s1[100],s2[300];
	printf("inputs1:");
	gets(s1);
	expand(s1, s2);
	printf("%s\n",s2 );
}
函数isalpha(a)用于判断字符a是否为字母,isigit(b)用于判断字符b是否为数字，如果是，返回1,否则返回0。
函数tlower(a)的功能是当字符a是大写字母，返回其小写字母,其余情况不变
规定:输入的字符串只包含大小写字母，数字和“-”，且保证“-”不会出现在首位和末位。

判断题

第 23 题若输入的字符串不包含“-”号，则输出的字符串和输入相同。( )

第 24 题若输入的字符串包含“-”号，输出的字符串长度可能与输入的相同。( )

第 25 题若存在一个字符，只存在于s2字符串中而不存在于sl字符串中，则s1字符串中一定存在“-”号。( )

第 26 题若存在一个字符，只存在于s2字符串中而不存在于sl字符串中，则该字符一定不可能是大写字母。( )

第 27 题若输入6个字符，最多输出( )个字符。

第 28 题若输出500个字符，至少输入( )个字符。

第 30 题

#include<iostream>
#include<cstring>
#include<cstdio>
#define N 500+10
using namespace std;
int a[N],n;
int main()
{
	cin>> n;
	for(int i=1; i<=n; ++i) cin>>a[i];
	for(int i=1; i<=n; ++i)
	{
		int tmp= i;
		for(int j=i+1; j<=n; ++j)
			if(a[j]<a[tmp]) tmp=j;
		swap(a[i],a[tmp]);
	}
	for(int i=1; i<=n; ++i) cout<<a[i]<<' ';
	cout<< endl;
	return 0;
}

判断题

第 30 题上述代码实现了对一个长度为n的序列进行排序。( )

第 31 题去掉头文件“#include”后程序仍然正常编译运行。( )

第 32 题去掉“using namespce std;”后程序仍然正常编译运行。( )

第 33 题我们将上述算法称为( )

第 34 题上述代码的时间复杂度为( )

第 35 题若输入数据为:5 3 2 1 5 4 则if(a[j]

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

第 37 题 (最大连续子段和)给出一个数列(元素个数不多于100)，数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为4,-5,3,2,4时，输出9和3:数列为1,2,3,-5,0,7,8时，输出16和7。

#include <iostream>
using namespace std;
int a[101];
int n, i, ans, len, tmp, beg, end;
int main() {
	cin>>>n;
	for(i=1; i<=n; i++)
		cin>>a[i];
	tmp= 0;
	ans=0;
	len = 0;
	beg=___(1)___;
	for (i=1; i<=n; i++) {
		if(tmp + a[i]> ans) {
			ans= tmp + a[i];
			len=i-beg;
		} else if(___(2)___)&& i-beg>len) {
			len=i-beg;
		}
		if (tmp+a[i]___(3)___) {
			beg=___(4)___;
			tmp= 0;
		} else
			___(5)___;
		}
	cout<< ans<<" "<< len << endl;
	return 0;
}

第 37 题 ①处应填( )

第 38 题 ②处应填( )

第 39 题 ③处应填( )

第 40 题 ④处应填( )

第 41 题 ⑤处应填( )

第 43 题 (棋盘覆盖问题)在一个$2^k \times 2^k $个方格组成的棋盘中恰有一个方格与其他方格不同(如图中标记为-1的方格)，称之为特殊方格。现用L形(占3个小方格)纸片覆盖棋盘上除特殊方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是$(4^k-1)/3$。在下面给出的覆盖方案例子中，k=2，相同的3个数字构成一个纸片。下面给出的程序使用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下角、右下角，递归进行。请将程序补充完整。例:

-1为特殊方格的位置,其他数字表示L形方格放置的顺序

#include<bits/stdc++.h>
using namespace std ;
int board[65][65],tile;//tile 为纸片编号
void chessboard(int tr, int tc,int dr,int dc,int size)
{	/* dr,dc依次为特殊方格的行、列号 */
	int t, s;
	if(size==1)
		return ;
	tile++;
	s= size/2;
	if(___(1)___)
		chessboard(tr,tc,dr,dc,s);
	else{
		bourd[tr+s-1][tc+s-1]=t;
		___(2)___;
	}
	if(dr<tr+s&&dc<tc+s)
		chessboard(tr,tc+s,dr,dc,s);
	else{
		bourd[tr+s-1][tc+s]=t;
		___(3)___;
	}
	if(dr>=tr+s&&dc<tc+s)
		chessboard(tr + s, te, dr, dc,s);
	else{
		board[tr+s][te+s-1]= t;
		___(4)___;
	}
	if(dr>= tr+ s&& dc>= tc+s)
		chessboard( tr + s, tc + s, dr, dc, s );
	else{		board[tr+ s][tc+s]= t;
		___(5)___;	}
}

void prtl(int b[][65],int n)
{
	int i, j;
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=n; j++)
			cout<< setw(3)<< b[i][j];
		cout << endl;
	}
}

int main(){
	int size, dr, dc;
	cout << "input  size(4/8/16/64):"<<endl;
	cin>> size;	
	cout<< "input the position of special block(x,y):"<< endl;
	cin>> dr>> dc;
	board[dr][dc]=-1;
	tile++;
	chesbord(1,1,dr,dc, size);
	prl(board, size);
}

第 43 题 ①处应填( )

第 44 题 ②处应填( )

第 45 题 ③处应填( )

第 46 题 ④处应填( )

第 47 题 ⑤处应填( )

2021入门组 CSP-J 初赛模拟试题 (9)