#77. 普及组CSP-J2025初赛模拟卷10
-
ID: 77
Type: Objective
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
jike1994
Tags> 普及组CSP-J2025初赛模拟卷10
普及组CSP-J2025初赛模拟卷10
一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
- 以下列扩展名结尾的文件，不是多媒体文件的是（ ） {{ select(1) }}
- mp3
- txt
- avi
- jpg
- 以下关于链表和数组的描述中，错误的是（ ） {{ select(2) }}
- 数组和链表都可以排序
- 数组中查询元素的效率比较高
- 链表中插入和删除元素的效率比较高
- 向量和静态数组一样，不能动态调整数组大小
- 与C++语言中的
cout<<a>b?'a':'b';功能类似的是（ ） {{ select(3) }}
- 顺序结构
- 循环结构
- 条件结构
- 递推函数
- 下面的C++代码中
data占用（ ）字节内存空间。union Data { int no; double score; char name[6]; }; union Data data;
{{ select(4) }}
- 4
- 8
- 18
- 6
- 学号为1到30的幼儿园小朋友顺时针围成一圈，从1号小朋友开始按顺时针方向报数，报数从0开始，依次为0,1,2,3，…,28,29,30,31,32，…，一圈又一圈，报数到数字n的小朋友的学号是多少？（ ） {{ select(5) }}
- n%30+1
- (n+1)%30
- (n+1)%30+1
- n%30
- 以下哪个不属于STL模板中队列的操作函数？（ ） {{ select(6) }}
- push
- pop
- empty
- top
- 在C++语言中，（ ）算法的时间复杂度是O(nlogn)。 {{ select(7) }}
- 插入排序
- 归并排序
- 选择排序
- 冒泡排序
- 以下关于字符串的判定语句中正确的是（ ） {{ select(8) }}
- 字符串一般以字符'0'结尾
- 串的长度必须大于零
string s;中定义的s也可以看作字符数组，首字母是s[0]- 全部都由空格字符组成的串就是空串
- 以下算法中，（ ）算法用到了栈。 {{ select(9) }}
- BFS
- 二分查找
- DFS
- 贪心
- 32位计算机系统中，一个非负长整型指针变量
unsigned long long *p占（ ）字节。 {{ select(10) }}
- 1
- 2
- 8
- 4
- 某山峰型数列有1~2025共2025个各不相同的数，先是奇数由小到大，后是偶数由大到小，即1，3，5，7,9，……2023,2025,2024,2022,2020，…8,6,4,2。现要对该数列进行检索，查找某正整数x的下标（x为1~2025中的某正整数，包含1和2025），最多检索（ ）次即可。 {{ select(11) }}
- 2025
- 11
- 10
- 9
- 在C++程序中，
lowbit(x)函数返回整数x在二进制表示下最低一位1以及后续0一起表示的数字，如lowbit(12)=4。下面的表达式中，（ ）能得到相同的结果。 {{ select(12) }}
- x ^ (x - 1)
- x & (x - 1)
- x & (~x + 1)
- x | (x - 1)
- 某二叉树的中序遍历序列为BDCEAFHG，后序遍历序列为DECBHGFA，其前序遍历序列为（ ） {{ select(13) }}
- ABCDEFGH
- ABDCEFHG
- ABCDFEHG
- ABDCEFGH
- 有5条线段，长度分别为1,3,5,7,9。从中任取3条能构成一个三角形的概率为（ ） {{ select(14) }}
- 1/2
- 3/10
- 1/5
- 2/5
- 对于非负整数组{x,y,z}，满足x+2y+3z=100的非负整数解组数为（ ）个。 {{ select(15) }}
- 886
- 885
- 884
- 883
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）
(1)
01 #include<bits/stdc++.h>
02 using namespace std;
03 const int N=2e4+5,inf=2e9+7;
04 int n, a[N], ans=inf;
05 int main() {
06 scanf("%d",&n);
07 for (int i=1;i<=n;i++)
08 scanf("%d",&a[i]);
09 sort(a+1,a+n+1);
10 for (int i=2;i<=n;i+=2) {
11 int mi=inf,ma=-inf,x=0;
12 for (int j=1;j<=i;++j) {
13 x=a[j]+a[i-j+1];
14 mi=min(mi,x),ma=max(ma,x);
15 }
16 if (i^n)
17 ans=min(ans,max(a[n],ma)-min(a[i+1],mi));
18 else
19 ans=min(ans,ma-mi);
20 }
21 return printf("%d\n",ans),0;
22 }
判断题
- 若将程序第12行中的
i改成i/2，程序的输出结果一定不会改变。（ ） {{ select(16) }}
- 正确
- 错误
- （2分）若将程序第10行中的
i+=2改成i++，程序的输出结果一定不会改变。（ ） {{ select(17) }}
- 正确
- 错误
- 若将头文件
#include<bits/stdc++.h>改成#include<iostream>，程序仍能正常运行。（ ） {{ select(18) }}
- 正确
- 错误
选择题
- 若输入
4 1 3 6 7，则输出为（ ） {{ select(19) }}
- 0
- 1
- 2
- 3
- （4分）若输入
7 2 8 9 15 17 18 16，则输出为（ ） {{ select(20) }}
- 2
- 3
- 4
- 5
(2)
01 #include<bits/stdc++.h>
02 using namespace std;
03 int n, m,k,l,r,mid;
04 int check(int g) {
05 int st=1,ed=m,cnt=0;
06 while(st<=n && ed>=1) {
07 if(st*ed>g)
08 ed--;
09 else {
10 cnt+=ed;
11 st++;
12 }
13 }
14 return cnt>=k;
15 }
16 int main() {
17 scanf("%d%d%d",&n,&m,&k);
18 l=1,r=n*m;
19 while(l<r) {
20 mid=(l+r)/2;
21 if(check(mid))r=mid;
22 else l=mid+1;
23 }
24 cout<<l<<endl;
25 return 0;
26 }
判断题
- 每次运行
check时，第7行必定运行n次。（ ） {{ select(21) }}
- 正确
- 错误
- 如果保证
m=1，则输出一定为k。（ ） {{ select(22) }}
- 正确
- 错误
- 若将第21行中的
r=mid改成r=mid-1，程序输出一定不变。（ ） {{ select(23) }}
- 正确
- 错误
- 第24行可以改成
cout<<r<<endl;。（ ） {{ select(24) }}
- 正确
- 错误
选择题
- 该程序的时间复杂度为（ ） {{ select(25) }}
- O(n)
- O(nlogn)
- O(n^2)
- O(nk)
- 若输入为
2 3 4，则输出为（ ） {{ select(26) }}
- 1
- 2
- 3
- 6
(3)
01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N=10,dx[10]={0,1,0,-1,0},dy[10]={0,0,1,0,-1};
04 int n,m,ans;
05 char c[N][N];
06 void dfs(int x) {
07 if (!x) return ++ans,void();
08 vector<int> v; v.clear();
09 for (int i=1;i<=n;++i)
10 for (int j=1;j<=n;++j)
11 if (c[i][j]=='#') {
12 bool flag=0;
13 for (int k=1;k<=4;++k) {
14 int tx=i+dx[k],ty=j+dy[k];
15 flag|=tx>=1&&tx<=n&&ty>=1&&ty<=n&&c[tx][ty]== 1;
16 }
17 if(flag)
18 v.push_back(i*10+j),c[i][j]=1,dfs(x-1),c[i][j]='#';
19 }
20 if(!v.empty())
21 for (int i=0;i<v.size();++i)
22 c[v[i]/10][v[i]%10]='.';
23 }
24 int main() {
25 scanf("%d%d",&n,&m);
26 for (int i=1;i<=n;++i)
27 scanf("%s",c[i]+1);
28 for (int i=1;i<=n;++i)
29 for (int j=1;j<=n;++j)
30 if(c[i][j]=='.')
31 c[i][j]=1,dfs(m-1),c[i][j]='#';
32 return printf("%d\n",ans),0;
33 }
判断题
- 将第18行中的
c[i][j]='#'去除，结果一定不变。（ ） {{ select(27) }}
- 正确
- 错误
- 第6行运行的次数不超过
n^2 * 4^m。（ ） {{ select(28) }}
- 正确
- 错误
选择题
- 若输入为
2 2 #. ..，则输出为（ ） {{ select(29) }}
- 0
- 1
- 2
- 3
- 若输入为
3 5 #.# ... .#.，则输出为（ ） {{ select(30) }}
- 2
- 3
- 4
- 5
- （4分）若
n=3，m=3，则输出的最大值为（ ） {{ select(31) }}
- 16
- 18
- 22
- 26
- 若
n=4，m=13，则输出的最大值为（ ） {{ select(32) }}
- 488
- 496
- 512
- 560
三、完善程序（单选题，每小题3分，共计30分）
(1) 题目描述：
给定两个由小写字母构成的字符串s1和s2，同时给定一个由数字1,2,3...| operation |组成的排列。按该排列顺序依次删除字符串s1相应位置上的字母，在删除过程中，约定各个字符的位置不变。请计算最多可以删除几次，字符串s1中仍然包含字符串s2（即字符串s2仍然是字符串s1的子串）。
01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 2e5 + 5;
04 bool book[N];
05 char s1[N], s2[N];
06 vector<int> num;
07 int n = 1, len1, len2, ans, operation[N];
08 bool check(int x) {
09 num.clear();
10 for (int i = x + 1; i <= n; i++)
11 if (①)
12 num.push_back(operation[i]);
13 sort(num.begin(), num.end());
14 int i = 0, j = 1;
15 while (②)
16 j += ③;
17 return j == len2 + 1;
18 }
19 inline void func(int l, int r) {
20 if (④) return;
21 int mid = (l + r) >> 1;
22 if (check(mid)) ans = mid, func(mid + 1, r);
23 else func(l, mid - 1);
24 }
25 int main() {
26 scanf("%s", s1 + 1);
27 scanf("%s", s2 + 1);
28 len1 = strlen(s1 + 1);
29 len2 = strlen(s2 + 1);
30 while (⑤) ++n;
31 n--;
32 for (int i = 1; i <= len2; i++)
33 book[int(s2[i])] = true;
34 func(1, n);
35 printf("%d\n", ans);
36 return 0;
37 }
- ①处应填（ ） {{ select(33) }}
- book[s1[operation[i]]]
- book[s1[i]]
- !book[s1[operation[i]]]
- !book[s1[i]]
- ②处应填（ ） {{ select(34) }}
- i < num.size() && j <= len2
- i <= num.size() && j <= len2
- i <= num.size() && j < len2
- i < num.size() && j < len2
- ③处应填（ ） {{ select(35) }}
- s1[num[i++]] == s2[j]
- s1[num[++i]] == s2[j]
- s1[num[i++]] == s2[j++]
- s1[num[++i]] == s2[j++]
- ④处应填（ ） {{ select(36) }}
- l >= r
- l == r
- l > r
- l ^ r
- ⑤处应填（ ） {{ select(37) }}
- scanf("%d", &operation[n])
- ~scanf("%d", &operation[n])
- ~(cin >> operation[n])
- scanf("%d", operation[n])
(2) 题目描述：
如果存在一个长度为n的排列（即该排列由1,2,3，…，n这n个数字各出现一次组成）对于所有满足2≤i≤n-1的整数i，都有pi<=pi-1，pi<=pi+1或者pi>=pi-1，pi>=pi+1成立，则称这个序列为一个山峰山谷序列。 对所有长度为n的山峰山谷序列排序，求字典序第k大的排列。 dpi，j，0/1表示长度为i的排列中第一个数为j，其中第一个数小于/大于第二个数。
01 #include<bits/stdc++.h>
02 using namespace std;
03 const int N=105;
04 int n, k, dp[N][N][2], ans[N], vis[N];
05 signed main(){
06 scanf("%d%d", &n, &k);
07 dp[1][1][0] = dp[1][1][1] = 1;
08 dp[2][1][0] = dp[2][2][1] = 1;
09 for (int i = 2; i < n; ++i)
10 for (int j = 1; j <= i; ++j)
11 for (int k = 1; k <= i + 1; ++k)
12 if (①) dp[i + 1][k][1] += dp[i][j][0];
13 else ②;
14 for (int i = 1; i <= n; ++i) {
15 int las = 0, mk = 1;
16 if (i > 2 && ans[i - 1] < ans[i - 2])
17 mk = ③;
18 for (int j = mk; j <= n; ++j)
19 if (!vis[j]) {
20 int cnt = 0;
21 for (int k = 1; k <= j; ++k) if (!vis[k]) cnt++;
22 int x = ④;
23 if(i == 1) x += dp[n][j][0];
24 if (x >= k) { las = j; break; }
25 ⑤;
26 }
27 ans[i] = las, vis[las] = 1;
28 }
29 for (int i = 1; i <= n; ++i)
30 printf("%d ", ans[i]);
31 return 0;
32 }
- ①处应填（ ） {{ select(38) }}
- j < k
- j <= k
- i < k
- i <= k
- ②处应填（ ） {{ select(39) }}
- dp[i + 1][k][1] += dp[i][j][0]
- dp[i + 1][k][0] += dp[i][j][1]
- dp[i + 1][j][1] += dp[i][k][0]
- dp[i + 1][j][0] += dp[i][k][1]
- ③处应填（ ） {{ select(40) }}
- ans[i - 1] + 1
- ans[i - 2] + 1
- i + 1
- ans[i - 1]
- ④处应填（ ） {{ select(41) }}
- dp[n - i + 1][cnt][ans[i - 1] < j]
- dp[n - i + 1][cnt][ans[i - 1] > j]
- dp[n - i + 1][j - cnt][ans[i - 1] > j]
- dp[n - i + 1][j - cnt][ans[i - 1] < j]
- ⑤处应填（ ） {{ select(42) }}
- k -= x
- k -= x * (n - i + 1)
- k -= x * cnt
- k -= x * mk