资讯 / 正文
2022年CSP-S第一轮(提高级)真题及答案
一、单项选择题(第 1~15 题,每题 2 分,共 30 分)
第 1 题 在 Linux 系统终端中,用于切换工作目录的命令为( )。
A. ls B. cd C. cp D. all
【答案】B
解析:ls 列出目录内容,cd 切换工作目录,cp 复制文件,all 并不是 Linux 终端命令。
第 2 题 你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如下:real 0m30.721suser 0m24.579ssys 0m6.123s以下最接近秒表计时的时长为( )。
A. 30s B. 24s C. 18s D. 6s
【答案】A
解析:real 是程序实际流逝的墙钟时间(含等待),秒表量的正是它;user+sys 是 CPU 时间(24.579+6.123≈30.7s,但被等待打断时秒表只会更长),最接近秒表读数的是 real=30s。
第 3 题 若元素 a、b、c、d、e、f 依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次退栈操作,则不可能得到的出栈序列是( )。
A. d c e b f a B. c b d a e f C. b c a e f d D. a f e d c b
【答案】D
解析:要最先弹出 a 只需进 1 个退 1 个;随后要依次弹出 f、e、d、c、b,必须先把 b~f 全部压栈再连退 5 次,违反“不连续三次退栈”,故 D 不可能。
第 4 题 考虑对 n 个数进行排序,以下最坏时间复杂度低于 O(n²) 的排序方法是( )。
A. 插入排序 B. 冒泡排序 C. 归并排序 D. 快速排序
【答案】C
解析:归并排序最坏 O(n log n);插入、冒泡最坏 O(n²),快速排序最坏也会退化到 O(n²)。
第 5 题 假设在基数排序过程中,受宇宙射线的影响,某项数据异变为一个完全不同的值。请问排序算法结束后,可能出现的最坏情况是( )。
A. 移除受影响的数据后,最终序列是有序序列B. 移除受影响的数据后,最终序列是前后两个有序的子序列C. 移除受影响的数据后,最终序列是一个有序的子序列和一个基本无序的子序列D. 移除受影响的数据后,最终序列基本无序
【答案】A
解析:基数排序每一趟只按当前位分桶,其余元素之间的相对次序始终由各自的数位决定,不会因一个值异变而被“搅乱”;移除异变的那个数后,其余数据仍是全局有序的。
第 6 题 计算机系统用小端(Little Endian)和大端(Big Endian)来描述多字节数据的存储地址顺序模式,其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式和大端模式的系统上分别编译运行以下代码,将分别输出什么结果?( )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
解析:p 指向 x 的最低地址字节。小端机低地址放最低位字节 EF,大端机低地址放最高位字节 DE,故输出 EF、DE。
第 7 题 一个深度为 5(根结点深度为 1)的完全 3 叉树,按前序遍历的顺序给结点从 1 开始编号,则第 100 号结点的父结点是第( )号。
A. 95 B. 96 C. 97 D. 98
【答案】C
解析:深度 5 的满三叉树共 1+3+9+27+81=121 个结点,根的三棵子树各 40 个结点:2 号子树占 2~41,42 号子树占 42~81,82 号子树占 82~121。100 号在 82 号的子树内;82 的子树中 83 占 13 个(83~95),96 号是 82 的第二个儿子,其第一个儿子 97 号带三个儿子 98、99、100,故 100 号的父结点是 97 号。
第 8 题 强连通图的性质不包括( )。
A. 每个顶点的度数至少为 1B. 任意两个顶点之间都有边相连C. 任意两个顶点之间都有路径相连D. 每个顶点至少都连有一条边
【答案】B
解析:强连通只要求任意两点之间相互可达(有路径),并不要求直接有边相连;“任意两点之间都有边相连”是完全图的定义。
第 9 题 每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为 1 到 n 的顶点构成的所有 2 正规图中,包含欧拉回路的不同 2 正规图的数量为( )。
A. n! B. (n-1)! C. n!/2 D. (n-1)!/2
【答案】D
解析:要含欧拉回路必须连通,即所有点构成一个环;n 个点的环是圆排列,数为 (n-1)!;无向环顺逆时针两种定向算同一个,再除以 2,得 (n-1)!/2。
第 10 题 共有 8 人选修了程序设计课程,期末大作业要求由 2 人组成的团队完成。假设不区分每个团队内 2 人的角色和作用,请问共有多少种可能的组队方案。( )。
A. 28 B. 32 C. 56 D. 64
【答案】A
解析:不考虑角色区别即组合数 C(8,2)=8×7/2=28。
第 11 题 小明希望选到形如“省 A·LLDDD”的车牌号。车牌号在“·”之前的内容固定不变;后面的 5 位号码中,前 2 位必须是大写英文字母,后 3 位必须是阿拉伯数字(L 代表 A 至 Z,D 表示 0 至 9,两个 L 和三个 D 之间可能相同也可能不同)。请问总共有多少个可供选择的车牌号。( )
A. 20280 B. 52000 C. 676000 D. 1757600
【答案】C
解析:26×26×10×10×10=676000。
第 12 题 给定地址区间为 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
解析:71→1,23→3,73 冲突→4,99→9,44 冲突→5,79 冲突→0;89 冲突→0、1、2 均被占(0 是 79,1 是 71,2 空)→ 存入地址 2。
第 13 题 对于给定的 n,分析以下代码段对应的时间复杂度,其中最为准确的是( )。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√n) D. O(n²)
【答案】B
解析:外层 n 次,内层 j 每次翻倍,执行约 log n 次,总计 O(n log n)。
第 14 题 以比较为基本运算,在 n 个数的数组中找最大的数,在最坏情况下至少要做( )次运算。
A. n/2 B. n-1 C. n D. n+1
【答案】B
解析:每个非最大元素都至少要“输”一次比较,而每次比较只产生一个败者,故至少 n-1 次;顺序扫描恰好 n-1 次可达成。
第 15 题 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));}
A. 5 B. 7 C. 9 D. 13
【答案】B
解析:递推:ack(1,n)=n+2,ack(2,n)=2n+3。故 ack(2,2)=7。也可手模:ack(2,1)=ack(1,ack(2,0))=ack(1,3)=5,ack(2,2)=ack(1,5)=7。
二、阅读程序(判断题 1.5 分/题,选择题 3 分/题,共 40 分;判断题正确填√、错误填×)
(1)字符串匹配
下面的程序在主串 a 中查找模式串 b 首次出现的位置:
1 #include <iostream>
2 #include <string>
3 #include <vector>
4
5 using namespace std;
6
7 int f(const string &s, const string &t)
8 {
9 int n = s.length(), m = t.length();
10
11 vector<int> shift(128, m + 1);
12
13 int i, j;
14
15 for (j = 0; j < m; j++)
16 shift[t[j]] = m - j;
17
18 for (i = 0; i <= n - m; i += shift[s[i + m]]){
19 j = 0;
20 while (j < m && s[i + j] == t[j]) j++;
21 if (j == m) return i;
22 }
23
24 return -1;
25 }
26
27 int main()
28 {
29 string a, b;
30 cin >> a >> b;
31 cout << f(a, b) << endl;
32 return 0;
33 }
假设输入字符串由 ASCII 可见字符组成,完成下面的判断题和单选题:
16.(1 分)当输入为 “abcde fg” 时,输出为 -1。( )
【答案】√
解析:abcde 中找不到 fg,返回 -1。
17. 当输入为 “abbababbbab abab” 时,输出为 4。( )
【答案】×
解析:abab 首次出现在第 4 个字符处,但下标从 0 开始,程序输出的是 3 而不是 4。
18. 当输入为 “GoodLuckCsp2022 22” 时,第 20 行的 “j++” 语句执行次数为 2。( )
【答案】√
解析:失配时按 shift 跳跃,i 依次为 0、3、6、9、10、13;前五次窗口都不匹配(j++ 共 0 次),i=13 时连中两个 2,j++ 恰好执行 2 次。
19. 该算法最坏情况下的时间复杂度为( )。
A. O(n+m) B. O(n log m) C. O(m log n) D. O(nm)
【答案】D
解析:构造 s=aaa…a、t=aaab,模式串内部字符的跳跃距离最小只有 2,每个窗口仍可能比较 m 次,最坏 O(nm)。
20. f(a, b) 与下列( )语句的功能最类似。
A. a.find(b) B. a.rfind(b) C. a.substr(b) D. a.compare(b)
【答案】A
解析:f 返回 b 在 a 中第一次出现的下标,等价于正向查找 a.find(b)。
21. 当输入为 “baaabaaabaaabaaaa aaaa” 时,第 20 行的 “j++” 语句执行次数为( )。
A. 9 B. 10 C. 11 D. 12
【答案】B
解析:注意跳跃会跳过一些 a。i 的取值依次为 0、5、6、7、8、13,对应 j++ 次数 0、3、2、1、0、4,合计 10 次。
(2)k 进制基数排序
下面的程序对输入的 n 个整数按 k 进制做 LSD 基数排序:
1 #include <iostream>
2
3 using namespace std;
4
5 const int MAXN = 105;
6
7 int n, m, k, val[MAXN];
8 int temp[MAXN], cnt[MAXN];
9
10 void init()
11 {
12 cin >> n >> k;
13 for (int i = 0; i < n; i++) cin >> val[i];
14 int maximum = val[0];
15 for (int i = 1; i < n; i++)
16 if (val[i] > maximum) maximum = val[i];
17 m = 1;
18 while (maximum >= k) {
19 maximum /= k;
20 m++;
21 }
22 }
23
24 void solve()
25 {
26 int base = 1;
27 for (int i = 0; i < m; i++) {
28 for (int j = 0; j < k; j++) cnt[j] = 0;
29 for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
30 for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
31 for (int j = n - 1; j >= 0; j--) {
32 temp[cnt[val[j] / base % k] - 1] = val[j];
33 cnt[val[j] / base % k]--;
34 }
35 for (int j = 0; j < n; j++) val[j] = temp[j];
36 base *= k;
37 }
38 }
39
40 int main()
41 {
42 init();
43 solve();
44 for (int i = 0; i < n; i++) cout << val[i] << ' ';
45 cout << endl;
46 return 0;
47 }
假设输入的 n 为不大于 100 的正整数,k 为不小于 2 且不大于 100 的正整数,val[i] 在 int 表示范围内,完成下面的判断题和单选题:
22. 这是一个不稳定的排序算法。( )
【答案】×
解析:每趟用“倒序扫描 + 计数数组递减”放置元素,相同键值保持原有相对顺序——这是稳定的计数排序,整体是稳定的基数排序。
23. 该算法的空间复杂度仅与 n 有关。( )
【答案】×
解析:cnt 数组大小与基数 k 有关,空间复杂度为 O(n+k),并非只与 n 有关。
24. 该算法的时间复杂度为 O(m(n+k))。( )
【答案】√
解析:外层 m 趟(m 是最大值在 k 进制下的位数),每趟内含 O(n) 的统计/写回循环和 O(k) 的计数处理,总时间 O(m(n+k))。
25. 当输入为 “5 3 98 26 91 37 46” 时,程序第一次执行到第 36 行,val[] 数组的内容依次为( )。
A. 91 26 46 37 98 B. 91 46 37 26 98C. 98 26 46 91 37 D. 91 37 46 98 26
【答案】D
解析:第一趟只按 3 进制第 0 位(个位)排序:98、26 余 2,91、37、46 余 1;稳定性使同键值保持原序,结果为 91 37 46 98 26。
26. 若 val[i] 的最大值为 100,k 取( )时算法运算次数最少。
A. 2 B. 3 C. 10 D. 不确定
【答案】D
解析:总运算次数约为 m(n+k):k=2、3、10 时 m 分别为 7、5、3,对应 7(n+2)、5(n+3)、3(n+10)。n 较小时 k=2/3 更省,n 较大时 k=10 更省,而题目未给定 n,故无法确定。★注:个别答案表给 C(默认 n 较大、位数主导),本文采用解析主流口径 D。
27. 当输入的 k 比 val[i] 的最大值还大时,该算法退化为( )算法。
A. 选择排序 B. 冒泡排序 C. 计数排序 D. 桶排序
【答案】C
解析:此时 m=1,每个数只有一位,val[j]/base%k 就是数值本身,一趟计数 + 前缀和 + 倒序写回正是计数排序。
(3)负进制转换
下面的程序把整数 n 转换为 -k 进制输出:
1 #include <iostream>
2 #include <algorithm>
3
4 using namespace std;
5
6 const int MAXL = 1000;
7
8 int n, k, ans[MAXL];
9
10 int main(void)
11 {
12 cin >> n >> k;
13 if (!n) cout << 0 << endl;
14 else
15 {
16 int m = 0;
17 while (n)
18 {
19 ans[m++] = (n % (-k) + k) % k;
20 n = (ans[m - 1] - n) / k;
21 }
22 for (int i = m - 1; i >= 0; i--)
23 cout << char(ans[i] >= 10 ?
24 ans[i] + 'A' - 10 :
25 ans[i] + '0');
26 cout << endl;
27 }
28 return 0;
29 }
假设输入的 n 在 int 范围内,k 为不小于 2 且不大于 36 的正整数,完成下面的判断题和单选题:
28. 该算法的时间复杂度为 O(logkn)。( )
【答案】×
解析:n 允许为负数,对负数取对数没有意义,严格的表述应为 O(logk|n|)。★注:也有解析从渐近意义出发判“正确”,两种口径考试时以官方答案为准。
29. 删除第 23 行的强制类型转换,程序的行为不变。( )
【答案】×
解析:ans[i]+'A'-10 的结果是 int 类型,没有 (char) 强转时 cout 会输出一个整数(如 72)而不是字符(如 'H'),行为改变。
30. 除非输入的 n 为 0,否则程序输出的字符数为 O(⌊logk|n|⌋+1)。( )
【答案】√
解析:每次循环 n 变为 -(n/k) 截断商,绝对值每两轮至少缩小到约 1/k,输出字符数即循环轮数,为 O(log|n|) 量级。
31. 当输入为 “100 7” 时,输出为( )。
A. 202 B. 1515 C. 244 D. 1754
【答案】A
解析:逐位取正余数:100→余2 商-14;-14→余0 商2;2→余2 商0。低位到高位为 2、0、2,输出 202。
32. 当输入为 “-255 8” 时,输出为( )。
A. 1400 B. 1401 C. 417 D. 400
【答案】B
解析:-255→余1 商32;32→余0 商-4;-4→余4 商1;1→余1 商0。低位到高位 1、0、4、1,输出 1401。
33. 当输入为 “1000000 19” 时,输出为( )。
A. BG939 B. 87GIB C. 1CD428 D. 7CF1B
【答案】B
解析:负进制转换(每次取正余数、商变号):1000000→余11(B) 商-52631;-52631→余18(I) 商2771;2771→余16(G) 商-145;-145→余7 商8;8→余8 商0。低到高为 B I G 7 8,输出 87GIB。★注:选项 D 的 7CF1B 是普通正 19 进制表示(干扰项),多个网络答案表误选 D,本文经逐位验算确认选 B。
三、完善程序(单选题,每空 3 分,共 30 分)
(1)归并第 k 小
已知两个长度均为 n 的有序数组 a1 和 a2(均为递增序,但不保证严格单调递增),给定正整数 k(1≤k≤2n),求两数组归并后第 k 小的数值。试补全程序:
#include <bits/stdc++.h>
using namespace std;
int solve(int *a1, int *a2, int n, int k) {
int left1 = 0, right1 = n - 1;
int left2 = 0, right2 = n - 1;
while (left1 <= right1 && left2 <= right2) {
int m1 = (left1 + right1) >> 1;
int m2 = (left2 + right2) >> 1;
int cnt = ①;
if (②) {
if (cnt < k) left1 = m1 + 1;
else right2 = m2 - 1;
} else {
if (cnt < k) left2 = m2 + 1;
else right1 = m1 - 1;
}
}
if (③) {
if (left1 == 0) {
return a2[k - 1];
} else {
int x = a1[left1 - 1], ④;
return std::max(x, y);
}
} else {
if (left2 == 0) {
return a1[k - 1];
} else {
int x = a2[left2 - 1], ⑤;
return std::max(x, y);
}
}
}
34. ①处应填( )。A. (m1 + m2) * 2 B. (m1 - 1) + (m2 - 1)C. m1 + m2 D. (m1 + 1) + (m2 + 1)
【答案】C
解析:数组下标从 0 开始,a1[m1] 之前恰有 m1 个元素、a2[m2] 之前恰有 m2 个元素,cnt=m1+m2 表示当前已“确定更小”的元素个数。
35. ②处应填( )。A. a1[m1] == a2[m2] B. a1[m1] <= a2[m2]C. a1[m1] >= a2[m2] D. a1[m1] != a2[m2]
【答案】B
解析:cnt<k 时需要把中位较小一侧的窗口右移。比较 a1[m1] 与 a2[m2],较小的一侧才可能继续向右扩,故用 a1[m1] <= a2[m2] 区分两分支。
36. ③处应填( )。A. left1 == right1 B. left1 < right1C. left1 > right1 D. left1 != right1
【答案】C
解析:循环结束当且仅当某一侧窗口被清空(left > right),此处先处理 a1 侧耗尽的情形。
37. ④处应填( )。A. y = a1[k - left2 - 1] B. y = a1[k - left2]C. y = a2[k - left1 - 1] D. y = a2[k - left1]
【答案】C
解析:a1 的前 left1 个元素已确定属于前 k 小,还需从 a2 中取第 k-left1 个(下标 k-left1-1);与 x=a1[left1-1] 取 max 是为了处理重复值边界。
38. ⑤处应填( )。A. y = a1[k - left2 - 1] B. y = a1[k - left2]C. y = a2[k - left1 - 1] D. y = a2[k - left1]
【答案】A
解析:与上一空对称:a2 的前 left2 个元素已确定,剩余的从 a1 中取第 k-left2 个,即 y = a1[k - left2 - 1]。
(2)容器分水
有两个容器,容量分别为 a 升和 b 升,允许三种操作:FILL(i) 灌满容器 i;DROP(i) 倒空容器 i;POUR(i,j) 把容器 i 倒向容器 j(直到 j 满或 i 空)。求获得恰好 c 升水的最少操作数和操作序列(a、b、c 均不超过 100,且 c≤max{a,b})。试补全程序:
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N];
int ans;
int a, b, c;
int init;
int dfs(int x, int y) {
if (f[x][y] != init)
return f[x][y];
if (x == c || y == c)
return f[x][y] = 0;
f[x][y] = init - 1;
f[x][y] = min(f[x][y], dfs(a, y) + 1);
f[x][y] = min(f[x][y], dfs(x, b) + 1);
f[x][y] = min(f[x][y], dfs(0, y) + 1);
f[x][y] = min(f[x][y], dfs(x, 0) + 1);
int t = min(a - x, y);
f[x][y] = min(f[x][y], ①);
t = min(x, b - y);
f[x][y] = min(f[x][y], ②);
return f[x][y];
}
void go(int x, int y) {
if (③)
return;
if (f[x][y] == dfs(a, y) + 1) {
cout << "FILL(1)" << endl;
go(a, y);
} else if (f[x][y] == dfs(x, b) + 1) {
cout << "FILL(2)" << endl;
go(x, b);
} else if (f[x][y] == dfs(0, y) + 1) {
cout << "DROP(1)" << endl;
go(0, y);
} else if (f[x][y] == dfs(x, 0) + 1) {
cout << "DROP(2)" << endl;
go(x, 0);
} else {
int t = min(a - x, y);
if (f[x][y] == ④) {
cout << "POUR(2,1)" << endl;
go(x + t, y - t);
} else {
t = min(x, b - y);
if (f[x][y] == ⑤) {
cout << "POUR(1,2)" << endl;
go(x - t, y + t);
} else
assert(0);
}
}
}
int main() {
cin >> a >> b >> c;
ans = 1 << 30;
memset(f, 127, sizeof f);
init = **f;
if ((ans = dfs(0, 0)) == init - 1)
cout << "impossible";
else {
cout << ans << endl;
go(0, 0);
}
}
39. ①处应填( )。A. dfs(x + t, y - t) + 1 B. dfs(x + t, y - t) - 1C. dfs(x - t, y + t) + 1 D. dfs(x - t, y + t) - 1
【答案】A
解析:t=min(a-x,y) 是 POUR(2,1)(把容器 2 的水倒进容器 1)后的新状态 (x+t, y-t),倒一步花 1 次操作,故为 dfs(x+t, y-t)+1。
40. ②处应填( )。A. dfs(x + t, y - t) + 1 B. dfs(x + t, y - t) - 1C. dfs(x - t, y + t) + 1 D. dfs(x - t, y + t) - 1
【答案】C
解析:对称地,t=min(x, b-y) 是 POUR(1,2) 后的状态 (x-t, y+t),同样 +1 步,选 C。
41. ③处应填( )。A. x == c || y == c B. x == c && y == cC. x >= c || y >= c D. x >= c && y >= c
【答案】A
解析:任一容器恰好装 c 升即达成目标,用逻辑或;用 >= 反而会在恰好等于之前误判结束。
42. ④处应填( )。A. dfs(x + t, y - t) + 1 B. dfs(x + t, y - t) - 1C. dfs(x - t, y + t) + 1 D. dfs(x - t, y + t) - 1
【答案】A
解析:go 函数回溯输出操作序列:这一分支对应 POUR(2,1),判断条件与 ① 完全一致,为 dfs(x+t, y-t)+1。
43. ⑤处应填( )。A. dfs(x + t, y - t) + 1 B. dfs(x + t, y - t) - 1C. dfs(x - t, y + t) + 1 D. dfs(x - t, y + t) - 1
【答案】C
解析:最后的 else 分支输出 POUR(1,2),对应转移 dfs(x-t, y+t)+1。
四、全卷答案速查表
选择题 1~15:B A D C A B C B D A C D B B B
阅读程序(1) 16~21:√ × √ D A B
阅读程序(2) 22~27:× × √ D D C
阅读程序(3) 28~33:× × √ A B B
完善程序(1) 34~38:C B C C A
完善程序(2) 39~43:A C A A C
📌 备考提示:本卷考点集中在 栈的手算模拟(第 3 题,注意“不允许连续三次退栈”的约束)、计数原理(第 9~11 题,圆排列去重 / 组合数 / 乘法原理)、哈希线性探查(第 12 题,逐个插入模拟即可)、类 Boyer-Moore 字符串匹配的跳跃计数(阅读程序 1)、基数排序的稳定性与复杂度(阅读程序 2,其中第 26 题为争议题)、负进制转换的逐位取余(阅读程序 3,第 33 题务必区分正负进制)、二分求第 k 小与 记忆化搜索模拟倒水(完善程序)。第 26、28、33 题网络答案分歧较大,本文已逐题注明口径与验证过程。
📢 下期预告:2022年CSP-J第二轮(入门级)真题及答案,欢迎持续关注,每天一套真题带答案,稳步冲击 CSP/NOIP!
题目版权归 CCF 所有,本文仅作学习交流之用;答案经多个独立来源交叉核对,若与官方公布不一致,以官方为准。
💪 建议先掐 120 分钟独立做完全卷再对照答案复盘:第 3 题把四个选项的出入栈过程画一遍,阅读程序 1 的 j++ 计数题动手列表模拟,阅读程序 3 的 "1000000 19" 逐位验算一遍再对照选项,完善程序补完后把 ①~⑤ 代回去走一遍逻辑。加油,我们明天见!