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

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

1. 在C++程序中，假设一个字符占用的内存空间是1字节，则下列程序中，s占用的内存空间是（）字节。

char s[]="hello oiers"; 
size_t cnt = strlen(s);
cout<<cnt<<endl;

{{ select(1) }}

• 10
• 11
• 13
• 12

2. 十六进制数B2025转换成八进制数是（ ）

{{ select(2) }}

• 2620045
• 2004526
• 729125
• 2420045

3. 以下能正确定义二维数组的是（ ）

{{ select(3) }}

• int a[3][]
• int a[][]
• int a[][4]
• int a[][2]={{1,2},{1,2},{3,4}}

4. 二进制[1000001]原码和[1000001]补码表示的十进制数值分别是（）

{{ select(4) }}

• -125，-3
• -3，-125
• -3，-3
• -125，-125

5. 在C++中，下列定义方式中，变量的值不能被修改的是（）

{{ select(5) }}

• unsigned int a =5;
• static double d=3.14;
• string s= "ccf csp-j";
• const char c='k';

6. 走迷宫的深度优先搜索算法经常用到的数据结构是（）

{{ select(6) }}

• 向量
• 栈
• 链表
• 队列

7. 关于递归，以下叙述中正确的是（）

{{ select(7) }}

• 动态规划算法都是用递归实现的
• 递归比递推更高级，占用的内存空间更少
• A函数调用B函数，B函数再调用A函数不属于递归的一种
• 递归是通过调用自身来求解问题的编程技术

8. 以下不属于计算机输入设备的是（）

{{ select(8) }}

• 扫描仪
• 显示器
• 鼠标
• 麦克风

9. 关于排序算法，下面的说法中正确的是（）

{{ select(9) }}

• 快速排序算法在最坏情况下的时间复杂度是O(n log n)
• 插入排序算法的时间复杂度是O(n log n)
• 归并排序算法的时间复杂度是O(n log n)
• 冒泡排序算法是不稳定的

10. 下列关于C++语言的叙述中不正确的是（）

{{ select(10) }}

• 变量没有定义也能使用
• 变量名不能以数字开头，且中间不能有空格
• 变量名不能和C语言中的关键字重复
• 变量在定义的时候可以不用赋值

11. 如果x和y均为int类型的变量，下列表达式中能正确判断"x等于y"的是（）

{{ select(11) }}

• (1==(x / y))
• (x==(x & y))
• (0==(x ^ y))
• (y==(x | y))

12. 在如今的智能互联网时代，AI如火如茶，除了计算机领域以外，通信领域的技术发展也做出了很大贡献。被称为"通信之父"的是（）

{{ select(12) }}

• 克劳德·香农
• 莱昂哈德·欧拉
• 约翰·冯·诺依曼
• 戈登·摩尔

13. 一棵满二叉树的深度为3（根结点的深度为1），按照后序遍历的顺序从1开始编号，根结点的右子结点的编号是（）

{{ select(13) }}

• 3
• 6
• 7
• 5

14. 三头奶牛Bessie、Elise和Nancy去参加考试，考场是连续的6间牛棚，用栅栏隔开。为了防止作弊，任意两头奶牛都不能在相邻的牛棚，则考场安排共有（）种不同的方法。

{{ select(14) }}

• 18
• 24
• 30
• 48

15. 为强化安全意识，某学校准备在某消防月连续10天内随机抽取3天进行消防紧急疏散演习，抽取的3天为连续3天的概率为（）

{{ select(15) }}

• 3/10
• 3/20
• 1/15
• 1/18

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

(1)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using i64=long long;

int clz(i64 x)
{
    for(int i=0;i!=64;i++)
        if((x>>(63-i))&1)
            return i;
    return 64;
}

bool cmp(i64 x,i64 y)
{
    if(clz(x)==clz(y))
        return x<y;
    return clz(x)<clz(y);
}

int main()
{
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a.begin(),a.end(),cmp);
    for(int i=0;i<n;i++)
        cout <<a[i]<<" \n"[i==n-1];
    return 0;
}

判断题

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

• 正确
• 错误

17. 若将第19行中的<换为>，则当程序输入5 0 4 2 1 3时，程序输出为4 3 2 1 0。（ ） {{ select(17) }}

• 正确
• 错误

18. 当调用cmp(3,3)时，函数的返回值为false。（ ） {{ select(18) }}

• 正确
• 错误

选择题

19. 若输入5 4 2 1 3 1，则输出是什么？（） {{ select(19) }}

• 3 4 2 1 1
• 3 2 4 1 1
• 4 3 2 1 1
• 4 2 3 1 1

20. 这个程序实现了什么功能？（） {{ select(20) }}

• 将输入的数组按照二进制位上从左到右第一个1前0的个数由多到少进行排序
• 将输入的数组按照二进制位上从左到右第一个1前0的个数由少到多进行排序
• 将输入的数组按照二进制位上从左到右第一个1前0的个数由多到少进行排序，当0的个数相同时，按照原数字由小到大进行排序
• 将输入的数组按照二进制位上从左到右第一个1前0的个数由少到多进行排序，当0的个数相同时，按照原数字由小到大进行排序

(2)

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
using namespace std;

const int inf=0x3f3f3f3f;

int calc(vector<vector<int>> &grid)
{
    int m=grid.size(),n=grid[0].size();
    vector<vector<int>>dp(m+1,vector<int>(n+1,inf));
    dp[0][0]=grid[0][0];
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
        {
            if(i>0)
                dp[i][j]=min(dp[i][j],dp[i-1][j]+grid[i][j]);
            if(j>0)
                dp[i][j]=min(dp[i][j],dp[i][j-1]+grid[i][j]);
        }
    return dp[m-1][n-1];
}

int main()
{
    int m,n;
    cin>>m>>n;
    vector<vector<int>>a(m,vector<int>(n));
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    cout<<calc(a)<<endl;
    return 0;
}

判断题

21. 若输入2 3 1 2 3 4 5 6，则输出为10。（ ） {{ select(21) }}

• 正确
• 错误

22. 计算dp数组的时间复杂度为O(n²)。（ ） {{ select(22) }}

• 正确
• 错误

23. 在calc函数中，访问dp[m][n]不会发生越界错误。（ ） {{ select(23) }}

• 正确
• 错误

选择题

24. 当输入的a数组为{{1,3,1},{1,5,1},{4,2,1}}时，程序输出为（） {{ select(24) }}

• 4
• 7
• 6
• 5

25. 若将第19行改为dp[i][j]=min(dp[i][j],dp[i-1][j]-grid[i][j]);，则当输入的a数组为{{1,2,3},{4,5,6}}时，程序的输出为（） {{ select(25) }}

• -3
• -2
• -1
• 0

26. 若将第10行中的&符号去除，可能出现什么情况？（） {{ select(26) }}

• dp数组计算错误
• calc函数中的grid数组和a数组不一致
• 无影响
• 发生编译错误

(3)

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
using namespace std;

const int N=1010;

vector<int>E[N];
int V[N];
int n;

void add(int x,int y)
{
    E[x].push_back(y);
}

int gcd(int x,int y)
{
    return y?gcd(y,x%y):x;
}

void calc(int cur,int fa)
{
    V[cur]=(gcd(cur,fa)!=1);
    for(auto v:E[cur])
    {
        if(v==fa)
            continue;
        calc(v,cur);
        V[cur]+=V[v];
    }
    return;
}

int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    calc(1,1);
    for(int i=1;i<=n;i++)
        cout<<V[i]<<" \n"[i==n];
    return 0;
}

判断题

27. 当输入为4 1 2 1 3 1 4时，程序的输出为0 0 0 0（ ） {{ select(27) }}

• 正确
• 错误

28. gcd函数用来计算两个数x和y的最大公约数。（ ） {{ select(28) }}

• 正确
• 错误

29. 对于树上的一条边(x,y)，若x为y的父结点，则必然有V[x]≤V[y]。（ ） {{ select(29) }}

• 正确
• 错误

选择题

30. 当输入为4 1 2 1 3 2 4时，程序的输出为（） {{ select(30) }}

• 0 0 0 0
• 1 1 0 1
• 0 0 1 0
• 1 1 1 1

31. calc函数的时间复杂度为（） {{ select(31) }}

• O(nlogn)
• O(n²)
• O(n)
• O(logn)

32. 若将第32行中的代码改为V[cur]*=V[v]，则当输入为4 1 2 1 3 2 4时，得到的输出为（） {{ select(32) }}

• 1 1 1 0
• 1 1 0 1
• 0 0 1 0
• 0 0 0 1

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

(1)

题目描述:

给定一个长为n（1<n≤2×10）的数组a（-10≤a[1]≤10⁹），执行如下操作，直到a中只剩下1个数：删除a[i]。如果a[i]左右两边都有数字，则把a[i-1]和a[i+1]合并成一个数。输出最后剩下的那个数的最大值。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve()
{
    int n, flag=0, mx=①;
    cin>>n;
    vector<int>a(n +1);
    for(int i=1;i<=n; i++)
    {
        cin>>a[i];
        if(a[i]<0)
        {
            mx = max(mx,a[i]); flag++;
        }
        if(②)
        {
            cout<<mx<<endl;
            return;
        }
    ③sum1=, sum2=0;
    for(inti=1;i<=n; i+=2)
        sum1+=max(a[i],0);
    for(inti=2;i<=n;i+=2)
        ④;
    cout<<⑤<<endl;
    return;
}

int main()
{
    int t=1;
    cin>>t;
    while(t--)
        solve();
}

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

• 0
• 1E9
• -1E8
• -2E9

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

• flag==n
• flag==0
• flag!=0
• flag!=n

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

• int
• i64
• i32
• unsigned int

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

• sum2+=max(a[i],0 )
• sum2+=min(a[i],0)
• sum2-=min(a[i],0)
• sum2-=max(a[i],0)

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

• min(sum1,sum2)
• max(sum1,sum2)
• sum1+sum2
• sum1-sum2

(2)

题目描述:

给定一个字符串t和一个字符串列表s作为字典。保证s中的字符串互不相同，且t和s[i]中均只包含小写英文字母。如果可以利用字典中出现的一个或多个单词拼接出t，则返回true。注意:不要求字典中出现的单词全部使用，并且字典中的单词可以重复使用。

#include <iostream>
#include <vector>
#include <algorithm>
#include<set>
#include <string>
using namespace std;

const int N=1010;

int n,mx,m;
vector<string> s;
vector<int> mem;
string t;
set<string> st;

int dfs(int i)
{
    if(i==0)
        return 1;
    if(①) return mem[i];
    for(int j=i-1;j>=max(i-mx,0);j--)
        if(st.find(②)!=st.end()&&dfs(j))
            return mem[i]=1;
    return ③;
}

int main()
{
    cin>>n;
    s.resize(n);
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
        mx=max(mx,④);
    }
    st = set<string>(s.begin(),s.end());
    cin>>t;
    m=(int)t.length();
    mem.resize(m+1,-1);
    if(⑤)
        cout<<"Yes\n";
    else
        cout<<"No\n";

    return 0;
}

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

• mem[i]!=-1
• mem[i]==-1
• mem[i]==0
• mem[i]!=0

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

• t.substr(j,i-j)
• t.substr(j,i)
• t.substr(i-j,j)
• t.substr(i,j-i)

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

• 1
• mem[i]=1
• 0
• mem[i]=0

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

• s[i].length()
• (int)s[i].length()
• s[i].length()-1
• (int)s[i].length()-1

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

• !dfs(m)
• !dfs(n)
• dfs(m)
• dfs(n)