CSP-S 2026 初赛模拟卷 1

ID: 3034

客观题

尝试: 4

已通过: 0

难度: 10

上传者:

吴乐辉

信息学奥赛 CSP-S 2026 初赛模拟卷 1

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

第 1 题 在 $NOI\ Linux$ 中，使用 $g$ ++ 编译 $C$ ++ 程序时，如果要开启所有警告信息，应该使用选项（　　）。 {{ select(1) }}

-O2
-g
-static
-Wall

第 2 题 如果 $x$ 是正整数，则表达式 (x & (x-1)) == 0 成立当且仅当（　　）。 {{ select(2) }}

$x$ 是偶数
$x$ 是 $2$ 的幂次
$x$ 的二进制表示中没有相邻的 $1$
$x$ 等于 $1$

第 3 题 操作系统的主要功能不包括（　　）。 {{ select(3) }}

进程管理
内存管理
数据库管理
文件管理

第 4 题 以下问题中，贪心算法不能得到最优解的是（　　）。 {{ select(4) }}

哈夫曼编码
$Dijkstra$ 算法
$01$ 背包
$Prim$ 算法

第 5 题 采用长度为 $7$ 的哈希表，哈希函数 $h(k) = k\%7$ ，采用线性探查法解决冲突。依次插入关键字 $19,26,35,48,55$ ，最后 $55$ 存放在位置（　　）。 {{ select(5) }}

第 6 题 以下关于欧拉图的叙述中，正确的是（　　）。 {{ select(6) }}

欧拉图必须包含欧拉回路
欧拉图一定不包含哈密顿回路
所有顶点度数为偶数的无向图一定是欧拉图
有且仅有两个奇度数顶点的连通无向图是欧拉图

第 7 题 以下给定代码段的时间复杂度为（　　）。

for (int i = 1; i <= n; i *= 2) {
	for (int j = 1; j <= i; j++) {
		// O(1) 操作
	}
}

$O(n)$
$O(n\log n)$
$O(n^2)$
$O(\log n)$

第 8 题 定义函数 $f(n) = f(n-1) + 2f(n-2)$ ，其中 $f(0) = 1$ ， $f(1) = 3$ ，则 $f(4)$ 的值为（　　）。 {{ select(8) }}

$11$
$17$
$21$
$25$

第 9 题 对长度为 $n$ 的有序数组进行二分查找，（　　）不是必须满足的条件。 {{ select(9) }}

数组元素必须连续存储
数组必须按关键字有序
必须能够随机访问元素
数组元素必须从小到大排好序

第 10 题 在模 $11$ 运算中， $7$ 的乘法逆元是（　　）。 {{ select(10) }}

第 11 题 在 $4\times 5$ 的网格中，起点为左上角的格子，终点为右下角的格子，每次可以移动到右方、下方、右下方的格子，则总共有（　　）种不同的路径。 {{ select(11) }}

$20$
$35$
$126$
$129$

第 12 题 一个无向图至少需要 $3$ 种颜色对顶点着色（才能保证任何一条边的两端不同色），当且仅当该图（　　）。 {{ select(12) }}

是二分图
包含奇环
是完全图
顶点数至少为 $3$

第 13 题 在以下排序算法中，最坏情况下时间复杂度为 $O(n\log n)$ 且是稳定排序的是（　　）。 {{ select(13) }}

快速排序
堆排序
归并排序
希尔排序

第 14 题 要交换两个整数 $a$ 和 $b$ 的值，不使用临时变量，最安全稳妥的办法是（　　）。 {{ select(14) }}

a = b - a; b = b - a; a = a + b;
a = a ^ b; b = a ^ b; a = a ^ b;
a = a * b; b = a / b; a = a / b;
a = a + b; b = a - b; a = a - b;

第 15 题 已知哈夫曼树有 $5$ 个叶节点，其权值分别为 $1,3,5,7,9$ ，该树的带权路径长度为（　　）。 {{ select(15) }}

$50$
$54$
$60$
$65$

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

(1)

1  #include <iostream>
2  #include <vector>
3  #include <algorithm>
4  using namespace std;
5
6  int main() {
7      int n, m, k;
8      cin >> n >> m >> k;
9      vector<int> nums(n);
10     for (int i = 0; i < n; i++) cin >> nums[i]; // 保证输入的都是正整数
11
12     vector<vector<bool> > dp(k + 1, vector<bool>(m + 1, false));
13     dp[0][0] = true;
14     for (int idx = 0; idx < n; idx++) {
15         int num = nums[idx];
16         for (int i = k; i >= 1; i--) {
17             for (int j = m; j >= num; j--) {
18                 if (dp[i - 1][j - num]) {
19                     dp[i][j] = true;
20                 }
21             }
22         }
23     }
24
25     if (dp[k][m]) {
26         cout << "Yes" << endl;
27     } else {
28         cout << "No" << endl;
29     }
30     return 0;
31 }

判断题

第 16 题 输入 5 10 3 1 2 3 4 5 时，输出结果为 $Yes$ 。　　（　　） {{ select(16) }}

第 17 题 如果 $m < k$ ，最终输出肯定是 $No$ 。　　（　　） {{ select(17) }}

第 18 题 将 for (int i = k; i >= 1; i--) 改为正序遍历，程序结果不变。　　（　　） {{ select(18) }}

选择题

第 19 题 dp[i][j] 的状态定义正确的是（　　）。 {{ select(19) }}

使用前 $i$ 个数，能否组成 $j$
使用不超过 $i$ 个数，能否组成 $j$
使用恰好 $i$ 个数，能否组成 $j$
使用最少 $i$ 个数，能否组成 $j$

第 20 题 （4 分）当 $n > 0、k = 0$ 且 $m = 0$ 时，下列说法中正确的是（　　）。 {{ select(20) }}

程序输出 $Yes$
程序输出 $No$
程序运行过程中会报错
程序无输出

(2)

1  #include <iostream>
2  using namespace std;
3  typedef long long ll;
4
5  ll fPow(ll a, ll b, ll mod) {
6      ll res = 1;
7      a %= mod;
8      while (b > 0) {
9          if (b & 1) res = (res * a) % mod;
10         a = (a * a) % mod;
11         b >>= 1;
12     }
13     return res;
14 }
15
16 int main() {
17     ll n, p;
18     cin >> n >> p;
19     if (n >= p) {
20         cout << 0 << endl;
21         return 0;
22     }
23     ll res = p - 1;
24     for (ll i = n + 1; i < p; i++)
25         res = (res * fPow(i, p - 2, p)) % p;
26
27     cout << res << endl;
28     return 0;
29 }

判断题

第 21 题 输入 $n = 1,p = 5$ 时，输出结果为 $4$ 。　　（　　） {{ select(21) }}

第 22 题 当 p 是合数时，程序仍然能正常运行。　　（　　） {{ select(22) }}

第 23 题 fPow(2,10,1000) 的返回值是 $24$ 。　　（　　） {{ select(23) }}

选择题

第 24 题 如果输入 $n = 0,p = 7$ ，程序的输出结果是（　　）。 {{ select(24) }}

第 25 题 （ $4$ 分）如果 $p$ 是素数，程序的时间复杂度是（　　）。 {{ select(25) }}

$O(p)$
$O(p\log p)$
$O(p^2)$
$O(1)$

(3)

1  #include <iostream>
2  using namespace std;
3
4  bool isPrime(int n) {
5      if (n < 2) return false;
6      if (n == 2 || n == 3) return true;
7      if ((n & 1) == 0) return false;
8      for (int i = 3; i * i <= n; i += 2)
9          if (n % i == 0) return false;
10     return true;
11 }
12
13 int main() {
14     int l, r;
15     cin >> l >> r;
16     int cnt = 0;
17
18     for (int i = l; i <= r; i++) {
19         if (isPrime(i)) {
20             int power2 = 1;
21             while (power2 < i) power2 <<= 1;
22             if ((power2 - i) <= 2 || (i - (power2 >> 1)) <= 2)
23                 cnt++;
24         }
25     }
26     cout << cnt << endl;
27     return 0;
28 }

判断题

第 26 题 对于任意大于 $2$ 的素数，isPrime 函数中的循环次数严格小于 $\lfloor\sqrt{n}/2\rfloor$ 。　　（　　） {{ select(26) }}

第 27 题 如果区间 $[l,r]$ 内没有素数，程序输出 $0$ 。　　（　　） {{ select(27) }}

第 28 题 若输入 5 7，则程序输出 $0$ 。　　（　　） {{ select(28) }}

选择题

第 29 题 （ $4$ 分）输入 5 31 时，程序的输出结果为（　　）。 {{ select(29) }}

第 30 题 （ $4$ 分）该程序在最坏情况下的时间复杂度是（　　）。 {{ select(30) }}

$O(r)$
$O(r\sqrt{r})$
$O(r^2)$
$O(2^r)$

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

(1)

求解同余方程组： $x \equiv a_i \pmod{m_i}$ ， $i = 0,\cdots,n-1$ ，输出 $x$ 的最小正整数解，若无解则输出 -1。

1  #include <iostream>
2  #include <vector>
3  using namespace std;
4  typedef long long ll;
5
6  ll exgcd(___①___) {
7      if (___②___) {
8          x = 1;
9          y = 0;
10         return a;
11     }
12     ll g = exgcd(b, a % b, y, x);
13     y = y - a / b * x;
14     return g;
15 }
16
17 ll mod(ll a, ll b) {
18     return (a % b + b) % b;
19 }
20
21 ll crt(vector<ll> &a, vector<ll> &m) {
22     int n = a.size();
23     ll a1 = a[0], m1 = m[0];
24
25     for (int i = 1; i < n; i++) {
26         ll a2 = a[i], m2 = m[i];
27         ll x, y;
28         ll g = exgcd(m1, m2, x, y);
29         if (___③___) return -1;
30
31         ll p, q;
32         exgcd(m1 / g, m2 / g, p, q);
33
34         ___④___;
35
36         ll x_val = (a1 + m1 * (a2 - a1) / g * p) % lcm;
37         a1 = mod(x_val, lcm);
38         m1 = lcm;
39     }
40     return ___⑤___;
41 }
42
43 int main() {
44     int n;
45     cin >> n;
46     vector<ll> a(n), m(n);
47     for (int i = 0; i < n; i++) // 表示一个方程 x ≡ a (mod m)
48         cin >> a[i] >> m[i];
49     ll res = crt(a, m);
50     if (res == -1) cout << -1 << endl;
51     else cout << res << endl;
52     return 0;
53 }

第 31 题 ① 处应填（　　）。 {{ select(31) }}

int a, int b, int x, int y
int a, int b, int &x, int &y
ll a, ll b, ll x, ll y
ll a, ll b, ll &x, ll &y

第 32 题 ② 处应填（　　）。 {{ select(32) }}

a == 0
b == 0
x == 0
y == 0

第 33 题 ③ 处应填（　　）。 {{ select(33) }}

a1 % g != 0
a2 % g != 0
a1 % g == a2 % g
(a2 - a1) % g != 0

第 34 题 ④ 处应填（　　）。 {{ select(34) }}

ll lcm = m1 * m2;
ll lcm = m1 / g * m2;
ll lcm = g / m1 * m2;
ll lcm = m1 * g / m2;

第 35 题 ⑤ 处应填（　　）。 {{ select(35) }}

a1
m1
-1
lcm

(2)

给定一棵有 $n$ 个节点的树，树以节点 $1$ 为根。程序使用倍增算法求解树上任意两个节点的最近公共祖先（ $LCA$ ）。最近公共祖先是指两个节点在树上的公共祖先中深度最大的那个节点。当有多组问询时，按照问询的顺序，依次输出每个问询的答案。

1  #include <bits/stdc++.h>
2  using namespace std;
3  const int N = 200009;
4
5  vector<int> to[N];
6  int L, n, q, p[N][20];
7  int tI[N], tO[N], timer;
8
9  void dfs(int u, int fa) {
10     tI[u] = ++timer;
11     p[u][0] = fa;
12     for (int i = 1; i <= L; ++i) p[u][i] = ___①___;
13     for (int i = 0; i < to[u].size(); ++i)
14         if (to[u][i] != fa) dfs(to[u][i], u);
15     tO[u] = ++timer;
16 }
17
18 bool up(int u, int v) {
19     return ___②___;
20 }
21
22 int lca(int u, int v) {
23     if (up(u, v)) return u;
24     if (up(v, u)) return v;
25     for (int i = L; i >= 0; --i)
26         if (___③___) u = p[u][i];
27     return ___④___;
28 }
29
30 int main() {
31     cin >> n;
32     for (int i = 1; i <= n - 1; i++) {
33         int u, v;
34         cin >> u >> v;
35         to[u].push_back(v);
36         to[v].push_back(u);
37     }
38     L = 1;
39     while (___⑤___) ++L;
40     dfs(1, 0);
41
42     cin >> q;
43     for (int i = 1; i <= q; i++) {
44         int x, y;
45         cin >> x >> y;
46         cout << lca(x, y) << endl;
47     }
48     return 0;
49 }

第 36 题 ① 处应填（　　）。 {{ select(36) }}

p[p[u][i]][i-1]
p[p[u][i-1]][i-1]
p[p[fa][i]][i-1]
p[p[fa][i-1]][i-1]

第 37 题 ② 处应填（　　）。 {{ select(37) }}

u && tI[u] <= tI[v] && tO[v] <= tO[u]
u || tI[u] <= tI[v] && tO[v] <= tO[u]
!u && tI[u] <= tI[v] && tO[v] <= tO[u]
!u || tI[u] <= tI[v] && tO[v] <= tO[u]

第 38 题 ③ 处应填（　　）。 {{ select(38) }}

!up(p[u][i], v)
up(p[u][i], v)
!up(u, p[v][i])
up(u, p[v][i])

第 39 题 ④ 处应填（　　）。 {{ select(39) }}

u
v
p[u][0]
p[v][0]

第 40 题 ⑤ 处应填（　　）。 {{ select(40) }}

(1 << L) <= n
L <= n
(1 << L) < n
L < n

#S0001. CSP-S 2026 初赛模拟卷 1

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

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

(1)

(2)

(3)

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

(1)

(2)

登录