CSP 2019 提高组第一轮

第 1 题
若有定义：int a=7; float x=2. 5, y=4. 7:则表达式 x+a%3*（int）（x+y）%2 的值是：（）
A.0.000000
B.2.750000
C.2.500000
D.3.500000
正确答案： D
本题共 2 分

第 2 题
下列属于图像文件格式的有（）
A.WMV
B.MPEG
C.JPEG
D.AVI
正确答案： C
本题共 2 分

第 3 题
二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑或运算的结果是（）。
A.11 1111 1101 1111
B.11 1111 1111 1101
C.10 1111 1111 1111
D.11 1111 1111 1111
正确答案： D
本题共 2 分

第 4 题
编译器的功能是（）
A.将源程序重新组合
B.将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言）
C.将低级语言翻译成高级语言
D.将一种编程语言翻译成自然语言
正确答案： B
本题共 2 分

第 5 题
设变量x为float型且已赋值，则以下语句中能将x中的数值保留到小数点后两位，并将第三位四舍五入的是（）
A.x= (x*100+0. 5)/100. 0;
B.x=(int) (x*100+0. 5)/100. 0;
C.x=(x/100+0. 5）*100. 0;
D.x=x*100+0. 5/100. 0;
正确答案： B
本题共 2 分

第 6 题
由数字1, 1, 2, 4, 8, 8所组成的不同的4位数的个数是（）。
A.104
B.102
C.98
D.100
正确答案： B
本题共 2 分

第 7 题
排序的算法很多，若按排序的稳定性和不稳定性分类，则（）是不稳定排序。
A.冒泡排序
B.直接插入排序
C.快速排序
D.归并排序
正确答案： C
本题共 2 分

第 8 题
G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有（）个顶点。
A.10
B.9
C.11
D.8
正确答案： B
本题共 2 分

第 9 题
一些数字可以颠倒过来看，例如0、1、8颠倒过来还是本身，6颠倒过来是 9,9颠倒过来看还是6,其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901 。假设某个城市的车牌只有5位数字，每一位都可以取0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的5位数能被3整除？（）
A.40
B.25
C.30
D.20
正确答案： B
本题共 2 分

第 10 题
—次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（）。
A.23
B.21
C.20
D.22
正确答案： A
本题共 2 分

第 11 题
设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（）。
A.n^2
B.n logn
C.2n
D.2n – 1
正确答案： D
本题共 2 分

第 12 题
以下哪个结构可以用来存储图（）
A.栈
B.二叉树
C.队列
D.邻接矩阵
正确答案： D
本题共 2 分

第 13 题
以下哪些算法不属于贪心算法？（）
A.Dijkstra 算法
B.Floyd 算法
C.Prim算法
D.Kruskal 算法
正确答案： B
本题共 2 分

第 14 题
有一个等比数列，共有奇数项，其中第一项和最后一项分别是2和118098, 中间一项是486,请问以下哪个数是可能的公比？（）
A.5
B.3
C.4
D.2
正确答案： B
本题共 2 分

第 15 题
正实数构成的数字三角形排列形式如图所示。第一行的数为 a_{1,1}a1,1?；第二行的数从左到右依次为 a_{2,1}a2,1?，a_{2,2}a2,2?,第n行的数为a_{n,1}an,1?,a_{n,2}an,2?,……, a_{n,n}an,n? 从 a_{1,1}a1,1?开始，每一行的数a_{i,j}ai,j?只有两条边可以分别通向下一行的两个数 a_{i+1,j}ai+1,j?和a_{i+1,j+1}ai+1,j+1?。用动态规划算法找出一条从 a_{1,1}a1,1? 向下通到a_{n,1}an,1?，a_{n,2}an,2?,……, a_{n,n}an,n? 中某个数的路径，使得该路径上的数之和最大。

令c[i] [j]是从a_{1,1}a1,1?到a_{i,j}ai,j?的路径上的数的最大和，并且C[i][0]=C[0] [j]=0,则 C[i][j] = ( )。
A.max{C[i-1][j-1],C[i-1][j]}+a_{i,j}ai,j?
B.C[i-1][j-1]+C[i-1][j]
C.max{C[i-1][j-1],C[i-1][j]}+1
D.max{C[i][j-1],C[i-1][j]}+a_{i,j}ai,j?
正确答案： A
本题共 2 分

第 16 题
二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填错误填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;

}

?判断题
1）（1分）第16行输出ans时，ans的值一定大于i。（）
2）（1分）程序输出的ans小于等于n。（）
3）若将第12行的 < 改为 !=，程序输出的结果不会改变。（）
4）当程序执行到第16行时，若ans – i> 2,则a[i + 1] ≤ a[i]。（）

?选择题
5）(3分)若输入的a数组是一个严格单调递增的数列, 此程序的时间复杂度（）
6）最坏情况下，此程序的时间复杂度是()。
1.? A.正确? B.错误?? 正确答案： B
2.? A.正确? B.错误? 正确答案：A
3.? A.正确? B.错误? 正确答案： A
4.? A.正确? B.错误? 正确答案： A
5.? A.O(logn)? B.O(n^2)? C.O(nlogn)? D.O(n)??? 正确答案：D
6.? A.O(n^2)? B.O(logn)? C.O(n)? D.O(nlogn)??? 正确答案： A
本题共 12 分

第 17 题

#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;

}

?判断题

(1分)输入的a和b值应在[0, n-1]的范围内。()
(1分)第16行改成“ fa[i] = 0；”，不影响程序运行结果。()
若输入的a和b值均在[0, n-1]的范围内，则对于任意0<=i<n 都有0 <= fa[i] <n ()
若输入的a和b值均在[0, n-1]的范围内，则对于任意0<=i<n都有1 <=cnt[i]<=n ()

?选择题
5) 当n等于50时，若a、b的值都在[0,49]的范围内，且在第25行时x 总是不等于y,那么输出为()。
6) 此程序的时间复杂度是()。
1.? A.正确? B.错误? 正确答案： A
2.? A.正确? B.错误? 正确答案： B
3.? A.正确? B.错误? 正确答案： A
4.? A.正确? B.错误? 正确答案： B
5.? A.1276? B.1176? C.1225? D.1250? 正确答案： C
6.? A.O(n)? B.O(logn)? C.O(n2)? D.O(nlogn)? 正确答案： C
本题共 13 分

第 18 题
tt 是 ss 的子序列的意思是：从 ss 中删去若干个字符，可以得到 tt；特别的，如果 s=t,s=t, 那么 tt 也是 ss 的子序列；空串是任何串的子序列。例如：”acd”是“ abcde ”的子序列，“ acd” 是“ acd ”的子序列，但 “adc ”不是“ abcde ”的子序列。
s[x..y]s[x..y] 表示 s[x] cdots s[y]s[x]?s[y] 共 y-x+ly?x+l 个字符构成的字符串，若 x>yx>y 则 s[x..y]s[x..y] 是空串。t[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]的子序列。

?判断题
1）（1分）程序输出时，suf数组满足：对任意0 <= i < slen, suf[i] <= suf[i + 1]。（）
2）（2分）当t是s的子序列时，输出一定不为0。（）
3）（2分）程序运行到第23行时，“j – i – 1” 一定不小于0。（）
4）（2分）当t是s的子序列时，pre数组和suf数组满足：对任意0 <= i < slen, pre[i] > suf[i + 1] + 1。（）

?选择题
5）若tlen=10,输出为0,则slen最小为（）。
6）若tlen=10,输出为2,则slen最小为（）。
1.? A.正确? B.错误? 正确答案： A
2.? A.正确? B.错误? 正确答案： B
3.? A.正确? B.错误? 正确答案： B
4.? A.正确? B.错误? 正确答案： B
5.? A.10? B.12? C.0? D.1? 正确答案： D
6.? A.0? B.10? C.12? D.1? 正确答案： C
本题共 15 分

第 19 题
三、完善程序（单选题，每小题3分，共计30分）

（匠人的自我修养）

一个匠人决定要学习nn个新技术。要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数n (l<=n<=10^3)n(l<=n<=103),以及己有经验值（le10^7≤107）。
接下来n行。第i行的两个正整数，分别表示学习第i个技术所需的最低经验值（le10^7≤107）,以及学会第i个技术后可获得的经验值（<=10^7<=107)
接下来 nn行。第i行的第一个数m_imi?（0le m_i<n0≤mi?<n），表示第ii个技术的相关技术数量。紧跟着 mm 个两两不同的数，表示第ii个技术的相关技术编号。
输出最多能学会的新技术个数。
下面的程序以 O(n^2)O(n2) 的时间复杂度完成这个问题，试补全程序。

#include<cstdio>

using namespace std;

const int maxn = 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;

}

①处应填（）
②处应填（）
③处应填（）
④处应填（）
⑤处应填（）

1.? A.unlock[i] <= 0? B.unlock[i] >= 0? C.unlock[i] == 0? D.unlock[i] == –1? 正确答案： C
2.? A.threshold[i] > points? B.threshold[i] >= points? C.points > threshold[i]? D.points >= threshold[i]? 正确答案： D
3.? A.target = –1? B.–cnt[target]? C.bonus[target] = 0? D.points += bonus[target]? 正确答案： D
4.? A.cnt[child[target][i]] –= 1? B.cnt[child[target][i]] = 0? C.unlock[child[target][i]] –= 1? D.unlock[child[target][i]] = 0? 正确答案： C
5.? A.unlock[i] = cnt[i]? B.unlock[i] = m? C.unlock[i] = 0? D.unlock[i] = –1? 正确答案： B
本题共 15 分

相关文章: