#156. 2024 CSP-S 满分之路 模拟卷二

2024 CSP-S 满分之路 模拟卷二

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

  1. 在NOI Linux系统终端中，以下哪个命令可以用来创建一个新的空白文档？（ ） {{ select(1) }}
  • mkdir
  • cp -a
  • mv
  • touch
  1. 以下关于数据结构的表述中不恰当的一项是（ ）。 {{ select(2) }}
  • 栈是一种后进先出的数据结构
  • 非连通有向图的边数一定小于顶点数
  • 队列是一种先进先出的数据结构
  • 哈希表是一种通过哈希函数将关键字映射到存储位置的数据结构
  1. 对于4个结点的简单有向图，最少（ ）条边可以形成一个覆盖所有结点的环。 {{ select(3) }}
  • 2
  • 3
  • 4
  • 5
  1. 对于给定的正整数a和n（n为2的正整数次幂），下面求(a^{n})值的方法的最准确描述是（ ）。
Long long fun(int a, int n)
{
    Long Long ret = 1;
    if (n <= 1)
        return pow(a, n);
    else
    {
        ret = fun(a, n / 2);
        return ret * ret;
    }
}

{{ select(4) }}

  • 倍增
  • 二分
  • 折半
  • 迭代
  1. 约定杨辉三角形第0行只有1个元素是1，第1行有2个元素是1，则第5行的所有元素之和是（ ）。 {{ select(5) }}
  • 8
  • 16
  • 32
  • 64
  1. 下列哪个问题不能用贪心法精确求解？（ ） {{ select(6) }}
  • 哈夫曼编码
  • 多重背包
  • 打水问题
  • 最小生成树
  1. 对于具有n个元素的二叉排序树（又名二分查找树），进行后序遍历的时间复杂度是（ ）。 {{ select(7) }}
  • (O(log n))
  • (O(n))
  • (O\left(n^{2}\right))
  • (O(n log n))
  1. 考虑对n个数进行排序，以下方法中最坏时间复杂度最优的排序方法是（ ）。 {{ select(8) }}
  • 选择排序
  • 快速排序
  • 堆排序
  • 插入排序
  1. 下面有向图中的数字表示顶点序号，则从1号顶点出发的BFS遍历输出的顶点序列可能是（ ）。 {{ select(9) }}

  • 1 4 3 2
  • 1 4 2 3
  • 1 3 2 4
  • 1 2 4 3
  1. 给定地址区间为0~10的哈希表，哈希函数为h(x)=x % 11，采用线性探查的冲突解决策略（若出现冲突情况，会往后探查第一个空的地址存储；若地址10冲突了，则从地址0重新开始探查）。哈希表初始为空表，依次存储(60,34,62,8,2,57,78)后，78存储在哈希表的哪个地址中？（ ） {{ select(10) }}
  • 1
  • 2
  • 3
  • 4
  1. STL中的容器可以分为顺序容器和关联容器。以下哪个不属于顺序容器？（ ） {{ select(11) }}
  • multiset
  • vector
  • list
  • deque
  1. 二分图是指能将顶点划分成两个部分，且每一部分内的顶点间没有边相连的简单无向图。含有24个顶点的二分图（两部分的顶点和之差不超过6）至少有（ ）条边。 {{ select(12) }}
  • 144
  • 128
  • 135
  • 140
  1. 令二叉树根结点的高度为0，则一棵含有2024个结点的二叉树的高度可能是（ ）。 {{ select(13) }}
  • 2024
  • 2023
  • 9
  • 8
  1. 设全集(I={1,2,3,4,5})，选择集合I的两个非空子集A和B，要使B中最小的数大于A中最大的数，则不同的选择方法有（ ）种。 {{ select(14) }}
  • 50
  • 49
  • 48
  • 47
  1. 设全集(I={1,2,3,4,5,6,7,8})，集合(B \cup A={1,2,3,4,5,6})，(C \cap A={3,4,5})，(\sim B \cap A={1,4})，那么集合(C \cap B \cap A)为（ ）。 {{ select(15) }}
  • {3,5}
  • {4,5}
  • {3,4,5}
  • {4,6}

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 typedef pair <int, int> PII;
04 const int N = 1007;
05 int n, m, ans;
06 char g[N][N];
07 bool st[N][N];
08 void bfs(int x, int y) {
09     queue<PII> q;
10     q.push({x, y});
11     st[x][y] = true;
12     while (q.size()) {
13         PII t = q.front();
14         q.pop();
15         for (int i = t.first - 1; i <= t.first + 1; ++i)
16             for (int j = t.second - 1; j <= t.second + 1; ++j) {
17                 if (i == t.first && j == t.second)
18                     continue;
19                 if (i < 1 || i > n || j < 1 || j > m)
20                     continue;
21                 if (g[i][j] != 'W' || st[i][j])
22                     continue;
23                 q.push({i, j});
24                 st[i][j] = true;
25             }
26     }
27 }
28 int main()
29 {
30     cin >> n >> m;
31     for (int i = 1; i <= n; ++i)
32         scanf("%s", g[i] + 1);
33     for (int i = 1; i <= n; ++i)
34         for (int j = 1; j <= m; ++j)
35             if (g[i][j] == 'W' && !st[i][j]) {
36                 bfs(i, j);
37                 ++ans;
38             }
39     printf("%d\n", ans);
40     return 0;
41 }

■ 判断题 16. 若将第30行改为cin>>m>>n;，程序的输出不变。（ ） {{ select(16) }}

  • 正确
  • 错误
  1. 该问题也可以用DFS解决。（ ） {{ select(17) }}
  • 正确
  • 错误
  1. 当输入为 4 5 WSWWSS WWWSSS SSWSWS SSSSWS 时，程序会崩溃。（ ） {{ select(18) }}
  • 正确
  • 错误
  1. 从程序中可以看出题目允许的拓展方向有4个。（ ） {{ select(19) }}
  • 正确
  • 错误

■ 选择题 20. 对于输入 4 5 WSWWS WWWSS SSWSW SSSSW 程序的输出是（ ）。 {{ select(20) }}

  • 1
  • 2
  • 3
  • 4
  1. 本程序的时间复杂度是（ ）。 {{ select(21) }}
  • (O(n))
  • (O\left(n^{2} m^{2}\right))
  • (O\left(n^{2} m\right))
  • (O(n m))

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 typedef struct {
05     double x;
06     double y;
07 }Point;
08 
09 Point point_init(double x, double y) {
10     Point p;
11     p.x = x;
12     p.y = y;
13     return p;
14 }
15 
16 Point point_sub(Point a, Point b) {
17     Point p;
18     p.x = a.x - b.x;
19     p.y = a.y - b.y;
20     return p;
21 }
22 
23 double cross(Point a, Point b) {
24     return a.x * b.y - a.y * b.x;
25 }
26 
27 double polygonArea(const vector<Point> v) {
28     double area = cross(v.back(), v.front());
29     for (size_t i = 0; i < v.size() - 1; ++i) {
30         area += cross(v[i], v[i + 1]);
31     }
32     return area;
33 }
34 
35 void solve(int n) {
36     vector<Point> pts(n);
37     for (int i = 0; i < n; ++i) {
38         double a, b;
39         cin >> a >> b;
40         pts[i] = point_init(a, b);
41     }
42     double area = polygonArea(pts) / 2;
43     cout << fixed << setprecision(1) << fabs(area) << endl;
44 }
45 
46 int main() {
47     while (true) {
48         int n;
49         cin >> n;
50         if (n == 0) break;
51         solve(n);
52     }
53     return 0;
54 }

■ 判断题 22. 将第42行改为double area = polygonArea(pts) >> 1;，程序正常运行。（ ） {{ select(22) }}

  • 正确
  • 错误
  1. 无论点是按逆时针方向还是按顺时针方向给出，程序都可以计算出正确的结果。（ ） {{ select(23) }}
  • 正确
  • 错误
  1. 程序可以处理凹多边形而不需要任何修改。（ ） {{ select(24) }}
  • 正确
  • 错误
  1. polygonArea的返回值始终为正。（ ） {{ select(25) }}
  • 正确
  • 错误

■ 选择题 26. cross函数的计算结果用于表示（ ）。 {{ select(26) }}

  • 两个点的欧几里得距离
  • 连接两点的直线的斜率
  • 两个向量的点积
  • 两个向量的叉积
  1. 对于输入 3 1 1 0 0 1 0 程序输出（ ）。 {{ select(27) }}
  • 1.0
  • 0.5
  • 0.0
  • 0.6

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 class BIT {
05 public:
06     vector<int> bit;
07     int size;
08     BIT(int n) : size(n), bit(n + 1, 0) {}
09     void update(int x, int delta) {
10         ++x;
11         while (x <= size) {
12             bit[x] += delta;
13             x += x & -x;
14         }
15     }
16     int query(int x) const {
17         ++x;
18         int sum = 0;
19         while (x > 0) {
20             sum += bit[x];
21             x -= x & -x;
22         }
23         return sum;
24     }
25 };
26 
27 int main() {
28     int n, q;
29     cin >> n >> q;
30     vector<int> arr(n);
31     vector<pair<int, int>> queries[q];
32     vector<int> solution(q);
33     for (int i = 0; i < n; ++i) {
34         cin >> arr[i];
35     }
36     for (int i = 0; i < q; ++i) {
37         int a, b;
38         cin >> a >> b;
39         a--, b--;
40         queries[a].emplace_back(b, i);
41     }
42     BIT bit(n);
43     map<int, int> last_index;
44     for (int i = n - 1; i >= 0; --i) {
45         int val = arr[i];
46         if (last_index.find(val) != last_index.end()) {
47             bit.update(last_index[val], -1);
48         }
49         last_index[val] = i;
50         bit.update(i, 1);
51 
52         for (const auto& query : queries[i]) {
53             solution[query.second] = bit.query(query.first);
54         }
55     }
56     for (int ans : solution) {
57         cout << ans << ' ';
58     }
59     return 0;
60 }

■ 判断题 28. 程序支持在线查询。（ ） {{ select(28) }}

  • 正确
  • 错误
  1. 将第13行改为x += x & (~x + 1);，程序功能不变。（ ） {{ select(29) }}
  • 正确
  • 错误

■ 选择题 30. BIT类中的query函数的返回值是（ ）。 {{ select(30) }}

  • 指定索引的值
  • 自根开始到指定索引的所有值的乘积
  • 指定索引之前所有值的累加和
  • 自根开始到指定索引的所有值的最大值
  1. 程序的时间复杂度为（ ）。 {{ select(31) }}
  • (O(n))
  • (O(n log n))
  • (O\left(n^{2} log n\right))
  • (O(log n))
  1. 如果输入的arr数组的元素大小互不相同，则last_index.size()的值是（ ）。 {{ select(32) }}
  • 0
  • 1
  • n
  • q
  1. （4分）如果输入为 5 3 3 2 3 1 2 1 3 2 4 1 5 则输出将是（ ）。 {{ select(33) }}
  • 2 3 3
  • 3 2 4
  • 3 2 5
  • 0 1 0

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

(1) 定义*数字，对于一个没有前导0的数，数字d恰好出现在这个数的所有偶数位置。现在给定(m, d, a, b)，询问([a, b])范围内是m倍数的x数字的数量，答案对1e9+7取模。

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int M = 2005;
05 const int mod = 1e9 + 7;
06 int dp[M][M][2];
07 int m, d;
08 
09 int dfs(int i, int sum, int small_taken, string s) {
10     if (①) return sum == 0;
11     int ans = dp[i][sum][small_taken];
12     if (ans != -1) return ans;
13     ans = 0;
14     int digit = s[i] - '0';
15     int low = 0, high = digit;
16     if (small_taken) high = 9;
17     for (int j = low; j <= high; ++j) {
18         if (i % 2 == 1 && j != d) continue;
19         if (i % 2 == 0 && j == d) continue;
20         int new_small = ②;
21         int new_sum = ③;
22         ans += dfs(i + 1, new_sum, new_small, s);
23         ans %= mod;
24     }
25     return dp[i][sum][small_taken] = ans;
26 }
27 
28 int main() {
29     string a, b;
30     cin >> m >> d >> a >> b;
31     int is_a_magic = 1;
32     int res = 0;
33     for (int i = 0; i < a.size(); ++i) {
34         int dig = a[i] - '0';
35         if ((i % 2 == 1 && dig != d)) is_a_magic = 0;
36         if (④) is_a_magic = 0;
37         res = (res * 10 + dig) % m;
38     }
39     if (res) is_a_magic = 0;
40     memset(dp, -1, sizeof dp);
41     int sum_a = dfs(0, 0, 0, a);
42     memset(dp, -1, sizeof dp);
43     int sum_b = dfs(0, 0, 0, b);
44     cout << ⑤ << endl;
45     return 0;
46 }
  1. ①处应填（ ）。 {{ select(34) }}
  • i >= s.size()
  • i > s.size()
  • i >= sum
  • i > sum
  1. ②处应填（ ）。 {{ select(35) }}
  • j != d || j < high
  • small_taken && j < high
  • j == d || j < high
  • small_taken || j < high
  1. ③处应填（ ）。 {{ select(36) }}
  • (sum + digit) % m
  • (sum * 10 + j) % m
  • (sum + high) % m
  • (sum * 10 + high) % m
  1. ④处应填（ ）。 {{ select(37) }}
  • i % 2 == 1 && dig == d
  • dig != d || is_a_magic
  • i % 2 == 0 && dig != d
  • dig != d && !is_a_magic
  1. ⑤处应填（ ）。 {{ select(38) }}
  • (sum_b - sum_a + mod) % mod
  • (sum_b - is_a_magic) % mod
  • (sum_b - sum_a - is_a_magic + mod) % mod
  • (sum_b + sum_a + is_a_magic) % mod

(2) 给定n个人和m条信息，每条信息描述了若干人的站队要求，比如信息2、5、1，那么站队时2号应该在5号前，5号应该在1号前，这些信息是按照优先级排列的，所以现在希望你能找到一个站队序列满足前x条信息，使得这个x尽可能大。对于这个最大的x，你需要找到字典序最小的答案。

01 #include <bits/stdc++.h>
02 #define LL long long
03 #define PII pair<int, int>
04 using namespace std;
05 
06 vector<int> ret;
07 vector<vector<int>> order;
08 int n, m;
09 
10 struct TopoSort {
11     int N;
12     vector<int> in, res;
13     vector<vector<int>> adj;
14     void init(int _N) {
15         N = _N;
16         in.resize(N);
17         adj.resize(N);
18     }
19     void addedge(int x, int y) { adj[x].push_back(y), ①; }
20     bool sort() {
21         ②;
22         for (int i = 1; i < N; i++)
23             if (③) todo.push(i);
24         while (todo.size()) {
25             int x = todo.top(); todo.pop();
26             res.push_back(x);
27             for (const int& i : adj[x])
28                 if (!(--in[i])) todo.push(i);
29         }
30         return res.size() == N - 1;
31     }
32 };
33 
34 bool check(int x) {
35     TopoSort g;
36     g.init(n + 1);
37     for (int i = 0; i < x; i++) {
38         for (int j = 0; j < order[i].size() - 1; j++) {
39             g.addedge(order[i][j], order[i][j + 1]);
40         }
41     }
42     bool ans = g.sort();
43     if (ans)
44         ④;
45     return ans;
46 }
47 
48 int main() {
49     cin >> n >> m;
50     order.resize(m);
51     for (int i = 0; i < m; i++) {
52         int k; cin >> k;
53         vector<int> v(k);
54         for (int j = 0; j < k; j++) cin >> v[j];
55         order[i] = v;
56     }
57     int l = 0, r = m;
58     while (l < r) {
59         int mid = ⑤;
60         if (check(mid))
61             l = mid;
62         else
63             r = mid - 1;
64     }
65     check(l);
66     for (int i = 0; i < n; i++) {
67         cout << ret[i] << " ";
68     }
69     return 0;
70 }
  1. ①处应填（ ）。 {{ select(39) }}
  • ++in[x]
  • adj[y].push_back(x)
  • ++in[y]
  • ++res[x]
  1. ②处应填（ ）。 {{ select(40) }}
  • priority_queue<int, vector<int>, greater<int>> todo
  • priority_queue<int, vector<int>, less<int>> todo
  • set<int, less<int>> todo
  • set<int, greater<int>> todo
  1. ③处应填（ ）。 {{ select(41) }}
  • in[i] == i
  • in[i]
  • in[i] != i
  • !in[i]
  1. ④处应填（ ）。 {{ select(42) }}
  • ret[x] = g.res[x]
  • ret = g.res, ret.resize(x)
  • ret.resize(x), ret[x] = g.res[x]
  • ret = g.res
  1. ⑤处应填（ ）。 {{ select(43) }}
  • (l + r) >> 1
  • l + (r - l + 1) >> 1
  • (l + r) / 2
  • l + (r - l + 1) / 2
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  3. Worker 0, 35ms
  4. Powered by Hydro v4.19.1 Community