【真题】暑假备战CSP-J/S：CSP-S2019提高组初赛(第一轮)试题及参考答案(PDF版、无水印可直接打印)

小码匠

发布于 2023-08-31 15:29:14

4450

发布于 2023-08-31 15:29:14

文章被收录于专栏：小码匠和老码农

资料下载

公众号内回复: CSP-S2019 即可获取下载链接，直接打印电子版让孩子做即可，文件包含

试题真题
参考答案

注意：其他比赛年份得资料正在紧张整理中，大家耐心等，整理完毕后，会陆续在公众号内分享。

关注：小码匠和老码农，和小码匠一起携手备战2023年CSP-J/S，祝愿所有孩子们取得好成绩！！！

第 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

本题共 2 分

第 2 题

下列属于图像文件格式的有（）

A. WMV
B. MPEG
C. JPEG
D. AVI

本题共 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

本题共 2 分

第 4 题

编译器的功能是（）

A. 将源程序重新组合
B. 将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言）
C. 将低级语言翻译成高级语言
D. 将一种编程语言翻译成自然语言

本题共 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;

本题共 2 分

第 6 题

由数字1, 1, 2, 4, 8, 8所组成的不同的4位数的个数是（）。

A. 104
B. 102
C. 98
D. 100

本题共 2 分

第 7 题

排序的算法很多，若按排序的稳定性和不稳定性分类，则（）是不稳定排序。

A. 冒泡排序
B. 直接插入排序
C. 快速排序
D. 归并排序

本题共 2 分

第 8 题

G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有（）个顶点。

A. 10
B. 9
C. 11
D. 8

本题共 2 分

第 9 题

一些数字可以颠倒过来看，例如0、1、8颠倒过来还是本身，6颠倒过来是 9,9颠倒过来看还是6,其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901 。假设某个城市的车牌只有5位数字，每一位都可以取0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的5位数能被3整除？（）

A. 40
B. 25
C. 30
D. 20

本题共 2 分

第 10 题

—次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（）。

A. 23
B. 21
C. 20
D. 22

本题共 2 分

第 11 题

设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（）。

n^2

B. nlogn
C. 2n
D. 2n - 1

本题共 2 分

第 12 题

以下哪个结构可以用来存储图（）

A. 栈
B. 二叉树
C. 队列
D. 邻接矩阵

本题共 2 分

第 13 题

以下哪些算法不属于贪心算法？（）

A. Dijkstra 算法
B. Floyd 算法
C. Prim算法
D. Kruskal 算法

本题共 2 分

第 14 题

有一个等比数列，共有奇数项，其中第一项和最后一项分别是2和118098, 中间一项是486,请问以下哪个数是可能的公比？（）

A. 5
B. 3
C. 4
D. 2

本题共 2 分

第 15 题

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

img

令c[i] [j]是从a1,1到ai,j的路径上的数的最大和，并且C[i][0]=C[0] [j]=0,则 C[i][j] = ( )。

A. max{C[i-1][j-1],C[i-1][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]}+ai,j

本题共 2 分

第 16 题

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

#include <cstdio>
usingnamespacestd;
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);
    }
    return0;
}

判断题1）（1分）第16行输出ans时，ans的值一定大于i。（）

A. 正确
B. 错误

2）（1分）程序输出的ans小于等于n。（）

A. 正确
B. 错误

3）若将第12行的 < 改为 !=，程序输出的结果不会改变。（）

A. 正确

B. 错误

4）当程序执行到第16行时，若ans - i> 2,则a[i + 1] ≤ a[i]。（）

A. 正确
B. 错误

选择题

5）(3分)若输入的a数组是一个严格单调递增的数列, 此程序的时间复杂度（）

O(logn)

O(n^2)

O(nlogn)

O(n)

6）最坏情况下，此程序的时间复杂度是()。

O(n^2)

O(logn)

O(n)

O(nlogn)

本题共 12 分

第 17 题

#include <iostream>
usingnamespacestd;

constint 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;
    return0;
}

判断题

(1分)输入的a和b值应在[0, n-1]的范围内。()

A. 正确
B. 错误

(1分)第16行改成fa[i] = 0;，不影响程序运行结果。()

A. 正确
B. 错误

若输入的a和b值均在[0, n-1]的范围内，则对于任意0<=i<n 都有0 <= fa[i] <n ()

A. 正确
B. 错误

若输入的a和b值均在[0, n-1]的范围内，则对于任意0<=i<n都有1 <=cnt[i]<=n ()

A. 正确
B. 错误

选择题

当n等于50时，若a、b的值都在[0,49]的范围内，且在第25行时x 总是不等于y,那么输出为()。

A. 1276
B. 1176
C. 1225
D. 1250

此程序的时间复杂度是()。

A. O(n)
B. O(logn)
C.

O(n^2)

D. O(nlogn)

本题共 13 分

第 18 题

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>
usingnamespacestd;
constint 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;
    return0;
}

提示： 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]。（）

A. 正确
B. 错误

2）（2分）当t是s的子序列时，输出一定不为0。（）

A. 正确
B. 错误

3）（2分）程序运行到第23行时，“j - i - 1” 一定不小于0。（）

A. 正确
B. 错误

4）（2分）当t是s的子序列时，pre数组和suf数组满足：对任意0 <= i < slen, pre[i] > suf[i + 1] + 1。（）

A. 正确
B. 错误

选择题5）若tlen=10,输出为0,则slen最小为（）。

A. 10
B. 12
C. 0
D. 1

6）若tlen=10,输出为2,则slen最小为（）。

A. 0
B. 10
C. 12
D. 1

本题共 15 分

第 19 题

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

（匠人的自我修养）

一个匠人决定要学习n个新技术。要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。

输入第一行有两个数，分别为新技术个数n (l<=n<=103),以及己有经验值（≤107）。

接下来n行。第i行的两个正整数，分别表示学习第i个技术所需的最低经验值（≤107）,以及学会第i个技术后可获得的经验值（<=107)

接下来 n行。第i行的第一个数mi（0<= mi<n），表示第ii个技术的相关技术数量。紧跟着 m个两两不同的数，表示第i个技术的相关技术编号。

输出最多能学会的新技术个数。

下面的程序以 O(n2)的时间复杂度完成这个问题，试补全程序。

#include<cstdio>
usingnamespacestd;
constint 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)
        returnfalse;
    unlock[target] = -1;
    ③
    for (int i = 0; i < cnt[target]; ++i)
        ④
    returntrue;
}

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);
    return0;
}

①处应填（）

A. unlock[i] <= 0
B. unlock[i] >= 0
C. unlock[i] == 0
D. unlock[i] == -1

②处应填（）

A. threshold[i] > points
B. threshold[i] >= points
C. points > threshold[i]
D. points >= threshold[i]

③处应填（）

A. target = -1
B. --cnt[target]
C. bonus[target] = 0
D. points += bonus[target]

④处应填（）

A. cnt[child[target][i]] -= 1
B. cnt[child[target][i]] = 0
C. unlock[child[target][i]] -= 1
D. unlock[child[target][i]] = 0

⑤处应填（）

A. unlock[i] = cnt[i]
B. unlock[i] = m
C. unlock[i] = 0
D. unlock[i] = -1

本题共 15 分

第 20 题

( 取石子 )

Alice 和 Bob 两个人在玩取石子游戏。他们制定了 n条取石子的规则，第 i条规则为：如果剩余石子的个数大于等于 a[i]且大于等于 b[i]，那么他们可以取走 b[i]个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了。一开始石子有 m个。请问先取石子的人是否有必胜的方法？

输入第一行有两个正整数，分别为规则个数 n(1<n<64) 以及石子个数 m( <= 107)。

接下来 n行。第 i行有两个正整数 a[i]和 b[i]。(l <= a[i]<= 107, l <= 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>
usingnamespacestd;
constint maxn = 64;
int n, m;
int a[maxn], b[maxn];
unsignedlonglong 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");

    return0;
}

①处应填（ )