不是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,输出结果不会改变。( )
2) 对于输入的正整数程序输出的值小于等于n。()
3) 如果输入的n是负数的话,该程序会出现死循环,所以该程序不能求解n是负数的情况。( )
4) 如果多次运行该程序,并且输入的n是单调递增的正整数,那么每次输出的结果也是一个严格单调递增的数列。( )

选择题

5) 若两次输入n的值相差1,但输出的结果却是一个正数,一个负数,那么两次输入的n可能是下面四组中的( )。
6) 此程序的时间复杂度是( )。

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]的范围内。( )
2) 如果输入的字符数组所有字符都是从大到小的,那么会输出"No result!"。( )
3) 第25行输出的值为输入字符串里的ASCII最小的那个字符。()
4) 第26行到第28行是把chr[]数组中存在的对应字符按照从小到大输出,即把剩下未输出的字符按照从小到大输出。()


选择题

5) 如果输入的是abcdzdcba,则第16行输出的是( )
6) 如果程序的输出结果是"fhhggh",则输入有可能是()

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]处。( )
2) (2分) check函数是用来检测蛇是否吃到果实的。( )
3) (2分)第54行及第58行输入1 x y表示在第x秒按下了y键,y为LURD中的一种,分别表示按下了左、上,右、下四种按钮。( )
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秒过后)的位置。( )


选择题

5) 若输入地图边长为x,共n次操作(x>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) ①处应填( )
2) ②处应填( )
3) ③处应填( )
4) ④处应填( )
5) ⑤处应填( )

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) ①处应填( )
2) ②处应填( )
3) ③处应填( )
4) ④处应填( )
5) ⑤处应填( )