CSP-S2025初赛真题

ID: 3018

客观题

尝试: 11

已通过: 0

难度: 10

上传者:

吴乐辉

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

第 1 题 有 $5$ 个红色球和 $5$ 个蓝色球，它们除了颜色之外完全相同。将这 $10$ 个球排成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法？

$25$
$30$
$6$
$120$

第 2 题 在 $KMP$ 算法中，对于模式串 P="abacaba"，其 $next$ 数组 ( $next[i]$ 定义为模式串 $P[0...i]$ 最长公共前后缀的长度，且数组下标从 $0$ 开始) 的值是什么？

$\{0, 0, 1, 0, 1, 2, 3\}$
$\{0, 1, 2, 3, 4, 5, 6\}$
$\{0, 0, 1, 1, 2, 2, 3\}$
$\{0, 0, 0, 0, 1, 2, 3\}$

第 3 题 对一个大小为 $16$ (下标 $0\sim 15$ ) 的数组上构造满线段树，查询区间 $[3, 11]$ 时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？

$7$
$8$
$9$
$10$

第 4 题 将字符串 "cat", "car", "cart", "case", "dog", "do" 插入一个空的 $Trie$ 树（前缀树）中，构造完成 $Trie$ 树（包括根节点）共有多少个结点？

$8$
$9$
$10$
$11$

第 5 题 对于一个包含 $n$ 个结点和 $m$ 条边的有向无环图 ( $DAG$ )，其拓扑排序的结果有多少种可能？

只有 $1$ 种
最多 $n$ 种
等于 $n-m$ 种
以上都不对

第 6 题 在一个大小为 $13$ 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 $H(key)=key\ mod\ 13$ ，依次插入关键字 $18, 26, 35, 9, 68, 74$ ，插入 $74$ 后，它最终被放置在哪个索引位置？

$5$
$7$
$9$
$11$

第 7 题 一个包含 $8$ 个顶点的完全图（顶点的编号为 $1$ 到 $8$ ），任意两点之间的边权重等于两顶点编号的差的绝对值。例如，顶点 $3$ 和 $7$ 之间的边权重为 $|7 - 3| = 4$ 。该图的最小生成树总权重是多少？

$7$
$8$
$9$
$10$

第 8 题 如果一棵二叉搜索树的后序遍历序列是 $2, 5, 4, 8, 12, 10, 6$ ，那么该树的前序遍历是什么？

$6, 4, 2, 5, 10, 8, 12$
$6, 4, 5, 2, 10, 12, 8$
$2, 4, 5, 6, 8, 10, 12$
$12, 8, 10, 5, 2, 4, 6$

第 9 题 一个 $01$ 背包问题，背包容量为 $20$ ，现有 $5$ 个物品，其重量和价值分别为 $7, 5, 4, 3, 6$ 和 $15, 12, 9, 7, 13$ 。装入背包的物品能获得的最大总价值是多少？

$43$
$41$
$45$
$44$

第 10 题 在一棵以结点 $1$ 为根的树中，结点 $12$ 和结点 $18$ 的最近公共祖先 ( $LCA$ ) 是结点 $4$ 。那么下列哪个结点的 $LCA$ 组合是不可能出现的？

$LCA(12, 4) = 4$
$LCA(18, 4) = 4$
$LCA(12, 18, 4) = 4$
$LCA(12, 1) = 4$

第 11 题 递归关系式 $T(n) = 2T(\frac{n}{2}) + O(n^2)$ 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？

$O(n)$
$O(nlogn)$
$O(n^2)$
$O(n^2logn)$

第 12 题 在一个初始为空的最小堆 $(min-heap)$ 中，依次插入元素 $20, 12, 15, 8, 10, 5$ 。然后连续执行两次删除最小值 ( $delete-min$ ) 操作，请问此时堆顶元素是什么？

$10$
$12$
$15$
$20$

第 13 题 $1$ 到 $1000$ 之间，不能被 $2、3、5$ 中任意一个数整除的整数有多少个？

$266$
$267$
$333$
$734$

第 14 题 斐波那契数列的定义为 $F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2)$ 。使用朴素递归方法计算 $F(n)$ 的时间复杂度是指数级的。而使用动态规划（或迭代）方法的时间复杂度是线性的。适应这种巨大差异的根本原因是？

递归函数调用栈开销过大
操作系统对递归深度有限制
朴素递归中存在大量的重叠子问题未被重复利用
动态规划使用了更少的数据存储空间

第 15 题 有 $5$ 个独立的、不可抢占的任务 $A1, A2, A3, A4, A5$ 需要在一台机器上执行（从时间 $0$ 开始执行），每个任务都有对应的处理时长和截止时刻，按顺序分别为 $3,4,2,5,1$ 和 $5,10,3,15,11$ 。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务？

处理时间最短的任务 $A5$
截止时间最早的任务 $A3$
处理时间最长的任务 $A4$
任一任务都可以

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

（1）

01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 bool flag[27];
05 int n;
06 int p[27];
07 int ans = 0;
08 void dfs(int k) {
09    if (k == n + 1){
10        ++ ans;
11        return;
12    }
13    for (int i = 1; i <= n; ++i) {
14        if (flag[i]) continue;
15        if (k > 1 && i == p[k - 1] + 1) continue;
16        p[k] = i;
17        flag[i] = true;
18        dfs(k + 1);
19        flag[i] = false;
20    }
21    return;
22 }
23 int main() {
24    scanf("%d", &n);
25    dfs(1);
26    printf("%d\n", ans);
27    return 0;
28 }

第 16 题 ( $1$ 分) 当输入的 $n=3$ 的时候，程序输出的答案为 $3$ 。

第 17 题 在 dfs 函数运行过程中， $k$ 的取值会满足 $1\le k\le n+1$ 。

第 18 题 删除第 $19$ 行的 flag[i]=false，对答案不会产生影响。

第 19 题 当输入的 $n=4$ 的时候，程序输出的答案为 ( )。

$11$
$12$
$24$
$9$

第 20 题 如果因为某些问题，导致程序运行第 $25$ 行的 dfs 函数之前，数组 $p$ 的初值并不全为 $0$ ，则对程序的影响是 ( )。

输出的答案比原答案要小
无法确定输出的答案
程序可能陷入死循环
没有影响

第 21 题 假如删去第 $14$ 行的 if(flag[i])continue，输入 $3$ ，得到的输出答案是 ( )。

$27$
$3$
$16$
$12$

（2）

01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 #define ll long long
05 int cnt_broken = 0;
06 int cnt_check = 0;
07 int n, k;
08 inline bool check(int h) {
09    printf("now check:%d\n", h);
10    ++cnt_check;
11    if (cnt_broken == 2) {
12       printf("You have no egg!\n");
13       return false;
14   }
15   if (h >= k) {
16       ++cnt_broken;
17       return true;
18   } else {
19       return false;
10   }
21 }
22 inline bool assert_ans(int h) {
23    if (h == k) {
24        printf("You are Right using %d checks\n", cnt_check);
25        return true;
26    } else {
27        printf("Wrong answer!\n");
28        return false;
29    }
30 }
31 inline void guess1(int n) {
32    for (int i = 1; i <= n; ++i) {
33        if (check(i)) {
34            assert_ans(i);
35            return;
36        }
37    }
38 }
39 inline void guess2(int n) {
40    int w = 0;
41    for (w = 1; w * (w + 1) / 2 < n; ++w)
42        ;
43    for (int ti = w, nh = w;; --ti, nh += ti, nh = std::min(nh, n)) {
44        if (check(nh)) {
45            for (int j = nh - ti + 1; j < nh; ++j) {
46                if (check(j)) {
47                    assert_ans(j);
48                    return;
49                }
50            }
51            assert_ans(nh);
52            return;
53        }
54    }
55 }
56 int main() {
57    scanf("%d", &n, &k);
58    int t;
59    scanf("%d", &t);
60    if (t == 1) {
61        guess1(n);
62    } else {
63        guess2(n);
64    }
65    return 0;
66 }

(注意：下述的猜测数为调用 check 函数的次数 (即 cnt_check 的值)；猜测正确的含义为 assert_ans 函数 return true (执行第 $25$ 行所在分支)的情况；所有输入保证 $1 \le k \le n$ 。)

第 22 题 当输入为 6 5 1 时，猜测次数为 $5$ ；当输入为 6 5 2 时，猜测次数为 $3$ 。

第 23 题 不管输入的 $n$ 和 $k$ 具体为多少， $t=2$ 时的猜测数总是小于等于 $t=1$ 时的猜测数。

第 24 题 不管 $t=1$ 或 $t=2$ ，程序都一定会得到正确结果。

第 25 题 函数 guess1 在运行过程中，cnt_broken 的值最多为 ( )。

第 26 题 函数 guess2 在运行过程中，最多使用的猜测次数的量级为 ( )。

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

第 27 题 当输入的 $n=100$ 的时候，代码中 $t=1$ 和 $t=2$ 分别需要的猜测次数最多分别为 ( )。

$100, 14$
$100, 13$
$99, 14$
$99, 13$

（3）

01  #include <algorithm>
02  #include <cstdio>
03  #include <cstring>
04  #include <vector>
05  #define ll long long
06  int n, m;
07  std::vector<int> k, p;
08  inline int mpow(int x, int k) {
09      int ans = 1;
10      for (; k; k = k >> 1, x = x * x) {
11          if (k & 1)
12              ans = ans * x;
13      }
14      return ans;
15  }
16  std::vector<int> ans1, ans2;
17  int cnt1, cnt2;
18  inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
19      if (l > r) {
20          ++cnt;
21          ans.push_back(v);
22          return;
23      }
24      for (int i = 1; i <= m; ++i) {
25          dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
26      }
27      return;
28  }
29  std::vector<int> cntans1;
30  int main() {
31      scanf("%d%d", &n, &m);
32      k.resize(n + 1);
33      p.resize(n + 1);
34      for (int i = 1; i <= n; ++i) {
35          scanf("%d%d", &k[i], &p[i]);
36      }
37      dfs(ans1, cnt1, 1, n >> 1, 0);
38      dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
39      std::sort(ans1.begin(), ans1.end());
40      int newcnt1 = 1;
41      cntans1.push_back(1);
42      for (int i = 1; i < cnt1; ++i) {
43          if (ans1[i] == ans1[newcnt1 - 1]) {
44              ++cntans1[newcnt1 - 1];
45          } else {
46              ans1[newcnt1++] = ans1[i];
47              cntans1.push_back(1);
48          }
49      }
50      cnt1 = newcnt1;
51      std::sort(ans2.begin(), ans2.end());
52      int las = 0;
53      ll ans = 0;
54      for (int i = cnt2 - 1; i >= 0; --i) {
55          for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las)
56              ;
57          if (las < cnt1 && ans1[las] + ans2[i] == 0)
58              ans += cntans1[las];
59      }
60      printf("%lld\n", ans);
61      return 0;
62  }

第 28 题 删除第 $51$ 行的 std::sort(ans2.begin(), ans2.end()); 后，代码输出的结果不会受到影响。

第 29 题 假设计算过程中不发生溢出，函数 mpow(x, k) 的功能是求出 $x^k$ 的取值。( )

第 30 题 代码中第 $39$ 行到第 $50$ 行的目的是为了将 $ans1$ 数组进行去重操作。( )

第 31 题 当输入为 3 15 1 2 -1 2 1 2 时，输出结果为 ( )

$4$
$8$
$0$
$10$

第 32 题 记程序结束前 $p$ 数组元素的最大值为 $P$ ，则该代码的时间复杂度是 ( )

$O(n)$
$O(m^n log m^n)$
$O(m^{\frac{n}{2}} log m^{\frac{n}{2}})$
$O(m^{\frac{n}{2}}(log m^{\frac{n}{2}} + log P))$

第 33 题 本题所求的是 ( )。

满足 $a, b, c ∈ [1, m]$ 的整数方程 $a^3+ b^3 = c^3$ 的解的数量
满足 $a, b, c ∈ [1, m]$ 的整数方程 $a^2 + b^2 = c^2$ 的解的数量
满足 $xi ∈ [0, m]$ 的整数方程 $\sum_{i=1}^n k_ix_i^{p_i} = 0$ 的解的数量
满足 $xi ∈ [1, m]$ 的整数方程 $\sum_{i=1}^n k_ix_i^{p_i} = 0$ 的解的数量

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

（1）给定一个含 $N$ 个点、 $M$ 条边的带权无向图，边权非负。起点为 $S$ ，终点为 $T$ 。对于一条 $S$ 到 $T$ 的路径，可以在整条路径中，至多选择一条边作为免费边：当第一次经过这条被选中的边时，费用视为 $0$ ；如果之后再次经过该边，则仍按其原始权重计费。点和边均允许重复经过。求从 $S$ 到 $T$ 的最小总费用。

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const long long INF = 1e18;

struct Edge {
  int to;
  int weight;
};

struct State {
  long long dist;
  int u;
  int used_freebie; // 0 for not used, 1 for used
  bool operator>(const State &other) const {
      return dist > other.dist;
  }
};

int main() {
  int n, m, s, t;
  cin >> n >> m >> s >> t;

  vector<vector<Edge>> adj(n + 1);
  for (int i = 0; i < m; ++i) {
      int u, v, w;
      cin >> u >> v >> w;
      adj[u].push_back({v, w});
      adj[v].push_back({u, w});
  }

  vector<vector<long long>> d(n + 1, vector<long long>(2, INF));
  priority_queue<State, vector<State>, greater<State>> pq;

  d[s][0] = 0;
  pq.push({0, s, __1__});

  while (!pq.empty()) {
      State current = pq.top();
      pq.pop();

      long long dist = current.dist;
      int u = current.u;
      int used = current.used_freebie;

      if (dist > __2__) {
          continue;
      }

      for (const auto &edge : adj[u]) {
          int v = edge.to;
          int w = edge.weight;

          if (d[u][used] + w < __3__) {
              __3__ = d[u][used] + w;
              pq.push({__3__, v, used});
          }

          if (used == 0) {
              if (__4__ < d[v][1]) {
                  d[v][1] = __4__;
                  pq.push({d[v][1], v, 1});
              }
          }
      }
  }

  cout << __5__ << endl;
  return 0;
}

第 34 题 ①处应填( )

0
1
-1
false

第 35 题 ②处应填( )

d[u][!used]
d[u][used]
d[t][used]
INF

第 36 题 ③处应填( )

d[v][1]
d[v][used]
d[u][used]
d[v][0]

第 37 题 ④处应填( )

d[v][0]
d[v][1]
d[u][0]
d[u][1]

第 38 题 ⑤处应填( )

d[t][1]
d[t][0]
min(d[t][0], d[t][1])
d[t][0] + d[t][1]

（2）工厂有 $n$ 条生产线（编号 $0\sim n-1$ ），已知其中恰有一条生产线存在缺陷。工厂打算通过客户反馈来测试生产线，从而找到存在缺陷的生产线。

每一轮测试为：从若干生产线的产品取样合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退货（结果记为 $1$ ），否则正常收货（记为 $0$ ）。受售后压力限制，在所有发货批次中，最多只能有 $k$ 次退货（即结果为 $1$ 的次数 $\le k$ ）。

工厂的目标是：设计最少的测试轮数 $w$ （发货总批次），保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;

long long comb(int w, int i) {
  if (i < 0 || i > w) {
      return 0;
  }
  long long res = 1;
  for (int t = 1; t <= i; ++t) {
      res = res * (w - t + 1) / t;
  }
  return res;
}

// 计算长度为 w、1 的个数 ≤ k 的码字总数
long long count_patterns(int w, int k) {
  long long total = 0;
  for (int t = 0; t <= min(w, k); ++t) {
      total += comb(w, t);
  }
  return total;
}

// 抽象测试接口
int test_subset(const vector<vector<int>> &plan);

int solve(int n, int k) {
  // === 第 1 步：求最小 w ===
  int w = 1;
  while (__1__) {
      ++w;
  }
  cout << w << endl;

  // === 第 2 步：生成测试方案 ===
  vector<vector<int>> code(n, vector<int>(w, 0));
  int idx = 0;
  for (int ones = 0; ones <= k && idx < n; ++ones) {
      vector<int> bits(w, 0);
      fill(bits.begin(), bits.begin() + ones, 1);
      do {
          for (int b = 0; b < w; ++b) {
              code[idx][b] = bits[b];
          }
          ++idx;
          if (idx >= n) {
              break;
          }
      } while (std::__2__);
  }

  vector<vector<int>> plan(w);
  for (int i = 0; i < w; ++i) {
      for (int j = 0; j < n; ++j) {
          if (__3__) {
              plan[i].push_back(j);
          }
      }
  }

  // === 第 3 步：调用测试接口 ===
  int signature = test_subset(plan);

  // === 第 4 步：结果解码 ===
  vector<int> sig_bits(w, 0);
  for (int i = 0; i < w; ++i) {
      if (__4__) {
          sig_bits[i] = 1;
      }
  }

  for (int j = 0; j < n; ++j) {
      if (__5__) return j;
  }
}

int main() {
  int n, k;
  cin >> n >> k;
  int ans = solve(n, k);
  cout << ans << endl;
  return 0;
}

第 39 题 ①处应填( )

(1 << w) < n
count_patterns(w, k) < n
count_patterns(k, w) < n
comb(w, k) < n

第 40 题 ②处应填( )

next_permutation(bits.begin(), bits.end())
prev_permutation(bits.begin(), bits.end())
next_permutation(bits.begin(), bits.begin()+ones)
prev_permutation(bits.begin(), bits.begin()+ones)

第 41 题 ③处应填( )

(j>>i) & 1
(i>>j) & 1
code[i][j] == 1
code[j][i] == 1

第 42 题 ④处应填( )

(signature >> i) & 1
(signature >> i) ^ 1
signature | (1 << i)
(signature >> i) | 1

第 43 题 ⑤处应填( )

is_permutation(code[j].begin(), code[j].end(), sig_bits.begin())
code[j] == sig_bits
plan[j] == sig_bits
code[j][i] == sig_bits[i]

13.5 #S2025. CSP-S2025初赛真题

登录