#P2100. CSP 2019 提高级第一轮
CSP 2019 提高级第一轮
单项选择
第 1 题
若有定义:int a=7; float x=2.5, y=4.7
,则表达式 x+a%3(int) (x+y)%2
的值是:()
{{ select(1) }}
- 0.000000
- 2.750000
- 2.500000
- 3.500000
第 2 题 下列属于图像文件格式的有() {{ select(2) }}
- WMV
- MPEG
- JPEG
- AVI
第 3 题 二进制数 11 1011 1001 011111 1011 1001 0111 和 01 0110 1110 101101 0110 1110 1011 进行按位或运算的结果是()。
编者注:原题为“逻辑或”,但是根据题意应当是按位或。 {{ select(3) }}
- 11 1111 1101 1111
- 11 1111 1111 1101
- 10 1111 1111 1111
- 11 1111 1111 1111
第 4 题 编译器的功能是() {{ select(4) }}
- 将源程序重新组合
- 将一种语言(通常是高级语言)翻译成另一种语言(通常是低级语言)
- 将低级语言翻译成高级语言
- 将一种编程语言翻译成自然语言
第 5 题 设变量 x 为 float 型且已赋值,则以下语句中能将 x 中的数值保留到小数点后两位,并将第三位四舍五入的是() {{ select(5) }}
x= (x100+0. 5)/100.0;
x=(int) (x100+0. 5)/100.0;
x=(x/100+0. 5)100.0;
x=x100+0. 5/100. 0;
第 6 题 由数字 11,1,2,4,8,8 所组成的不同的 4 位数的个数是()。 {{ select(6) }}
- 104
- 102
- 98
- 100
第 7 题 排序的算法很多,若按排序的稳定性和不稳定性分类,则()是不稳定排序。 {{ select(7) }}
- 冒泡排序
- 直接插入排序
- 快速排序
- 归并排序
第 8 题 G 是一个非连通无向图(没有重边和自环),共有 28 条边,则该图至少有 ()个顶点。 {{ select(8) }}
- 10
- 9
- 11
- 8
第 9 题 一些数字可以颠倒过来看,例如 0,1,8 颠倒过来还是本身,6 颠倒过来是 9,9 颠倒过来看还是 6,其他数字颠倒过来都不构成数字。类似的,一些多位数也可以颠倒过来看,比如 106 颠倒过来是 901。假设某个城市的车牌只有 5 位数字,每一位都可以取 0到 9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌,并且车牌上的 5 位数能被 3 整除?() {{ select(9) }}
- 40
- 25
- 30
- 20
第 10 题 —次期末考试,某班有 15 人数学得满分,有 12 人语文得满分,并且有 4人语、数都是满分,那么这个班至少有一门得满分的同学有多少人?()。 {{ select(10) }}
- 23
- 21
- 20
- 22 本题共 2 分
第 11 题 设 A 和 B 是两个长为 n 的有序数组,现在需要将 A 和 B 合并成一个排好序的数组,问任何以元素比较作为基本运算的归并算法,在最坏情况下至少要做多少次比较?()。 {{ select(11) }}
第 12 题 以下哪个结构可以用来存储图() {{ select(12) }}
- 栈
- 二叉树
- 队列
- 邻接矩阵
第 13 题 以下哪些算法不属于贪心算法?() {{ select(13) }}
- Dijkstra 算法
- Floyd 算法
- Prim 算法
- Kruskal 算法
第 14 题 有一个等比数列,共有奇数项,其中第一项和最后一项分别是 2 和 118098,中间一项是 486,请问以下哪个数是可能的公比?() {{ select(14) }}
- 5
- 3
- 4
- 2
第 15 题 正实数构成的数字三角形排列形式如图所示。$第一行的数为 a_{1,1};第二行的数从左到右依次为 a_{2,1},a_{2,2},第 n 行的数为a_{n,1},a_{n,2},…,a_{n,n} 从 a_{1,1} 开始,每一行的数ai,j 只有两条边可以分别通向下一行的两个数 a_{i+1,j} 和 a_{i+1,j+1}。用动态规划算法找出一条从 a_{1,1} 向下通到 a_{n,1},a_{n,2},…,a_{n,n} $中某个数的路径,使得该路径上的数之和最大。 令 C[i][j] 是从 的路径上的数的最大和,并且 C[i][0]=C[0][j]=0,则 C[i][j]= ( )。 {{ select(15) }}
- C[i−1][j−1]+C[i−1][j]}
本题共 2 分
二、阅读程序
(程序输入不超过数组或字符串定义的范围;判断题正确填√错误填X;除特殊说明外,判断题 1.5 分,选择题 4分,共计40 分)
阅读程序(一)
#include <cstdio>
using namespace std;
int n;
int a[100];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
int ans = 1;
for (int i = 1; i <= n; ++i) {
if (i > 1 && a[i] < a[i - 1])
ans = i;
while (ans < n && a[i] >= a[ans + 1])
++ans;
printf("%d\n", ans);
}
return 0;
}
16.(1 分)第 16 行输出 ans 时,ans 的值一定大于 i。() {{ select(16) }}
- 正确
- 错误
- (1 分)程序输出的 ans 小于等于 n。() {{ select(17) }}
- 正确
- 错误
- 若将第 12 行的
<
改为!=
,程序输出的结果不会改变。() {{ select(18) }}
- 正确
- 错误
- 当程序执行到第 16 行时,若 ans−i>2,则 a[i+1]≤a[i]。 () {{ select(19) }}
- 正确
- 错误
20.(3 分)若输入的 a 数组是一个严格单调递增的数列, 此程序的时间复杂度() {{ select(20) }}
- O(logn)
- O(nlogn)
- O(n)
- 最坏情况下,此程序的时间复杂度是()。 {{ select(21) }}
- O(logn)
- O(n)
- O(nlogn)
本题共 12 分
阅读程序(二)
#include <iostream>
using namespace std;
const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];
int getRoot(int v) {
if (fa[v] == v) return v;
return getRoot(fa[v]);
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
fa[i] = i;
cnt[i] = 1;
}
int ans = 0;
for (int i = 0; i < n - 1; ++i) {
int a, b, x, y;
cin >> a >> b;
x = getRoot(a);
y = getRoot(b);
ans += cnt[x] * cnt[y];
fa[x] = y;
cnt[y] += cnt[x];
}
cout << ans << endl;
return 0;
}
22.(1 分)输入的 a 和 b 值应在 [0,n−1]的范围内。() {{ select(22) }}
- 正确
- 错误
- (1 分)第 16 行改成
fa[i] = 0;
,不影响程序运行结果。()
{{ select(23) }}
- 正确
- 错误
- 若输入的 a 和 b 值均在 [0,n−1] 的范围内,则对于任意 0≤i<n 都有 0≤fa[i]<n () {{ select(24) }}
- 正确
- 错误
- 若输入的 a 和 b 值均在 [0,n−1] 的范围内,则对于任意0≤i<n 都有 1≤cnt[i]≤n () {{ select(25) }}
- 正确
- 错误
- 当 n 等于50时,若 a,b 的值都在 [0,49] 的范围内,且在第25 行时 x 总是不等于 y,那么输出为()。 {{ select(26) }}
- 1276
- 1176
- 1225
- 1250
- 此程序的时间复杂度是()。 {{ select(27) }}
- O(n)
- O(logn)
- O(n2)
- O(nlogn)
本题共 13 分
阅读程序(三)
t 是 s 的子序列的意思是:从 s 中删去若干个字符,可以得到 t;特别的,如果 =s=t,那么 t 也是 s 的子序列;空串是任何串的子序列。例如:acd 是 abcde 的子序列,acd 是 acd 的子序列,但 adc 不是 abcde 的子序列。 s[x..y] 表示s[x]⋯s[y] 共 y−x+l 个字符构成的字符串,若 x>y 则 s[x..y] 是空串。t[x..y] 同理。
#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];
int main() {
cin >> s >> t;
int slen = s.length(), tlen = t.length();
for (int i = 0, j = 0; i < slen; ++i) {
if (j < tlen && s[i] == t[j]) ++j;
pre[i] = j; // t[0..j-1] 是 s[0..i] 的子序列
}
for (int i = slen - 1 , j = tlen - 1; i >= 0; --i) {
if(j >= 0 && s[i] == t [j]) --j;
suf[i]= j; // t[j+1..tlen-1] 是 s[i..slen-1] 的子序列
}
suf[slen] = tlen -1;
int ans = 0;
for (int i = 0, j = 0, tmp = 0; i <= slen; ++i){
while(j <= slen && tmp >= suf[j] + 1) ++j;
ans = max(ans, j - i - 1);
tmp = pre[i];
}
cout << ans << endl;
return 0;
}
提示:
- t[0…pre[i]−1] 是s[0…i] 的子序列;
- t[suf[i]+1…tlen−1] 是 s[i…slen−1] 的子序列。
28.(1分)程序输出时,suf
数组满足:对任意 0≤i<slen,suf[i]≤suf[i+1]。 ()
{{ select(28) }}
- 正确
- 错误
- (2分)当 t 是 s 的子序列时,输出一定不为 0。() {{ select(29) }}
- 正确
- 错误
- (2分)程序运行到第 23 行时,j−i−1 一定不小于 0。() {{ select(30) }}
- 正确
- 错误
- (2分)当 t 是 s 的子序列时,
pre
数组和suf
数组满足:对任意 0≤i<slen,pre[i]>suf[i+1]+1。 () {{ select(31) }}
- 正确
- 错误
- 若
tlen=10
,输出为 0,则 slen 最小为()。 {{ select(32) }}
- 10
- 12
- 0
- 1
- 若
tlen=10
,输出为 2,则 slen 最小为()。 {{ select(33) }}
- 0
- 10
- 12
- 1
本题共 15 分
三、完善程序
(单选题,每小题 3 分,共计 30 分)
完善程序(一)
1.(匠人的自我修养) 一个匠人决定要学习 n 个新技术。要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个新技术。 输入第一行有两个数,分别为新技术个数,以及己有经验值。 接下来 n 行。第 i 行的两个正整数,分别表示学习第 i 个技术所需的最低经验值,以及学会第i个技术后可获得的经验值 接下来 n 行。第 i 行的第一个数 mi(0≤mi<n),表示第 i 个技术的相关技术数量。紧跟着 m 个两两不同的数,表示第 i 个技术的相关技术编号。 输出最多能学会的新技术个数。 下面的程序以 的时间复杂度完成这个问题,试补全程序。
#include<cstdio>
using namespace std;
const int maxc++n = 1001;
int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn], bonus[maxn];
int points;
bool find(){
int target = -1;
for (int i = 1; i <= n; ++i)
if(① && ②){
target = i;
break;
}
if(target == -1)
return false;
unlock[target] = -1;
③
for (int i = 0; i < cnt[target]; ++i)
④
return true;
}
int main(){
scanf("%d%d", &n, &points);
for (int i = 1; i <= n; ++i){
cnt[i] = 0;
scanf("%d%d", &threshold[i], &bonus[i]);
}
for (int i = 1; i <= n; ++i){
int m;
scanf("%d", &m);
⑤
for (int j = 0; j < m; ++j){
int fa;
scanf("%d", &fa);
child[fa][cnt[fa]] = i;
++cnt[fa];
}
}
int ans = 0;
while(find())
++ans;
printf("%d\n", ans);
return 0;
}
34、①处应填() {{ select(34) }}
unlock[i] <= 0
unlock[i] >= 0
unlock[i] == 0
unlock[i] == -1
- ②处应填()
{{ select(35) }}
threshold[i] > points
threshold[i] >= points
points > threshold[i]
points >= threshold[i]
- ③处应填()
{{ select(36) }}
target = -1
--cnt[target]
bonus[target] = 0
points += bonus[target]
- ④处应填()
{{ select(37) }}
cnt[child[target][i]] -= 1
cnt[child[target][i]] = 0
unlock[child[target][i]] -= 1
unlock[child[target][i]] = 0
- ⑤处应填()
{{ select(38) }}
unlock[i] = cnt[i]
unlock[i] = m
unlock[i] = 0
unlock[i] = -1
本题共 15 分
完善程序(二)
取石子
Alice 和 Bob 两个人在玩取石子游戏。他们制定了 n 条取石子的规则,第 i 条规则为:如果剩余石子的个数大于等于 a[i] 且大于等于 b[i],那么他们可以取走 b[i] 个石子。他们轮流取石子。如果轮到某个人取石子,而他无法按照任何规则取走石子,那么他就输了。一开始石子有 m 个。请问先取石子的人是否有必胜的方法?
输入第一行有两个正整数,分别为规则个数 n(1<n<64), 以及石子个数m。
接下来 n 行。第 i 行有两个正整数 a[i] 和 b[i]。(1≤a[i]≤,1≤b[i]≤64)。
如果先取石子的人必胜,那么输出 Win,否则输出 Loss。
提示:
可以使用动态规划解决这个问题。由于 b[i] 不超过 64 ,所以可以使用 64 位无符号整数去压缩必要的状态。
status 是胜负状态的二进制压缩,trans 是状态转移的二进制压缩。
试补全程序。
代码说明:
~
表示二进制补码运算符,它将每个二进制位的 0 变为 1、1 变为 0;
而 ^
表示二进制异或运算符,它将两个参与运算的数中的每个对应的二进制位一一进行比较,若两个二进制位相同,则运算结果的对应二进制位为 0 ,反之为 1。
ull 标识符表示它前面的数字是 unsigned long long 类型。
#include <cstdio>
#include<algorithm>
using namespace std;
const int maxn = 64;
int n, m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win;
int main(){
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i)
scanf("%d%d", &a[i], &b[i]);
for(int i = 0; i < n; ++i)
for(int j = i + 1; j < n; ++j)
if (a[i] > a[j]){
swap(a[i], a[j]);
swap(b[i], b[j]);
}
status = ①;
trans = 0;
for(int i = 1, j = 0; i <= m; ++i){
while (j < n && ②){
③;
++j;
}
win = ④;
⑤;
}
puts(win ? "Win" : "Loss");
return 0;
}
39、①处应填( ) {{ select(39) }}
0
~0ull
~0ull^1
1
- ②处应填( )
{{ select(40) }}
a[j] < i
a[j] == i
a[j] !=i
a[j]>1
- ③处应填( )
{{ select(41) }}
trans |=1ull << (b[j] - 1)
status |=1ull << (b[j] - 1)
status +=1ull << (b[j] - 1)
trans +=1ull << (b[j] - 1)
- ④处应填( )
{{ select(42) }}
~status| trans
status & trans
status | trans
~status & trans
- ⑤处应填( )
{{ select(43) }}
-
trans =status | trans ^ win
-
status = trans >> 1 ^ win
-
trans =status ^ trans | win
-
status = status << 1 ^ win
本题共 15 分