CSP-S 2026 初赛模拟试卷五

ID: 2886

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

Hydro

在NOI Linux中，编译成功后，运行可执行文件main的命令是（）。 {{ select(1) }}

run main
./main
execute main
start main

计算机能直接识别和执行的语言是（）。 {{ select(2) }}

C++语言
汇编语言
机器语言
Python语言

用24位二进制数来表示的RGB颜色，将其每位二进制数取反（0改为1，1改为0），即变为另一种颜色，这种操作称为颜色反相。若某RGB颜色值用十六进制表示为123456H，则其反相后的颜色值用十六进制表示为（）。 {{ select(3) }}

654321H
987654H
EDCBA9H
FEDCBAH

以下代码段的时间复杂度是（）。

int i = 2;
while (i <= n) { // 保证n不大于1e9
    for (int j = 1; j <= i; j++) {
        // O(1) 操作
    }
    i += i / 2;
}

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

无向连通图存在欧拉通路的充要条件是（）。 {{ select(5) }}

恰有0或2个奇度数顶点
所有顶点的度数为偶数
顶点数 - 边数 = 1
图是树

$x$ 是int变量，表达式 $x \& -x$ 的结果是（）。 {{ select(6) }}

清除 $x$ 最低位的1
将 $x$ 的最低位保留，其他位取反
将 $x$ 的最低位取反，其他位不变
保留 $x$ 最低位的1，其余位置为0

用哈夫曼树处理 $n$ 个权值不同的字符，哈夫曼树的节点总数为（）。 {{ select(7) }}

n
2n
2n - 1
2n + 1

执行 int a = 15, b = 6; a = a ^ b; b = a ^ b; a = a ^ b; 后，a和b的值是（）。 {{ select(8) }}

a = 6，b = 15
a = 15，b = 6
a = 21，b = 15
a = 6，b = 21

一个具有 $n$ 个顶点且无重边的二分图，最多有（）条边。 {{ select(9) }}

$n^2 / 4$
$n(n - 1) / 2$
$n^2 / 2$
$n(n - 1)$

后缀表达式 5 3 + 2 * 4 - 的值是（）。 {{ select(10) }}

下列几种排序算法中，在最坏情况下，（）算法的时间复杂度与其他三种不同。 {{ select(11) }}

快速排序
堆排序
插入排序
冒泡排序

抛掷一枚均匀骰子，直到出现6为止，期望抛掷次数是（）。 {{ select(12) }}

在 $6 \times 4$ 的网格中，要从左上角格子内走到右下角，只可以向右、向下、向右下移动，有（）种不同的路径。 {{ select(13) }}

在单调不降的数组中进行二分查找，目标值可能出现多次，希望找到第一次出现的位置，正确的处理方式是（）。 {{ select(14) }}

使用顺序查找，确保找到的位置为第一次出现的位置
找到后直接返回，并从前往后遍历查找第一次出现的位置
找到后继续在右半部分查找
找到后继续在左半部分查找

将字母 $A \sim F$ 排成圆环，要求A和B必须相邻，C和D不能相邻，旋转重合视为排法相同，则共有（）种排法。 {{ select(15) }}

阅读程序（1）：

#include <bits/stdc++.h>
using namespace std;
const int N = 1009;
int n, a[N], res[2];

void solve() {
    int xor_all = 0;
    for (int i = 0; i < n; i++) xor_all ^= a[i];
    int low_bit = xor_all & -xor_all;

    for (int i = 0; i < n; i++) {
        if (a[i] & low_bit) res[0] ^= a[i];
        else res[1] ^= a[i];
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    solve();
    cout << res[0] << " " << res[1] << endl;
    return 0;
}

输入数据说明: (1) $1 \leq n \leq 1000$ ; (2) $1 \leq a[i] \leq 1000$ ，保证最多有2个不同的 $a[i]$ 出现次数为奇数，其他的 $a[i]$ 出现次数均为偶数。

程序的输出结果有可能为 0。 {{ select(16) }}

正确
错误

xor_all 是两个单独数值的异或结果。 {{ select(17) }}

正确
错误

程序的功能是找出数组中最多两个不同的数，这两个数的出现次数是奇数。 {{ select(18) }}

正确
错误

low_bit = xor_all & -xor_all 能找到 xor_all 二进制中最低位的 1。 {{ select(19) }}

正确
错误

（2 分）输入 6 1 2 2 3 3 5 时，输出为（）。 {{ select(20) }}

（2 分）输入 7 2 1 3 3 6 1 2 时，输出为（）。 {{ select(21) }}

阅读程序（2）：

#include <bits/stdc++.h>
using namespace std;
const int N = 100009;
int n, k;
int d[N];

int solve(int left, int right, int k) {
    if (left == right) return d[left];

    int pivot = d[right], i = left - 1;
    for (int j = left; j < right; j++)
        if (d[j] > pivot) swap(d[++i], d[j]);

    swap(d[i + 1], d[right]);
    int pivotIndex = i + 1;

    if (k == pivotIndex) return d[k];
    if (k < pivotIndex) return solve(left, pivotIndex - 1, k);
    return solve(pivotIndex + 1, right, k);
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> d[i];
    cout << solve(0, n - 1, k - 1) << endl;
    return 0;
}

输入 7 3 1 5 4 2 7 3 6 时，输出结果是 3。 {{ select(22) }}

正确
错误

程序的功能是实现快速排序。 {{ select(23) }}

正确
错误

算法在处理过程中，总是将数组分为大于基准值和小于或等于基准值的两部分。 {{ select(24) }}

正确
错误

如果数组的所有元素都相同，该算法会陷入无限循环。 {{ select(25) }}

正确
错误

输入 8 3 1 5 4 2 7 3 6 8 时，输出结果是（）。 {{ select(26) }}

该算法在最坏情况下的时间复杂度出现在（）时。 {{ select(27) }}

数组中的元素已排好序
数组的所有元素相等
数组中的数随机生成
数组元素分布均匀

阅读程序（3）：

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

int solve(string t1, string t2) {
    int m = t1.length(), n = t2.length();

    vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (t1[i - 1] == t2[j - 1]) {
                f[i][j] = f[i - 1][j - 1] + 1;
            } else {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        }
    }
    return f[m][n];
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    cout << solve(s1, s2) << endl;
    return 0;
}

当两个字符串的长度差异很大时，该算法的时间复杂度会显著增加。 {{ select(28) }}

正确
错误

如果交换两个输入字符串的顺序，程序最终输出的结果有可能不同。 {{ select(29) }}

正确
错误

程序的功能是求两个字符串的最长公共子序列的长度。 {{ select(30) }}

正确
错误

输入的两个字符串不为空时，输出的结果也可能为0。 {{ select(31) }}

正确
错误

输入 ABCDCBABCACBDCABAC 时，程序的输出结果为()。 {{ select(32) }}

在状态转移方程中，当 t1[i-1] != t2[j-1] 时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，这体现了()。 {{ select(33) }}

贪心选择性质
最优子结构性质
重叠子问题性质
分治思想

完善程序（1）：

#include <bits/stdc++.h>
using namespace std;
const int N = 1009;
int m, n, d;
int h[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

struct Node {
    int x, y, dst;
    bool operator>(const Node& other) const {
        return dst > other.dst;
    }
};

int solve() {
    vector<vector<int>> dst(m, vector<int>(n, INT_MAX));
    dst[0][0] = 0;

    priority_queue<Node, vector<Node>, ① > q;
    q.push((Node){0, 0, 0});

    while (!q.empty()) {
        Node now = q.top();
        q.pop();

        if (②) continue;

        for (int i = 0; i < 4; i++) {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];

            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                if (③) {
                    int cost = now.dst + 1;
                    if (cost < dst[nx][ny]) {
                        dst[nx][ny] = cost;
                        ④
                    }
                }
            }
        }
    }
    return ⑤
}

int main() {
    cin >> m >> n >> d;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) cin >> h[i][j];
    cout << solve() << endl;
    return 0;
}

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

less<int>
less<Node>
greater<int>
greater<Node>

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

now.dst < dst[now.x][now.y]
now.dst <= dst[now.x][now.y]
now.dst > dst[now.x][now.y]
now.dst >= dst[now.x][now.y]

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

h[now.x][now.y] - h[nx][ny] <= d
h[nx][ny] - h[now.x][now.y] <= d
abs(h[now.x][now.y] - h[nx][ny]) <= d
abs(h[now.x][now.y] - h[nx][ny]) > d

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

q.push((Node)(nx, ny));
q.push((Node)nx, ny);
q.push((Node)(nx, ny, cost));
q.push((Node){nx, ny, cost});

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

(dst[n][m] == INT_MAX ? -1 : dst[n][m]);
(dst[n-1][m-1] == INT_MAX ? -1 : dst[n-1][m-1]);
(dst[m][n] == INT_MAX ? -1 : dst[m][n]);
(dst[m-1][n-1] == INT_MAX ? -1 : dst[m-1][n-1]);

完善程序（2）：

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

ll eulerPhi(int n) {
    if (n == 1) return 1;

    vector<int> prime;
    int temp = n;

    for (int i = 2; i * i <= temp; i++) {
        if (temp % i == 0) {
            prime.push_back(i);
            while (temp % i == 0) temp /= i;
        }
    }
    if (temp > 1) ①

    int k = prime.size();
    ll result = 0;

    for (int mask = 0; mask < (1 << k); mask++) {
        ll product = 1;
        int cnt = 0;

        for (int i = 0; i < k; i++) {
            if (②) {
                cnt++;
                product *= prime[i];
            }
        }

        if (cnt == 0) {
            ③
        } else {
            if (cnt % 2 == 1) {
                ④
            } else {
                ⑤
            }
        }
    }
    return result;
}

int main() {
    int n;
    cin >> n;
    cout << eulerPhi(n) << endl;
    return 0;
}

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

prime.add(i);
prime.push_back(i);
prime.add(temp);
prime.push_back(temp);

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

mask & i
mask | (1 << i)
mask & (1 << i)
mask >> i

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

result *= n
result += n
result -= n
result /= 0

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

result += n / product;
result -= n / product;
result == n / product;
result *= n / product;

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

result += n / product;
result == n / product;
result == n / product;
result *= n / product;

#CSP0021. CSP-S 2026 初赛模拟试卷五

状态

开发

支持

关于

#CSP0021. CSP-S 2026 初赛模拟试卷 五

CSP-S 2026 初赛模拟试卷 五

状态

开发

支持

关于

登录

#CSP0021. CSP-S 2026 初赛模拟试卷五

CSP-S 2026 初赛模拟试卷五