CSP-J 2022 · 入门级第一轮真题

以下哪种功能没有涉及C++语言的面向对象特性支持： （ ）。

有 $6$ 个元素，按照 $6$、$5$、$4$、$3$、$2$、$1$ 的顺序进入栈 S，请问下列哪个出栈序列是非法的（ ）。

运行以下代码片段的行为是（ ）。

01int x = 101;
02int y = 201;
03int *p = &x;
04int *q = &y;
05p = q;

链表和数组的区别包括（ ）。

对假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据，每个数据按照进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈，队列 Q 依次有数据 e2、e4、e3、e6、e5 和 e1 出队列。则栈 S 的容量至少是（ ）个数据。

对表达式 a+(b-c)*d 的前缀表达式为（ ），其中 +、-、* 是运算符。

假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%、15%、30%、16%、29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度为（ ）位。

一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 $1$ 个位置。若存储在数组第 $9$ 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。

考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。

以下对数据结构的表述不恰当的一项为：（ ）。

以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：（ ）。

以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。

八进制数 $32.1$ 对应的十进制数是（ ）。

一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有（ ）个内容互不相同的子串。

以下对递归方法的描述中，正确的是：（ ）

1  #include <iostream>
2 
3  using namespace std;
4 
5  int main()
6  {
7      unsigned short x, y;
8      cin >> x >> y;
9      x = (x | x << 2) & 0x33;
10      x = (x | x << 1) & 0x55;
11      y = (y | y << 2) & 0x33;
12      y = (y | y << 1) & 0x55;
13      unsigned short z = x | y << 1;
14      cout << z << endl;
15      return 0;
16  }

1  #include <algorithm>
2  #include <iostream>
3  #include <limits>
4 
5  using namespace std;
6 
7  const int MAXN = 105;
8  const int MAXK = 105;
9 
10  int h[MAXN][MAXK];
11 
12  int f(int n, int m)
13  {
14      if (m == 1) return n;
15      if (n == 0) return 0;
16 
17      int ret = numeric_limits<int>::max();
18      for (int i = 1; i <= n; i++)
19          ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
20      return ret;
21  }
22 
23  int g(int n, int m)
24  {
25      for (int i = 1; i <= n; i++)
26          h[i][1] = i;
27      for (int j = 1; j <= m; j++)
28          h[0][j] = 0;
29 
30      for (int i = 1; i <= n; i++) {
31          for (int j = 2; j <= m; j++) {
32              h[i][j] = numeric_limits<int>::max();
33              for (int k = 1; k <= i; k++)
34              h[i][j] = min(
35                  h[i][j],
36                  max(h[i - k][j], h[k - 1][j - 1]) + 1);
37          }
38      }
39 
40      return h[n][m];
41  }
42 
43  int main()
44  {
45      int n, m;
46      cin >> n >> m;
47      cout << f(n, m) << endl << g(n, m) << endl;
48      return 0;
49  }

1  #include <iostream>
2 
3  using namespace std;
4 
5  int n, k;
6 
7  int solve1()
8  {
9      int l = 0, r = n;
10      while (l <= r) {
11          int mid = (l + r) / 2;
12          if (mid * mid <= n) l = mid + 1;
13          else r = mid - 1;
14      }
15      return l - 1;
16  }
17 
18  double solve2(double x)
19  {
20      if (x == 0) return x;
21      for (int i = 0; i < k; i++)
22          x = (x + n / x) / 2;
23      return x;
24  }
25 
26  int main()
27  {
28      cin >> n >> k;
29      double ans = solve2(solve1());
30      cout << ans << ' ' << (ans * ans == n) << endl;
31      return 0;
32  }

假设 int 为 $32$ 位有符号整数类型，输入的 n 是不超过 $47000$ 的自然数、k 是不超过 int 表示范围的自然数，

试补全程序。

1  #include <bits/stdc++.h>
2  using namespace std;
3 
4  int main() {
5    int n;
6    cin >> n;
7 
8    vector<int> fac;
9    fac.reserve((int)ceil(sqrt(n)));
10 
11    int i;
12    for (i = 1; i * i < n; ++i) {
13      if (①) {
14        fac.push_back(i);
15      }
16    }
17 
18    for (int k = 0; k < fac.size(); ++k) {
19      cout << ② << " ";
20    }
21    if (③) {
22      cout << ④ << " ";
23    }
24    for (int k = fac.size() - 1; k >= 0; --k) {
25      cout << ⑤ << " ";
26    }
27  }

试补全程序。

1  #include <bits/stdc++.h>
2  using namespace std;
3 
4  const int ROWS = 8;
5  const int COLS = 8;
6 
7  struct Point {
8    int r, c;
9    Point(int r, int c) : r(r), c(c) {}
10  };
11 
12  bool is_valid(char image[ROWS][COLS], Point pt,
13                  int prev_color, int new_color) {
14    int r = pt.r;
15    int c = pt.c;
16    return (0 <= r && r < ROWS && 0 <= c && c < COLS &&
17            ① && image[r][c] != new_color);
18  }
19 
20  void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
21    queue<Point> queue;
22    queue.push(cur);
23 
24    int prev_color = image[cur.r][cur.c];
25    ②;
26 
27    while (!queue.empty()) {
28      Point pt = queue.front();
29      queue.pop();
30 
31      Point points[4] = {③, Point(pt.r - 1, pt.c),
32                          Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
33      for (auto p : points) {
34        if (is_valid(image, p, prev_color, new_color)) {
35          ④;
36          ⑤;
37        }
38      }
39    }
40  }
41 
42  int main() {
43    char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
44                                {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
45                                {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
46                                {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
47                                {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
48                                {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
49                                {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
50                               {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};
51 
52    Point cur(4, 4);
53    char new_color = 'y';
54 
55    flood_fill(image, cur, new_color);
56 
57    for (int r = 0; r < ROWS; r++) {
58      for (int c = 0; c < COLS; c++) {
59        cout << image[r][c] << " ";
60      }
61      cout << endl;
62    }
63    // 输出：
64    // g g g g g g g g
65    // g g g g g g r r
66    // g r r g g r g g
67    // g y y y y r g r
68    // g g g y y r g r
69    // g g g y y y y r
70    // g g g g g y g g
71    // g g g g g y y g
72 
73    return 0;
74  }