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

1. Linux 操作系统中，以下哪个命令是分页显示普通文本类型文件 csp？{{ select(1) }}

• A. vi csp
• B. more csp
• C. cat csp
• D. ls csp

2. 表达式 (1 + 34) * 5 - 56 / 7 的后缀表达式为（　　）。{{ select(2) }}

• A. 1 34 + 5 * 56 7 / -
• B. 1 + 34 * 5 - 56 / 7
• C. - * + 1 34 5 / 56 7
• D. 1 34 + 5 56 7 - * /

3. 调试工具 GDB 中的不进入函数的单步执行语句的调试命令是（　　）。{{ select(3) }}

• A. next 或 n
• B. step 或 s
• C. break 或 b
• D. continue 或 c

4. 小明和小杨轮流掷硬币（每次掷硬币正面朝上概率是 $2/3$，反面朝上的概率是 $1/3$），小明先掷，如果谁先掷到正面算谁赢，请问小明赢的概率是（　　）。{{ select(4) }}

• A. $2/3$
• B. $1/2$
• C. $3/4$
• D. $3/5$

5. 以下哪个说法是正确的？（　　）{{ select(5) }}

• A. CSP-S 初赛交卷后考试没结束前可以回考场取遗忘的身份证
• B. CSP-S 的认证选手可携带已关机的手机放在自己身边的包里
• C. CSP-S 的认证选手在认证时间内上厕所的时候可携带手机
• D. CCF 全称是中国计算机学会

6. 解决区间查询 RMQ 问题通常使用（　　）。{{ select(6) }}

• A. 哈夫曼树
• B. 并查集
• C. 哈希表
• D. 稀疏表

7. 由 $1, 3, 5, 7, 9$ 五个不同数值的点构成的二叉搜索树有（　　）种。{{ select(7) }}

• A. $30$
• B. $35$
• C. $42$
• D. $60$

8. 假设我们有以下的 C++ 代码：

   unsigned char a = 143, b = 3, c = 4;
   a <<= 2;
   int res = a | (b + c >> 1);
   

   请问，res 的值是多少？（　　）{{ select(8) }}

• A. 63
• B. 61
• C. 573
• D. 575

9. 关于贪心算法，下面的说法哪些是不正确的？（　　）{{ select(9) }}

• A. 哈夫曼编码用到了贪心算法的思想
• B. 最小生成树的 Prim 算法用到了贪心算法的思想
• C. 0-1 背包问题可以用贪心算法解决
• D. 最小生成树的 Kruskal 算法用到了贪心算法的思想

10. 下列说法中哪个关于图的说法不正确？（　　）{{ select(10) }}

• A. 判定一个无向图是否为连通图可以从任意一点出发用 DFS 算法进行搜索
• B. 对于有向图，如果拓扑排序可以完成，则说明图中有环
• C. 标准的 Bellman–Ford 算法中会进行松弛操作
• D. 除 Tarjan 算法外，还可以使用 Kosaraju 算法来求解强连通分量

11. 设文本串为 $S$，其长度为 $n$，模式串为 $T$，其长度为 $m$，则 KMP 算法的时间复杂度为（　　）。{{ select(11) }}

• A. $\mathcal O (n + m)$
• B. $\mathcal O (n \cdot m)$
• C. $\mathcal O (n \log m)$
• D. $\mathcal O (m \log n)$

12. 设 A = true，B = false，C = false，D = true，以下逻辑运算表达式值为假的是（　　）。{{ select(12) }}

• A. $((A \land B) \lor C) \land D$
• B. $A \land ((B \lor C) \lor D)$
• C. $(A \land (B \lor C)) \lor D$
• D. $(A \lor B) \land (C \lor D)$

13. BFS 算法通常会用到的数据结构是（　　）。{{ select(13) }}

• A. binary tree
• B. list
• C. stack
• D. queue

14. 若三个正整数 $a, b, c$ 的位数之和为 $8$，且组成 $a, b, c$ 的 $8$ 个数码能排列为 $2, 0, 2, 4, 0, 9, 0, 8$，则称 $(a, b, c)$ 为“幸运数组”，例如 $(9, 8, 202400)$ 是一个幸运数组。满足 $10<a<b<c$ 的幸运数组 $(a, b, c)$ 的个数为（　　）。{{ select(14) }}

• A. $520$
• B. $300$
• C. $480$
• D. $591$

15. 假设有以下的 C++ 代码：

    int a[] = {1, 1, 3, 3, 5, 7, 9};
    cout << (lower_bound(a, a + 7, 3) - a) << " ";
    cout << (upper_bound(a, a + 7, 7) - a) << endl;
    

    请问，上述输出的值是什么？（　　）{{ select(15) }}

• A. 2 5
• B. 1 5
• C. 2 6
• D. 1 6

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

1. 01  #include <bits/stdc++.h>
   02  using namespace std;
   03  int t, n, m, q, k, a, b;
   04  vector<pair<int,int> >G;
   05  bool vis[1001];
   06  bool dfs(int now, int dep) {
   07      if(now == m) return true;
   08      int u = G[now].first, v = G[now].second;
   09      while((vis[u] || vis[v]) && now < m) {
   10          now++;
   11          if(now == m) break;
   12          u = G[now].first, v = G[now].second;
   13      }
   14      if(now == m) return true;
   15      if(dep == k) return false;
   16      bool res = false;
   17      vis[u] = 1;
   18      res |= dfs(now + 1, dep + 1);
   19      vis[u] = 0;
   20      vis[v] = 1;
   21      res |= dfs(now + 1, dep + 1);
   22      vis[v] = 0;
   23      return res;
   24  }
   25  int main() {
   26      cin >> n >> m >> q;
   27      k = n - q;
   28      for(int i = 1; i <= m; i++) {
   29          cin >> a >> b;
   30          G.push_back({a, b});
   31      }
   32      if(dfs(0, 0)) cout << "Yes\n";
   33      else cout << "No\n";
   34  }
   

判断题

1. 若交换 14、15 行，程序运行结果不会改变。{{ select(16) }}

• √
• ×

2. 若将 30 行改为 G.push_back({b,a});，程序运行结果不会改变。{{ select(17) }}

• √
• ×

3. 该程序的存图方式为邻接表法。{{ select(18) }}

• √
• ×

4. 若删除 19 行，则程序运行结果可能会发生改变；但删去 22 行则不会。{{ select(19) }}

• √
• ×

选择题

5. 本程序的时间复杂度是（　　）。{{ select(20) }}

• A. $\mathcal O (2^{n - q})$
• B. $\mathcal O (2^{n - q} \cdot m)$
• C. $\mathcal O (2^{n - q} + m)$
• D. $\mathcal O (2^n + m)$

6. 已知输入的 $n=8$，$m=7$，对应的 $7$ 组 $a,b$ 分别为 $[1,3], [2,3], [5,2], [6,3], [7,1], [7,4], [2,8]$。请问 $q$ 至多为多少时可以输出 Yes？（　　）{{ select(21) }}

• A. $2$
• B. $3$
• C. $4$
• D. $5$

2. 01  #include <bits/stdc++.h>
   02  using namespace std;
   03  const int mod = 1e9 + 7;
   04  long long dp[(1<<17)+2], a[20], n, k;
   05  int main(){
   06      cin >> n >> k;
   07      for(int i = 0; i < n; i++){
   08          cin >> a[i];
   09          if(a[i] > k) return cout << 0, 0;
   10      }
   11      dp[0] = 1;
   12      for(int i = 0; i < (1 << n); i++){
   13          for(int j = 0; j < n; j++){
   14              if(i >> j & 1) continue;
   15              dp[i | 1<<j] = (dp[i | 1<<j] + dp[i]) % mod;
   16              for(int u = 0; u < n; u++){
   17                  if(i >> u & 1) continue;
   18                  if(j == u) continue;
   19                  if(a[j] + a[u] > k) continue;
   20                  int now = i | (1 << j) | (1 << u);
   21                  dp[now] = (dp[now] + dp[i]) % mod;
   22              }
   23          }
   24      }
   25      cout << dp[(1<<n)-1] << endl;
   26  }
   

判断题

1. 若将第 11 行的语句删除，则无论输入是什么，程序的输出都是 0。{{ select(22) }}

• √
• ×

2. 第 20 行定义的 now 在任何时候都大于等于 3。{{ select(23) }}

• √
• ×

3. 若输入的 n 为 17，则程序会发生数组越界的情况。{{ select(24) }}

• √
• ×

4. 若删除第 9 行，则程序的结果可能会发生改变。{{ select(25) }}

• √
• ×

选择题

5. （2 分）若输入为 2 5 3 4（前两个数为 $n, k$，后两个数为 $a_i$），则输出为（　　）。{{ select(26) }}

• A. 1
• B. 2
• C. 3
• D. 4

6. 若输入为 4 6 2 3 4 5（前两个数为 $n, k$，后四个数为 $a_i$），则输出为（　　）。{{ select(27) }}

• A. 120
• B. 60
• C. 48
• D. 24

3. 01  #include<bits/stdc++.h>
   02  const int maxn = 1000;
   03  using namespace std;
   04  struct node{
   05      int weight;
   06      int parent, lchild, rchild;
   07  };
   08  int s1, s2, w[maxn], n, res[maxn];
   09  char ans[maxn];
   10  node HT[maxn];
   11  void getMin(int x){
   12      int min1 = 0x3f3f3f3f, min2 = 0x3f3f3f3f;
   13      for(int i = 1; i <= x; i++){
   14          if(HT[i].parent) continue;
   15          int val = HT[i].weight;
   16          if(val < min1){
   17              min2 = min1;
   18              s2 = s1;
   19              min1 = val;
   20              s1 = i;
   21          }else if(val < min2){
   22              min2 = val;
   23              s2 = i;
   24          }
   25      }
   26  }
   27  void init(){
   28      int m = 2 * n - 1;
   29      for(int i = 1; i <= m; i++) {
   30          if(i <= n)
   31              HT[i].weight = w[i];
   32          else
   33              HT[i].weight = 0;
   34          HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
   35      }
   36      for(int i = n + 1; i <= m; i++){
   37          getMin(i-1);
   38          HT[s1].parent = HT[s2].parent = i;
   39          HT[i].lchild = s1;
   40          HT[i].rchild = s2;
   41          HT[i].weight = HT[s1].weight + HT[s2].weight;
   42      }
   43      for(int i = 1; i <= n; i++){
   44          char s[maxn];
   45          int cnt = 0;
   46          int start = n - 1, c, f;
   47          for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent){
   48              if(HT[f].lchild == c)
   49                  s[cnt] = '0';
   50              else
   51                  s[cnt] = '1';
   52              cnt++;
   53          }
   54          cout << ans[i] << " ";
   55          for(int j = cnt - 1; j >= 0; j--)
   56              cout << s[j];
   57          cout << endl;
   58      }
   59  }
   60  int main(){
   61      string s;
   62      cin >> s;
   63      int cnt[200] = {};
   64      for(int i = 0; i < s.size(); i++){
   65          cnt[s[i]]++;
   66      }
   67      for(int i = 1; i < 200; i++){
   68          if(cnt[i] != 0){
   69              w[++n] = cnt[i];
   70              ans[n] = i;
   71              res[n] = cnt[i];
   72          }
   73      }
   74      init();
   75  }
   

   保证输入的字符串只包含大写英文字母。

判断题

1. 为了避免程序崩溃，输入字符串 s 的长度至多为 999，即被 maxn 限制。{{ select(28) }}

• √
• ×

2. （2 分）若输入的字符串 s 的所有字符全相同，则程序不会输出任何数字。{{ select(29) }}

• √
• ×

3. getMin 函数的功能可以用优先队列或 set 替代，从而优化程序的时间复杂度。{{ select(30) }}

• √
• ×

选择题

4. 该程序的时间复杂度为（　　）。{{ select(31) }}

• A. $\mathcal O (n)$
• B. $\mathcal O (n^2)$
• C. $\mathcal O (n^3)$
• D. $\mathcal O (n \log n)$

5. 若输入字符串 s 为 CSPCSP，则程序输出的数位的个数之和为（　　）。{{ select(32) }}

• A. 4
• B. 3
• C. 6
• D. 5

6. 若输入字符串 s 为 AKAKCSP，则程序输出时哪两个字母后面的有三个数位（　　）。{{ select(33) }}

• A. C P
• B. S P
• C. C S
• D. A K

7. 若输入字符串 s 为 AKAKCSP，则程序输出时 A 后面的数字为（　　）。{{ select(34) }}

• A. 10
• B. 01
• C. 101
• D. 111

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

1. （树的染色）给一棵至多包含 $2 \times 10^5$ 个点的无根树，初始每个点都是白色的，你每次可以选择一个白点变成黑色。第一次可以任选，之后每次选择的白点都必须和至少一个黑点相邻。选择一个白点变黑可以得到的收益是这个白点所在的连通块大小，当树的所有点全部变黑时结束。请问你最多可以获得多少收益？

   

   例如本图中最大收益为 $36$，每次选点分别为 $[8, 9, 4, 1, 2, 3, 5, 6, 7]$，每一步所得收益为 $[9, 8, 6, 5, 4, 1, 1, 1, 1]$ 求和得到 $36$。注意：第一次选 $8$ 号点，第二次选 $7$ 号点是非法的，因为第二次选点没有和一个黑点相邻。当然，$[8, 9, 7, 4, 1, 2, 6, 5, 3]$ 也是一种合法且收益最大的选择。

   提示：我们令第一个选择的点为树根，不难发现，当根节点确定时，整棵树的选择及收益都确定了。所以此题难点在于如何寻找第一个点。考虑换根 DP，设 $\mathit{dp2}[i]$ 为以 $i$ 为根的收益，我们通过一个 $\mathit{dp2}[i]$ 的值来推得以其他点为根的收益。试完成代码。

   01  #include <bits/stdc++.h>
   02  using namespace std;
   03  #define ll long long
   04  const int maxn = 2e5 + 5;
   05  vector <int> G[maxn];
   06  ll sz[maxn], dp1[maxn], dp2[maxn], n, ans = 0;
   07  long long dfs(int now, int pre){
   08      sz[now] = 1;
   09      for(int i = 0; i < G[now].size(); i++){
   10          int nxt = G[now][i];
   11          if(nxt == pre) continue;
   12              sz[now] += dfs(nxt, now);
   13              ➀;
   14          }
   15          dp1[now] += sz[now];
   16          return sz[now];
   17  }
   18  void dfs2(int now, int pre){
   19      dp2[now] = ➁;
   20      for(int i = 0; i < G[now].size(); i++){
   21          int nxt = G[now][i];
   22          if(nxt == pre) continue;
   23          dp2[nxt] = ➂;
   24          dfs2(nxt, now);
   25      }
   26      ans = max(ans, dp2[now]);
   27  }
   28  int main(){
   29      cin >> n;
   30      for(int i = 1; i < n; i++){
   31          int a, b;
   32          cin >> a >> b;
   33          G[a].push_back(b);
   34          G[b].push_back(a);
   35      }
   36      ➃
   37      cout << ans << endl;
   38  }
   

1. ➀处应填（　　）。{{ select(35) }}

• A. dp1[now] = max(dp1[now], dp1[nxt])
• B. dp1[now] += dp1[nxt]
• C. dp1[now] += sz[nxt]
• D. dp1[now] = max(dp1[now], sz[nxt])

2. ➁处应填（　　）。{{ select(36) }}

• A. 1
• B. dp1[now]
• C. sz[now]
• D. now == 1 ? dp1[now] : dp2[now]

3. ➂处应填（　　）。{{ select(37) }}

• A. dp2[now] + n - sz[nxt] - sz[nxt]
• B. dp2[now] + n - sz[nxt] - sz[now]
• C. dp2[now] + n - sz[now] - sz[now]
• D. dp2[now] + sz[nxt] + sz[now]

4. ➃处应填（　　）。{{ select(38) }}

• A. dfs2(1,1); dfs(1,1);
• B. dfs2(1,n); dfs(1,1);
• C. dfs(1,1); dfs2(1,n);
• D. dfs(1,1); dfs2(1,1);

2. （入度）给定一张 $n$ 个点、$m$ 条边的简单无向图，每条边有一个权值，你可以任选一些边并给这些边定向，使得每个点的入度均为 $1$。问是否能够做到，若能，则输出所选边的最大权值和；否则输出 impossible。

   思路：将所有边排序，然后逐个添加，用并查集维护添加边之后是否有某个点不得不出现两条入边的情况。

   01  #include <bits/stdc++.h>
   02  using namespace std;
   03  struct node{
   04      int u, v, val;
   05  };
   06  bool cmp(node a, node b){
   07      return ➀;
   08  }
   09  const int maxn = 100005;
   10  node a[maxn];
   11  int f[maxn], flag[maxn];
   12  int Find(int x){
   13      return f[x] == x ? x : f[x] = Find(f[x]);
   14  }
   15  void Union(int x, int y){
   16      int fx = Find(x), fy = Find(y);
   17      f[fx] = fy;
   18      ➁;
   19  }
   20  int main(){
   21      int n, m, t;
   22      cin >> t;
   23      while(t--){
   24          long long cnt=0, ans=0;
   25          cin >> n >> m;
   26          for(int i = 1; i <= n; i++){
   27              f[i] = i;
   28              flag[i] = 1;
   29          }
   30         for(int i = 1; i <= m; i++)
   31              cin >> a[i].u >> a[i].v >> a[i].val;
   32          sort(a+1, a+1+m, cmp);
   33          for(int i = 1; i <= m; i++){
   34              int x = a[i].u, y = a[i].v;
   35              int fx = Find(x), fy = Find(y);
   36              if(fx == fy && ➂){
   37                  ➃;
   38                  cnt++;
   39                  ans += a[i].val;
   40              }else if(fx != fy && ➄){
   41                  Union(fx, fy);
   42                  cnt++;
   43                  ans += a[i].val;
   44              }
   45          }
   46          if(➅){
   47              cout << ans << endl;
   48          }else{
   49              cout << "impossible" << endl;
   50          }
   51      }
   52  }
   

1. ➀处应填（　　）。{{ select(39) }}

• A. a.u < b.u
• B. a.u > b.u
• C. a.val > b.val
• D. a.val < b.val

2. ➁处应填（　　）。{{ select(40) }}

• A. flag[fx] = flag[fy]
• B. flag[fx] &= flag[fy]
• C. flag[fx] |= flag[fy]
• D. flag[fx] ^= flag[fy]

3. ➂处应填（　　）。{{ select(41) }}

• A. flag[fx]==1
• B. flag[fx]==0
• C. cnt==n
• D. cnt!=n

4. ➃处应填（　　）。{{ select(42) }}

• A. flag[fx] = 1
• B. flag[fx] = 0
• C. f[fx] = fy
• D. Union(fx, fy)

5. ➄处应填（　　）。{{ select(43) }}

• A. (flag[fx] || flag[fy])
• B. flag[fx] && flag[fy]
• C. flag[fx]==0&&flag[fy]==0
• D. (flag[fx] ^ flag[fy])

6. ➅处应填（　　）。{{ select(44) }}

• A. cnt == n
• B. cnt == n / 2
• C. flag[n] == 1
• D. flag[n] == 0