2026 CSP-S 第一轮真题

您的姓名：
1、执行下列代码后，cnt 的值是（ ）。
2、用权值 {1, 2, 3, 4, 5, 6, 7, 8} 构造哈夫曼树，其带权路径长度是（ ）。
3、把 1 到 1000 的所有整数按十进制写出，数字「1」总共出现了多少次（ ）。
4、将 5 封信随机装入 5 个写好地址的信封（每封一个），恰好有 2 封装对的方案数是（ ）。
5、3^2026 mod 100 的值是（ ）。
6、有 5 堆石子排成一行，重量依次为 4、1、3、2、5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（ ）。
7、树状数组维护长度 n=16 的序列，查询前缀和 sum（11） 与单点修改 add（3, x） 分别需要访问树状数组中多少个下标（ ）。
8、有向无环图 G 顶点集为 {1, 2, 3, 4}，边集为 {（1,2）, （1,3）}，顶点 4 与任何顶点均不相邻。该图不同的拓扑序共有多少种（ ）。
9、某分治算法满足 T（n） = T（n/3） + T（2n/3） + Θ（n），T（1）=O（1），则 T（n） 是（ ）。
10、无根树含 9 个结点（编号 1—9），边集为 {（1,2）,（1,3）,（2,4）,（2,5）,（3,6）,（6,7）,（7,8）,（5,9）}。该树的直径（以边数计）与重心分别是（ ）。
11、一张有向图缩点后得到的有向无环图含 6 个顶点，其中入度为 0 的顶点有 3 个，出度为 0 的顶点有 4 个。为使原图变成强连通图，至少需要添加多少条有向边（ ）。
12、含 6 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（ ）。
13、字符串 S="ababaabab"，其所有既是真前缀又是真后缀的子串（非空）的长度之和是（ ）。
14、用归并排序统计逆序对，合并部分核心代码为 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 统计出的结果（ ）。
15、执行 power（2, 100, 1000） 调用下列函数，返回值是（ ）。
16、阅读程序（1）阅读下列程序：
程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×。
说明：输入保证为一个长度恰为 32 的 '0'/'1' 字符串。

① 当输入为 32 个 '0' 时，程序输出 12 个 0。（ ）
17、（程序见第16题）程序运行结束后，数组 a 中下标从 0 到 31 的元素一定全部为 0。（ ）
18、（程序见第16题）若将第 12—14 行（为 a[32] 到 a[43] 补 0 的循环）删除，会改变程序输出的结果。（ ）
19、（程序见第16题）关于第 6 行定义的数组 gen，下列说法正确的是（ ）。
20、（程序见第16题）该程序实现的功能，最准确的说法是（ ）。
21、（程序见第16题）若把第 16 行 if （a[i] == 0） continue; 删除，说法正确的是（ ）。
22、阅读程序（2）
阅读下列程序：
说明：保证 1≤n≤100000，每次查询满足 1≤L≤R≤n，且数组 a 的元素均为正整数。

当 n=5，a={4,2,6,3,3}，且仅有一次查询 L=2, R=5 时，输出为 1。（ ）
23、（程序见第22题）当某次查询的区间长度为 1（即 L=R）时，该次查询的输出一定等于 a[L]。（ ）
24、（程序见第22题）任意一次查询的输出结果一定不小于该查询区间内的最小值。（ ）
25、（程序见第22题）对于 j≥1，数组 dp[i][j] 保存的是（ ）。
26、（程序见第22题）若把一次求最大公约数的运算视为 O（1），则第 17—22 行建表过程的时间复杂度为（ ）。
27、（程序见第22题）设 x 为一次查询的区间长度（即 x=R−L+1），则使得 lg[x]=5 的 x 的取值范围是（ ）。
28、阅读程序（3）
说明：输入第一行为结点个数 n，第二行为 n−1 个整数，依次表示结点 2—n 的父结点编号，满足 2≤n≤10000 且 1≤fa[i]<i，根结点为 1。

当 n=5，fa[2]∼fa[5]={1,2,3,4} 时，程序输出 4。（ ）
29、（程序见第28题）程序输出前，f[1] 的值一定等于 ans 的值。（ ）
30、（程序见第28题）将第 10—12 行与第 13—15 行两个 if 语句的顺序交换后，程序输出结果不受影响。（ ）
31、（程序见第28题）程序输出的 ans 表示的是（ ）。
32、（程序见第28题）当 n=7，fa[2]∼fa[7]={1,1,2,2,3,3} 时，输出为（ ）。
33、（程序见第28题）当 n=10，满足输出为 9 的合法输入种类数为（ ）。
34、完善程序 
（1）平衡路线
给定一张有 n 个顶点、m 条边的无向图，每条边带有符号 '+' 或 '-'。对于一条从顶点 s 到顶点 t 的路线，允许重复经过顶点和边。定义路线的权值为 |n₊ − n₋|（n₊、n₋ 分别为经过的 '+' 边数和 '-' 边数）。请计算从 s 到 t 的路线的最小权值；若不存在路线，输出 −1。以下程序通过 BFS 求出最小权值。

① 处应填（ ）。
35、（程序见第34题）② 处应填（ ）。
36、（程序见第34题）③ 处应填（ ）。
37、（程序见第34题）④ 处应填（ ）。
38、（程序见第34题）⑤ 处应填（ ）。
39、完善程序（2）标准答案构造
有 n 名学生参加考试，考试共有 m 道选择题，每道题只有 A、B 两个选项。第 i 名学生的答案用
一个长度为 m、仅包含 A 和 B 的字符串表示。若最终公布的标准答案与该学生在某道题上的答案
相同，该学生在这道题上得 1 分，否则不得分；记第 i 名学生最终总分为 r_i。给定每名学生对应
的数值 x_i，需要构造一份标准答案，使 ∑|r_i − x_i| 尽可能大。可辨认数据范围：1≤m≤300，
0≤x_i≤m；学生数 n 的范围被遮挡，程序枚举 2^n 个状态，原卷具体数字无法确认。从符号选择
的角度处理绝对值之和。


① 处应填（ ）。
40、（程序见第39题）② 处应填（ ）。
41、（程序见第39题）③ 处应填（ ）。
42、（程序见第39题）④ 处应填（ ）。
43、（程序见第39题）⑤ 处应填（ ）。
更多问卷 复制此问卷