ID: 939

客观题

难度: 10

上传者:

大陆 (guodong_lu)

标签>

初赛

普及组 CSP-J 2025 初赛模拟卷 4

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

正整数 2025 与 1800 的最大公约数是（）。 {{ select(1) }}

表达式 ( ( '0' == 0) + 's' + 5 + 2.0 ) 的结果类型为（）。 {{ select(2) }}

double
int
char
bool

对一个 int 类型的值，执行以下哪个操作后，一定会变回原来的值？（） {{ select(3) }}

左移 5 位，再右移 5 位
右移 5 位，再左移 5 位
按位或 15，再按位与 15
按位异或 15，再按位异或 15

在数组 H[x] 中，若存在 ( (i<j) \ && \ (H[i]>H[j]) )，则称 ( (H[i],H[j]) ) 为数组 H[x] 的一个逆序对。对于序列 27, 4, 1, 59, 3, 26, 38, 15，在不改变顺序的情况下，去掉（）会使逆序对的个数减少 4。 {{ select(4) }}

如果字符串 s 在字符串 str 中出现，则称字符串 s 为字符串 str 的子串。设字符串 str = "oiers"，则 str 的非空子串的数目是（）。 {{ select(5) }}

以下哪种排序算法的平均时间复杂度最好？（） {{ select(6) }}

插入排序
归并排序
选择排序
冒泡排序

如果 x 和 y 均为 int 类型的变量，且 y 的值不为 0，那么能正确判断"x 是 y 的 2 倍"的表达式是（）。 {{ select(7) }}

$(x > 2 == y)$
$(x - 2*y) % 2 != 0$
$(x / y == 2)$
$(x == 2 * y)$

表达式 a*(b+c)-d 的后缀表达式为（）。 {{ select(8) }}

abcd++-
abc+*d-
abc*+d-
--+xabcd

关于计算机网络，下列说法中正确的是（）。 {{ select(9) }}

SMTP 和 POP3 都是电子邮件发送协议
IPv6 地址是从 IPv4、IPv5 一路升级过来的
计算机网络是一个在协议控制下的多机互连系统
192.168.0.1 是 A 类地址

下列哪种语言不是面向对象的语言？（） {{ select(10) }}

Java
C++
Python
Fortran

信息学奥赛的所有课程和课程间的先修关系构成一个有向图 G，我们用有向边<A, B>表示课程 A 是课程 B 的先修课，则要找到某门课程 C 的全部先修课，下面哪种方法不可行？（） {{ select(11) }}

BFS
DFS
枚举
BFS+DFS

一个字长为 8 位的整数的补码为 11111001，则它的原码是（）。 {{ select(12) }}

00000111
10000110
10000111
11111001

元素 A、B、C、D、E、F 入栈的顺序为 A, B, C, D, E, F，如果第一个出栈的是 C，则最后一个出栈的不可能是（）。 {{ select(13) }}

一个三位数等于它的各位数字的阶乘之和，则此三位数的各位数字之和为（）。 {{ select(14) }}

9
10
11
多于一种情况

在一个非连通无向图 G 中有 36 条边，则该图至少有（）个顶点。 {{ select(15) }}

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

(1)

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 k = 3;
const i64 mod = 8;

i64 taint(string s)
{
    sort(s.begin(), s.end());
    i64 ans = 0;
    for(int i = 0; i < s.length(); i++)
        ans = (ans * k + (s[i] - 'a' + 1)) % mod;
    return ans;
}

vector<vector<string>> solve(vector<string>& strs)
{
    map<i64, vector<string>> mp;
    for(auto s: strs)
        mp[taint(s)].push_back(s);
    vector<vector<string>> ans;
    for(auto v: mp)
        ans.push_back(v.second);
    return ans;
}

int main()
{
    int n;
    cin >> n;
    vector<string> vec(n);
    for(int i = 0; i < n; i++)
        cin >> vec[i];
    auto ans = solve(vec);
    for(auto v: ans)
        for(int i = 0; i < v.size(); i++)
            cout << v[i] << " \n" [i == v.size() - 1];
    return 0;
}

假设 $1 \leq n \leq 10^3，1 \leq vec[i].length() \leq 10^3$，回答下面的问题。

判断题
16. 若程序输入 6 eat tea tan ate nat bat，则程序输出 bat（换行）eat tea ate（换行）tan nat（换行）。（）
{{ select(16) }}

正确
错误

对于这段代码，taint("aaf") != taint("atmoa")。（）
{{ select(17) }}

正确
错误

若将头文件<bits/stdc++.h>换为，程序依然可以正常运行。（） {{ select(18) }}

正确
错误

选择题
19. 若输入 4 aad zpf zpz yy1，则输出是什么？（） {{ select(19) }}

aad（换行）zpf（换行）zpz（换行）yy1（换行）
aad zpf（换行）zpz yy1（换行）
aad zpf zpz（换行）yy1（换行）
aad zpf zpz yy1（换行）

这个程序的时间复杂度是多少？（） {{ select(20) }}

$O(n)$
$O(n^2)$
$O(n\log n)$
$O(n^2\log n)$

(2)

#include <bits/stdc++.h>
using namespace std;

int calc(vector<vector<int>>& grid)
{
    int n = grid.size(), m = grid[0].size();
    vector<int> dp(m);
    dp[0] = (grid[0][0] == 0);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(grid[i][j] == 1)
            {
                dp[j] = 0;
                continue;
            }
            if(j - 1 >= 0 && grid[i][j - 1] == 0)
                dp[j] += dp[j - 1];
        }
    return dp[m - 1];
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> a[i][j];
    cout << calc(a) << endl;
    return 0;
}

判断题
21. 若输入 3 3 0 0 0 0 1 0 0 0 0，则输出为 2。（）
{{ select(21) }}

正确
错误

若 f[i][j] 表示从 (0,0) 走到 (i,j) 的路径数，则在第 10-19 行的循环中，f[i][j]=dp[j]。（）
{{ select(22) }}

正确
错误

（2 分）若将第 27 行的代码改为 vector<vector> a(n+1, vector(m+1))，则当输入的 n=3, m=3 时，calc 函数中的 n=3, m=3。（） {{ select(23) }}

正确
错误 选择题\

当输入的 a 数组为 {{0,0,1}, {1,1,0}, {0,1,0}, {1,0,1}, {0,0,0}} 时，程序的输出为（）。 {{ select(24) }}

若删除第 12~16 行的代码，则当输入的 a 数组为 {{0,0,0}, {0,1,0}, {0,0,0}} 时，程序的输出为（）。 {{ select(25) }}

（4 分）当输入的 a 数组为 {{0,0,2}, {0,1,2}, {5,3,4}} 时，程序的输出为（）。 {{ select(26) }}

(3)

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int cmp(string v1, string v2)
{
    int i = 0, j = 0;
    while(i < v1.length() || j < v2.length())
    {
        i64 num1 = 0, num2 = 0;
        while(i < v1.length() && v1[i] != '.')
            num1 = num1 * 10 + (v1[i++] - '0');
        while(j < v2.length() && v2[j] != '.')
            num2 = num2 * 10 + (v2[j++] - '0');
        if(num1 > num2)
            return 1;
        else if(num1 < num2)
            return -1;
        i++, j++;
    }
    return 0;
}

int main()
{
    int n;
    cin >> n;
    vector<string> s(n);
    for(int i = 0; i < n; i++)
    {
        cin >> s[i];
        if(s[i][0] == '.')
        {
            cout << "err" << endl;
            return 0;
        }
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cout << cmp(s[i], s[j]) << " \n"[j == n - 1];
    return 0;
}

假设 $f[i][j] = \text{cmp}(s[i], s[j])$ ，完成下面的问题。

判断题
27. 任取 $0 < i < n$ ，都有 $f[i][i] = 0$ 。（）
{{ select(27) }}

正确
错误

若输入 3 1.0 1.2.1 1.1.0，则 $f[0][1] = 1$ 。（）
{{ select(28) }}

正确
错误

任取 $0 < i, j < n$ ，都有 $f[i][j] + f[j][i] = 0$ 。（） {{ select(29) }}

正确
错误

选择题
30. 当输入的 s 数组为 {"1.2.3", "4.5", ".2"} 时，程序输出中第一行第二个数为（）。 {{ select(30) }}

-1
0
1
不存在

（4 分）若删除第 34~38 行代码，则当输入的 s 数组为 {"1.2.3", "4.5", ".2"} 时， $f[0][2]$ 的值为（）。 {{ select(31) }}

-1
0
1
未计算

阅读代码可知，当两个点之间的数为（）时，cmp 函数将无法得到正确的结果。 {{ select(32) }}

$1 \times 10^9$
$2 \times 10^9$
$4 \times 10^8$
-1

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

(1)

题目描述：
输入 $n (3 \leq n \leq 2 \times 10^5)$ 和长为 $n$ 的数组 $a(1 \leq a[i] \leq 1 \times 10^9)$ 。你需要从a中恰好删除一个数，得到长为 $n-1$ 的数组 $a'$ 。然后生成一个长为 $n-2$ 的数组 b，其中 $b[i] = GCD(a'[i], a'[i+1])$ 。你需要让数组 b是非降序列，即 $b[i] \leq b[i+1]$ 。能否做到？输出 YES 或 NO。（提示：枚举 i，考察删除 $a[i]$ 后对 b 数组产生的影响。）

#include <bits/stdc++.h>
using namespace std;

int gcd(int x, int y)
{
    return !y ? x : gcd(y, x % y);
}

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 2);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    b[n] = b[n + 1] = ①;
    for(int i = 1; i < n; i++)
        b[i] = gcd(a[i], a[i + 1]);
    vector<int> pre(n + 1), suf(n + 2);
    pre[0] = 1;
    for(int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] && (②);
    suf[n + 1] = 1;
    for(int i = n; i >= 1; i--)
        suf[i] = suf[i + 1] && (b[i] <= b[i + 1]);
    bool flag = ③;
    for(int i = 2; i < n; i++)
    {
        int cur = ④;
        if(⑤ && b[i - 2] <= cur && cur <= b[i + 1])
            flag = true;
    }
    cout << (flag ? "YES\n" : "NO\n");
    return;
}

int main()
{
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
}

①处应填（）。 {{ select(33) }}

0
3E9
-1E9
2E9

②处应填（）。 {{ select(34) }}

b[i]>b[i-1]
b[i]<b[i-1]
b[i]>=b[i-1]
b[i]<=b[i-1]

③处应填（）。 {{ select(35) }}

pre[n-2] & suf[2]
pre[n-2] | suf[2]
pre[n-2] ^ suf[2]
pre[n-2] - suf[2]

④处应填（）。 {{ select(36) }}

gcd(a[i], b[i])
gcd(a[i], a[i+1])
gcd(a[i-1], a[i+1])
gcd(a[i-1], a[i])

⑤处应填（）。 {{ select(37) }}

pre[i-2] & suf[i+1]
pre[i-1] & suf[i+1]
pre[i-2] || suf[i+1]
pre[i-1] || suf[i+1]

(2)

题目描述：
输入 $n (1 \leq n \leq 2 \times 10^5)$ 和长为n的数组 $a (1 \leq a[i] \leq 1 \times 10^6)$ 。

对于数组 B，如果满足 B[0] + 1 =len(B) ，那么称数组 B 为"块"。对于数组 A，如果可以将其划分成若干个"块"，那么称数组 A 是合法的。

例如 $A=[3, 3, 4, 5, 2, 6, 1]$ 是合法的，因为 $A = [3, 3, 4, 5] + [2, 6, 1]$ ，这两段都是块。

把数组 a 变成合法数组，至少要删除多少个元素？（提示：令 dp[i] 表示将 a[i] 到 a[n] 变成合法数组最少要删除的元素个数。）

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), dp(①, inf);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    dp[n + 1] = ②;
    for(int i = n; i >= 1; i--)
    {
        dp[i] = ③;
        if(i + a[i] + 1 <= n + 1)
            dp[i] = min(dp[i], ④);
    }
    cout << ⑤ << endl;
    return 0;
}

①处应填（）。 {{ select(38) }}

②处应填（）。 {{ select(39) }}

0
1
-1
inf

③处应填（）。 {{ select(40) }}

dp[i+1]
dp[i-1]
dp[i+1]+1
dp[i-1]+1

④处应填（）。 {{ select(41) }}

dp[i+a[i]+1]
dp[i+a[i]]
dp[a[i]+1]
dp[i+a[i]-1]

⑤处应填（）。 {{ select(42) }}

dp[n]
dp[1]
dp[n-1]
dp[0]

#939. 普及组CSP-J 2025初赛模拟卷4

普及组CSP-J 2025初赛模拟卷4

普及组 CSP-J 2025 初赛模拟卷 4

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

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

(1)

(2)

(3)

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

(1)

(2)

状态

开发

支持

#939. 普及组CSP-J 2025初赛模拟卷4

普及组CSP-J 2025初赛模拟卷4

普及组 CSP-J 2025 初赛模拟卷 4

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

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

(1)

(2)

(3)

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

(1)

(2)

状态

开发

支持

登录