2022年CCF非专业级别软件能力认证第一轮（CSP-S）提高级C++语言试题的内容：

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

$1$. 在 Linux 系统终端中，用于切换工作目录的命令为（ ）。 {{ select(1) }}

• $ls$
• $cd$
• $cp$
• $all$

$2$. 你同时用 $time$ 命令和秒表为某个程序在单核 CPU 的运行计时。假如 $time$ 命令的输出如下： real 0m30.721s user 0m24.579s sys 0m6.123s 以下最接近秒表计时的时长为（ ） {{ select(2) }}

• $30s$
• $24s$
• $18s$
• $6s$

$3$. 若元素 $a$、$b$、$c$、$d$、$e$、$f$ 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈操作，则不可能得到的出栈序列是（ ）。 {{ select(3) }}

• $dcebfa$
• $cbdaef$
• $bcaefd$
• $afedcb$

$4$. 考虑对 $n$ 个数进行排序，以下最坏时间复杂度低于 $O(n^2)$ 的排序方法是（ ）。 {{ select(4) }}

• 插入排序
• 冒泡排序
• 归并排序
• 快速排序

$5$. 假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排序算法结束后，可能出现的最坏情况是（ ） {{ select(5) }}

• 移除受影响的数据后，最终序列是有序序列
• 移除受影响的数据后，最终序列是前后两个有序的子序列
• 移除受影响的数据后，最终序列是一个有序的子序列和一个基本无序的子序列
• 移除受影响的数据后，最终序列基本无序

$6$. 计算机系统用小端（Little Endian）和大端（Big Endian）来描述多字节数据的存储地址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++代码段表示的程序，将分别输出什么结果？（ ）

unsigned x = 0xDEADBEEF;  
unsigned char *p = (unsigned char *)&x;  
printf("%X", *p);

{{ select(6) }}

• $EF$、$EF$
• $EF$、$DE$
• $DE$、$EF$
• $DE$、$DE$

$7$. 一个深度为 $5$（根结点深度为 $1$）的完全 $3$ 叉树，按前序遍历的顺序给结点从 $1$ 开始编号，则第 $100$ 号结点的父结点是第（ ）号。 {{ select(7) }}

• $95$
• $96$
• $97$
• $98$

$8$. 强连通图的性质不包括（ ）： {{ select(8) }}

• 每个顶点的度数至少为 $1$
• 任意两个顶点之间都有边相连
• 任意两个顶点之间都有路径相连
• 每个顶点至少都连有一条边

$9$. 每个顶点度数均为 $2$ 的无向图称为“$2$ 正规图”。由编号为从 $1$ 到 $n$ 的顶点构成的所有 $2$ 正规图，其中包含欧拉回路的不同 $2$ 正规图的数量为（ ） {{ select(9) }}

• $n!$
• $(n - 1)!$
• $n!/2$
• $(n - 1)!/2$

$10$. 共有 $8$ 人选修了程序设计课程，期末大作业要求由 $2$ 人组成的团队完成。假设不区分每个团队内 $2$ 人的角色和作用，请问共有多少种可能的组队方案。（ ） {{ select(10) }}

• $28$
• $32$
• $56$
• $64$

$11$. 小明希望选到形如“省 A·ℒℒDDD”的车牌号。车牌号在“·”之前的内容固定不变；后面的 5 位号码中，前 2 位必须是大写英文字母，后 3 位必须是阿拉伯数字（ℒ代表 A 至 Z，D 表示 0 至 9，两个ℒ和三个 D 之间可能相同也可能不同）。请问总共有多少个可供选择的车牌号。 {{ select(11) }}

• $20280$
• $52000$
• $676000$
• $1757600$

$12$. 给定地址区间为 0~9 的哈希表，哈希函数为 $h(x) = x \% 10$，采用线性探查的冲突解决策略（对于出现冲突情况，会往后探查第一个空的地址存储；若地址 9 冲突了则从地址 0 重新开始探查）。哈希表初始为空表，依次存储$(71, 23, 73, 99, 44, 79, 89)$后，请问 89 存储在哈希表哪个地址中。（ ） {{ select(12) }}

• $9$
• $0$
• $1$
• $2$

$13$. 对于给定的 $n$，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（ ）。

int i, j, k = 0;  
for (i = 0; i < n; i++) {  
    for (j = 0; j < n; j*=2) {  
        k = k + n / 2;  
    }  
}

{{ select(13) }}

• $O(n)$
• $O(n \log n)$
• $O(n\sqrt{n})$
• $O(n^2)$

$14$. 以比较为基本运算，在 $n$ 个数的数组中找最大的数，在最坏情况下至少要做（ ）次运算。 {{ select(14) }}

• $n/2$
• $n - 1$
• $n$
• $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));  
}

{{ select(15) }}

• $5$
• $7$
• $9$
• $13$

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

阅读下列程序完成16-21题

01 #include <iostream>
02 #include <string>
03 #include <vector>
04
05 using namespace std;
06
07 int f(const string &s, const string &t)
08 {
09     int n = s.length(), m = t.length();
10     vector<int> shift(128, m + 1);
11     int i, j;
12     for (j = 0; j < m; j++)
13         shift[t[j]] = m - j;
14     for (i = 0; i <= n - m; i += shift[s[i + m]]) {
15         j = 0;
16         while (j < m && s[i + j] == t[j]) j++;
17         if (j == m) return i;
18     }
19     return -1;
20 }
21
22 int main()
23 {
24     string a, b;
25     cin >> a >> b;
26     cout << f(a, b) << endl;
27     return 0;
28 }

$16$. 当输入为“abcde fg”时，输出为 $-1$。（ ） {{ select(16) }}

• 正确
• 错误

$17$. 当输入为“abbababbbab abab”时，输出为 $4$。（ ） {{ select(17) }}

• 正确
• 错误

$18$. 当输入为“GoodLuckCsp2022 22”时，第 $20$ 行的“j++”语句执行次数为 $2$。（ ） {{ select(18) }}

• 正确
• 错误

$19$. 该算法最坏情况下的时间复杂度为（ ）。 {{ select(19) }}

• $O(n + m)$
• $O(n \log m)$
• $O(m \log n)$
• $O(nm)$

$20$. $f(a, b)$与下列（ ）语句的功能最类似。 {{ select(20) }}

• $a.find(b)$
• $a.rfind(b)$
• $a.substr(b)$
• $a.compare(b)$

$21$. 当输入为“baaabaaabaaabaaaa aaaa”，第 $20$ 行的“j++”语句执行次数为（ ）。 {{ select(21) }}

• $9$
• $10$
• $11$
• $12$

阅读下列程序完成22-27题

01 #include <iostream>
02 #include <iostream>
03 using namespace std;
04
05 const int MAXN = 105;
06 int n, m, k, val[MAXN];
07 int temp[MAXN], cnt[MAXN];
08
09 void init()
10 {
11     cin >> n >> k;
12     for (int i = 0; i < n; i++) cin >> val[i];
13     int maximum = val[0];
14     for (int i = 1; i < n; i++)
15         if (val[i] > maximum) maximum = val[i];
16     m = 1;
17     while (maximum >= k) {
18         maximum /= k;
19         m++;
20     }
21 }
22
23 void solve()
24 {
25     int base = 1;
26     for (int i = 0; i < m; i++) {
27         for (int j = 0; j < k; j++) cnt[j] = 0;
28         for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
29         for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
30         for (int j = n - 1; j >= 0; j--) {
31             temp[cnt[val[j] / base % k] - 1] = val[j];
32             cnt[val[j] / base % k]--;
33         }
34         for (int j = 0; j < n; j++) val[j] = temp[j];
35         base *= k;
36     }
37 }
38
39 int main()
40 {
41     init();
42     solve();
43     for (int i = 0; i < n; i++) cout << val[i] << ' ';
44     cout << endl;
45     return 0;
46 }

$22$. 这是一个不稳定的排序算法。（ ） {{ select(22) }}

• 正确
• 错误

$23$. 该算法的空间复杂度仅与 $n$ 有关。（ ） {{ select(23) }}

• 正确
• 错误

$24$. 该算法的时间复杂度为 $O(m(n + k))$。（ ） {{ select(24) }}

• 正确
• 错误

$25$. 当输入为“5 3 98 26 91 37 46”时，程序第一次执行到第 $36$ 行，$val[i]$ 数组的内容依次为（ ）。 {{ select(25) }}

• 91 26 46 37 98
• 91 46 37 26 98
• 98 26 46 91 37
• 91 37 46 98 26

$26$. 若 $val[i]$ 的最大值为 $100$，$k$ 取（ ）时算法运算次数最少。 {{ select(26) }}

• $2$
• $3$
• $10$
• 不确定

$27$. 当输入的 $k$ 比 $val[i]$ 的最大值还大时，该算法退化为（ ）算法。 {{ select(27) }}

• 选择排序
• 冒泡排序
• 计数排序
• 桶排序

阅读下列程序完成28-33题

01 #include <iostream>
02 #include <algorithm>
03
04 using namespace std;
05
06 const int MAXL = 1000;
07 int n, k, ans[MAXL];
08
09 int main(void)
10 {
11     cin >> n >> k;
12     if (!n) cout << 0 << endl;
13     else
14     {
15         int m = 0;
16         while (n)
17         {
18             ans[m++] = (n % (-k) + k) % k;
19             n = (ans[m - 1] - n) / k;
20         }
21         for (int i = m - 1; i >= 0; i--)
22             cout << char(ans[i] >= 10?
23                         ans[i] + 'A' - 10 :
24                         ans[i] + '0');
25         cout << endl;
26     }
27     return 0;
28 }

假设输入的 n 在 int 范围内，k 为不小于 2 且不大于 36 的正整数，完成下面的判断题和单选题：

$28$. 该算法的时间复杂度为 $O(\log_k n)$。（ ） {{ select(28) }}

• 正确
• 错误

$29$. 删除第 $23$ 行的强制类型转换，程序的行为不变。（ ） {{ select(29) }}

• 正确
• 错误

$30$. 除非输入的 $n$ 为 $0$，否则程序输出的字符数为（ ）。 {{ select(30) }}

• 正确
• 错误

$31$. 当输入为“100 7”时，输出为（ ）。 {{ select(31) }}

• 202
• 1515
• 244
• 1754

$32$. 当输入为“-255 8”时，输出为“（ ）”。 {{ select(32) }}

• 1400
• 1401
• 417
• 400

$33$. 当输入为“1000000 19”时，输出为“（ ）”。 {{ select(33) }}

• BG939
• 87GIB
• 1CD428
• 7CF1B

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

(1)（归并第k小）已知两个长度均为n的有序数组a1和a2（均为递增序，但不保证严格单调递增），并且给定正整数k（1≤k≤2n），求数组a1和a2归并排序后的数组里第k小的数值。

试补全程序。 阅读下列程序完成34-38题

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int solve(int *a1, int *a2, int n, int k) {
05     int left1 = 0, right1 = n - 1;
06     int left2 = 0, right2 = n - 1;
07     while (left1 <= right1 && left2 <= right2) {
08         int m1 = (left1 + right1) >> 1;
09         int m2 = (left2 + right2) >> 1;
10         int cnt = ①;
11         if (②) {
12             if (cnt < k) left1 = m1 + 1;
13             else right2 = m2 - 1;
14         } else {
15             if (cnt < k) left2 = m2 + 1;
16             else right1 = m1 - 1;
17         }
18     }
19     if (③) {
20         if (left1 == 0) {
21             return a2[k - 1];
22         } else {
23             int x = a1[left1 - 1], ④;
24             return std::max(x, y);
25         }
26     } else {
27         if (left2 == 0) {
28             return a1[k - 1];
29         } else {
30             int x = a2[left2 - 1], ⑤;
31             return std::max(x, y);
32         }
33     }
34 }

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

• $(m_1 + m_2) * 2$
• $(m_1 - 1) + (m_2 - 1)$
• $m_1 + m_2$
• $(m_1 + 1) + (m_2 + 1)$

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

• $a_1[m_1] == a_2[m_2]$
• $a_1[m_1] <= a_2[m_2]$
• $a_1[m_1] >= a_2[m_2]$
• $a_1[m_1] != a_2[m_2]$

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

• $left_1 == right_1$
• $left_1 < right_1$
• $left_1 > right_1$
• $left_1 != right_1$

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

• $y = a_1[k - left_2 - 1]$
• $y = a_1[k - left_2]$
• $y = a_2[k - left_1 - 1]$
• $y = a_2[k - left_1]$

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

• $y = a_1[k - left_2 - 1]$
• $y = a_1[k - left_2]$
• $y = a_2[k - left_1 - 1]$
• $y = a_2[k - left_1]$

阅读下列程序完成39-43题

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 110;
04
05 int f[N][N];
06 int ans;
07 int a, b, c;
08 int init;
09
10 int dfs(int x, int y) {
11     if (f[x][y]!= init)
12         return f[x][y];
13     if (x == c || y == c)
14         return f[x][y] = 0;
15     f[x][y] = init - 1;
16     f[x][y] = min(f[x][y], dfs(a, y) + 1);
17     f[x][y] = min(f[x][y], dfs(x, b) + 1);
18     f[x][y] = min(f[x][y], dfs(0, y) + 1);
19     f[x][y] = min(f[x][y], dfs(x, 0) + 1);
20     int t = min(a - x, y);
21     f[x][y] = min(f[x][y], ①);
22     t = min(x, b - y);
23     f[x][y] = min(f[x][y], ②);
24     return f[x][y];
25 }
26
27 void go(int x, int y) {
28     if (③)
29         return;
30     if (f[x][y] == dfs(a, y) + 1) {
31         cout << "FILL(1)" << endl;
32         go(a, y);
33     } else if (f[x][y] == dfs(x, b) + 1) {
34         cout << "FILL(2)" << endl;
35         go(x, b);
36     } else if (f[x][y] == dfs(0, y) + 1) {
37         cout << "DROP(1)" << endl;
38         go(0, y);
39     } else if (f[x][y] == dfs(x, 0) + 1) {
40         cout << "DROP(2)" << endl;
41         go(x, 0);
42     } else {
43         int t = min(a - x, y);
44         if (f[x][y] == ④) {
45             cout << "POUR(2,1)" << endl;
46             go(x + t, y - t);
47         } else {
48             t = min(x, b - y);
49             if (f[x][y] == ⑤) {
50                 cout << "POUR(1,2)" << endl;
51                 go(x - t, y + t);
52             } else
53                 assert(0);
54         }
55     }
56 }
57
58 int main() {
59     cin >> a >> b >> c;
60     ans = 1 << 30;
61     memset(f, 127, sizeof f);
62     init = (*f)[0];
63     if ((ans = dfs(0, 0)) == init - 1)
64         cout << "impossible";
65     else {
66         cout << ans << endl;
67         go(0, 0);
68     }
69 }

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

• $\text{dfs}(x + t, y - t) + 1$
• $\text{dfs}(x + t, y - t) - 1$
• $\text{dfs}(x - t, y + t) + 1$
• $\text{dfs}(x - t, y + t) - 1$

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

• $\text{dfs}(x + t, y - t) + 1$
• $\text{dfs}(x + t, y - t) - 1$
• $\text{dfs}(x - t, y + t) + 1$
• $\text{dfs}(x - t, y + t) - 1$

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

• $x == c || y == c$
• $x == c \&\& y == c$
• $x >= c || y >= c$
• $x >= c \&\& y >= c$

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

• $\text{dfs}(x + t, y - t) + 1$
• $\text{dfs}(x + t, y - t) - 1$
• $\text{dfs}(x - t, y + t) + 1$
• $\text{dfs}(x - t, y + t) - 1$

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

• $\text{dfs}(x + t, y - t) + 1$
• $\text{dfs}(x + t, y - t) - 1$
• $\text{dfs}(x - t, y + t) + 1$
• $\text{dfs}(x - t, y + t) - 1$