#ACSP1016. cspj-模拟题16
-
ID: 67
Type: Objective
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
jike1994
Tags> cspj-模拟题16
一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）
- ({{ select(1) }}) 提出计算机的体系结构主要包括运算器、( )、存储器、输入和输出设备。
- 图灵 控制器
- 冯诺依曼 控制器
- 图灵 CPU
- 冯诺依曼 CPU
- 下面合法的电子邮件地址是 ({{ select(2) }})。
- http://www.csp-j.com
- ftp://csp-j.com
- rb@csp-j.com
- rb@www.csp-j.com
- 一个二进制数的反码为 01011100，则其原码为 ({{ select(3) }})。
- 01011100
- 10100011
- 10100100
- 01011101
- 若 A=True, B=True, C=False, D=False，则下面表达式值为真的是 ({{ select(4) }})。
- (A||B)&&!B||C&&D
- C&&A&&(B||!C)||C&&D
- B&&!B||C||D&&!A
- D||(!B||C&&!A)||!D&&B&&!C
- 徐老师家买了一台4K超清电视，其屏幕分辨率是 4096 X 2160，每一个像素都是 32 位真彩色，一个视频文件有 2 分钟，每秒钟播放 24 帧。在没有压缩的情况下，这个视频占用空间最接近以下哪个值 ({{ select(5) }})。
- 80GB
- 25GB
- 100GB
- 200GB
- 表达式
(a+b)*c/d-e%f*g的前缀表达式为 ({{ select(6) }})。
- /+ abcd-% efg
- /+ abcd-%e fg
- -/+ abcd%e fg
- -/+ abcd% efg
- 考虑如下递归算法，问调用
solve(24,64)的返回值 ({{ select(7) }})。1 solve(n,m) 2 if m==0 return n 3 else return solve(m,n%m)
- 4
- 8
- 12
- 16
8.一个由 10 个结点的无向图至少需要 ({{ select(8) }}) 边。
- 0
- 1
- 9
- 45
9.C++表达式 15%6/2+14&5^3 的值为 ({{ select(9) }})。
- 4
- 6
- 7
- 8
10.在数据结构中，链表是 ({{ select(10) }})。
- 顺序存储的线性表结构
- 非顺序存储的线性表结构
- 非顺序存储的非线性表结构
- 顺序存储的非线性表结构
11.设电文中出现的字母为 A，B，C，D，E，每个字母在电文中出现的次数分别为70, 270, 50, 60和110, 按哈夫曼编码, 则字母C的编码不可能是 ({{ select(11) }})。
- 001
- 1001
- 1111
- 1011
12.有一个循环队列，队列空间是50，当前队首指针 head=23，指向队首元素的前一个位置，队尾指针 tail=5，指向队尾元素，那么当前队列中共有 ({{ select(12) }}) 个元素。
- 17
- 18
- 31
- 32
13.对一组 (82，47，25，12，21) 排序，数据的排到次序在排序的过程中的变化为： (1)82 47 25 12 21 (2)12 47 25 82 21 (3)12 21 25 82 47 (4)12 21 25 47 82 则采用的排序是 ({{ select(13) }}) 排序。
- 选择
- 冒泡
- 快速
- 插入
14.用数字0，1，2，3，4可以组成 ({{ select(14) }}) 个小于1000的且没有重复数字的自然数。
- 25
- 31
- 65
- 69
15.CSP-J初赛结束后，王老师带4名女生和5名男生排成一行拍照留念，要求男生必须排在一起，王老师肯定要在中间，女生也必须排在一起，那么不同的排列方式共有 ({{ select(15) }})。
- 2880
- 5760
- 8640
- 11520
二、阅读程序（程序输入不超过数组或字符串定义的范围；注意：判断题正确填T ，错误填F；除特殊说明外，判断题1.5分，选择题3分，共计40分）
第一小题
阅读下面程序，完成第16~20题。
#include <iostream>
using namespace std;
long long fun one(int n) {
if (n==1) return 1;
else if (n==2) return 2;
else return fun one(n-1) + fun one(n-2);
}
long long fun two(int n) {
long long a[2005];
a[1]=1;
a[2]=-2;
for(int i=3; i<=n; i++) {
a[i]=a[i-1]+a[i-2];
}
return a[n];
}
int main() {
int k;
cin>>k;
cout<< fun two(k)<<endl;
cout<< fun one(k)<<endl;
return 0;
}
16.输入的k必须大于0。 ({{ select(16) }})
- T
- F
17.输入的k值只要小于2000,则 20和21行会得到大于0的数。 ({{ select(17) }})
- T
- F
18.输入的k值不能太大，否则会发生运行错误。 ({{ select(18) }})
- T
- F
19.若输入k值为10,则输出的值是 ({{ select(19) }})。
- 89 88
- -47 89
- -47 88
- 88 89
20.以下说法正确的是 ({{ select(20) }})。
- 随着k值的变大, 函数 fun two(k)和 fun one(k)的输出结果几乎同时得到
- 随着k值的变大, 函数 fun two(k)的输出结果快于 fun one(k)且时间差越来越大
- 随着k值的变大, 函数 fun two(k)的输出结果慢于 fun one(k)且时间差越来越大
- 无法确定函数 fun two(k)和 fun one(k)输出结果的得到时间
第二小题
阅读下面程序，完成第21~26题。
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int prime[1000010], tot, cnt[1000010], n;
bool vis[1000010];
long long ans = 1;
void init() {
for (int i = 2; i <= n; i++) {
if (! vis[i])
prime[++ tot] = i;
for (int j = 1; j <= tot; j++) {
if (prime[j] * i > n) break;
vis[prime[j] * i] = 1;
if (i % prime[j] == 0) break;
}
}
}
int main() {
scanf("%d", &n);
init();
for (int i = 1; i <= tot; i++)
for (int j = prime[i]; j <= n; j += prime[i])
for (int k = j; k % prime[i] == 0; k /= prime[i])
cnt[i]++;
for (int i = 1; i <= tot; i++)
ans = (ans * 1LL * (cnt[i] * 2 + 1) % mod) % mod;
printf("%11d\n", ans);
return 0;
}
21.将第8行的“int i=2;”改为“int i=1;”, 程序输出不变。 ({{ select(21) }})
- T
- F
22.将第12行删除, 程序输出不变。 ({{ select(22) }})
- T
- F
23.将第14行删除, 程序输出不变。 ({{ select(23) }})
- T
- F
24.将第22行的“int j=prime[i]”改为“int j=0”, 程序会无法执行。 ({{ select(24) }})
- T
- F
25.如果输入的n为2, 输出为 ({{ select(25) }})。
- 1
- 2
- 3
- 4
26.该代码中 init() 函数的时间复杂度为 ({{ select(26) }})。
- O(logn)
- O(m)
- O(n)
- O(nlogn)
第三小题
阅读下面程序，完成第27~32题。
#include<bits/stdc++.h>
int n,cnt, d[50005], f[50005], size[50005], head[50005];
struct edge {
int to, next;
} edge[100005];
void add(int x, int y) {
edge[++cnt].to=y;
edge[cnt].next=head[x];
head[x]=cnt;
}
void dfs1(int now) { //得到当前节点的深度和子树大小
size[now]=1;
for (int i=head[now]; i; i=edge[i].next) {
int to=edge[i].to;
if(d[to]) continue;
d[to]=d[now]+1;
dfs1(to);
size[now]+=size[to];
}
}
void dfs(int now, int fa) {
f[now]=f[fa]+n-2*size[now];
for (int i=head[now]; i; i=edge[i].next) {
int to=edge[i].to;
if (to==fa) continue;
dfs(to, now);
}
}
int main() {
scanf("%d", &n);
for (int x, y, i=1; i<n; i++) {
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
d[1]=1;
dfs1(1);
int maxn=0, idx=1;
for (int i=1; i<=n; i++) maxn+=d[i];
maxn-=n;
f[1]=maxn;
for (int i=head[1]; i; i=edge[i].next) {
int to=edge[i].to;
dfs(to, 1);
}
for (int i=2; i<=n; i++)
if (f[i]<maxn) maxn=f[i], idx=i;
printf("%d %d", idx, maxn);
return 0;
}
27.将第33、34行上下交换, 程序输出不变。 ({{ select(27) }})
- T
- F
28.将第15行删除，程序可能出现递归栈溢出风险。 ({{ select(28) }})
- T
- F
29.将第25行的“continue;”改为“break;”, 程序输出不变。 ({{ select(29) }})
- T
- F
30.将第46行的“int i=2;”改为“int i=1;”,程序输出可能发生变化。 ({{ select(30) }})
- T
- F
31.如果输入数据如下所示：
4
1 2
2 3
3 4
则输出为 ({{ select(31) }})。
- 1 2
- 1 4
- 2 3
- 2 4
32.该代码的时间复杂度为 ({{ select(32) }})。
- O(n)
- O(nlogn)
- O(n^2)
- O(n)
三、完善程序（单选题，每小题3分，共计30分）
第一小题
(数字矩阵) 一个n*m(1<=n,m<=10) 的由非负整数构成的数字矩阵, 现在需要从中选出若干个数字，并且保证取出的数字不相邻(规定一个数字与他周围的八个数字相邻) ，求出取出的数字的最大的和是多少。
#include <iostream>
#include <algorithm>
using namespace std;
const int d[8][2] = {1, 0, -1, 0, 0, 1, 0, -1, 1, 1, -1, 1, 1, -1, -1, -1};
int t, n, m, s[10][10], mark[10][10], ans, mx;
void dfs(int x, int y) {
if ({{ select(33) }}) {
dfs(x+1, 1);
return;
}
if (x==n+1) {
{{ select(34) }};
return;
}
dfs(x, y+1);
if ({{ select(35) }}) {
ans+=s[x][y];
for(int fx=0;fx<8;++fx) ++mark[x+d[fx][0]][y+d[fx][1]];
{{ select(36) }};
for(int fx=0;fx<8;++fx) --mark[x+d[fx][0]][y+d[fx][1]];
{{ select(37) }};
}
}
int main() {
cin>>n>>m;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
cin>>s[i][j];
}
}
mx=0;
dfs(1, 1);
printf("%d\n", mx);
return 0;
}
33.①处应填 ({{ select(33) }})
- y!=m
- y==m+1
- y<=m
- y>=m
34.②处应填 ({{ select(34) }})
- mx+=ans
- mx=ans
- mx=min(mx,ans)
- mx=max(mx, ans)
35.③处应填 ({{ select(35) }})
- x<=n&&y<=m
- x!=n||y!=m
- mark[x][y]==0
- mark[x][y]!=0
36.④处应填 ({{ select(36) }})
- dfs(x,y)
- dfs(x+1,y)
- dfs(x,y+1)
- dfs(x+1,y+1)
37.⑤处应填 ({{ select(37) }})
- dfs(x+1,y)
- dfs(x,y+1)
- ans-=s[x][y]
- ans+=s[x][y]
第二小题
(打牌) 三名同学在学习编程的休息时间(编号 1，2，3) 打扑克，每人一开始 n 张牌，牌一共 m 种，若干张相同的牌可以一起出。一开始由第一个人出，打出自己的牌里最小的牌。接下来，以玩家 1，2，3，1，2，3... 的顺序轮流出牌，每人打出一组比上个人打出的牌大的，自己能打出的最小的牌，若没有则跳过。牌的大小是这么决定的：一组张数多的牌比张数少的牌大，如果张数同样多，那么点数大的牌比较大。例如: (1,1,1)>(3,3)>(2,2)>(4)>(1)。 若一轮中，其余两个人都无法打出牌，则重新下次由打出最后一张牌的人开始打。谁最先打完所有的牌，谁就赢了。请问最后谁会胜利呢？输出胜者的编号。对于所有数据, n, m≤50。 输入格式：第1 行输入 2 个正整数 n, m。第2 到 4 行，每行输入 n 个数，表示每个人一开始的牌。 输出格式：输入共 1 行 1 个正整数，表示胜者的编号。 注意：
last[1]：存储了上一次成功出牌的牌面（即牌的数值）。
last[2]：存储了上一次成功出牌的数量（即出了多少张相同的牌）。
last[3]：存储了上一次成功出牌的玩家编号。
输入样例：
10 3
1 3 3 1 3 3 1 2 3 3
3 2 1 2 2 3 3 1 1 2
2 2 1 2 3 1 2 3 3 1
输出样例： 3
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[5][55],x,last[5],sum[5],who=1,tmp;
signed main() {
cin>>n>>m;
sum[1]=sum[2]=sum[3]=n;
last[3]=1;
for(int i=1; i<=3; i++) {
for(int j=1; j<=n; j++) {
cin>>x;
{{ select(38) }};
}
}
for(int i=1;; i++) {
tmp=0;
who=(i-1)%3+1;
if(last[3]==who) {{ select(39) }};
for(int j=0; j<=sum[who]; j++) {
for(int k=1; k<=m; k++) {
if({{ select(40) }}) continue;
if(a[who][k]>=j+last[2]) {
sum[who]-=j+last[2], tmp=1;
{{ select(41) }};
{{ select(42) }};
if(sum[who]==0) {
cout<<who;
return 0;
}
break;
}
}
}
if(tmp) break;
}
return 0;
}
38.①处应该填 ({{ select(38) }})
- a[i][x] =1
- a[i][x]+=1
- a[x][i]=1
- a[x][i]+=1
39.②处应该填 ({{ select(39) }})
- last[1]=0, last[2]=0
- last[1]=0, last[2]=1
- last[1]=1, last[2]=0
- last[1]=1, last[2]=1
40.③处应该填 ({{ select(40) }})
- j==0||k<=last[1]
- j==1||k<last[1]
- j==0||k<last[1]
- j==1||k<=last[1]
41.④处应该填 ({{ select(41) }})
- last[1]=j, last[2]+=who, last[3]=k
- last[1]=k, last[2]=j, last[3]=who
- last[1]=k, last[2]+=j, last[3]=who
- last[1]=j, last[2]+=k, last[3]=who
42.⑤处应该填 ({{ select(42) }})
- a[who][j]-=last[2]
- a[who][k]-=last[2]
- a[who][j]+=last[2]
- a[who][k]+=last[2]