一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)

1. 八进制数2025用二进制表示是()。

{{ select(1) }}

• 1000000101
• 10000010101
• 1000000101
• 10000100101

2. C++语言的创始人是()。

{{ select(2) }}

• 林纳斯·托瓦茨
• 丹尼斯·里奇
• 吉多·范罗苏姆
• 本贾尼·斯特劳斯特卢普

3. 以下设备中,()不是输出设备。

{{ select(3) }}

• 扫描仪
• 触摸屏
• 绘图仪
• 音箱

4. 当执行以下C++程序段后输出结果为()。

char c1='2'+'0';
char c2='2'+'5';
cout<<c1<<c2<<endl;

{{ select(4) }}

• 2025
• 27
• bg
• ch

5. 应用二分算法的思想,在一个有n个数的有序序列中查找某个指定的数m,其程序时间复杂度为()。

{{ select(5) }}

• $O(n \log n)$
• $O(n)$
• $O(\log n)$
• $O(m \log n)$

6. 贝希要参加CSP-J比赛,在CCF官网注册时需设置登录密码,下列选项中()最安全。

{{ select(6) }}

• 12345678
• abcd1234
• 20010911
• FI@CcfGq6dh

7. 双向链表的优点是()。

{{ select(7) }}

• 查找速度快
• 插入和删除方便
• 节省内存
• 后进先出

8. 小明买了一块1TB的固态硬盘,相当于()MB的存储容量。

{{ select(8) }}

• $2^{10}$
• $2^{20}$
• $2^{30}$
• $2^{40}$

9. 下面()没有用到有关人工智能的技术。

{{ select(9) }}

• 智能手机设置的闹钟定时叫我起床
• 智能手环收集患者的数据并上传至医疗系统云端进行分析
• 国家围棋队棋手和围棋机器人下围棋
• 大学校园用人脸识别门禁系统控制人员出入

10. 下列选项中()不是C++标准库string类的函数。

{{ select(10) }}

• substr
• size
• replace
• strcmp

11. 有一个2025位的正整数,它的各位数字按照如下规则排列:123456789123456789123456789…,请问这个数被9除的余数是多少?()

{{ select(11) }}

• 3
• 2
• 0
• 1

12. 九宫格数独游戏是一种训练推理能力的数字谜题游戏。九宫格分为九个小宫格,某小九宫格如图所示,小明需要在9个小格子中填上1至9中不重复的整数。小明通过推理已经得到了4个小格子中的准确数字,其中,a、b、c、d、e这5个数字未知,且b和d为奇数,则$a+b>5$的概率为()

$9$	$a$	$7$
$b$	$c$	$d$
$4$	$e$	$5$

{{ select(12) }}

• 3/5
• 1/2
• 2/3
• 1/3

13. 四位同学进行篮球传球练习,要求每个人接球后再传给别人。开始时甲同学发球,并作为第一次传球,第五次传球后,球又回到甲同学手中,则不同的传球方法有()种。

{{ select(13) }}

• 60
• 65
• 70
• 75

14. 字符串CCCSSSPPP共有()种不同的非空子串。

{{ select(14) }}

• 45
• 36
• 37
• 39

15. 向一个栈顶指针为head的链式栈中插入一个指针p指向的结点时,应执行()。

{{ select(15) }}

• head->next=p;
• p->next=head; head=p;
• p->next=head->next;head->next=p;
• p->next=head;head=head->next;

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

(1)

01#include <bits/stdc++.h>
02using namespace std;
03int t,p,a,b,c;
04int f(int a,int b){
05    if(a%b==0) return 0;
06    return b-a%b;
07}
08void solve(){
09    scanf("%d%d%d%d",&p,&a,&b,&c);
10    printf("%d",min(min(f(p,a),f(p,b)),f(p,c)));
11}
12int main(){
13    scanf("%d",&t);
14    while(t--) solve();
15    return 0;
16}

判断题

16. 若程序输入 1 26 10 9 则最终输出为4。

{{ select(16) }}

• 正确
• 错误

17. (2分)若将第5行删除,程序的输出结果一定不会改变。()

{{ select(17) }}

• 正确
• 错误

18. 若将头文件#include <bits/stdc++.h>改成#include <stdio.h>,程序仍能正常运行。

{{ select(18) }}

• 正确
• 错误

选择题

19. 若程序输入2 95 48 109 99,则输出是()。

{{ select(19) }}

• 18
• 11
• 08
• 01

20. (4分)若将第10行的输出内容改为$f(f(f(p,a),b),c)$,则输入1 26 10 9时,输出是()。

{{ select(20) }}

• 3
• 4
• 5
• 6

(2)

01#include <bits/stdc++.h>
02using namespace std;
03const int N=2e5+5;
04int a,b,n,k;
05char s[N];
06void solve(int a,int b,int k){
07    while(k--)
08        putchar(a? (--a,'1') : (--b,'0'));
09}
10int main(){
11    cin>>a>>b>>k;
12    n=a+b;
13    for(int i=1;i<=a;++i)s[i]='1';
14    for(int i=1;i<=b;++i)s[i+a]='0';
15    while((s[n-k]=='0'||s[n]=='1')&&n>k)
16        --n;
17    if(n<=k+1&&k) return printf("No\n"),0;
18    printf("Yes\n");
19    if(!k) return printf("%s\n%s\n",s+1,s+1),0;
20    a-=2,b-=1;
21    int A=a,B=b;
22    printf("11");
23    solve(A,B,k-1);
24    putchar('0');
25    solve(A,B,a+b-k+1);
26    A=a,B=b;
27    printf("\n10");
28    solve(A,B,k-1);
29    putchar('1');
30    solve(A,B,a+b-k+1);
31    return 0;
32}

判断题

21. 去掉第6行的两个int,程序的输出一定不改变。

{{ select(21) }}

• 正确
• 错误

22. 如果$a=0$,$k≠0$,则必定输出No。

{{ select(22) }}

• 正确
• 错误

23. 当a+b<k+3时,必定输出No。

{{ select(23) }}

• 正确
• 错误

24. 若输出Yes,则输出的两个数在二进制下的差一定有k位1。

{{ select(24) }}

• 正确
• 错误

选择题

25. 若输入为2 4 3,则输出为()。

{{ select(25) }}

• Yes 101000100001
• Yes110000100010
• Yes110000100001
• No

26. 若输入为2 3 4,则输出为()。

{{ select(26) }}

• Yes 1010010001
• Yes 11000 10001
• Yes 10001 00011
• No

(3)

01#include <bits/stdc++.h>
02using namespace std;
03const int N=2e5+5;
04int n,m,ans,pos[2][N];
05char a[N],b[N];
06int main(){
07    scanf("%d%d%s%s",&n,&m,a,b);
08    reverse(a,a+n);reverse(b,b+m);
09    for(int i=0,now=0;i<n&&now<m;++i)
10        if(a[i]==b[now])
11            pos[0][now++]=i;
12    for(int i=n-1,now=m-1;~i&&~now;--i)
13        if(a[i]==b[now])
14            pos[1][now--]=i;
15    for(int i=1;i<m;++i)
16        ans=max(pos[1][i]-pos[0][i-1],ans);
17    printf("%d",ans);
18    return 0;
19}

假设$m≤n≤200000$,完成下列各题。

判断题

27. 若m不为n的子序列,则输出必定为0。()

{{ select(27) }}

• 正确
• 错误

28. 若将第8行删除,程序输出结果一定不会改变。()

{{ select(28) }}

• 正确
• 错误

选择题

29. 若输入为5 3 abaab abb,则输出为()。

{{ select(29) }}

• 1
• 2
• 3
• 4

30. 若a="ababcdc",b的长度为5,则使答案取到最大值的b可能有()个。

{{ select(30) }}

• 3
• 4
• 6
• 7

31. (4分)当a为"1010101"时,b的长度为3,b的每一位上要么是0,要么是1。总共有8种情况,对应8个输出。这8个输出的和为()。

{{ select(31) }}

• 18
• 24
• 30
• 36

32. 当a为"1010101"时,b的长度为4,b的每一位上要么是0,要么是1。总共有16种情况,对应16个输出。这16个输出的和为()。

{{ select(32) }}

• 32
• 38
• 46
• 52

三、完善程序(单选题,每小题3分,共计30分)

(1)题目描述: 给定一个数组{a}表示一排蘑菇的数量。有一个篮子。每次到一个新的$a_i$时,篮子中会增加$a_i$个蘑菇。如果篮子里的蘑菇超过x个,则篮子里的蘑菇会清空。询问有多少组[1,r],使得从1采摘到r,蘑菇数量不为0。

01#include<bits/stdc++.h>
02using namespace std;
03const int N=2e5+5;
04int n,x,a[N],cnt[N],dp[N];
05int main(){
06    cin>>n>>x;
07    for(int i=1;i<=n;i++)
08        cin>>a[i];
09    int l=1,r=0,sum=0;
10    while(l<=n){
11        while(①)
12            ②;
13        cnt[l]=r;
14        ③;
15    }
16    sum=0;
17    for(int i=n;i>=1;i--){
18        if(cnt[i]==n+1) continue;
19        dp[i]=④;
20        sum+=dp[i];
21    }
22    cout<<⑤<<endl;
23    return 0;
24}

33. ①处应填()。

{{ select(33) }}

• r<=n&&sum<=x
• l<=n&&sum>x
• sum<=x
• sum>x

34. ②处应填()。

{{ select(34) }}

• sum+=a[++r]
• sum+=a[r++]
• sum-=a[++l]
• sum-=a[l++]

35. ③处应填()。

{{ select(35) }}

• sum-=a[r--]
• sum-=a[--r]
• sum-=a[++l]
• sum-=a[l++]

36. ④处应填()。

{{ select(36) }}

• dp[cnt[i]]+1
• dp[cnt[i]+1]+1
• dp[cnt[i+1]]+1
• dp[cnt[i+1]+1]+1

37. ⑤处应填()。

{{ select(37) }}

• dp[1]
• n-dp[1]
• n*(n+1)/2-sum
• sum

(2)题目描述: 一个字符串$s(|s|≤5000)$由小写字母组成,有$q(q≤1e6)$组询问,每组询问给你两个数l和r,问:在字符串区间l到r的子串中包含多少回文串?

01#include <bits/stdc++.h>
02using namespace std;
03const int N=5005;
04char s[N];
05int n,f[N][N],dp[N][N];
06bool check(int l,int r){
07    if(①)return f[l][r];
08    if(l>=r) return f[l][r]=1;
09    if(s[l]^s[r]) return f[l][r]=0;
10    return f[l][r]=②;
11}
12int main(){
13    memset(f,-1,sizeof(f));
14    scanf("%s",s+1);
15    n=strlen(s+1);
16    for(int i=1;i<=n;++i)③;
17    for(int l=2;l<=n;++l){
18        for(int i=1;i<=n-l+1;++i){
19            int j=i+l-1;
20            dp[i][j]=④;
21            if(check(i,j))⑤;
22        }
23    }
24    int T;
25    scanf("%d",&T);
26    while(T--){
27        int x,y;
28        scanf("%d%d",&x,&y);
29        printf("%d\n",dp[x][y]);
30    }
31    return 0;
32}

38. ①处应填()。

{{ select(38) }}

• ~f[l][r]
• !f[l][r]
• r>1
• r-1>1

39. ②处应填()。

{{ select(39) }}

• $check(l+1, r-1)$
• $check(l+1, r)+1$
• $f[l+1][r-1]+1$
• $f[l+1][r]+1$

40. ③处应填()。

{{ select(40) }}

• $dp[i][i] = 1$
• $dp[i][i+1] = 1$
• $dp[i][i+1] = (s[i] == s[i+1]) + 2$
• $dp[i][i+1] = s[i] == s[i+1]$

41. ④处应填()。

{{ select(41) }}

• $dp[i+1][j] + dp[i][j-1] + dp[i+1][j-1]$
• $dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]$
• $dp[i+1][j] + dp[i][j-1] + (s[i] == s[j])$
• $dp[i+1][j] + dp[i][j-1] - (s[i] == s[j])$

42. ⑤处应填()。

{{ select(42) }}

• $dp[i][j]++$
• $dp[i][j] += dp[i+1][j-1]$
• $dp[i][j]--$
• $dp[i][j] -= dp[i+1][j-1]$