2026 CCF CSP-S 第一轮 C++ 语言试题

本卷共43个作答小题，满分100分。每题只选一个答案，答错或未答得0分；判断题A表示正确、B表示错误。

一、单项选择题（每题2分，共30分）

1（2分）

执行下列代码后，cnt 的值是（）。

int x = 2026, cnt = 0;
while (x) {
    x &= x - 1;
    cnt++;
}

{{ select(1) }}

• 6
• 7
• 11
• 8

2（2分）

用权值 $\{1,2,3,4,5,6,7,8\}$ 构造哈夫曼树，其带权路径长度是（）。

{{ select(2) }}

• 108
• 96
• 99
• 102

3（2分）

把 $1$ 到 $1000$ 的所有整数按十进制写出，数字“1”总共出现了多少次（）。

{{ select(3) }}

• 300
• 271
• 301
• 320

4（2分）

将 $5$ 封信随机装入 $5$ 个写好地址的信封（每封一个），恰好有 $2$ 封装对的方案数是（）。

{{ select(4) }}

• 44
• 24
• 10
• 20

5（2分）

$3^{2026}\bmod 100$ 的值是（）。

{{ select(5) }}

• 29
• 9
• 43
• 81

6（2分）

有 $5$ 堆石子排成一行，重量依次为 $4,1,3,2,5$。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（）。

{{ select(6) }}

• 36
• 35
• 34
• 33

7（2分）

树状数组维护长度 $n=16$ 的序列，查询前缀和 sum(11) 与单点修改 add(3, x) 分别需要访问树状数组中多少个下标（）。

{{ select(7) }}

• 3 和 4
• 4 和 4
• 3 和 5
• 4 和 3

8（2分）

有向无环图 $G$ 顶点集为 $\{1,2,3,4\}$，边集为 $\{(1,2),(1,3)\}$，顶点 $4$ 与任何顶点均不相邻。该图不同的拓扑序共有多少种（）。

{{ select(8) }}

• 12
• 8
• 4
• 6

9（2分）

某分治算法满足 $T(n)=T(n/3)+T(2n/3)+\Theta(n)$，$T(1)=O(1)$，则 $T(n)$ 是（）。

{{ select(9) }}

• $\Theta(n\log n)$
• $\Theta(n^2)$
• $\Theta(n^{1.5})$
• $\Theta(n)$

10（2分）

无根树含 $9$ 个结点（编号为 $1$—$9$），边集为 $\{(1,2),(1,3),(2,4),(2,5),(3,6),(6,7),(7,8),(5,9)\}$。该树的直径（以边数计）与重心分别是（）。

{{ select(10) }}

• 直径 6，重心为结点 3
• 直径 7，重心为结点 2
• 直径 8，重心为结点 1
• 直径 7，重心为结点 1

11（2分）

一张有向图缩点后得到的有向无环图含 $6$ 个顶点，其中入度为 $0$ 的顶点有 $3$ 个，出度为 $0$ 的顶点有 $4$ 个。为使原图变成强连通图，至少需要添加多少条有向边（）。

{{ select(11) }}

• 7
• 6
• 4
• 3

12（2分）

含 $6$ 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（）。

{{ select(12) }}

• 42
• 429
• 132
• 720

13（2分）

字符串 S = "ababaabab"，其所有既是真前缀又是真后缀的子串（非空）的长度之和是（）。

{{ select(13) }}

• 4
• 6
• 7
• 5

14（2分）

用归并排序统计逆序对，合并部分的核心代码为：

// 合并 a[l..mid] 与 a[mid+1..r]，同时累加逆序对
if (a[i] <= a[j]) {
    tmp[k++] = a[i++]; // 取左半段元素
} else {
    tmp[k++] = a[j++]; // 取右半段元素
    ans += mid - i + 1;
}

若把判断条件中的 a[i] <= a[j] 改成 a[i] < a[j]，则 ans 统计出的结果（）。

{{ select(14) }}

• 完全不变
• 变为原来的两倍
• 变为满足 $i<j$ 且 $a[i]\ge a[j]$ 的数对个数
• 变为原来的一半

15（2分）

执行 power(2, 100, 1000) 调用下列函数，返回值是（）。

long long power(long long a, long long b, long long p) {
    long long r = 1 % p;
    while (b) {
        if (b & 1)
            r = r * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return r;
}

{{ select(15) }}

• 576
• 376
• 976
• 176

二、阅读程序（共40分）

程序输入不超过数组或字符串定义的范围。除特殊说明外，判断题1.5分，选择题3分。

阅读程序（1）

16（1分）

当输入为 $32$ 个 '0' 时，程序输出 $12$ 个 0。

{{ select(16) }}

• 正确（√）
• 错误（×）

17（1.5分）

程序运行结束后，数组 a 中下标从 $0$ 到 $31$ 的元素一定全部为 $0$。

{{ select(17) }}

• 正确（√）
• 错误（×）

18（1.5分）

若将第 $12$—$14$ 行（为 a[32] 到 a[43] 补 $0$ 的循环）删除，会改变程序输出的结果。

{{ select(18) }}

• 正确（√）
• 错误（×）

19（3分）

关于第 $6$ 行定义的数组 gen，下列说法正确的是（）。

{{ select(19) }}

• gen 共有 12 个元素，表示一个 12 位的除数
• gen 共有 13 个元素，表示一个 13 位的被除数
• gen 共有 13 个元素，其中 gen[0] 是除数的最高位
• gen 共有 13 个元素，其中 gen[12] 是除数的最高位

20（3分）

该程序实现的功能，最准确的说法是（）。

{{ select(20) }}

• 将输入的 32 位串看成二进制数 $M$，输出 $M$ 与 13 位二进制数 1100000001111 按位异或的结果
• 将输入串视为 32 位二进制数 $M$，在其后补 12 个 0（即计算 $M\times 2^{12}$），再对它做模 2 除法求余数，并输出 12 位余数
• 对输入的 32 位串逐位取反并输出结果
• 统计输入串中 1 的个数，并把该个数用 12 位二进制表示后输出

21（3分）

若把第 $16$ 行 if (a[i] == 0) continue; 删除，说法正确的是（）。

{{ select(21) }}

• 程序输出的结果不会改变
• 可能造成程序运行错误
• 程序能够正常输出一个 12 位 '0' / '1' 串，但是输出结果与输入的 s 无关
• 程序运行结束后，a[0] 的值一定为 0

阅读程序（2）

22（1.5分）

当 $n=5$，$a=\{4,2,6,3,3\}$，且仅有一次查询 $L=2,R=5$ 时，输出为 $1$。

{{ select(22) }}

• 正确（√）
• 错误（×）

23（1.5分）

当某次查询的区间长度为 $1$（即 $L=R$）时，该次查询的输出一定等于 a[L]。

{{ select(23) }}

• 正确（√）
• 错误（×）

24（1.5分）

任意一次查询的输出结果一定不小于该查询区间内的最小值。

{{ select(24) }}

• 正确（√）
• 错误（×）

25（3分）

对于 $j\ge 1$，数组 dp[i][j] 保存的是（）。

{{ select(25) }}

• 从 a[i] 开始连续 $j$ 个数的最大公约数
• 从 a[i] 开始连续 $2^j$ 个数的最大公约数
• a[i] 与 a[j] 的最大公约数
• 从 a[1] 到 a[i] 的最大公约数

26（3分）

若把一次求最大公约数的运算视为 $O(1)$，则第 $17$—$24$ 行建表过程的时间复杂度为（）。

{{ select(26) }}

• $\Theta(n)$
• $\Theta(n\log n)$
• $\Theta(n^2)$
• $\Theta(mn)$

27（3分）

设 $x$ 为一次查询的区间长度（即 $x=R-L+1$），则使得 lg[x] = 5 的 $x$ 的取值范围是（）。

{{ select(27) }}

• $[16,31]$
• $[17,32]$
• $[32,63]$
• $[33,64]$

阅读程序（3）

28（1.5分）

当 $n=5$，$fa[2]\sim fa[5]=\{1,2,3,4\}$ 时，程序输出 $4$。

{{ select(28) }}

• 正确（√）
• 错误（×）

29（1.5分）

程序输出前，f[1] 的值一定等于 ans 的值。

{{ select(29) }}

• 正确（√）
• 错误（×）

30（1.5分）

将第 $10$—$12$ 行与第 $13$—$15$ 行两个 if 语句的顺序交换后，程序输出结果不受影响。

{{ select(30) }}

• 正确（√）
• 错误（×）

31（3分）

程序输出的 ans 表示的是（）。

{{ select(31) }}

• 树中距离最远的两个结点之间路径所经过的边数
• 根结点 1 到最远叶子结点之间路径所经过的边数
• 树中叶子结点的个数
• 所有结点的父结点编号之和

32（3分）

当 $n=7$，$fa[2]\sim fa[7]=\{1,1,2,2,3,3\}$ 时，输出为（）。

{{ select(32) }}

• 2
• 3
• 4
• 5

33（3分）

当 $n=10$，满足输出为 $9$ 的合法输入种类数为（）。

{{ select(33) }}

• 0
• 9
• 256
• 512

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

完善程序（1）平衡路线

34（3分）

①处应填（）。

{{ select(34) }}

• op[0] == '+' ? 0 : 1
• op[0] == '+'
• op[0] == '+' ? 1 : -1
• op[0] == '-' ? 1 : 0

35（3分）

②处应填（）。

{{ select(35) }}

• hh < n
• tt < n
• hh <= tt
• hh < tt

36（3分）

③处应填（）。

{{ select(36) }}

• d[y] + 1
• d[x] + 1
• d[x]
• d[x] - 1

37（3分）

④处应填（）。

{{ select(37) }}

• c[y] == c[x]
• w[i] == 1
• c[y] != c[x]
• d[y] + 1 != d[x]

38（3分）

⑤处应填（）。

{{ select(38) }}

• ok && c[s] == c[t]
• ok && c[s] != c[t]
• !ok || c[s] == c[t]
• !ok && c[s] != c[t]

完善程序（2）标准答案

39（3分）

①处应填（）。

{{ select(39) }}

• 2 * x[i] - m
• -m + 2 * x[i] + 1
• m - 2 * x[i]
• m + 2 * x[i]

40（3分）

②处应填（）。

{{ select(40) }}

• mask | (mask >> 1)
• mask ^ (mask >> 1)
• mask & (mask >> 1)
• mask ^ ((mask >> 1) + 1)

41（3分）

③处应填（）。

{{ select(41) }}

• __builtin_ctzll(d) + 1
• __builtin_popcountll(d)
• __builtin_ctzll(g)
• __builtin_ctzll(d)

42（3分）

④处应填（）。

{{ select(42) }}

• 2ll * s[k] * c[k]
• s[k] * c[k]
• 2ll * (s[k] - c[k])
• 2ll * c[k]

43（3分）

⑤处应填（）。

{{ select(43) }}

• v >= (n & 1)
• v > (n & 1)
• v + (n & 1) >= 0
• v * (n & 1) >= 0