ID: 72

Type: Objective

Tried: 0

Accepted: 0

Difficulty: (None)

Uploaded By:

jike1994

Tags>

CSP通关之路

普及组CSP-J2025初赛模拟卷5

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

十进制数2025的十六进制表示是（）。 {{ select(1) }}

07D9
07E9
07F9
07F1

以下关于计算机竞赛IOI的描述正确的是（）。 {{ select(2) }}

IOI非英语国家参赛选手可以在比赛中携带电子词典
IOI参赛选手可携带已关机的手机放在自己座位后面的包里
IOI参赛选手在比赛时间内去厕所的时候可携带手机
IOI全称是国际信息学奥林匹克竞赛

以下不能用ASCII码表示的字符是（）。 {{ select(3) }}

@
①
^
~

设变量s为double型且已赋值，下列哪条语句能将s中的数值保留到小数点后一位，并将第二位四舍五入？（） {{ select(4) }}

s = (s * 10 + 0.5) / 10.0
s = s * 10 + 0.5 / 10.0
s = (s / 10 + 0.5) * 10.0
s = (int)(s * 10 + 0.5) / 10.0

以下不属于STL链表中的函数的是（）。 {{ select(5) }}

sort
empty
push_back
resize

小明写了个程序，在这里用到的数据结构是（）。

#include <iostream>
using namespace std;
int k;
int f(int a) {
    if (a - k > 0 && (a - k) % 2 == 0)
        return f((a + k) / 2) + f((a - k) / 2);
    else
        return 1;
}
int main() {
    int n;
    cin >> n >> k;
    if ((n + k) & 1 )
        cout << 1 << endl;
    else
        cout << f(n);
    return 0;
}

树
栈
链表
队列

小明想求n个不同正整数的全排列，他设计的程序采用DFS方法的时间复杂度是（）。 {{ select(7) }}

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

在下列排序算法中，（）是不稳定的排序算法。 {{ select(8) }}

归并排序
插入排序
选择排序
冒泡排序

一台32位操作系统的计算机运行C++，下列说法中错误的是（）。 {{ select(9) }}

double类型的变量占用8字节内存空间
bool类型的变量占用1字节内存空间
long long类型变量的取值范围比int类型变量的大一倍
char类型的变量也可以作为循环变量

若整型变量n的值为25，则表达式n & (n + 1) >> 1的值是（）。 {{ select(10) }}

25
26
9
16

一群学生参加学科夏令营，每名同学至少参加一个学科的考试。已知有100名学生参加了数学考试，50名学生参加了物理考试，48名学生参加了化学考试，学生总数是参加至少两门考试学生的两倍，也是参加三门考试学生数的三倍，则学生总数为（）。 {{ select(11) }}

90
96
108
120

以下不是C++中的循环语句的是（）。 {{ select(12) }}

while
do...while
for
switch...case

二叉树T，已知其后序遍历序列为4 2 7 5 6 3 1，中序遍历序列为4 2 1 5 7 3 6，则其前序遍历序列为（）。 {{ select(13) }}

1 2 5 7 6 3 4
1 2 4 3 5 7 6
1 4 2 7 5 3 6
1 4 7 2 3 5 6

一个六位数是完全平方数，且最后三位数字都是4，这样的六位数有（）个。 {{ select(14) }}

用三种颜色给1×4的长方形方格区域涂色，在每种颜色至少用1次的前提下，相邻方格不涂同一种颜色的概率为（）。 {{ select(15) }}

1/3
2/3
1/2
4/9

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 int solve(vector<int> &nums) {
05     map<int, int> cnt;
06     int tot = 0;
07     for (auto v : nums) {
08         cnt[v]++;
09         tot += v;
10     }
11     int ans = -1E5;
12     for (auto v : nums) {
13         cnt[v]--;
14         if ((tot - v) % 2 == 0 && cnt[(tot - v) / 2] > 0)
15             ans = max(ans, v);
16         cnt[v]++;
17     }
18     return ans;
19 }
20 
21 int main() {
22     int n;
23     cin >> n;
24     vector<int> a(n);
25     for (int i = 0; i < n; i++)
26         cin >> a[i];
27     cout << solve(a) << endl;
28     return 0;
29 }

判断题

若程序输入5 -2 -1 -3 -6 4，则程序输出4。（） {{ select(16) }}

正确
错误

对于第14行的代码，如果不判断(tot - v) % 2 == 0，则程序依然可以得到正确的结果。（） {{ select(17) }}

正确
错误

若将头文件#include <bits/stdc++.h>换为#include <iostream>，程序依然可以正常运行。（） {{ select(18) }}

正确
错误

选择题

若输入8 6 -31 50 -35 41 37 -42 13，则输出是（）。 {{ select(19) }}

13
-35
-31
-100000

如果去除第16行的代码，对于输入4 2 3 5 10，输出是（）。 {{ select(20) }}

2
5
10
-100000

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int inf = 0x3f3f3f3f;
05 
06 int solve(vector<string> &words, string target) {
07     const int n = target.length();
08     set<string> s;
09     for (auto v : words)
10         for (int i = 1; i <= v.length(); i++)
11             s.insert(v.substr(0, i));
12     vector<int> dp(n + 1, inf);
13     dp[0] = 0;
14     for (int i = 0; i < n; i++)
15         for (int j = 0; j <= i; j++)
16             if (s.find(target.substr(j, i - j + 1)) != s.end())
17                 dp[i + 1] = min(dp[i + 1], dp[j] + 1);
18     return dp[n] != inf ? dp[n] : -1;
19 }
20 
21 int main() {
22     int n;
23     cin >> n;
24     vector<string> a(n);
25     for (int i = 0; i < n; i++)
26         cin >> a[i];
27     string t;
28     cin >> t;
29     cout << solve(a, t) << endl;
30     return 0;
31 }

判断题

若输入3 abc aaaaa bcdef aabcdabc，则输出为2。（） {{ select(21) }}

正确
错误

若将第17行中的dp[i + 1]改为dp[i]，则可能出现编译错误。（） {{ select(22) }}

正确
错误

（2分）该程序的输出一定小于或等于输入的n。（） {{ select(23) }}

正确
错误

选择题

当输入的a数组为{"abababab", "ab"}，t = "ababaababa"时，程序的输出为（）。 {{ select(24) }}

若删除第16行的代码，则当输入的a数组为{"abababab", "ab"}，t = "ababa"时，程序的输出为（）。 {{ select(25) }}

（4分）这段代码的时间复杂度为（）。 {{ select(26) }}

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

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 int calc(int n, int presses) {
05     set<int> seen;
06     for (int i = 0; i < (1 << 4); i++) {
07         vector<int> pressArr(4);
08         for (int j = 0; j < 4; j++)
09             pressArr[j] = (i >> j) & 1;
10         int sum = 0;
11         for (int j = 0; j < 4; j++)
12             sum += pressArr[j];
13         if (sum % 2 == presses % 2 && sum <= presses) {
14             int status = pressArr[0] ^ pressArr[2] ^ pressArr[3];
15             if (n >= 2)
16                 status |= (pressArr[0] ^ pressArr[1]) << 1;
17             if (n >= 3)
18                 status |= (pressArr[0] ^ pressArr[2]) << 2;
19             if (n >= 4)
20                 status |= (pressArr[0] ^ pressArr[1] ^ pressArr[3]) << 3;
21             seen.insert(status);
22         }
23     }
24     return seen.size();
25 }
26 
27 int main() {
28     int n, presses;
29     cin >> n >> presses;
30     cout << calc(n, presses) << endl;
31     return 0;
32 }

判断题

若输入为2 1，则程序的输出为3。（） {{ select(27) }}

正确
错误

对于第7行代码，变量i的上界为16。（） {{ select(28) }}

正确
错误

对于任意的输入，程序的输出不会大于8。（） {{ select(29) }}

正确
错误

选择题

当输入为n = 3，presses = 2时，程序的输出为（）。 {{ select(30) }}

（4分）若删除第15~16行的代码，当输入为n = 3，presses = 2时，程序的输出为（）。 {{ select(31) }}

上述代码的时间复杂度为（）。 {{ select(32) }}

O(1)
O(logn)
O(n)
O(nlogn)

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

(1) 题目描述：

输入n（1 ≤ n ≤ 2 × 10^5）和长为n的数组a（1 ≤ a[i] ≤ n）。你可以多次执行如下操作：选择两个下标i和j，满足a[i] = a[j]。删除下标[i, j]中的元素。删除后，数组长度减小i - j + 1。输出你最多可以删多少个数。

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int inf = 0x3f3f3f3f;
05 
06 void solve() {
07     int n;
08     cin >> n;
09     vector<int> a(n + 1);
10     for (int i = 1; i <= n; i++)
11         cin >> a[i];
12     vector<int> dp(n + 1), ①;
13     for (int i = 1; i <= n; i++) {
14         dp[i] = max(dp[i], ②);
15         dp[i] = max(dp[i], ③);
16         lst[a[i]] = max( lst[a[i]],④ );
17     }
18     cout << ⑤ << endl;
19     return;
20 }
21 
22 int main() {
23     int t = 1;
24     cin >> t;
25     while (t--)
26         solve();
27     return 0;
28 }

①处应填（）。 {{ select(33) }}

lst(n + 1)
lst(n + 1, 0)
lst(n + 1, inf)
lst(n + 1, -inf)

②处应填（）。 {{ select(34) }}

dp[i - 1]
dp[i] - 1
dp[i + 1]
dp[i] + 1

③处应填（）。 {{ select(35) }}

lst[a[i]]
lst[a[i]] + i + 1
lst[a[i]] + i
lst[i] + i

④处应填（）。 {{ select(36) }}

dp[i - 1] - i
dp[i - 1] + i
dp[i + 1] - i
dp[i + 1] + i

⑤处应填（）。 {{ select(37) }}

dp[1]
dp[0]
dp[n - 1]
dp[n]

(2) 题目描述：

输入n（1 ≤ n ≤ 1 × 10^5）和长为n的数组a（0 ≤ a[i] < 2^20）。输出最小的正整数k，使得a的所有长为k的连续子数组的OR都相同。注意答案是一定存在的，因为k = n一定满足要求。

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 void solve() {
05     int n;
06     cin >> n;
07     vector<int> a(n + 1);
08     for (int i = 1; i <= n; i++)
09         cin >> a[i];
10     int ans = 0;
11     for (int i = 0; i < ①; i++) {
12         int cnt = 0, lst = 0;
13         for (int j = 1; j <= n; j++) {
14             if (②)
15                 cnt++;
16             else
17                 lst = ③ , cnt = 0;
18         }
19         lst = max(lst, cnt);
20         if (④)
21             continue;
22         ans = max(ans, lst + 1);
23     }
24     cout << ⑤ << endl;
25     return;
26 }
27 
28 int main() {
29     int t = 1;
30     cin >> t;
31     while (t--)
32         solve();
33     return 0;
34 }

①处应填（）。 {{ select(38) }}

i < 20
i <= 20
i > 20
i != 20

②处应填（）。 {{ select(39) }}

!(a[i] & (1 << j))
a[i] & (1 << j)
a[j] & (1 << i)
!(a[j] & (1 << i))

③处应填（）。 {{ select(40) }}

min(lst, cnt)
max(lst, cnt)
cnt
lst + cnt

④处应填（）。 {{ select(41) }}

lst < n
lst != n
lst == n
lst > n

⑤处应填（）。 {{ select(42) }}

ans
min(ans, n)
min((ans == 0 ? 1 : ans), n)
(ans == 0 ? 1 : ans)

#72. 普及组CSP-J2025初赛模拟卷5

普及组CSP-J2025初赛模拟卷5

普及组CSP-J2025初赛模拟卷5

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

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

(1)

判断题

选择题

(2)

判断题

选择题

(3)

判断题

选择题

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

(1) 题目描述：

(2) 题目描述：

Status

Development

Support

#72. 普及组CSP-J2025初赛模拟卷5

普及组CSP-J2025初赛模拟卷5

普及组CSP-J2025初赛模拟卷5

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

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

(1)

判断题

选择题

(2)

判断题

选择题

(3)

判断题

选择题

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

(1) 题目描述：

(2) 题目描述：

Status

Development

Support

SIGN IN