提高组CSP-S2025初赛模拟卷1
一、单项选择题（共15题，每题2分，共计30分）
- 已知开放集合s规定，如果正整数x属于该集合，则2x和3x同样属于该集合。若集合包含1，则集合一定包含()。
{{ select(1) }}
- 2024
- 1536
- 2025
- 2026
- 在C++语言中，容器vector类型不包含函数( )。
{{ select(2) }}
- top()
- front()
- back()
- pop_back()
- 在NOI Linux系统中，列出文件夹内所有文件的命令是( )。
{{ select(3) }}
- dir
- display
- ls
- show
- 在C++语言中，(-5)/(-6)的值为( )。
{{ select(4) }}
- -1
- -3
- 1
- 3
- 已知由x个点组成的森林中有y棵树，则此森林中有( )条边。
{{ select(5) }}
- x-y+1
- x-y-1
- x-1
- x-y
- 某大学计算机系排课，某些课程需要先学才能学习后续的课程，这个排课过程中常用的算法是()。
{{ select(6) }}
- 堆排序
- 拓扑排序
- 插入排序
- 归并排序
- 迪杰斯特拉算法在最坏情况下的时间复杂度为( )。
{{ select(7) }}
- O(n log n)
- O(n² log n)
- O(n²)
- O(n³)
- 我们通常称之为FIFO的数据结构为()。
{{ select(8) }}
- 队列
- 链表
- 栈
- 向量
- 关于C++语言中类的说法中错误的是( )。
{{ select(9) }}
- 以struct声明的类中的成员默认为public形式
- 以class声明的类中的成员默认为private形式
- 以private关键字修饰的类对象，可以直接访问，但不能修改其成员数据
- 类可被认为是包含其成员的名字空间
- 若根结点在第一层，则有2025个结点的二叉树的最大深度为( )。
{{ select(10) }}
- 2024
- 2025
- 11
- 12
- 下面的编码组合中，()不是合法的哈夫曼编码。
{{ select(11) }}
- (0,1,00,11)
- (00,01,10,11)
- (0,10,110,111)
- (1,01,000,001)
- 在程序运行过程中，如果函数A调用函数B，函数B又调用函数A，这种间接调用操作的循环次数过多可能会引发()空间溢出。
{{ select(12) }}
- 队列
- 栈
- 链表
- 堆
- 若事件A和事件B相互独立，二者发生的概率相同，即 (P(A)=P(B))，且 (P(A \cup B)=0.64)，则事件A发生的概率 (P(A)=( ))。
{{ select(13) }}
- 0.3
- 0.4
- 0.6
- 0.8
- 将8本不同的书分给5个人，其中3个人各拿一本，1个人拿两本，1个人拿三本，共有()种分配法。
{{ select(14) }}
- 33600
- 36000
- 72000
- 67200
- 随机生成n个各不相同的正整数数组元素，快速排序算法的第一轮执行一遍以后，已经被排到正确位置的元素至少有()个。
{{ select(15) }}
- n / 2
- n / 3
- 1
- 0
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）
(1)
01 #include <bits/stdc++.h>
02
03 using namespace std;
04
05 #define ll long long
06
07 int read(){
08 int x=0,f=1;char ch=' ';
09 while(!isdigit(ch)) {ch=getchar();if(ch=='-') f=-1;}
10 while(isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
11 return x*f;
12 }
13
14 int a[50],Len,f[50][65],vis[50][65];
15
16 int dfs(bool Limit,bool lead,int pos,int cha){
17 if(pos==0) return cha>=30;
18 if(!Limit&&!lead&&vis[pos][cha]) return f[pos][cha];
19 int res=0;
20 int up=Limit?a[pos]:1;
21 for(int i=0;i<=up;i++){
22 res+=dfs(Limit&&(i==a[pos]),lead&&(i==0),pos-1,cha+(i==0?(lead?0:1):-1));
23 }
24 if(!Limit&&!lead) vis[pos][cha]=1,f[pos][cha]=res;
25 return res;
26 }
27
28 int solve(int x){
29 Len=0;
30 while(x){
31 a[++Len]=x%2;
32 x/=2;
33 }
34 return dfs(1,1,Len,30);
35 }
36
37 int main() {
38 int l=read(),r=read();
39 cout<<solve(r)-solve(l-1);
40 }
判断题
16. 该程序能够计算 ([l, r]) 区间内所有二进制下有且仅有一个0的数字的数量（例如 (2=10,101,1101)）。
{{ select(16) }}
- 正确
- 错误
- 如果输入0，则该程序获得结果12。
{{ select(17) }}
- 正确
- 错误
- 如果输入212，则该程序获得结果6。
{{ select(18) }}
- 正确
- 错误
- 第31行代码的执行次数不会超过60次。
{{ select(19) }}
- 正确
- 错误
选择题
20. 以下说法中正确的是( )。
{{ select(20) }}
- 该程序的时间复杂度为 (O(N \log N))
- 该程序能将double类型的数无误差地用a表示
- 输入1515时，程序输出为0
- 如果把除main函数前的int全改为long long，程序能够正确处理long long范围内的输入数据
- 对于以下哪组输入，程序会输出最大值？()
{{ select(21) }}
- 111
- 212
- 313
- 414
(2)
01 #include <algorithm>
02 #include <iostream>
03 #include <fstream>
04 #include<vector>
05 using namespace std;
06
07 const int INF =1000000000;
08 template<class T>inline int Size(const T&c){ return c.size();}
09
10 struct Impossible {};
11
12 vector<int> breeds;
13 vector<int> volumes;
14
15 void ReadInput(){
16 int n,b;cin>>n>>b;
17 for(int i=0;i<b;++i){
18 int v; cin >>v; breeds.push_back(v);
19 }
20 for(int i=0;i<n;++i){
21 int v;cin>>v; volumes.push_back(v);
22 }
23 }
24
25 vector<int> knapsack;
26
27 void ExtendKnapsack(){
28 int t=Size(knapsack);
29 int v= INF;
30 for(int i=0;i<Size(breeds);++i){
31 int t2=t-breeds[i];
32 if(t2>=0) v=min(v,1+knapsack[t2]);
33 }
34 knapsack.push_back(v);
35 }
36
37 int Knapsack(int total){
38 if(total<0) throw Impossible();
39 while(total>=Size(knapsack)) ExtendKnapsack();
40 if(knapsack[total]==INF) throw Impossible();
41 return knapsack[total];
42 }
43
44 int Solve(){
45 knapsack.assign(1,0);
46 int carry =0;
47 int res=0;
48 for(int i=0;i<Size(volumes);++i) {
49 carry =max(carry-1,0);
50 int v= volumes[i]-carry;
51 res+=Knapsack(v);
52 carry = volumes[i];
53 }
54 return res;
55 }
56
57 int main(){
58 ReadInput();
59 try{
60 cout<< Solve()<<"\n";
61 } catch (Impossible) {
62 cout<<"-1\n";
63 }
64 }
判断题（每题2分）
22. knapsack的初始容量是1。
{{ select(22) }}
- 正确
- 错误
- 如果total小于0，Knapsack函数会抛出Impossible异常。
{{ select(23) }}
- 正确
- 错误
- 如果breeds不全为0，那么输出一定不为0。
{{ select(24) }}
- 正确
- 错误
选择题
25. 若程序输入
4 3
4 2 1
0 4 5 7
则输出是()。
{{ select(25) }}
- 0
- -1
- 3
- 4
- 下列说法中正确的是( )。
{{ select(26) }}
- ExtendKnapsack函数本质上实现了一个背包功能，并且在复杂度上比普通背包更优秀
- knapsack[i]表示和为i时最少使用breeds中的数的个数（可重复使用，使用几次计几个）
- 这段代码的时间复杂度是O(K*N)（K指的是a数组的值域，N指的是a数组的大小）
- 若volume[i]都为一个值的话，程序要么输出0，要么输出-1
(3)
01 #include <bits/stdc++.h>
02 using namespace std;
03 #define N 2000005
04 int n,a[N];
05 pair<int,int> dp[N][10],ans;
06 string s,b="bessie";
07 pair<int,int> add(pair<int,int> x,pair<int,int> y) {
08 return {x.first+y.first,x.second+y.second};
09 }
10 pair<int,int> Max(pair<int,int> x,pair<int,int> y) {
11 if(x.first==y.first) {
12 if(x.second<y.second) return x;
13 return y;
14 }
15 if(x.first>y.first) return x;
16 return y;
17 }
18 int main() {
19 cin>>s;
20 n=s.size();
21 s=" "+s;
22 for(int i=1;i<=n;i++) scanf("%d",&a[i]);
23 for(int i=0;i<=n;i++) {
24 for(int j=0;j<=6;j++) dp[i][j]={-100,100};
25 }
26 dp[0][0]={0,0};
27 for(int i=1;i<=n;i++) {
28 dp[i][0]=dp[i-1][0];
29 if(s[i]==b[6]) dp[i][0]=Max(dp[i][0],add(dp[i-1][5],{1,0}));
30 for(int j=1;j<=5;j++) {
31 dp[i][j]=add(dp[i-1][j],{0,a[i]});
32 if(s[i]==b[j]) dp[i][j]=Max(dp[i][j],dp[i-1][j-1]);
33 }
34 }
35 for(int i=0;i<=5;i++) ans=Max(ans,dp[n][i]);
36 printf("%d %d",ans.first,ans.second);
37 }
判断题（每题2分）
27. 本题中ans.second表示的是满足字符串bessie出现次数最少的条件时最大的删除代价和。
{{ select(27) }}
- 正确
- 错误
- 如果将第6行代码修改为
string s,b="?beef";，程序将变成求s删去若干字符后最多能出现多少个beef以及求满足bessie出现次数最多的前提下最小的删除代价和。
{{ select(28) }}
- 正确
- 错误
选择题
29. dp[i][j].first的含义是()。
{{ select(29) }}
- 通过删除一些字符，字符串前i位匹配到bessie的第j位的，之前匹配了 dp[i][j].first个bessie
- 通过删除一些字符，字符串前i位匹配到bessie的第j位的，之前匹配了 dp[i][j].second个bessie
- 通过删除一些字符，字符串前i位有j个bessie，并且最后匹配到字符串b的 dp[i][j].first-1位
- 通过删除一些字符，字符串前i位有j个bessie，并且最后匹配到字符串b的 dp[i][j].first位
- 如果本题中输入：
Besgiraffesiebessibessie
111111111111111111111111
则程序输出为()。
{{ select(30) }}
- 1 18
- 2 13
- 1 0
- 3 7
- 对于以下哪种情况，程序可能会发生运行错误或者输出错误答案？( )
{{ select(31) }}
- 输入了一个长度为0的字符串
- 输入了一个长度为200000-2的字符串，并且数组a的平均值不超过10000
- 输入了一个长度为200000的字符串，并且数组a的平均值超过100000
- 输入了一个长度为200000+100的字符串，并且a都是1
- 下列说法中正确的是()。
{{ select(32) }}
- 在本段程序中Max({1,4},{2,3})返回{1,4}
- 将第24行代码
dp[i][j]={-100,100};改成dp[i][j]={-1,1};，程序仍能运行并且输出正确答案 - 在一些情况下，dp[n][6]也可能是正确答案
- 这段代码的时间复杂度是 (O(M \log N))，其中 N 代表字符串的长度
三、完善程序（单选题，每小题3分，共计30分）
(1)
01 #include <bits/stdc++.h>
02 #define NMAX 50010
03 using namespace std;
04 struct station {
05 int pos,cost;
06 bool operator<(station const &o) const { return pos<o.pos; }
07 };
08 station stations[NMAX];
09 int s[NMAX];
10 int nextSmall[NMAX];
11 int main(){
12 int n, maxGas, curGas, dist;
13 scanf("%d%d%d%d",&n,&maxGas,&curGas,&dist);
14 for(int i=1;i<=n; i++) {
15 scanf("%d",&stations[i].pos);
16 scanf("%d",&stations[i].cost);
17 }
18 sort(①);
19 int stacklen=0;
20 for (int i=n;i>=1;i--) {
21 while (stacklen>0 && ②) stacklen--;
22 nextSmall[i]=(stacklen==0 ? -1 : s[stacklen-1]);
23 s[stacklen] = i;
24 stacklen++;
25 }
26 curGas -= stations[1].pos;
27 long long cost = 0;
28 for (int i=1;i<=n;i++) {
29 if(③) {
30 printf("-1\n");
31 return 0;
32 }
33 int gasNeeded = min(maxGas, (nextSmall[i]==-1 ? dist : ④) - stations[i].pos);
34 if (gasNeeded > curGas)
35 cost += ⑤;
36 curGas = gasNeeded;
37 curGas -= ((i==n ? dist : stations[i+1].pos) - stations[i].pos);
38 }
39 if (curGas<0) printf("-1\n");
40 else printf("%lld\n",cost);
41 }
- ①处应填( )。
{{ select(33) }}
- stations+1,stations+n
- stations+1,stations+n+1
- stations,stations+n+1
- stations,stations+n
- ②处应填()。
{{ select(34) }}
- stations[s[stacklen-1]].cost>=stations[i].cost
- stations[s[stacklen]].cost>=stations[i].cost
- stations[stacklen-1].cost >=stations[i].cost
- stations[stacklen].cost >=stations[i].cost
- ③处应填()。
{{ select(35) }}
- curGas<=0
- curGas=0
- curGas<0
- curGas>0
- ④处应填()。
{{ select(36) }}
- stations[nextSmall[i]].pos
- stations[nextSmall[i-1]].pos
- nextSmall[i]
- nextSmall[i-1]
- ⑤处应填()。
{{ select(37) }}
- (long long)(gasNeeded) * (long long)stations[i].cost
- (long long)(gasNeeded - curGas) * (long long)stations[i].cost
- (long long)(nowneed) * (long long)stations[i].cost
- (long long)(gasNeeded - curGas) * (long long)stations[i+1].cost
(2)
01 #include <cstdio>
02 #include <cassert>
03 #include <cstring>
04 #include <vector>
05 using namespace std;
06 #define NMAX 100000
07 struct Node {
08 bool isFile;
09 vector<Node*> children;
10 int namelen;
11 int numLeaves;
12 long long totalSubtreeLen;
13 long long total;
14 };
15 Node nodes[NMAX];
16 int n;
17 int nleaves;
18 void dfs1(Node* node) {
19 node->numLeaves = (node->isFile ? 1 : 0);
20 node->totalSubtreeLen = 0;
21 for (Node* child : node->children) {
22 dfs1(child);
23 node->numLeaves += child->numLeaves;
24 node->totalSubtreeLen += child->totalSubtreeLen + ①;
25 }
26 }
27 void dfs2(Node* node, long long parentlen) {
28 node->total = ②;
29 long long plenadd = 0;
30 for(Node* child : node->children) {
31 plenadd += child->totalSubtreeLen + child->numLeaves * (child->namelen + (child->isFile ? 0 : 1));
32 }
33 for(Node* child : node->children) {
34 dfs2(child, parentlen + plenadd - (child->totalSubtreeLen + child->numLeaves * (child->namelen + (child->isFile ? 0 : 1)) + ③);
35 }
36 }
37 int main() {
38 scanf("%d",&n);
39 char name[40];
40 nleaves=0;
41 for (int i=0; i<n; i++) {
42 scanf("%s",name);
43 nodes[i].namelen = strlen(name);
44 int numChildren;
45 scanf("%d",&numChildren);
46 nodes[i].isFile = ④;
47 if (nodes[i].isFile) nleaves++;
48 for (int j=0;j<numChildren; j++) {
49 int id;
50 scanf("%d",&id);
51 nodes[i].children.push_back(&nodes[id-1]);
52 }
53 }
54 assert(!nodes[0].isFile);
55 dfs1(nodes[0]);
56 dfs2(nodes[0],0);
57 long long ans=nodes[0].total;
58 for (int i=0;i<n; i++) {
59 if(!nodes[i].isFile) ⑤;
60 }
61 printf("%lld\n",ans);
62 }
- ①处应填( )。
{{ select(38) }}
- child->numLeaves
- child->numLeaves * (child->namelen)
- child->numLeaves * (child->namelen + (child->isFile ? 0 : 1))
- child->numLeaves * (child->namelen + (child->isFile ? 0 : 1) + child->children.size())
- ②处应填()。
{{ select(39) }}
- parentlen + (node->isFile ? 0 : node->totalSubtreeLen)
- parentlen + (node->isFile ? node->totalSubtreeLen : 0)
- parentlen
- parentlen + node->totalSubtreeLen
- ③处应填()。
{{ select(40) }}
- 1 * (nleaves - child->numLeaves)
- 3 * (nleaves - child->numLeaves)
- 1 * nleaves
- 3 * nleaves
- ④处应填( )。
{{ select(41) }}
- numChildren>0
- numChildren==1
- numChildren=0
- numChildren==0
- ⑤处应填( )。
{{ select(42) }}
- ans = nodes[i].total
- ans = min(ans, nodes[i].total)
- ans = max(ans, nodes[i].total)
- ans = -1