昨天刚考完 CSP-S1，反正没什么想做的（最近好颓废…），来复盘一下。
本次比赛评价（转载）：
CSP-S1 是由 CCF 自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「基数排序」的幻想世界，在这里，被神选中的人将被授予「time计时」，导引宇宙射线。你将扮演一位名为「计数排序」的神秘角色，在自由的旅行中邂逅性格各异、能力独特的大作业，和他们一起击败强敌，找回失散的
% (-k)——同时，逐步发掘「for(int j = 0; j < n; j *= 2)」的真相。
以下答案来自有道小图灵，解析为个人见解，如果有错欢迎指出w
单选题
- 在 Linux 系统终端中，用于切换工作目录的命令为( )。
A. ls B. cd C. cp D. all
答案：B
解析：第一题，很水。ls 为列出目录下的文件夹和文件，cd 为切换目录，cp 为复制，all 只是一个操作值。
2.你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如下：
real 0m30.721s
user 0m24.579s
sys 0m6.123s
以下最接近秒表计时的时长为( )。
A.30s B. 24s C.18s D.6s
答案：A
解析：第二题就是一个下马威……这几年确实没考过 time 命令，弄得措手不及。
real 表示实际使用时间，user 表示用户态使用时间，sys 表示内核态使用时间，故为 A。顺带一提，real 远大于剩下两个是因为把大量的文件读入时间算了进去。
3.若元素 a、b、c、d、e、f 依次进栈， 允许进栈、退栈操作交替进行， 但不允许连续三次退栈操作，则不可能得到的出栈序列是( )。
A.dcebfa B.cbdaef C.bcaefd D.afedcb
答案：D
解析：手模一遍进出栈的操作就很容易得答案了。话说 D 选项如果没有出栈次数限制也得不到……
4.考虑对 n 个数进行排序，以下最坏时间复杂度低于 \(O(n^2)\) 的排序方法是( )。
A.插入排序 B.冒泡排序 C.归并排序 D.快速排序
答案：C
解析：插入和冒泡的时间复杂度都为 \(O(n^2)\)，快速排序虽然平均时间复杂度为 \(O(n\log n)\)，但在极端数据下会退化成 \(O(n^2)\)，而归并排序在极端情况下时间复杂度也为 \(O(n\log n)\)。
5.假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排序算法结束后，可能出现的最坏情况是( )。
A. 移除受影响的数据后，最终序列是有序序列
B. 移除受影响的数据后，最终序列是前后两个有序的子序列
C. 移除受影响的数据后，最终序列是一个有序的子序列和一个基本无序的子序列
D. 移除受影响的数据后，最终序列基本无序
答案：A？
解析：本题有歧义，暂时不写解析。
- 计算机系统用小端（Little Endian）和大端（Big Endian）来描述多字节数据的存储地址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++代码段表示的程序，将分别输出什么结果？（ ）
unsigned x = 0xDEADBEEF;
unsigned char *p = (unsigned char *)&x;
printf("%X", *p);
A. EF、EF
B. EF、DE
C. DE、EF
D. DE、DE
答案：B
解析：熟悉各种指针操作就很容易得到答案，可惜没啥人用，实际写题也没必要用。
unsigned char 会取八位二进制数字，也就是两位十六进制。那么小端就是取 \(x\) 的最后两位，大端就是取最前两位。
- 一个深度为 5（根结点深度为 1）的完全 3 叉树，按前序遍历的顺序给结点从 1 开始编号，则第 100 号结点的父结点是第（ ）号。
A. 95 B. 96 C. 97 D. 98
答案：C
解析：按照前序遍历的原则手模就行了，不多解释。三叉树的前序遍历顺序是根-左-中-右。
- 强连通图的性质不包括( )：
A. 每个顶点的度数至少为 1
B. 任意两个顶点之间都有边相连
C. 任意两个顶点之间都有路径相连
D. 每个顶点至少都连有一条边
答案：B
解析：学过连通性问题那一块的知识就可以轻松答出来了。
对于一张有向图，如果这张图任意两个节点都可以到达，那么这张图是强连通图。根据这个定义，ACD 都是对的。
对于 B 选项，我们可以构造出一个反例：画一个四边形，取顶点为结点，此时这是一个强连通图，但对角线的点没有边相连。
- 每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为从 1 到 n 的顶点构成的所有 2 正规图，其中包含欧拉回路的不同 2 正规图的数量为( )。
A. \(n!\)
B. \((n-1)!\)
C. \(n!/2\)
D. \((n-1)!/2\)
答案：D
解析：根据欧拉回路的判定定理（每个点的度数必定为偶数），可知 2 正规图一定有欧拉回路。
然后就可以构造特殊值了，画一个三角形，取顶点为结点，此时 2 正规图有且只有一个，符合的答案就是 D。
10.共有 8 人选修了程序设计课程，期末大作业要求由 2 人组成的团队完成。假设不区分每个
团队内 2 人的角色和作用，请问共有多少种可能的组队方案。（ ）
A.28 B.32 C.56 D.64
答案：A
解析：很简单的排列组合，答案就是 \(C^2_8\)。
11.小明希望选到形如“省 A ·ℒℒ\(DDD\)”的车牌号。车牌号在“ ·”之前的内容固定不变； 后面 的 5 位号码中， 前 2 位必须是大写英文字母， 后 3 位必须是阿拉伯数字(ℒ 代表 A 至 Z，\(D\) 表示 0 至 9，两个 ℒ 和三个 \(D\) 之间可能相同也可能不同)。请问总共有多少个可供选择的车牌号。( )
A.20280 B.5200 C.67600 D.1757600
答案：C
解析：也是很简单的排列组合，答案就是 \(26^2 \times 10^3\)。
- 给定地址区间为 0~9 的哈希表，哈希函数为
h(x) = x % 10，采用线性探查的冲突解决 策略(对于出现冲突情况，会往后探查第一个空的地址存储；若地址 9 冲突了则从地址 0 重新开始探查)。哈希表初始为空表，依次存储(71, 23, 73, 99, 44, 79, 89)后，请 问 89 存储在哈希表哪个地址中。( )
A.9 B.0 C.1 D.2
答案：D
解析：去年就考过一次哈希冲突，这次也很简单。按照题意模拟即可。
- 对于给定的 n，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为( )。
int i, j, k = 0;
for (i = 0; i < n; i++) {
for (j = 1; j < n; j *= 2) {
k = k + n / 2;
}
}
A. \(O(n)\)
B. \(O(n\log n)\)
C. \(O(n\sqrt n)\)
D. \(O(n^2)\)
答案：B
解析：毫不意外地考了时间复杂度分析，不过难度没想象的难（我递推方程呢？！）
外层会执行 \(n\) 次，内层由于每次 \(j\) 扩大两倍，执行次数是 \(\log_2 n\)，所以答案就是 \(O(n\log n)\)。
14.以比较为基本运算， 在 n 个数的数组中找最大的数，在最坏情况下至少要做( )次运算。
A.n / 2 B. n - 1 C. n D. n + 1
答案：B
解析：假设最大的数在最后面，从头开始找数字，自然就要找 n - 1 次了。
什么？你问我为什么不是 n？当然是因为第一个数不用比较啦……
- ack 函数在输入参数“(2,2)”时的返回值为（ ）。
unsigned ack(unsigned m, unsigned n) {
if (m == 0) return n + 1;
if (n == 0) return ack(m - 1, 1);
return ack(m - 1, ack(m, n - 1));
}
答案：B
解析：这个函数实际上是 Ackermann 函数，增长速度非常快，感兴趣可以查一下资料。
还是手模出结果，就是有点累人……
单选题终于结束啦！来看看阅读程序ww
阅读程序
第一大题
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int f(const string &s, const string &t) {
int n = s.length(), m = t.length();
vector<int> shift(128, m + 1);
int i, j;
for (j = 0; j < m; j++)
shift[t[j]] = m - j;
for (i = 0; i <= n - m; i += shift[s[i + m]]) {
j = 0;
while (j < m && s[i + j] == t[j]) j++;
if (j == m) return i;
}
return -1;
}
int main() {
string a, b;
cin >> a >> b;
cout << f(a, b) << endl;
return 0;
}
假设输入字符串由 ASCII 可见字符组成，完成下面的判断题和单选题：
判断题
-
（1 分）当输入为“abcde fg”时，输出为-1。（ ）
-
当输入为“abbababbbab abab”时，输出为 4。（ ）
-
当输入为“GoodLuckCsp2022 22”时，第 20 行的“j++”语句执行次数为 2。
（ ）
单选题
- 该算法最坏情况下的时间复杂度为（ ）。
A.\(O(n+m)\) B.\()n \log m)\) C. O(m\log n) D. O(nm)
- f(a, b)与下列（ ）语句的功能最类似。
A. a.find(b) B. a.rfind(b)
C. a.substr(b) D. a.compare(b)
- 当输入为“baaabaaabaaabaaaa aaaa”，第 20 行的“j++”语句执行次数为（ ）。
A. 9 B. 10 C. 11 D. 12
答案（A 为正确 B 为错误）：ABADA
解析：不难看出这是一个找字符串位置的函数，返回 b 在 a 中第一次出现的下标。原理是先对 b 构造一个用于跳转的 shift 数组（记录右数第一次出现这个字符的位置，不出现的字符记为 b 的长度加一），然后对 a 一位位比较，找不到就利用 shift 数组跳转。
16 题，显然不存在输出 -1。
17 题，由于是第一次出现，所以取 4。
18 题，由于字符串前面不存在字符 2，所以会一直向后跳转直到匹配成功，也就只会自增两次。
19 题，取一个 \(m = 1\) 且完全不匹配的情况就是答案。
20 题，有点考 string 的用法，不过也可以猜到是 A。
21 题，每次找到 a 都会自增一次，结果就是 12 次。
第二大题
#include <iostream>
using namespace std;
const int MAXN = 105;
int n, m, k, val[MAXN];
int temp[MAXN], cnt[MAXN];
void init() {
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> val[i];
int maximum = val[0];
for (int i = 1; i < n; i++)
if (val[i] > maximum) maximum = val[i];
m = 1;
while (maximum >= k) {
maximum /= k;
m++;
}
}
void solve() {
int base = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < k; j++) cnt[j] = 0;
for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
for (int j = n - 1; j >= 0; j--) {
temp[cnt[val[j] / base % k] - 1] = val[j];
cnt[val[j] / base % k]--;
}
for (int j = 0; j < n; j++) val[j] = temp[j];
base *= k;
}
}
int main() {
init();
solve();
for (int i = 0; i < n; i++) cout << val[i] << ' ';
cout << endl;
return 0;
}
假设输入的 n 为不大于 100 的正整数，k 为不小于 2 且不大于 100 的正整数，val[i]在 int 表示范围内，完成下面的判断题和单选题：
判断题
22.这是一个不稳定的排序算法。（ ）
23.该算法的空间复杂度仅与 n 有关。（ ）
24.该算法的时间复杂度为 \(O(m(n+k))\)。（ ）
单选题
25.当输入为“5 3 98 26 91 37 46”时，程序第一次执行到第 33 行，val[]数组的内容依次为（ ）。
A. 91 26 46 37 98 B. 91 46 37 26 98
C. 98 26 46 91 37 D. 91 37 46 98 26
26.若 val[i]的最大值为 100，k 取（ ）时算法运算次数最少。
A. 2 B. 3 C. 10 D. 不确定
27.当输入的 k 比 val[i]的最大值还大时，该算法退化为（ ）算法。
A. 选择排序 B. 冒泡排序 C. 计数排序 D. 桶排序
答案：BBADDC
解析：不难发现这就是一个基数排序，其中 m 为 \(\log_k \max\{ val_i\}\)。然后就没什么好解释的了（
22 题，显然基于值域的排序都是稳定的。
23 题，空间复杂度还和 k 有关。
24 题，数循环即可得到答案。
25 题，手模即可。
26 题，本质上是找 \(k\log_k \max\{ val_i\}\) 的最小值。
27 题要注意计数排序和桶排序的区别（虽然很多教材都没区分过……）。桶排序会把空桶做一个排序，此时时间复杂度和值域没关系；计数排序不做排序，时间复杂度和值域有关。根据这点，基数排序会退化成计数排序。
第三大题
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXL = 1000;
int n, k, ans[MAXL];
int main(void) {
cin >> n >> k;
if (!n) cout << 0 << endl;
else {
int m = 0;
while (n) {
ans[m++] = (n % (-k) + k) % k;
n = (ans[m - 1] - n) / k;
}
for (int i = m - 1; i >= 0; i--)
cout << char(ans[i] >= 10 ?
ans[i] + 'A' - 10 :
ans[i] + '0');
cout << endl;
}
return 0;
}
假设输入的 n 在 int 范围内，k 为不小于 2 且不大于 36 的正整数，完成下面的判断题和单选题：
判断题
28.该算法的时间复杂度为 \(O(\log_km)\)。（ ）
29.删除第 23 行的强制类型转换，程序的行为不变。（ ）
30.除非输入的 n 为 0，否则程序输出的字符数为 \(O(⌊\log
标签：排序,val,真题,int,S2,Coel,dfs,答案,解析 From： https://www.cnblogs.com/Coel-Flannette/p/16708924.html