#CSP2023S1. CSP 2023 提高级第一轮

CSP 2023 提高级第一轮

CSP 2023 提高级第一轮

（满分：100 分 考试时间：120 分钟）

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

  1. 在 Linux 系统终端中，以下哪个命令用于创建一个新的目录？

{{ select(1) }}

  • newdir
  • mkdir
  • create
  • mkfold

  1. 0,1,2,3,4 中选取 4个数字，能组成（）个不同四位数（注：最小的四位数是 1000最大的四位数是 9999）。

    {{ select(2) }}

  • 96
  • 188
  • 120
  • 84
  1. 假设 𝑛是图的顶点的个数，𝑚 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 𝑚=Θ(𝑛)的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小（）。

{{ select(3) }}

  • 𝑂(𝑚log⁡⁡𝑛\sqrt{\log⁡𝑛}⋅log⁡log⁡𝑛)​
  • 𝑂(𝑛2𝑛^2+𝑚)
  • 𝑂(𝑛2log⁡⁡𝑚\frac{𝑛^2}{\log⁡𝑚}+𝑚log⁡𝑛)​
  • 𝑂(𝑚+𝑛log⁡𝑛)

本题共 2 分

  1. 假设有 𝑛根柱子，需要按照以下规则依次放置编号为 1,2,3,⋯ 的圆环：每根柱子的底 部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有 4根柱子时，最多可以放置（）个圆环

{{ select(4) }}

  • 7
  • 99**
  • 11
  • 5**

本题共 2 分

  1. 以下对数据结构的表述不恰当的一项是：

{{ select(5) }}

  • 队列是一种先进先出（FIFO）的线性结构
  • 哈夫曼树的构造过程主要是为了实现图的深度优先搜索
  • 散列表是一种通过散列函数将关键字映射到存储位置的数据结构
  • 二叉树是一种每个结点最多有两个子结点的树结构

本题共 2 分

  1. 以下连通无向图中，（）一定可以用不超过两种颜色进行染色

{{ select(6) }}

  • 完全三叉树
  • 平面图
  • 边双连通图
  • 欧拉图

本题共 2 分

  1. 最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列 𝑋=𝑥1,𝑥2,𝑥3,⋯,𝑥𝑚𝑥_1,𝑥_2,𝑥_3,⋯,𝑥_𝑚 和 𝑌=𝑦1,𝑦2,𝑦3,⋯,𝑦𝑛𝑦_1,𝑦_2,𝑦_3,⋯,𝑦_𝑛，最长公共子序列（LCS）问题的目标是找到一个最长的新序列 𝑍=𝑧1,𝑧2,𝑧3,⋯,𝑧𝑘𝑧_1,𝑧_2,𝑧_3,⋯,𝑧_𝑘, 使得序列 𝑍 既是序列 𝑋的子序列，又是序列 𝑌 的子序列，且序列 𝑍 的长度 𝑘在满足上述条件的序列里是最大的。 （注：序列 𝐴 是序列 𝐵 的子序列，当且仅当在保持序列 𝐵元素顺序的情况下，从序列 𝐵中删除若干个元素，可以使得剩余的元素构成序列 𝐴。）则序列 ABCAAAABA 和 ABABCBABA 的最长公共子序列长度为（）

{{ select(7) }}

  • 4
  • 5
  • 6
  • 7

本题共 2 分

  1. 一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下：玩家第一次掷出 𝑥点，得到 2𝑥元；第二次掷出 𝑦 点，当 𝑦=𝑥 时玩家会失去之前得到的 2𝑥元而当 𝑦≠𝑥 时玩家能保住第一次获得的2𝑥元。上述 𝑥,𝑦∈1,2,3,4,5,6。 例如：玩家第 一次掷出 3点得到 6元后，但第二次再次掷出 3点，会失去之前得到的 6元，玩家最终收益为 0 元；如果玩家第一次掷出 3 点、第二次掷出 4 点，则最终收益是 6 元。假设骰子掷出任意一点的概率均为 16\frac{1}{6},玩家连续掷两次般子后，所有可能情形下收益的平均值是多少？

    {{ select(8) }}

  • 7 元
  • 356\frac{35}{6}​ ​ 元
  • 163\frac{16}{3}​ 元
  • 193\frac{19}{3}​ 元

本题共 2 分

  1. 假设我们有以下的 C++ 代码：
int a = 5, b = 3, c = 4;
bool res = a & b || c ^ b && a | c;

请问，res 的值是什么？（） 提示：在 C++ 中，逻辑运算的优先级从高到低依次为：逻辑非（!）、逻辑与（&&）、逻辑或（||）。位运算的优先级从高到低依次为：位非（~）、位与（&）、位异或（^）、位或（|）。同时，双目位运算的优先级高于双目逻辑运算；逻辑非与位非优先级相同，且高于所有双目运算符。

{{ select(9) }}

  • true
  • false
  • 1
  • 0

本题共 2 分

  1. 假设快速排序算法的输入是一个长度为n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?

{{ select(10) }}

  • 快速排序对于此类输入的表现最好，因为数组已经排序。
  • 快速排序对于此类输入的时间复杂度是 Θ(𝑛log⁡𝑛)
  • 快速排序对于此类输入的时间复杂度是 Θ(𝑛2𝑛^2)。
  • 快速排序无法对此类数组进行排序，因为数组已经排序。

本题共 2 分

  1. 以下哪个命令，能将一个名为 main.cpp 的 C++ 源文件，编译并生成一个名为 main 的可执行文件？（）

{{ select(11) }}

  • g++ -o main main.cpp
  • g++ -o main.cpp main
  • g++ main -o main.cpp
  • g++ main.cpp -o main.cpp

本题共 2 分

  1. 在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心？

{{ select(12) }}

  • 4 个结点的树
  • 6 个结点的树
  • 7个结点的树
  • 8个结点的树

本题共 2 分

  1. 如图是一张包含 6个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这 6个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？（）

image

{{ select(13) }}

  • 1
  • 2
  • 3
  • 4

本题共 2 分

  1. 若 𝑛=∑𝑖=0k16𝑖⋅𝑥𝑖𝑛=∑_{𝑖=0}^k{16}^𝑖⋅𝑥_𝑖，定义 𝑓(𝑛)=∑𝑖=0k𝑥𝑖𝑓(𝑛)=∑_{𝑖=0}^k𝑥_𝑖，其中 𝑥𝑖𝑖𝑛0,1,⋯,15𝑥_𝑖𝑖𝑛0,1,⋯,15。对于给定自然数 𝑛0𝑛_0，存在序列 𝑛0,𝑛1,𝑛2,⋯,𝑛𝑚𝑛_0,𝑛_1,𝑛_2,⋯,𝑛_𝑚，其中对于 1≤𝑖≤𝑚 都有 𝑛𝑖=𝑓(𝑛𝑖−1)𝑛_𝑖=𝑓(𝑛_{𝑖−1})，且 𝑛𝑚=𝑛𝑚−1𝑛_𝑚=𝑛_{𝑚−1}，称 𝑛𝑚𝑛_𝑚为 𝑛0𝑛_0关于 𝑓的不动点。问在 10016{100}_{16} 到 1𝐴016{1𝐴0}_{16}中，关于 𝑓的不动点为 9 的自然数个数为（）。

{{ select(14) }}

  • 10
  • 11
  • 12
  • 13

本题共 2 分

  1. 现在用如下代码来计算 𝑥𝑛，其时间复杂度为（）。
double quick_power(double x, unsigned n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    return quick_power(x, n / 2)
        * quick_power(x, n / 2)
        * ((n & 1) ? x : 1);
}

{{ select(15) }}

  • 𝑂(𝑛)
  • 𝑂(1)
  • 𝑂(𝑙𝑜𝑔𝑛)
  • 𝑂(𝑛log⁡𝑛)

本题共 2 分

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

1.程序一

#include <iostream>
using namespace std;
unsigned short f(unsigned short x) {
    x ^= x << 6;
    x ^= x >> 8;
    return x;
}
int main() {
    unsigned short x;
    cin >> x;
    unsigned short y = f(x);
    cout << y << endl;
    return 0;
}

假设输入的 𝑥是不超过 65535的自然数，完成下面的判断题和单选题:

判断题

  1. 当输入非零时，输出一定不为零。（）

{{ select(16) }}

  • 正确
  • 错误
  1. （2 分）将 f 函数的输入参数的类型改为 unsigned int，程序的输出不变。（）

{{ select(17) }}

  • 正确
  • 错误
  1. 当输入为 65535 时，输出为 63。（）

{{ select(18) }}

  • 正确
  • 错误
  1. 当输入为 1 时，输出为 64。（）

{{ select(19) }}

  • 正确
  • 错误

单选题

  1. 当输入为 512 时，输出为（）。

{{ select(20) }}

  • 33280
  • 33410
  • 33106
  • 33346
  1. 当输入为 64 时，执行完第 5 行后 x 的值为（）。

{{ select(21) }}

  • 8256
  • 4130
  • 4128
  • 4160

本题共 12.5 分

2.程序二

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

long long solve1(int n) {
    vector<bool> p(n + 1, true);
    vector<long long> f(n + 1, 0), g(n + 1, 0);
    f[1] = 1;
    for (int i = 2; i * i <= n; i++) {
        if (p[i]) {
            vector<int> d;
            for (int k = i; k <= n; k *= i)
                d.push_back(k);
            reverse(d.begin(), d.end());
            for (int k : d) {
                for (int j = k; j <= n; j += k) {
                    if (p[j]) {
                        p[j] = false;
                        f[j] = i;
                        g[j] = k;
                    }
                }
            }
        }
    }
    for (int i = sqrt(n) + 1; i <= n; i++) {
        if (p[i]) {
            f[i] = i;
            g[i] = i;
        }
    }
    long long sum = 1;
    for (int i = 2; i <= n; i++) {
        f[i] = f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);
        sum += f[i];
    }
    return sum;
}

long long solve2(int n) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i * (n / i);
    }
    return sum;
}

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

假设输入的 𝑛是不超过 1000000的自然数，完成下面的判断题和单选题:

判断题

  1. 将第 15行删去，输出不变。（）

{{ select(22) }}

  • 正确
  • 错误
  1. 当输入为 10 时，输出的第一行大于第二行。（）

{{ select(23) }}

  • 正确
  • 错误
  1. （2 分） 当输入为 1000 时，输出的第一行与第二行相等。（）

{{ select(24) }}

  • 正确
  • 错误

单选题

  1. solve1(n) 的时间复杂度为（）。

{{ select(25) }}

  • 𝑂(𝑛log⁡2{𝑛 log⁡}^2𝑛)
  • 𝑂(𝑛)
  • 𝑂(𝑛 log⁡ 𝑛)
  • 𝑂(𝑛 log ⁡log⁡ 𝑛)
  1. solve2(n) 的时间复杂度为（）。

{{ select(26) }}

  • 𝑂(𝑛2𝑛^2)
  • 𝑂(𝑛)
  • 𝑂(𝑛 log⁡ 𝑛)
  • 𝑂(𝑛𝑛\sqrt{𝑛})
  1. 当输入为 5 时，输出的第二行为（）。

{{ select(27) }}

  • 20
  • 21
  • 22
  • 23

本题共 14 分

3.程序三：

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool f0(vector<int> &a, int m, int k) {
    int s = 0;
    for (int i = 0, j = 0; i < a.size(); i++) {
        while (a[i] - a[j] > m)
            j++;
        s += i - j;
    }
    return s >= k;
}

int f(vector<int> &a, int k) {
    sort(a.begin(), a.end());

    int g = 0;
    int h = a.back() - a[0];
    while (g < h) {
        int m = g + (h - g) / 2;
        if (f0(a, m, k)) {
            h = m;
        }
        else {
            g = m + 1;
        }
    }

    return g;
}

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

假设输入总是合法的且 1≤𝑎𝑖≤108,𝑛𝑙𝑒10000𝑎_𝑖≤{10}^8,𝑛𝑙𝑒10000,1≤𝑘≤𝑛(𝑛−1)2\frac{𝑛(𝑛−1)}{2}，完成下面的判断题和单选题:

判断题

  1. 将第 24行的 m 改为 m - 1，输出有可能不变，而剩下情况为少 1。（）

{{ select(28) }}

  • 正确
  • 错误
  1. 将第 22行的 g + (h - g) / 2 改为 (h + g) >> 1，输出不变。（）

{{ select(29) }}

  • 正确
  • 错误
  1. 当输入为 5 7 2 -4 5 1 -3，输出为 5。（）

{{ select(30) }}

  • 正确
  • 错误

单选题

  1. 设 𝑎 数组中最大值减最小值加 1 为 𝐴，则 f 函数的时间复杂度为（）。

{{ select(31) }}

  • 𝑂(𝑛 log ⁡𝐴)
  • 𝑂(𝑛2𝑛^2log ⁡𝐴)
  • 𝑂(𝑛 log⁡(𝑛𝐴))
  • 𝑂(𝑛 log ⁡𝑛)
  1. 将第 10行中的 > 替换为 >=，那么原输出与现输出的大小关系为（）。

{{ select(32) }}

  • 一定小于
  • 一定小于等于且不一定小于
  • 一定大于等于且不一定大于
  • 以上三种情况都不对.
  1. 当输入为 5 8 2 -5 3 8 -12，输出为（）。

{{ select(33) }}

  • 13
  • 14
  • 8
  • 15

本题共 13.5 分

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

1.程序一

（第 𝑘小路径）给定一张 𝑛个点 𝑚条边的有向无环图，定点编号从 0 到 𝑛−1，对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第 𝑘 小的路径。保证存在至少 𝑘 条路径。上述参数满足 1≤𝑛,𝑚≤105,1≤𝑘≤1018{10}^5,1≤𝑘≤{10}^{18}。

在程序中，我们求出从每个点出发的路径数量。超过 1018{10}^{18} 的数都用 1018{10}^{18}表示。然后我们根据 𝑘 的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。

试补全程序。

#include <iostream>
#include <algorithm>
#include <vector>

const int MAXN = 100000;
const long long LIM = 1000000000000000000ll;

int n, m, deg[MAXN];
std::vector<int> E[MAXN];
long long k, f[MAXN];

int next(std::vector<int> cand, long long &k) {
    std::sort(cand.begin(), cand.end());
    for (int u : cand) {
        if (①) return u;
        k -= f[u];
    }
    return -1;
}

int main() {
    std::cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v; // 一条从u到v的边
        E[u].push_back(v);
        ++deg[v];
    }
    std::vector<int> Q;
    for (int i = 0; i < n; ++i)
        if (!deg[i]) Q.push_back(i);
    for (int i = 0; i < n; ++i) {
        int u = Q[i];
        for (int v : E[u]) {
            if (②)
                Q.push_back(v);
            --deg[v];
        }
    }
    std::reverse(Q.begin(), Q.end());
    for (int u : Q) {
        f[u] = 1;
        for (int v : E[u])
            f[u] = ③;
    }
    int u = next(Q, k);
    std::cout << u << std::endl;
    while (④) {
        ⑤;
        u = next(E[u], k);
        std::cout << u << std::endl;
    }
    return 0;
}
  1. ①处应填（）

{{ select(34) }}

  • k >= f[u]
  • k <= f[u]
  • k > f[u]
  • k < f[u]
  1. ②处应填（）

{{ select(35) }}

  • deg[v] == 1
  • deg[v] == 0
  • deg[v] > 1
  • deg[v] > 0
  1. ③处应填（）

{{ select(36) }}

  • std::min(f[u] + f[v], LIM)
  • std::min(f[u] + f[v] + 1, LIM)
  • std::min(f[u] * f[v], LIM)
  • std::min(f[u] * (f[v] + 1), LIM)
  1. ④处应填（）

{{ select(37) }}

  • u != -1
  • !E[u].empty()
  • k > 0
  • k > 1
  1. ⑤处应填（）

{{ select(38) }}

  • K+=f[u]
  • k-=f[u]
  • --k
  • ++k

本题共 15 分

2、程序二

（最大值之和）给定整数序列 𝑎0,⋯,𝑎𝑛−1𝑎_0,⋯,𝑎_{𝑛−1}，求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤𝑛≤105{10}^5和 1≤𝑎𝑖≤108𝑎_𝑖≤{10}^8。

一个序列的非空连续子序列可以用两个下标 𝑙 和 𝑟（其中0≤𝑙≤𝑟<𝑛）表示，对应的序列为 𝑎𝑙,𝑎𝑙+1,⋯,𝑎𝑟𝑎_𝑙,𝑎_{𝑙+1},⋯,𝑎_𝑟​。两个非空连续子序列不同，当且仅当下标不同。

例如，当原序列为 [1,2,1,2]时，要计算子序列 [1]、[2]、[1]、[2]、[1,2]、[2,1]、[1,2]、[1,2,1]、[2,1,2]、[1,2,1,2] 的最大值之和，答案为 18。注意 [1,1] 和 [2,2]虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。

解决该问题有许多算法，以下程序使用分治算法，时间复杂度 𝑂(𝑛 log ⁡𝑛)。

试补全程序。

#include <iostream>
#include <algorithm>
#include <vector>

const int MAXN = 100000;

int n;
int a[MAXN];
long long ans;

void solve(int l, int r) {
    if (l + 1 == r) {
        ans += a[l];
        return;
    }
    int mid = (l + r) >> 1;
    std::vector<int> pre(a + mid, a + r);
    for (int i = 1; i < r - mid; ++i) ①;
    std::vector<long long> sum(r - mid + 1);
    for (int i = 0; i < r - mid; ++i)
        sum[i + 1] = sum[i] + pre[i];
    for (int i = mid - l, j = mid, max = 0; i >= l; --i) {
        while (j < r && ②) ++j;
        max = std::max(max, a[i]);
        ans += ③;
        ans += ④;
    }
    solve(l, mid);
    solve(mid, r);
}

int main() {
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    ⑤;
    std::cout << ans << std::endl;
    return 0;
}
  1. ①处应填（）

{{ select(39) }}

  • pre[i] = std::max(pre[i - 1], a[i - 1])
  • pre[i + 1] = std::max(pre[i],pre[i + 1])
  • pre[i] = std::max(pre[i -1], a[i])
  • pre[i] = std::max(pre[i], pre[i - 1])
  1. ②处应填（）

{{ select(40) }}

  • a[j] < max
  • a[j] < a[i]
  • pre[j - mid] < max
  • pre[j - mid] > max
  1. ③处应填（）

{{ select(41) }}

  • (long long)(j - mid) * max
  • (long long)(j - mid) * (i - 1) * max
  • sum[j - mid]
  • sum[j - mid] * (i - 1)
  1. ④处应填（）

{{ select(42) }}

  • (long long)(r - j) * max
  • (long long)(r - j) * (mid - i) * max
  • sum[r - mid] - sum[j - mid]
  • (sum[r - mid] - sum[j - mid]) * (mid - i)
  1. ⑤处应填（）

{{ select(43) }}

  • solve(0，n)
  • solve(0，n - 1)
  • solve(1，n)
  • solve(1，n - 1)

本题共 15 分

相关

在以下作业中:

GFHD 2023初赛真题CSP-S

  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. 粤ICP备2022142345号-1
  4. Worker 0, 42ms
  5. Powered by Hydro v4.14.1 Community