2024 CCF 非专业级别软件能力认证第一轮（CSP-S1）提高级 C++ 语言试题

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

$1.$ 在 Linux 系统中，如果你想显示当前工作目录的路径，应该使用哪个命令？（ ）

{{ select(1) }}

• pwd
• cd
• ls
• echo

$2.$ 假设一个长度为 $n$ 的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（ ）

{{ select(2) }}

• $O(n)$
• $O(\log n)$
• $O(n \log n)$
• $O(1)$

$3.$ 在 C++ 中，以下哪个函数调用会造成栈溢出？（ ）

{{ select(3) }}

• int foo() { return 0; }
• int bar() { int x = 1; return x; }
• void baz() { int a[1000]; baz(); }
• void qux() { return; }

$4.$ 在一场比赛中，有 $10$ 名选手参加，前三名将获得金、银、铜牌。若不允许并列，且每名选手只能获得一枚奖牌，则不同的颁奖方式共有多少种？（ ）

{{ select(4) }}

• $120$
• $720$
• $504$
• $1000$

$5.$ 下面哪个数据结构最适合实现先进先出（FIFO）的功能？（ ）

{{ select(5) }}

• 栈
• 队列
• 线性表
• 二叉搜索树

$6.$ 已知 $f(1) = 1$，且对于 $n \geq 2$ 有 $f(n) = f(n - 1) + f([n/2])$，则 $f(4)$ 的值为：（ ）

{{ select(6) }}

• $4$
• $5$
• $6$
• $7$

$7.$ 假设有一个包含 $n$ 个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？（ ）

{{ select(7) }}

• 所有顶点的度数均为偶数
• 该图连通
• 该图存在一个欧拉回路
• 该图的边数是奇数

$8.$ 对数组进行二分查找的过程中，以下哪个条件必须满足？（ ）

{{ select(8) }}

• 数组必须是有序的
• 数组必须是无序的
• 数组长度必须是 $2$ 的幂
• 数组中的元素必须是整数

$9.$ 考虑一个自然数 $n$ 以及一个模数 $m$，你需要计算 $n$ 的逆元（即 $n$ 在模 $m$ 意义下的乘法逆元）。下列哪种算法最为适合？（ ）

{{ select(9) }}

• 使用暴力法依次尝试
• 使用扩展欧几里得算法
• 使用快速解法
• 使用线性解法

$10.$ 在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有 $n$ 个键值对，表的表数因子为 $a$ $(a < a \leq 1)$。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为（ ）

{{ select(10) }}

• $O(1)$
• $O(\log n)$
• $O(1 / (1 - a))$
• $O(n)$

$11.$ 假设有一棵 $h$ 层的完全二叉树，该树最多包含多少个结点？

{{ select(11) }}

• $2^n + 1$
• $2^n(n+1)-1$
• $2^nn$
• $2^n(n+1)$

$12.$ 设有一个 $10$ 个顶点的完全图，每两个顶点之间都有一条边。有多少个长度为 $4$ 的环？（ ）

{{ select(12) }}

• $120$
• $210$
• $630$
• $5040$

$13.$ 对于一个整数 $n$，定义 $f(n)$ 为 $n$ 的各位数字之和。问使 $f(f(x)) = 18$ 的最小自然数 $x$ 是多少？（ ）

{{ select(13) }}

• $29$
• $199$
• $299$
• $399$

$14.$ 设有一个长度为 $n$ 的 $\Omega_1$ 字符串，其中有 $k$ 个 $1$，每次操作可以交换相邻两个字符。在最坏情况下将这 $k$ 个 $1$ 移到字符串最右边所需要的交换次数是多少？（ ）

{{ select(14) }}

• $k$
• $k^*(k-1)/2$
• $(n-k)^*k$
• $(2n-k-1)*k/2$

$15.$ 如图是一张包含 $7$ 个顶点的有向图，如果要删除其中一些边，使得从节点 $1$ 到节点 $7$ 没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？（ ）

{{ select(15) }}

• $1$
• $2$
• $3$
• $4$

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

1  #include <iostream>
2  using namespace std;
3
4  const int N = 1000;
5  int c[N];
6
7  int logic(int x, int y) {
8      return (x & y) ^ ((x ^ y) || (~x & y));
9  }
10
11 void generate(int a, int b, int *c) {
12     for (int i = 0; i < b; i++)
13         c[i] = logic(a, i) % (b * 1);
14     }
15 }
16
17 void recursion(int depth, int *arr, int size) {
18     if (depth <= 0 || size <= 1) return;
19     int pivot = arr[0];
20     int i = 0, j = size - 1;
21     while (i <= j) {
22         while (arr[i] < pivot) i++;
23         while (arr[j] > pivot) j--;
24         if (i <= j) {
25             int temp = arr[i];
26             arr[i] = arr[j];
27             arr[j] = temp;
28             i++;
29             j--;
30         }
31     }
32     recursion(depth - 1, arr, j + 1);
33     recursion(depth - 1, arr + i, size - i);
34 }
35
36 int main() {
37     int a, b, d;
38     cin >> a >> b >> d;
39     generate(a, b, c);
40     recursion(d, c, b);
41     for (int i = 0; i < b; ++i) cout << c[i] << " ";
42     cout << endl;
43 }

判断题

$16.$ 当 $1000 \geq d \geq b$ 时，输出的序列是有序的。（ ）

{{ select(16) }}

• √
• ×

$17.$ 当输入 "5 5 1" 时，输出为 "1 1 5 5 5"。（ ）

{{ select(17) }}

• √
• ×

$18.$ 假设数组 $c$ 长度无限制，该程序所实现的算法的时间复杂度是 $O(b)$ 的。（X）

{{ select(18) }}

• √
• ×

单选题

$19.$ 函数 int logic(int x, int y) 的功能是（ ）

{{ select(19) }}

• 按位与
• 按位或
• 按位异或
• 以上都不是

$20.$ （4 分）当输入为 “10 100 100” 时，输出的第 100 个数是（ ）

{{ select(20) }}

• $91$
• $94$
• $95$
• $98$

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

1  #include <iostream>
2  #include <string>
3  using namespace std;
4
5  const int P = 998244353, N = 1e4+10, M = 20;
6  int n, m;
7  string s;
8  int dp[1<<M];
9
10 {
11     int solve() {
12         dp[0] = 1;
13         for (int i = 0; i < n; ++i) {
14             for (int j = (1<<(m-1))-1; j >= 0; --j) {
15                 int k = (j<<1)|(s[i]='0');
16                 if (j != 0 || s[i] == '1')
17                     dp[k] = (dp[k] + dp[j]) % P;
18             }
19         }
20         int ans = 0;
21         for (int i = 0; i < (1<<m); ++i) {
22             ans = (ans + 11! * i * dp[i]) % P;
23         }
24         return ans;
25     }
26
27     int solve2() {
28         int ans = 0;
29         for (int i = 0; i < (1<<n); ++i) {
30             int cnt = 0;
31             int num = 0;
32             for (int j = 0; j < n; ++j) {
33                 if (i & (1<<j)) {
34                     num = num * 2 + (s[j]='0');
35                     cnt++;
36                 }
37                 if (cnt <= m) (ans *= num) % P;
38             }
39             return ans;
40         }
41     }
42
43     int main() {
44         cin >> n >> m;
45         cin >> s;
46         if (n <= 20) {
47             cout << solve2() << endl;
48         }
49         cout << solve() << endl;
50         return 0;
51     }
52 }

判断题

$21.$ 假设数组 $dp$ 长度无限制。函数 solve() 所实现的算法的时间复杂度是 $O(n \cdot 2^n)$。（ ）

{{ select(21) }}

• √
• ×

$22.$ 输入“11 2 10000000001”时，程序输出两个数 $32$ 和 $23$。（ ）

{{ select(22) }}

• √
• ×

$23.$ （2 分）在 $n \leq 10$ 时，solve() 的返回值始终小于 $4^{19}$。（ ）

{{ select(23) }}

• √
• ×

单选题

$24.$ 当 $n = 10$ 且 $m = 10$ 时，有多少种输入使得两行的结果完全一致？（ ）

{{ select(24) }}

• $1024$
• $11$
• $10$
• $0$

$25.$ 当 $n < 6$ 时，solve() 的最大可能返回值为（ ）

{{ select(25) }}

• $65$
• $211$
• $665$
• $2059$

$26.$ 若 $n = 8$，$m = 8$，solve 和 solve2 的返回值的最大可能的差值为（ ）

{{ select(26) }}

• $1477$
• $1995$
• $2059$
• $2187$

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

1  #include <iostream>
2  #include <cstring>
3  #include <algorithm>
4  using namespace std;
5
6  const int maxn = 1000000+5;
7  const int P1 = 998244353, P2 = 1000000007;
8  const int B1 = 2, B2 = 31;
9  const int K1 = 0, K2 = 13;
10
11 typedef long long l1;
12
13 int n;
14 bool p[maxn];
15 int p1[maxn], p2[maxn];
16
17 struct H {
18     int h1, h2, l;
19     H(bool b = false) {
20         h1 = b + K1;
21         h2 = b + K2;
22         l = 1;
23     }
24     H operator + (const H & h) const {
25         H hh;
26         hh.l = l + h.l;
27         hh.h1 = (lll * h1 * p1[h.l] + h.h1) % P1;
28         hh.h2 = (lll * h2 * p2[h.l] + h.h2) % P2;
29         return hh;
30     }
31     bool operator == (const H & h) const {
32         return l == h.l && h1 == h.h1 && h2 == h.h2;
33     }
34     bool operator < (const H & h) const {
35         if (l != h.l) return l < h.l;
36         else if (h1 != h.h1) return h1 < h.h1;
37         else return h2 < h.h2;
38     }
39 } h[maxn];
40
41 void init() {
42     memset(p, 1, sizeof(p));
43     p[0] = p[1] = false;
44     p1[0] = p2[0] = 1;
45     for (int i = 1; i <= n; ++i) {
46         p1[i] = (lll * 81 * p1[i-1]) % P1;
47         p2[i] = (lll * 82 * p2[i-1]) % P2;
48         if (!p[i]) continue;
49         for (int j = 2 * i; j <= n; j += i) {
50             p[j] = false;
51         }
52     }
53 }
54
55 int solve() {
56     for (int i = n; i; --i) {
57         h[i] = H(p[i]);
58         if (2 * i + 1 <= n) {
59             h[i] = h[2 * i] + h[i] + h[2 * i + 1];
60         } else if (2 * i <= n) {
61             h[i] = h[2 * i] + h[i];
62         }
63     }
64
65     cout << h[1].h1 << endl;
66     sort(h + 1, h + n + 1);
67     int m = unique(h + 1, h + n + 1) - (h + 1);
68     return m;
69 }
70
71 int main() {
72     cin >> n;
73     init();
74     cout << solve() << endl;
75 }

判断题

$27.$ 假设程序运行前能自动将 $\text{maxn}$ 改为 $n+1$。所实现的算法的时间复杂度是 $O(n \log n)$。（X）

{{ select(27) }}

• √
• ×

$28.$ 时间开销的瓶颈是 $\text{init()}$ 函数。（ ）

{{ select(28) }}

• √
• ×

$29.$ 若修改常数 $B1$ 或 $K1$ 的值，该程序可能会输出不同的结果。（ ）

{{ select(29) }}

• √
• ×

单选题

$30.$ 在 solve() 函数中，h[] 的合并顺序可以看作是：（ ）

{{ select(30) }}

• 二叉树的 BFS 序
• 二叉树的先序遍历
• 二叉树的中序遍历
• 二叉树的后序遍历

$31.$ 输入 “10”，输出的第一行是？（ ）

{{ select(31) }}

• $83$
• $424$
• $54$
• $110101000$

$32.$ （4 分）输入“16”，输出的第二行是？（ ）

{{ select(32) }}

• $7$
• $9$
• $10$
• $12$

三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分） 阅读下列程序完成33-37题 （序列合并）有两个长度为 $N$ 的单词不降序列 $A$ 和 $B$，序列的每个元素都是小于 $10^9$ 的非负整数。在 $A$ 和 $B$ 中各取一个数相加可以得到 $N^2$ 个和，求其中第 $K$ 小的和。上述参数满足 $N \leq 10^5$ 和 $1 \leq K \leq N^2$。

01 #include <iostream>
02 using namespace std;
03
04 const int maxn = 100005;
05
06 int n;
07 long long k;
08 int a[maxn], b[maxn];
09
10 int* upper_bound(int *a, int *an, int ai) {
11     int l = 0, r = __①___;
12     while (l < r) {
13         int mid = (l+r)>>1;
14         if (___②___) {
15             r = mid;
16         } else {
17             l = mid + 1;
18         }
19     }
20     return ___③___;
21 }
22
23 long long get_rank(int sum) {
24     long long rank = 0;
25     for (int i = 0; i < n; ++i) {
26         rank += upper_bound(b, b+n, sum - a[i]) - b;
27     }
28     return rank;
29 }
30
31 int solve() {
32     int l = 0, r = ___④___;
33     while (l < r) {
34         int mid = ((long long)l+r)>>1;
35         if (___⑤___) {
36             l = mid + 1;
37         } else {
38             r = mid;
39         }
40     }
41     return l;
42 }
43
44 int main() {
45     cin >> n >> k;
46     for (int i = 0; i < n; ++i) cin >> a[i];
47     for (int i = 0; i < n; ++i) cin >> b[i];
48     cout << solve() << endl;
49 }

$33.$ ①处应填

{{ select(33) }}

• $an-a$
• $an-a-1$
• $ai$
• $ai+1$

$34.$ ②处应填

{{ select(34) }}

• $a[mid] > ai$
• $a[mid] >= ai$
• $a[mid] < ai$
• $a[mid] <= ai$

$35.$ ③处应填

{{ select(35) }}

• $a+1$
• $a+1+1$
• $a+1-1$
• $an-1$

$36.$ ④处应填

{{ select(36) }}

• $a[n-1]+b[n-1]$
• $a[n]+b[n]$
• $2 * maxn$
• $maxn$

$37.$ ⑤处应填

{{ select(37) }}

• $get_rank(mid) < k$
• $get_rank(mid) <= k$
• $get_rank(mid) > k$
• $get_rank(mid) >= k$

阅读下列程序完成38-42题

1  #include <cstdio>
2  #include <queue>
3  #include <utility>
4  #include <cstring>
5  using namespace std;
6
7  const int maxn = 2e5+10, maxm = 1e6+10, inf = 522133279;
8
9  int n, m, s, t;
10 int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;
11 int dis[maxn<<1], *dis2;
12 int pre[maxn<<1], *pre2;
13 bool vis[maxn<<1];
14
15 void add(int a, int b, int c) {
16     ++tot;
17     nxt[tot] = head[a];
18     to[tot] = b;
19     w[tot] = c;
20     head[a] = tot;
21 }
22 bool upd(int a, int b, int d, priority_queue<pair<int, int>> &q) {
23     if (d >= dis[b]) return false;
24     if (b < n) ① ;
25     q.push(②);
26     dis[b] = d;
27     pre[b] = a;
28     return true;
29 }
30
31 void solve() {
32     priority_queue<pair<int, int>> q;
33     q.push(make_pair(0, s));
34     memset(dis, ③, sizeof(dis));
35     memset(pre, -1, sizeof(pre));
36     dis2 = dis+n;
37     pre2 = pre+n;
38
39     dis[s] = 0;
40     while (!q.empty()) {
41         int aa = q.top().second; q.pop();
42         if (vis[aa]) continue;
43         vis[aa] = true;
44         int a = aa % n;
45         for (int e = head[a]; e; e = nxt[e]) {
46             int b = to[e], c = w[e];
47             if (aa < n) {
48                 if (!upd(a, b, dis[a]+c, q))
49                     ______;
50             } else {
51                 upd(n+a, n+b, dis2[a]+c, q);
52             }
53         }
54     }
55 }
56
57 void out(int a) {
58     if (a != s) {
59         if (a < n) out(pre[a]);
60         else out(__⑥__);
61     }
62     printf("%d%c", a%n+1, "\n"[a == n+t]);
63 }
64
65 int main() {
66     scanf("%d%d%d%d", &n, &m, &s, &t);
67     s--, t--;
68     for (int i = 0; i < m; ++i) {
69         int a, b, c;
70         scanf("%d%d%d", &a, &b, &c);
71         add(a-1, b-1, c);
72     }
73     solve();
74     if (dis2[t] == inf) puts("-1");
75     else {
76         printf("%d\n", dis2[t]);
77         out(n+t);
78     }
79 }

$38.$ ①处应填（ ）

{{ select(38) }}

• $upd(pre[b], n+b, dis[b], q)$
• $upd(a, n+b, d, q)$
• $upd(pre[b], b, dis[b], q)$
• $upd(a, b, d, q)$

$39.$ ②处应填（ ）

{{ select(39) }}

• $make_pair(-d, b)$
• $make_pair(d, b)$
• $make_pair(b, d)$
• $make_pair(-b, d)$

$40.$ ③处应填（ ）

{{ select(40) }}

• $0xff$
• $0x1f$
• $0x3f$
• $0x7f$

$41.$ ④处应填（ ）

{{ select(41) }}

• $upd(a, n+b, dis[a]+c, q)$
• $upd(n+a, n+b, dis2[a]+c, q)$
• $upd(n+a, b, dis2[a]+c, q)$
• $upd(a, b, dis[a]+c, q)$

$42.$ ⑤处应填（ ）

{{ select(42) }}

• $pre2[a$
• $pre[a$
• $pre2[a]$
• $pre[a$