#722. CSP-S 2019 第一轮（初赛）真题

CSP-S 2019 第一轮（初赛）真题

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. 若有定义：int a=7; float x=2.5, y=4.7; 则表达式 x+a%3*(int)(x+y)%2 的值是（ ）{{ select(1-1) }}

  • 0.000000
  • 2.750000
  • 3.500000
  • 2.500000

2. 下列属于图像文件格式的有（ ）{{ select(1-2) }}

  • MPEG
  • WMV
  • AVI
  • JPEG

3. 二进制数 11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑或运算的结果是（ ）{{ select(1-3) }}

  • 11 1111 1111 1101
  • 11 1111 1101 1111
  • 11 1111 1111 1111
  • 10 1111 1111 1111

4. 编译器的功能是（ ）{{ select(1-4) }}

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

5. 设变量 x 为 float 型且已赋值，则以下语句中能将 x 中的数值保留到小数点后两位，并将第三位四舍五入的是（ ）{{ select(1-5) }}

  • x=(x*100+0.5)/100.0;
  • x=(x/100+0.5)*100.0;
  • x=x*100+0.5/100.0;
  • x=(int)(x*100+0.5)/100.0;

6. 由数字 1, 1, 2, 4, 8, 8 所组成的不同的 4 位数的个数是（ ）{{ select(1-6) }}

  • 98
  • 104
  • 102
  • 100

7. 排序的算法很多，若按排序的稳定性和不稳定性分类，则（ ）是不稳定排序。（ ）{{ select(1-7) }}

  • 快速排序
  • 直接插入排序
  • 归并排序
  • 冒泡排序

8. G 是一个非连通无向图（没有重边和自环），共有 28 条边，则该图至少有（ ）个顶点。（ ）{{ select(1-8) }}

  • 9
  • 8
  • 10
  • 11

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

  • 20
  • 25
  • 30
  • 40

10. 一次期末考试，某班有 15 人数学得满分，有 12 人语文得满分，并且有 4 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（ ）{{ select(1-10) }}

  • 21
  • 23
  • 22
  • 20

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

  • n2
  • n log n
  • 2n - 1
  • 2n

12. 以下哪个结构可以用来存储图（ ）{{ select(1-12) }}

  • 二叉树
  • 队列
  • 邻接矩阵
  • 栈

13. 以下哪些算法不属于贪心算法？（ ）{{ select(1-13) }}

  • Dijkstra 算法
  • Prim 算法
  • Kruskal 算法
  • Floyd 算法

14. 有一个等比数列，共有奇数项，其中第一项和最后一项分别是 2 和 118098，中间一项是 486，请问以下哪个数是可能的公比？（ ）{{ select(1-14) }}

  • 2
  • 5
  • 4
  • 3

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, …, an,n 中某个数的路径，使得该路径上的数之和最大。令 C[i][j] 是从 a1,1 到 ai,j 的路径上的数的最大和，并且 C[i][0]=C[0][j]=0，则 C[i][j] =（ ）{{ select(1-15) }}

  • max{C[i-1][j-1], C[i-1][j]} + ai,j
  • max{C[i-1][j-1], C[i-1][j]} + 1
  • C[i-1][j-1] + C[i-1][j]
  • max{C[i][j-1], C[i-1][j]} + ai,j

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

（1）

#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). 第 16 行输出 ans 时，ans 的值一定大于 i。（ ）{{ dropdown(2-1)[√, ×] }}（1 分）

2). 程序输出的 ans 小于等于 n。（ ）{{ dropdown(2-2)[√, ×] }}（1 分）

3). 若将第 12 行的“<”改为“!=”，程序输出的结果不会改变。（ ）{{ dropdown(2-3)[√, ×] }}

4). 当程序执行到第 16 行时，若 ans − i > 2，则 a[i + 1] ≤ a[i]。（ ）{{ dropdown(2-4)[√, ×] }}

选择题

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

  • O(n)
  • O(log n)
  • O(n2)
  • O(n log n)

6). 最坏情况下，此程序的时间复杂度是（ ）{{ select(2-6) }}

  • O(log n)
  • O(n2)
  • O(n log n)
  • O(n)

（2）

#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] 的范围内。（ ）{{ dropdown(2-7)[√, ×] }}（1 分）

2). 第 16 行改成“fa[i] = 0;”，不影响程序运行结果。（ ）{{ dropdown(2-8)[√, ×] }}（1 分）

3). 若输入的 a 和 b 值均在 [0, n-1] 的范围内，则对于任意 0 ≤ i < n，都有 0 ≤ fa[i] < n。（ ）{{ dropdown(2-9)[√, ×] }}

4). 若输入的 a 和 b 值均在 [0, n-1] 的范围内，则对于任意 0 ≤ i < n，都有 1 ≤ cnt[i] ≤ n。（ ）{{ dropdown(2-10)[√, ×] }}

选择题

5). 当 n 等于 50 时，若 a、b 的值都在 [0,49] 的范围内，且在第 25 行时 x 总是不等于 y，那么输出为（ ）{{ select(2-11) }}

  • 1250
  • 1276
  • 1225
  • 1176

6). 此程序的时间复杂度是（ ）{{ select(2-12) }}

  • O(n2)
  • O(log n)
  • O(n)
  • O(n log n)

（3）

本题 t 是 s 的子序列的意思是：从 s 中删去若干个字符，可以得到 t；特别的，如果 s=t，那么 t 也是 s 的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。s[x..y] 表示 s[x]...s[y] 共 y-x+1 个字符构成的字符串，若 x>y 则 s[x..y] 是空串。t[x..y] 同理。

#include <iostream>
#include <string>
using namespace std;
const int maxl = 202;
string s, t;
int pre[maxl], suf[maxl];

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). 程序输出时，suf 数组满足：对任意 0 ≤ i < slen，suf[i] ≤ suf[i + 1]。（ ）{{ dropdown(2-13)[√, ×] }}（1 分）

2). 当 t 是 s 的子序列时，输出一定不为 0。（ ）{{ dropdown(2-14)[√, ×] }}（2 分）

3). 程序运行到第 23 行时，“j - i - 1”一定不小于 0。（ ）{{ dropdown(2-15)[√, ×] }}（2 分）

4). 当 t 是 s 的子序列时，pre 数组和 suf 数组满足：对任意 0 ≤ i < slen，pre[i] > suf[i + 1] + 1。（ ）{{ dropdown(2-16)[√, ×] }}（2 分）

选择题

5). 若 tlen=10，输出为 0，则 slen 最小为（官方答案按语言区分：Pascal 选 B，C/C++ 选 C；本卷为 C++ 试题，答案取 C）（ ）{{ select(2-17) }}

  • 12
  • 0
  • 1
  • 10

6). 若 tlen=10，输出为 2，则 slen 最小为（ ）{{ select(2-18) }}

  • 1
  • 10
  • 0
  • 12

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

（1）匠人的自我修养

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

输入第一行有两个数，分别为新技术个数 n（1 ≤ n ≤ 103），以及已有经验值（≤ 107）。
接下来 n 行。第 i 行的两个正整数，分别表示学习第 i 个技术所需的最低经验值（≤ 107），以及学会第 i 个技术后可获得的经验值（≤ 104）。
接下来 n 行。第 i 行的第一个数 mi（0 ≤ mi < n），表示第 i 个技术的相关技术数量。紧跟着 m 个两两不同的数，表示第 i 个技术的相关技术编号。
输出最多能学会的新技术个数。

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

#include <cstdio>
using namespace std;
const int maxn = 1001;

int n;
int cnt[maxn];
int child[maxn][maxn];
int unlock[maxn];
int points;
int threshold[maxn], bonus[maxn];

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). ① 处应填（ ）{{ select(3-1) }}

  • unlock[i] == 0
  • unlock[i] <= 0
  • unlock[i] >= 0
  • unlock[i] == -1

2). ② 处应填（ ）{{ select(3-2) }}

  • threshold[i] > points
  • points >= threshold[i]
  • threshold[i] >= points
  • points > threshold[i]

3). ③ 处应填（ ）{{ select(3-3) }}

  • bonus[target] = 0
  • --cnt[target]
  • points += bonus[target]
  • target = -1

4). ④ 处应填（ ）{{ select(3-4) }}

  • unlock[child[target][i]] = 0
  • cnt[child[target][i]] = 0
  • cnt[child[target][i]] -= 1
  • unlock[child[target][i]] -= 1

5). ⑤ 处应填（ ）{{ select(3-5) }}

  • unlock[i] = 0
  • unlock[i] = -1
  • unlock[i] = m
  • unlock[i] = cnt[i]

（2）取石子

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

输入第一行有两个正整数，分别为规则个数 n（1 ≤ n ≤ 64），以及石子个数 m（≤ 107）。
接下来 n 行。第 i 行有两个正整数 a[i] 和 b[i]。（1 ≤ a[i] ≤ 107, 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;
}

1). ① 处应填（ ）{{ select(3-6) }}

  • ~0ull
  • 1
  • 0
  • ~0ull ^ 1

2). ② 处应填（ ）{{ select(3-7) }}

  • a[j] > i
  • a[j] != i
  • a[j] == i
  • a[j] < i

3). ③ 处应填（ ）{{ select(3-8) }}

  • trans += 1ull << (b[j] - 1)
  • trans |= 1ull << (b[j] - 1)
  • status |= 1ull << (b[j] - 1)
  • status += 1ull << (b[j] - 1)

4). ④ 处应填（ ）{{ select(3-9) }}

  • ~status & trans
  • ~status | trans
  • status | trans
  • status & trans

5). ⑤ 处应填（ ）{{ select(3-10) }}

  • status = trans >> 1 ^ win
  • trans = status ^ trans | win
  • trans = status | trans ^ win
  • status = status << 1 ^ win
难度 普及+/提高-
通过率 —
尝试 0
已通过 0
ID
722
类型
客观题
上传者
标签
  1. Language
  2. 兼容模式
  3. 主题
  2. AC Pro · 南昌信奥程老师 — 从 C++ 基础到 CSP-S 的闯关式信奥学习平台
  3. Worker 0, 30ms
  4. Powered by Hydro v5.0.4 Community