2023年 CSP-S 第一轮（提高级）

满分 100 分

时长 120 分钟

共 43 题

答题卡已答 0/43

已答正确错误编程题

选单项选择题（共 15 题，共 0 分）

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

create

mkfolder

newdir

mkdir

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

$18$

$120$

$84$

$96$

假设 $n$ 是图的顶点的个数，$m$ 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 $m=\Theta(n)$ 的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小。

$\mathrm{O}(n^2+m)$

$\mathrm{O}(\frac{n^2}{\log{m}}+m\log{n})$

$\mathrm{O}(m+n\log{n})$

$\mathrm{O}(m\sqrt{\log{n} \times \log{\log{n}}})$

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

$9$

$7$

$5$

$11$

以下对数据结构的表述不恰当的一项是：（）。

散列表是一种通过散列函数将关键字映射到存储位置的数据结构

二叉树是一种每个结点最多有两个子结点的树结构

队列是一种先进先出（FIFO）的线性结构

哈夫曼树的构造过程主要是为了实现图的深度优先搜索

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

完全三叉树

平面图

边双连通图

欧拉图

最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列 $X={x_1,x_z,x_3,...,x_m}$ 和 $Y={y_i,y_z,y_3,...,y_n}$, 最长公共子序列（LCS）问题的目标是找到一个最长的新序列 $Z={z_1,z_2,z_3,...,z_k}$ 使得序列 $Z$ 既是序列 $X$ 的子序列，又是序列 $Y$ 的子序列，且序列 $Z$ 的长度 $k$ 在满足上述条件的序列里是最大的。（注: 序列 $A$ 是序列 $B$ 的子序列，当且仅当在保持序列 $B$ 元素顺序的情况下，从序列 $B$ 中删除若干个元素，可以使得剩余的元素构成序列 $A$。）则序列 ABCAAAABA 和 ABABCBABA 的最长公共子序列长度为（）

$5$

$7$

$4$

$6$

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

$\frac{16}{3}$元

$\frac{19}{3}$ 元

$7$元

$\frac{35}{6}$ 元

假设我们有以下的 C++ 代码：

int a = 5, b = 3, c = 4;
bool res = a & b || c ^ b && a | c;

请问，res 的值是什么? （）

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

false

1

0

true

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

快速排序无法对此类数组进行排序，因为数组已经排序

快速排序对于此类输入的表现最好，因为数组已经排序

快速排序对于此类输入的时间复杂度是 $\mathrm{O}(n\log{n})$。

快速排序对于此类输入的时间复杂度是 $\mathrm{O}(n^2)$

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

g++ -o main.cpp main

g++ main -o main.cpp

g++ main.cpp -o main.cpp

g++ -o main main.cpp

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

$6$ 个结点的树

$8$ 个结点的树

$4$ 个结点的树

$7$ 个结点的树

[图片]

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

$2$

$4$

$1$

$3$

若 $n = \Sigma^{k}{i=0}16^i·{x_i}$，定义 $\mathrm{f}(n) = \Sigma^{k}{i=0}x_i$；其中 $x_i\in {0,1,\dots,15}$。对于给定自然数 $n_0$，存在序列 $n_0, n_1, n_2,\dots,n_m$，其中对于 $1\leq i \leq m$ 都有 $n_i = \mathrm{f}(n_{i-1})$，且 $n_m=n_{m-1}$，称 $n_m$ 为 $n_0$ 关于 $\mathrm{f}$ 的不动点。问在 $100_{16}$ 至 $\mathrm{1A0}_{16}$ 中，关于 $\mathrm{f}$ 的不动点为 $9$ 的自然数个数为（）。

$12$

$13$

$10$

$11$

现在用如下代码来计算 $x^n$，其时间复杂度为（）。

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

$\mathrm{O}(1)$

$\mathrm{O}(\log{n})$

$\mathrm{O}(n\log{n})$

$\mathrm{O}(n)$

阅阅读程序（共 18 题，共 0 分）

程序代码请先阅读以下程序

#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;
}

程序代码请先阅读以下程序

#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;
}

程序代码请先阅读以下程序

#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;
}

完完善程序（共 10 题，共 0 分）

程序代码请先阅读以下程序

#include <algorithm>
#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;
        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;
}

程序代码请先阅读以下程序

#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 - 1, 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;
}

选 单项选择题（共 15 题，共 0 分）

阅 阅读程序（共 18 题，共 0 分）

完 完善程序（共 10 题，共 0 分）

考试完成

选单项选择题（共 15 题，共 0 分）

阅阅读程序（共 18 题，共 0 分）

完完善程序（共 10 题，共 0 分）