#10624. 提高组CSP-S2025初赛模拟卷7

提高组CSP-S2025初赛模拟卷7

提高组 CSP-S 2025 初赛模拟卷 7

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

  1. 在 NOI Linux 系统终端的调试工具 GDB 的使用中，以下（ ）命令可以用来查看某个变量的值，并一直显示直到关闭或者程序结束。
    {{ select(1) }}
  • print
  • printf
  • show
  • display
  1. 以下关于数据结构的表述中不恰当的一项是（ ）。
    {{ select(2) }}
  • 并查集常用森林来表示
  • AVL 树插入破坏平衡的情况只有两种类型——LR 和 RL
  • 线段树维护的常见区间信息包括区间最大值、区间最小值、区间相等
  • 树状数组是主要用于前缀信息维护的一维数组
  1. 在 C++语言中，以下（ ）函数声明是合法的。
    {{ select(3) }}
  • int InsertSort(char a[], int n);
  • int InsertSort(char a[10]], int n);
  • int InsertSort(char a[][]20], int n);
  • int InsertSort(char[,] a, int n);
  1. 对于给定的代码，调用 fun(5,6)得到的结果是（ ）。
    {{ select(4) }}
  • 210
  • 126
  • 252
  • 240
  1. 二项展开式(x+yx+y)的系数正好满足杨辉三角的规律，二项展开式中 xy9xy^9项的系数是（ ）。
    {{ select(5) }}
  • 5
  • 9
  • 10
  • 8
  1. 以下不属于 TCP/IP 协议族中网络协议的是（ ）。
    {{ select(6) }}
  • IMAP
  • HTML
  • TELNET
  • UDP
  1. 构建具有 n 个元素的笛卡儿树的时间复杂度是（ ）。
    {{ select(7) }}
  • O(log⁡n)O(\log n)
  • O(n)O(n)
  • O(n2)O(n^2)
  • O(nlog⁡n)O(n\log n)
  1. 考虑对 n 个数进行排序，以下方法中最坏情况下时间复杂度最差的排序方法是（ ）。
    {{ select(8) }}
  • 桶排序
  • 快速排序
  • 堆排序
  • 归并排序
  1. 下面关于序列 {2,7,1,5,6,4,3,8,9}\{2, 7, 1, 5, 6, 4, 3, 8, 9\}的说法中正确的是（ ）。
    {{ select(9) }}
  • {6,4,3}\{6, 4, 3\}是它的唯一最长连续下降子序列
  • {1,5,6}\{1, 5, 6\}是它的唯一最长连续上升子序列
  • {1,5,6,8,9}\{1, 5, 6, 8, 9\}是它的唯一最长上升子序列
  • {7,5,4,3}\{7, 5, 4, 3\}是它的唯一最长下降子序列
  1. 给定地址区间为 0~13 的哈希表，哈希函数为 h(x)=x%13h(x) = x \% 13，采用线性探查的冲突解决策略（如果出现冲突情况，会往后探查第一个空的地址存储；若地址 13 冲突了，则从地址 0 重新开始探查）。哈希表初始为空表，依次存储 (65,34,27,80,22,57,78)(65, 34, 27, 80, 22, 57, 78)后，请问 78 存储在哈希表的哪个地址中？（ ）
    {{ select(10) }}
  • 1
  • 2
  • 3
  • 4
  1. 对于一个无向连通图 G，顶点之间的强连通关系不具有（ ）。
    {{ select(11) }}
  • 传递性
  • 自反性
  • 对称性
  • 偏序性
  1. 以下 C++程序运行后的输出结果为（ ）。
    {{ select(12) }}
  • 84
  • 90
  • 91
  • 96
  1. 下面的程序使用出边的邻接表表示有向图，则下列选项中哪个是它表示的图？（ ）

{{ select(13) }}

  1. 从不超过 30 的质数中随机抽取 2 个质数组成质数对 (m,n) (m,n) ，其中 m≤n m \leq n ，则这 2 个质数组成的质数对中满足 n−m≤3 n - m \leq 3 的概率为（ ）。
    {{ select(14) }}
  • 2/15
  • 17/30
  • 11/15
  • 7/12
  1. 在 4×4 方格表中，将若干格子染成黑色，每行每列恰有两个黑色格子的染色方法数为（ ）。
    {{ select(15) }}
  • 90
  • 72
  • 84
  • 96

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N=3e5+10;
04 int n,k;char temp;
05 bool a[N];int dp[N];
06 int sum1[N];int sum2[N];
07 int Stack[N];int head=1;int tail=0;
08 int main() {
09 scanf("%d%d",&n,&k);
10 getchar();
11 for(int i=1;i<=n;i++) {
12 temp=getchar();
13 if(temp=='H')a[i]=0,sum1[i]+t;
14 else a[i]=1,sum2[i]+t;
15 sum1[i]+=sum1[i-1];sum2[i]+=sum2[i-1];
16 }
17 Stack[++tail]=0;
18 for(int i=1;i<=n;i++) {
19 while(head<=tail&&i=Stack[head]>)++head;
20 dp[i]=dp[Stack[head]]+(sum1[i]-sum2[i]) <=(sum1[Stack[head]]-sum2[Stack[head]]));
21 while(head<=tail&&((dp[i]*dp[Stack[tail]])) || (dp[i]==dp[Stack[tail]]
22 &&(sum1[i]-sum2[i])<=(sum1[Stack[tail]]-sum2[Stack[tail]])))
23 tail--;
24 Stack[++tail]=i;
25 }
26 printf("%d",dp[n]);
27 return 0;
28 }

假设输入满足 1≤k≤n≤3e51 \leq k \leq n \leq 3e5，s 的长度为 n 且只含有 'H' 和 'G'。

判断题
  1. 这段代码的时间复杂度为 O(N)O(N)。
    {{ select(16) }}
  • √
  • ×
  1. 代码运行到第 20 行时，head 永远小于 tail。
    {{ select(17) }}
  • √
  • ×
  1. 删除第 10 行代码，程序运行结果可能改变。
    {{ select(18) }}
  • √
  • ×
选择题
  1. 若程序输入
    5 2
    GGHGG
    则程序的输出是（ ）。
    {{ select(19) }}
  • 0
  • 1
  • 2
  • 3
  1. 若程序输入
    7 2
    HGHGGHG
    则程序的输出是（ ）。
    {{ select(20) }}
  • 1
  • 2
  • 3
  • 4
  1. 程序运行到最后一行时，以下哪个选项不成立？（ ）
    {{ select(21) }}
  • sum1[n]+sum2[n] == n
  • tail-head <= n
  • stack[1] = 0
  • dp[n] 不一定是 dp 数组中的最小值

(2)

01 #include <bits/stdc++.h>
02 #define int long long
03 using namespace std;
04 int n,a[1000010],b[1000010],now,ans,front,N=1000000,c[3000010],id;
05
06 int lowbit(int x){return x6-x;}
07
08 void update(int x,int v){
09    x+=N;
10    for(int i=x;i<=n+N;i+=lowbit(i)) c[i]+=v;
11 }
12
13 int sum(int x) {
14    x+=N;
15    int ans=0;
16    for(int i=x;i;i-=lowbit(i)) ans+=c[i];
17    return ans;
18 }
19
20 signed main() {
21    ios::sync_with_stdio(0);
22    cin.tie(0),cout.tie(0);
23    cin>>n;
24    for(int i=0;i<n;i++) {
25    cin>>a[i];
26    b[i]=a[i]-(i+1);
27    now+=abs(b[i]);
28    update(b[i],1);
29 }
30    ans=now,id=0;
31    for(int i=i;i<n;i++) {
32    front=(front-1+n)%n;
33    b[front]--i-1;
34    now--abs(b[front]);
35    update(b[front],-1);
36    b[front]+=n-1;
37    now+=abs(b[front]);
38    int x=sum(0);
39    update(b[front],1);
40    N++;
41    now+=x*2-n+1;
42    if(ans>now) ans=now,id=i;
43 }
44    cout<<ans<<" "<<id;
45    return 0;
46 }

假设输入的是一个长度为 n n 的排列，并且 1≤n≤1e6 1 \leq n \leq 1e6 。

判断题（每题2分）
  1. lowbit(114514)的结果是2。
    {{ select(22) }}
  • √
  • ×
  1. 当 n=3 n=3 时，程序输出的 ans 值为6。
    {{ select(23) }}
  • √
  • ×
  1. 第32行代码 front=(front-1+n)%n 可以改成 front=(front)%n-1。
    {{ select(24) }}
  • √
  • ×
选择题
  1. 第35行中 update(b[front],-1)的作用是（ ）。
    {{ select(25) }}
  • 将 [1,b[front]] 的元素都减去1
  • 将 (b[front],n] 的元素都减去1
  • 将 b[front] 位置的元素减去1
  • 以上说法都不对
  1. 若程序输入
    3
    2 3 1
    则程序的输出为（ ）。
    {{ select(26) }}
  • 0 0
  • 0 1
  • 1 0
  • 1 1
  1. （4分）若程序输入
    5
    1 3 4 5 2
    则程序的输出为（ ）。
    {{ select(27) }}
  • 1 1
  • 1 2
  • 2 1
  • 2 2

(3)

01 #include <iostream>  
02 #include <cstdio>  
03 #include <cstring>  
04 using namespace std;  
05 const int N=1e7+10,INF=1e9;  
06 int n,m;  
07 char a[N],b[N];  
08 int z[N],p[N],f[N];  
09 int l,r,q[N];  
10 void Z(char *s,int n)
11 {
12 z[i]=n;
13 for(int i=2, l=0, r=0; i<=n; i++)
14 {
15 if(i<=r)z[i]=min(z[i-l+1], r-i+1);
16 while(i+z[i]<=n665[i+z[i]]==s[z[i]+1])z[i]+*;
17 if(i+z[i]-l>r)l=i, r=i+z[i]-1;
18 }
19 }
20 void exkmp(char *s,int n,char *t,int m)
21 {
22 Z(t,m);
23 for(int i=1, l=0, r=0; i<=n; i++)
24 {
25 if(i<=r)p[i]=min(z[i-l+1], r-i+1);
26 while(i+p[i]<=n665[i+p[i]]==t[p[i]+1])p[i]+*;
27 if(i+p[i]-l>r)l=i, r=i+p[i]-1;
28 }
29 }
30 int main()
31 {
32 scanf("%d %d %s %s", 6m, 6n, b+1, a+1);
33 exkmp(a,n,b,m);
34 for(int i=1, j=0; i<=n; i++)
35 j>i+p[i]>p[i]=0:j=i+p[i];
36 memset(f,0x3f,sizeof(f));
37 f[a[l-r=1]=n+1]=0;
38 for(int i=n; i; i--)
39 {
40 if(!p[i])continue;
41 while(!<r660q[l]>i+p[i])l++;
42 f[i]=f[a[l]]+1;
43 q[l+r]=i;
44 }
45 if(f[l]<=INF)printf("%d\n", f[1]);
46 else puts("Fake");
47 return 0;
48 }

假设输入满足 1≤n,m≤1e71 \leq n, m \leq 1e7，并且 ∣a∣=n,∣b∣=m|a|=n, |b|=m。

判断题
  1. 如果字符串 a 和 b 不能完全匹配，代码会输出 Fake。
    {{ select(28) }}
  • √
  • ×
  1. a 的长度必须小于或等于 b 的长度，否则只能输出 Fake。
    {{ select(29) }}
  • √
  • ×
  1. 本段代码的时间复杂度是 O(N)O(N)。
    {{ select(30) }}
  • √
  • ×
选择题
  1. 若程序读入
    3 5
    aba
    ababa
    则 z 数组为（ ）。
    {{ select(31) }}
  • 3 0 1
  • 3 1 0
  • 3 0 0
  • 3 2 1
  1. 程序读入
    3 5
    aba
    ababa
    后，f[i](1≤i≤5)f[i] (1 \leq i \leq 5) 数组中 INF（即 0×3f3f3f0 \times 3 f 3 f 3 f）的个数为（ ）。
    {{ select(32) }}
  • 0
  • 1
  • 2
  • 3

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

(1) 题目描述：

有 n 株草，第 i 株的高度为 (a1109)(a_1 10^9)，你可以预先拔掉不超过 k 株草，然后按如下方式操作：

选取没拔掉的最高的草（高度为 h），一次拔掉所有高度 > h2\frac{h}{2} 的草。

你需要在操作次数最少的情况下，最小化预先拔掉的草的数量。

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 const int N = 2e5 + 1;
05 int n, k, a[N], f[N][55];
06
07 int main()
08 {
09 scanf("%d %d", 6n, 6k);
10 for (int i = 1; i <= n; ++i) scanf("%d", 6a[i]);
11 sort(a + 1, a + n + 1);
12 memset(f, 127, sizeof f);
13 f[0][0] = 0;
14 int P=O;
15 for (int i = 1; i <= n; ++i)
16 {
17 if (i <= k) f[i][0] = i;
18 int p = \emptyset;
19 for (int j = 1; j < P; ++j)
20 f[i][j] = min(\emptyset);
21 }
22 for (int i = 0; i < P; ++i)
23 if (\emptyset)
24 {
25 printf("%d %d", i, f[n][i]);
26 \emptyset
27 }
28 return 0;
29 }
  1. ①处应填（ ）。
    {{ select(33) }}
  • 30
  • 31
  • 63
  • 64
  1. ②处应填（ ）。
    {{ select(34) }}
  • upper_bound(a + 1, a + i + 1, a[i] / 2) - a - 1
  • upper_bound(a + 1, a + i + 1, a[i] ) - a - 1
  • upper_bound(a + 1, a + i + 1, a[i] / 2) - a
  • upper_bound(a + 1, a + i + 1, a[i] ) - a
  1. ③处应填（ ）。
    {{ select(35) }}
  • f[i - 1][j] + 1, f[i][j]
  • f[i - 1][j] + 1, f[i][j - 1]
  • f[i - 1][j] + 1, f[p][j]
  • f[i - 1][j] + 1, f[p][j - 1]
  1. ④处应填（ ）。
    {{ select(36) }}
  • f[n][i] <= P
  • f[n][i] < P
  • f[n][i] <= k
  • f[n][i] < k
  1. ⑤处应填（ ）。
    {{ select(37) }}
  • 不填
  • return 0;
  • printf("\n");
  • continue;

(2) 题目描述：

构建一个序列 a，满足 m 条限制。限制形如 (1,r,q): (a:6a_{1+1}6\cdots 6a_{r-1}6a_{r}=q)（此处6为位运算的 AND 操作）。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int maxn=4e5+10,maxm=4e5+10;
04
05 int n,m;
06 int x,y,z;
07 int sm[maxn],lazy[maxn];
08 int s[maxm],h[maxm],t[maxm];
09
10 void pushdown(int o)
11 {
12 if(!lazy[o]) return;
13 lazy[o<<1]!=lazy[o];
14 lazy[o<<1|1]!=lazy[o];
15 sm[o<<1]!=lazy[o];
16 sm[o<<1|1]!=lazy[o];
17 ①
18 }
19 void update(int o,int l,int r)
20 {
21 if(②) {
22 lazy[o]!=z;
23 sm[o]!=z;
24 return;
25 }
26 pushdown(o);
27 int mid=(l+r)>>1;
28 if(x<=mid) update(o<<1,1,mid);
29 if(y>mid) update(o<<1|1,mid+1,r);
30 ③
31 }
32 int query(int o,int l,int r)
33 {
34 if(x<=lg6r<=y) return sm[o];
35 pushdown(o);
36 int res=④;
37 int mid=(l+r)>>1;
38 if(x<=mid) res6=query(o<<1,1,mid);
39 if(y>mid) res6=query(o<<1|1,mid+1,r);
40 return res;
41 }
42
43 int main()
44 {
45 memset(sm,0,sizeof(sm));
46 memset(lazy,0,sizeof(lazy));
47 scanf("%d%d",6n,6m);
48 for(int i=1;i<=m;i++)
49 {
50 scanf("%d%d%d",&s[i],6h[i],8t[i]);
51 x=s[i],y=h[i],z=t[i];
52 update(1,1,n);
53 }
54 for(int i=1;i<=m;i++){
55 x=s[i],y=h[i];
56 if(⑤) {
57 printf("NONn");
58 return 0;
59 }
60 }
61 printf("\YES\n");
62 for(int i=1;i<=n;i++){
63 x=y=i;
64 printf("%d ",query(1,1,n));
65 }
66 return 0;
67 }
  1. ①处应填（ ）。
    {{ select(38) }}
  • return;
  • lazy[0] = -1;
  • lazy[0] = 1;
  • lazy[0] ^= 1;
  1. ②处应填（ ）。
    {{ select(39) }}
  • x <= l || r <= y
  • x <= l && r <= y
  • !(x >= l) && !(r >= y)
  • !(x >= l) || !(r >= y)
  1. ③处应填（ ）。
    {{ select(40) }}
  • sm[0] = (sm[0<<1] | sm[0<<1|1]);
  • sm[0] = (sm[0<<1] ^ sm[0<<1|1]);
  • sm[0] = (sm[0<<1] + sm[0<<1|1]);
  • sm[0] = (sm[0<<1] & sm[0<<1|1]);
  1. ④处应填（ ）。
    {{ select(41) }}
  • res = (iul1<<29) - 1
  • res = (iul1<<30) - 1
  • res = (iul1<<31) - 1
  • res = (iul1<<32) - 1
  1. ⑤处应填（ ）。
    {{ select(42) }}
  • query(1,1,n) != t[i]
  • query(1,1,n) == t[i]
  • query(1,1,n) > t[i]
  • query(1,1,n) <= t[i]
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 闽ICP备2024031974号-1
  3. Powered by Hydro v5.0.0-beta.3 Community, Modified by Robinchen