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

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

1. 假设有以下定义:int a[5]={1,2,3,4,5},i=3,*p=a,*q=a; 则不能正确执行的语句是( )。

  • A.i= *p + *q;
  • B.a=i;
  • C.*p=*(a+i);
  • D.i= *p**(q+2);

2. 下列不属于CPU的有( )。

  • A.海思麒麟990
  • B.Intel 酷睿i7
  • C.影驰 RTX2070
  • D.AMD Ryzen 7

3. (2019)10+(2020)8的结果是( )。

  • A.(3049)10
  • B.(BF3)16
  • C.(101111110001)2
  • D.(5765)8

4. 某二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树具有的特征是( )。

  • A.高度等于其结点数
  • B.任一结点无左孩子
  • C.任一结点无右孩子
  • D.空或只有一个结点

5. 若有定义char x[] ="12345";char y[]={'1','2','3','4','5'};则( )。

  • A.x数组与y数组的所占内存空间相同
  • B.x数组比y数组占的内存空间大
  • C.x数组比y数组所占内存空间小
  • D.x数组等价于y数组

6. 公共汽车起点站于每小时的10分,30分,55分发车,该顾客不知发车时间,在每小时内的任一时刻随机到达车站,如果乘客到车站的时刻为发车时间,乘客不能坐上此时发车的公共汽车,则乘客候车时间的数学期望(准确到秒)是( )。

  • A.8分40秒
  • B.15分20秒
  • C.22分30秒
  • D.10分25秒

7. 设要将序列中的关键码按字母的升序重新排列,则( )是以第一个元素为分界元素的快速排序一趟扫描的结果。

  • A.F,H,C,D,P,A,M,Q,R,S,Y,X
  • B.P,A,C,S,Q,D,F,X,R,H,M,Y
  • C.A,D,C,R,F,Q,M,S,Y,P,H,X
  • D.H,C,Q,P,A,M,S,R,D,F,X,Y

8. 设G是有n个结点、m条边(n<=m)的连通图,必须删去G的( )条边,才能使得G变成一棵树。

  • A.m-n+1
  • B.m-n
  • C.m+n+1
  • D.n-m+1

9. 将2个红球,1个蓝球,1个白球放到10个编号不同的盒子中去,每个盒子最多放一个球,有多少种放法( )。

  • A.5040
  • B.2520
  • C.1260
  • D.420

10. 一个家具公司生产桌子和椅子。现在有113个单位的木材。每张桌子要使用20个单位的木材,售价是30元;每张椅子要使用16个单位的木材,售价是20元。使用已有的木材生产点桌和椅(不一定要把木材用光),最多可以卖( )元钱。

  • A.140
  • B.150
  • C.160
  • D.170

11. 给出 4种排序:插入排序、冒泡排序、选择排序、快速排序。这4种排序的时间代码分别是( )。

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

12. 以下数据结构中,哪一个不是线性结构? ( )

  • A.广义表
  • B.二叉树
  • C.队列
  • D.栈

13. 以下是最短路算法中不能处理带有负权值的算法的是( )。

  • A.Diikstra算法
  • B.Floyd 算法
  • C.Bel1man-Ford算法
  • D.SPFA 算法

14. 栈S最多能容纳4个元素。现有6个元素按1,2,3,4,5,6的顺序进栈,问下列哪一个序列是可能的出栈序列? ( )

  • A.5, 4, 3, 2, 1, 6
  • B.3, 2, 5, 4, 1, 5
  • C.2, 3, 5, 6, 1, 4
  • D.1, 4, 6, 5, 2, 3

15. 平面上有三条平行直线,每条直线上分别有7,5,6个点,且不同直线上三个点都不在同一条直线上。 问用这些点为顶点 ,能组成( )个不同四边形。

  • A.18
  • B.210
  • C.2250
  • D.4500

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

1.

#include<cstdio>
using namespace std;
int findvall(int n)
{
	int f;
	if(n==0) return 1;
	else
	{
		f=findvall(n/2);
	}	
	return (n*f);
}
int main()
{
	int n;
	scanf("%d",&n);
	printf("%d\n" ,findvall(n));
	return 0;
}


判断题

1) 第6行输出if(n==0)改成if(n==1)时,对于输入的正整数n,输出结果不会改变。( )
A.正确
B.错误
2) 对于输入的正整数程序输出的值小于等于n。()
A.正确
B.错误
3) 如果输入的n是负数的话,该程序会出现死循环,所以该程序不能求解n是负数的情况。( )
A.正确
B.错误
4) 如果多次运行该程序,并且输入的n是单调递增的正整数,那么每次输出的结果也是一个严格单调递增的数列。( )
A.正确
B.错误

选择题

5) 若两次输入n的值相差1,但输出的结果却是一个正数,一个负数,那么两次输入的n可能是下面四组中的( )。
A.不可能
B.-6,-7
C.-15,-16
D.-23,-24
6) 此程序的时间复杂度是( )。
A.O(n^2)
B.O(log n)
C.O(n)
D.O(nlog n)

2. 输入一串由小写字母组成的字符串,根据程序判断或选择正确的答案。

#include<cstdio>
#include<cstring>
using namespace std;
int main( ) {
	char str[60];
	int len,i,j,chr[26];
	char mmin='z';
	scanf("%s",str);
	len = strlen(str);
	for (i=len-1; i>=1; i--)
		if(str[i-1]<str[i]) break;
	if(i==0) {
		printf("No result! \n");
		return 0;
	}
	for(j=0; j<i-1; j++) putchar(str[j]);
	memset(chr, 0, sizeof(chr));
	for(j=i; j<len; j++) {
		if(str[j]> str[i-1] && str[j] < mmin)
			mmin = str[j];
		chr[str[j]-'a']++;
	}
	chr[mmin-'a']--;
	chr[str[i-1]-'a']++;
	putchar(mmin);
	for(i=0; i<26; i++)
		for (j=0; j<chr[i]; j++)
			putchar(i + 'a');
	putchar('\n');
	return 0;
}

判断题

1) 输入的字符串长度应该在[1,59]的范围内。( )
A.正确
B.错误
2) 如果输入的字符数组所有字符都是从大到小的,那么会输出"No result!"。( )
A.正确
B.错误
3) 第25行输出的值为输入字符串里的ASCII最小的那个字符。()
A.正确
B.错误
4) 第26行到第28行是把chr[]数组中存在的对应字符按照从小到大输出,即把剩下未输出的字符按照从小到大输出。()
A.正确
B.错误


选择题

5) 如果输入的是abcdzdcba,则第16行输出的是( )
A.abc
B.abcd
C.abcdz
D.abcdzd
6) 如果程序的输出结果是"fhhggh",则输入有可能是()
A.fghhghg
B.fghhgg
C.fghghhg
D.fghghgh

3. 本题是一款模拟贫吃蛇程序,游戏是在一个a*a的网格上进行的。其中输入第一行一个整数a。第二行两个些数n和m。接下来是n行,每行第一个数为opt,表示操作编号。接下来的输入的变量与操作编号对应,输出:即第m秒过后的地图,蛇所在的位置输出
“o”,其余位置输出“.”以换行结尾。


#include <bits/stdc++.h>
#include <windows.h>
using namespace std;
int a,mp[101][101];
int t[100003] ;
int y[100003] ;
int cnt;
int len=2,dir=3,die=0;
const int dx[5] = {0,0,-1,0,1};
const int dy[5] = {0,-1,0,1,0};
int nx=0, ny=1;
int px=1, py=2;
int check(int x, int yy)
{
	if(x<1||x>a||yy<1||yy>a)
		return 1;
	if(cnt+1-mp[x][yy] < len)
		return 1;
	return 0;
}
void work()
{
	if(die) return;
	px += nx;
	py += ny;
	die=check(px,py);
	if(die) return;
	mp[px][py]= ++cnt;
}
void show()
{
	for(int i= 1; i<=a; ++i)
	{
		for(int j=1; j<=a; ++j)
		{
			if(mp[i][j] != 0&& mp[i][j]>= cnt-len+1)
				putchar('o');
			else
				putchar('.');
		}
		puts("");
	}
}
int main()
{
	mp[1][1]= ++cnt;
	mp[1][2]= ++cnt;
	int n,m,op,xx;
	char s[3];
	scanf("%d",&a);
	scanf("%d%d",&n, &m);
	while(n--)
	{
		scanf("%d%d",&op,&xx);
		if(op==1)
		{
			t[xx]=1;
			scanf("%s",s);
			if(s[0]=='L')
				y[xx]= 1;
			else if(s[0]=='U')
				y[xx]= 2;
			else if(s[0]=='R')
				y[xx]= 3;
			else
				y[xx]= 4;
		}
		else
		{
			t[xx]= 2;
		}			
	}
	for(int tm=1; tm<=m; ++tm)
	{
		if(t[tm]==1)
		{
			if(y[tm]%2!= dir%2)
			{
				dir = y[tm];
				nx = dx[y[tm]];
				ny = dy[y[tm]];
			}
		}
		else if(t[tm]==2)
		{
			++len;
		}
		work();
		if(die)
		{
			break;
		}
	}
	show();
	return 0;
}

判断题

1) (2分)由程序代码可知,贪吃蛇的初始长度为2,蛇头和蛇尾分别在坐标[1,2]、[1,1]处。( )
A.正确
B.错误
2) (2分) check函数是用来检测蛇是否吃到果实的。( )
A.正确
B.错误
3) (2分)第54行及第58行输入1 x y表示在第x秒按下了y键,y为LURD中的一种,分别表示按下了左、上,右、下四种按钮。( )
A.正确
B.错误
4) (2分)当输入样例如下所示时:10\n10 20\n2 1\n2 2\n2 3\n2 4\n2 5\n1 6 R\n1 7 D\n1 8 L\n1 9 U最终程序的运行结果所代表的含义可表示为贪吃蛇在第9秒过后就死亡了,因此最后贪吃蛇保持的是死亡前(第7秒过后)的位置。( )
A.正确
B.错误


选择题

5) 若输入地图边长为x,共n次操作(x>n),则该程序时间复杂度为( )
A.x^2
B.n^2
C.n^2*x
D.x^2*n

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

1. (APP点餐)小D在外玩,回来时想在APP上点KFC,然后回宿舍。他想选择一家KFC,取了食品后尽快回宿舍,忽略取餐时间。地图可看作是n*m的网格,其中有一些不可通过的障碍,小D、KFC、宿舍均可以看做是道路,可以通过,他可穿过多个KFC。小D可以选择上下左右四个方向移动,一次移动算一步。求他取到餐并回到宿舍的最小步数。

输入第一行有两个数n,m.
接下来n行,每行包含m个字符,表示地图。
“S”表示小D初始位置,
“E”表示宿舍位置
“#”表示障碍物
“.”表示道路
“K”表示KFC
下面的程序已采用宽度优先搜索的算法完成这个问题,试补全程序。

#include<bits/stdc++.h>
# define fi first
# define se second
using namespace std;
const int MAXN=1e3+10;
const int INF = 0x313f3f3f;
typedef pair<int,int> P;
char s[MAXN][MAXN];
int n,m;
int dir[2][4]= {{1,-1,0,0},{0,0,1,-1}};
int dis[2][MAXN][MAXN];

void bfs(int p,int a,int b){
	memset(dis[p],INF,sizeof(dis[p]));
	dis[p][a][b]=0;
	queue<pair <P,int> > q;
	q.push({{a,b},0});
	while(!q.empty()) {
		int x=q.front().fi.fi,
		    y=q.front().fi.se,
		    d=q.front().se;
		q.pop();
		for(int i=0; i<4; i++)	{
			int dx=x+dir[0][i],
			    dy=y+dir[1][i];
			if (dx<1||dy<1||dx>n||dy>m||s[dx][dy]=='#')
				continue;
			if(___(1)___)	{
				___(2)___;
				___(3)___;
			}
		}
	}
}

int main(void)
{
	while(scanf("%d%d",&n,&m)!=EOF)	{
		int ans=INF;
		scanf("%d%d",&n,&m);
		for (int i=1; i<=n; i++)
			scanf("%s",s[i]+1);
		for(int i=1; i<=n; i++)
			for (int j=1; j<=m; j++)
				if(s[i][j]=='S')
					bfs(0,i,j);
				else if(s[i][j]=='E')
					___(4)___;
		for(int i=1; i<=n; i++)
			for (int j=1; j<=m; j++)
				if(s[i][j]=='K')
					ans=___(5)___;
		if(ans==INF)
			ans=-1;
		printf("%d\n",ans);
	}
	return 0;
}


选择题

1) ①处应填( )
A.dis[p][dx][dy]>d
B.dis[p][dx][dy]>d+1
C.dis[p][dx][dy]
D.dis[p][dx][dy]
2) ②处应填( )
A.dis[p][dx]][dy]=d
B.dis[p][dx][dy]=d-1
C.dis[p][dx][dy]=d+1
D.dis[p][dx][dy]= 1
3) ③处应填( )
A.q.push({dx,dy},d+1})
B.q.push({dx,dy},d})
C.q.push({{dx,dy},d-1})
D.q.push({dx,dy},1})
4) ④处应填( )
A.bfs(0,j,i)
B.bfs(1,j,i)
C.bfs(0,i,j)
D.bfs(1,i,j)
5) ⑤处应填( )
A.min(ans,dis[0][i][j]+ dis[1][i][j])
B.min(ans,dis[0][j][i]+ dis[1][j][i])
C.min(ans,dis[0][i][j])
D.min(ans,dis[1][i][j])

2. (尺取法求区间个数)给n个非负整数a[1]a[2],...,a[n],求区间和小于或等于k的区间个数,即求使SUM= a[L]+a[L+1]+...+a[R-1]+a[R]<=k的区间[L,R]的个数(1≤L≤R≤n),但由于对内存和复杂度有要求,本题已经用尺取法写好部分代码,请补全程序。
输入第一行两个整数 n,k(1 ≤ n ≤ 1000000, 0 ≤ n ≤ 1000000000000000)。
第二行为n个数,表示a[1]~a[n]的值(0≤a[i]≤1000000000)。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mx=1e6+10;
int n,a[mx];
ll k,sum,ans;
int main()
{
	scanf(" %d%lld", &n, &k);
	for (int i=1; i<=n; ++i)
	{
		scanf("%d" ,&a[i]);
	}
	int r=0;
	for (int i=1; i<=n; ++i)
	{
		while (r<n)
		{
			if (___(1)___)   ___(2)___;
			else break;
		}
		___(3)___;
		if (i<=r) ___(4)___;
		else ___(5)___;
	}
	printf("%lld\n",ans);
}

选择题

1) ①处应填( )
A.sum+a[r+1]<=k
B.sum+a[r]<=k
C.sum+a[r+1]
D.sum+a[r]
2) ②处应填( )
A.sum+=a[r]
B.sum+=a[++r]
C.sum+=a[r++]
D.sum+=a[r+1]
3) ③处应填( )
A.ans+=r-i+1
B.ans+=r-i
C.ans+=r-i-1
D.ans+=n-i+1
4) ④处应填( )
A.sum+=a[r]
B.sum=a[r]
C.sum=a[i]
D.sum-=a[i]
5) ⑤处应填( )
A.r=++i
B.r=i--
C.r=i++
D.r=i