2025CSP-J初赛试题解析

2025年11月08日 Tech 约3.9k字预计需要17分钟

J和S的复赛没考好，已经被上善若水和人杰地灵折磨疯了，写个初赛题解放松下吧。

2025 CCF 非专业级别软件能力认证第一轮（CSP-J1）入门级C++语言试题

考生注意事项：

试题共有9页，答题纸共有1页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。
不得使用任何电子设备（如计算器、手机、电子词典、电子手表等）或查阅任何书籍资料。

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

1. 一个32位无符号整数可以表示的最大值，最接近下列哪个选项？（）
A. $4\times10^9$
B. $3\times10^{10}$
C. $2\times10^9$
D. $2\times10^{10}$
答案： A
解析： 32位无符号整数可以表示的最大值为 $2^{32}-1=4294967295\approx4\times10^9$

2. 在C++中，执行int x=255; cout<<(x&(x-1));后，输出的结果是？（）
A. 255
B. 254
C. 128
D. 0
答案： B
解析： 即11111111 & 11111110=254

3. 函数calc(n)的定义如下，则calc(5)的返回值是多少？（）

int calc(int n){ 
    if(n<=1) return 1; 
    if(n%2==0) return calc(n/2)+1;
    else return calc(n-1)+calc(n-2);
}

A. 5
B. 6
C. 7
D. 8
答案： B
解析： cals(5)=cals(4)+cals(3)=cals(2)+1+cals(2)+cals(1)=cals(1)+1+1+cals(1)+1+1=1+1+1+1+1+1=6

==4. == 用5个权值10、12、15、20、25构造哈夫曼树，该树的带权路径长度是多少？（）
A. 176
B. 186
C. 196
D. 206
答案： B
解析： 构造哈夫曼树步骤：合并10和12，得22。合并15和20，得35。合并22和25，得47。合并35和47，得82。计算带权路径长度即可。

5. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于？（）
A. 顶点数
B. 边数
C. 顶点数+边数
D. 顶点数×2
答案： B
解析： 一条边贡献一个出度一个入度，因此选择边数，理解不上来画个图就好了。

6. 从5位男生和4位女生中选出4人组成一个学习小组，要求学习小组中男生和女生都有。有多少种不同的选举方法？（）
A. 126
B. 121
C. 120
D. 100
答案： C
解析： 全部-全男-全女，即 $C^9_4-C^5_4-C^4_4=126-5-1=120$

7. 假设a、b、c都是布尔变量，逻辑表达式(a&&b)||(!c&&a)的值与下列哪个表达式不始终相等？（）
A. a&&(b||!c)
B. (a||!c)&&(b||!c)&&(a||a)
C. a&&(!b||c)
D. !(a||!b)||(a&&!c)
答案： C
解析： 没啥说的，挨个试。

8. 已知f[0]=1，并且对于所有有f[n]=(f[n-1]+f[n-2])%7，那么f[2025]的值是多少？（）
A. 2
B. 4
C. 5
D. 6
答案： D
解析： 先递推，发现出现周期为十六的1 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0数列(考场上真是吓我一跳)，2025%16=9，D

9. 下列关于C++ string类的说法，正确的是？（）
A. string对象的长度在创建后不能改变。
B. 可以使用+运算符直接连接一个string对象和一个char类型的字符。
C. string的length()和size()方法返回的值可能不同。
D. string对象必须以\0结尾，且这个结尾符计入length()。答案： B
解析： A：加号就可以改变了；B：没毛病；C：一模一样；D：不用加\0，更不计入length()了。(话说这四个选项如果不确定都可以看阅读程序题进行验证)

10. 考虑以下C++函数，在main函数调用solve后，x和y的值分别是？（）
A. 5，10
B. 10，5
C. 10，10
D. 5，5

void solve(int &a, int b){
    a = a + b;
    b = a - b;
    a = a - b;
}
int main(){ 
    int x=5, y=10;
    solve(x, y);
}

A. 5，10
B. 10，5
C. 10，10
D. 5，5
答案： D
解析： 注意&a影响实际值，b不影响。推一下就好啦。

11. 一个8×8的棋盘，左上角坐标为(1,1)，右下角为(8,8)。一个机器人从(1,1)出发，每次只能向右或向下走一格。要到达(4,5)，有多少种不同的路径？（）
A. 20
B. 35
C. 56
D. 70
答案： B
解析： dp推一下就好了，f[i][j]=f[i-1][j]+f[i][j-1]

12. 某同学用冒泡排序对数组[6,1,5,2,4]进行升序排序，请问需要进行多少次元素交换？（）
A. 5
B. 6
C. 7
D. 8
答案： B
解析： 冒泡排序就是两两交换，捋几遍就知道了。

13. 十进制数 $720_{10}$ 和八进制数 $270_8$ （原题此处缺失）的和用十六进制表示是多少？（）
A. $388_{16}$
B. $3DE_{16}$
C. $288_{16}$
D. $990_{16}$
答案： A
解析： $720_{10}+270_8=720_{10}+184_{10}=904_{10}=388_{16}$

14. 一棵包含1000个结点的完全二叉树，其叶子结点的数量是多少？（）
A. 499
B. 512
C. 500
D. 501
答案： C
解析： 如果记不住公式大致推一下当作规律题做就好了，然而公式是 $n_{leaves}=\lceil n_{tot} /2 \rceil (n_{tot} \%2==1) n_{leaves}=n_{tot}/2(n_{tot}\%2==0)$

15. 给定一个初始为空的整数栈S和一个空的队列P。按顺序处理输入的整数队列A：7、5、8、3、1、4、2。处理规则：①若该数是奇数，压入栈S；②若该数是偶数且栈S非空，弹出栈顶元素加入队列P；③若该数是偶数且栈S为空，不操作。当队列A处理完毕后，队列P的内容是什么？（）
A. 5，1，3
B. 7，5，3
C. 3，1，5
D. 5，1，3，7
答案： A
解析： 模拟一下就好，队列先进先出，栈先进后出。

二、阅读程序（程序输入不超过数组或字符串定义的范围；

判断题正确填√，错误填×；除特殊说明外，判断题1.5分，选择题3分，共计40分）

(1)

#include <cstdio> 
#include <cstring> 
#include <algorithm>
inline int gcd(int a, int b){ 
   if(b==0) return a;
   return gcd(b, a%b);
}
int main(){ 
   int n;
   scanf("%d", &n);
   int ans=0; 
   for (int i=1; i<=n; ++i){ 
       for(int j=i+1; j<=n; ++j){ 
           for(int k=j+1; k<=n; ++k){
               if(gcd(i,j)==1 && gcd(j,k)==1 && gcd(i,k)==1){
                   ++ans;
               }
           }
       }
   }
   printf("%d\n", ans);
   return 0;
}

判断题

16. （1分）当输入为2时，程序并不会执行第16行的判断语句。（）

17. 将第16行中的&& gcd(i, k)==1删去不会影响程序运行结果。（）

18. 当输入的的时候，程序总是输出一个正整数。（）

单选题

19. 将第7行的gcd(b,a%b)改为gcd(a,a%b)后，程序可能出现的问题是（）。
A. 输出的答案大于原答案。
B. 输出的答案小于原答案。
C. 程序有可能陷入死循环。
D. 可能发生整型溢出问题。

20. 当输入为8的时候，输出为（）。
A. 37
B. 42
C. 35
D. 25

21. 调用gcd(36,42)会返回（）。
A. 6
B. 252
C. 3
D. 2

答案： √×√CCA
解析：

程序大意：寻找1-n中互质的三元组
16：i=2时j=3，循环都不会执行，别说判断了
17：不满足两两互质，必然不成立，例如4 5 16就不一样
18：注意到1 2 3满足要求，输出必然大于等于1
19：若a=a%b，在极端情况下会死循环
20：根据题意模拟即可
21: gcd(Greatest Common Divisor)意为最大公约数，36和42的最大公约数为6。

(2)

#include <algorithm>
#include <cstdio> 
#include <cstring> 
#define ll long long 
int n, k; 
int a[20000];
int ans[20007]; 
int main(){ 
   scanf("%d%d", &n, &k);
   for (int i=1; i<=n; ++i){ 
       scanf("%d", &a[i]);
   }
   std::sort(a+1, a+n+1); 
   n = std::unique(a+1, a+n+1) - a - 1; 
   for(int i=1, j=0; i<=n; ++i){
       for(; j<i && a[i]-a[j+1]>k; ++j);
       ans[i] = ans[j] + 1;
   }
   printf("%d\n", ans[n]);
   return 0;
}

判断题

22. 当输入为“3 1 3 2 1”时，输出结果为2。（）

23. 假设输入的n为正整数，输出的答案一定小于等于n，大于等于1。（）

24. 将第14行的n=std::unique(a+1,a+n+1)-a-1;删去后，有可能出现与原本代码不同的输出结果。（）

单选题

25. 假设输入的a数组和k均为正整数，执行第18行代码时，一定满足的条件不包括（）。
A. $j\le i$
B. $a[i]-a[j]>k$
C. $j\le n$
D. $a[j]<a[i]$

26. 当输入的n=100、k=2、a={1,2,…,100}时，输出为（）。
A. 34
B. 100
C. 50
D. 33

27. 假设输入的a数组和k均为正整数，但a数组不一定有序，若误删去第13行的std::sort(a+1,a+n+1);，程序有可能出现的问题有（）。
A. 输出的答案比原本答案更大
B. 输出的答案比原本答案更小
C. 出现死循环行为
D. 以上均可能发生

答案： ×√√BAD
解析：

程序大意：将数组分组，使每组数据差≤k，输出组数
22：数组为1、2、3，输出3
23：每组一个时为n，最少显然为1
24：unique用来去重，去重输出2，不去重输出1
25：a[i]-a[j]≤k
26：根据题意模拟即可->34
27: 删去后无法排序，均可能发生

(3)

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int f[5007][5007];
int a[5007], b[5007]; 
int n;
int main(){ 
    scanf("%d", &n); 
    for (int i=1; i<=n; ++i){
        scanf("%d", &a[i]);
    }
    for(int i=1; i<=n; ++i){
        scanf("%d", &b[i]);
    }
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j){ 
            f[i][j] = std::max(f[i-1][j], f[i][j-1]);
            if(a[i]==b[j]){ 
                f[i][j] = std::max(f[i][j], f[i-1][j-1]+1);
            }
        }
    }
    printf("%d\n", f[n][n]); 
    return 0;
}

判断题

28. 当输入“4 1 2 3 4 1 3 2 2”时，输出为2。（）

29. 当程序运行完毕后，对于所有的，都一定有。（）

30. 将第18行的f[i][j]=std::max(f[i][j],std::max(f[i-1][j],f[i][j-1]));删去后，并不影响程序运行结果。（）

选择题

31. 输出的答案满足的性质有（）。
A. 小于等于n
B. 大于等于0
C. 不一定大于等于1
D. 以上均是

32. 如果在16行的循环前加上以下两行：std::sort(a+1,a+n+1); std::sort(b+1,b+n+1)，则答案会（）。
A. 变大或不变
B. 变小或不变
C. 一定变大
D. 不变

33. (此题原本删除)如果输入的a数组是1,2,...,n，而且b数组中数字均为1~n中的正整数，则上述代码等价于下面哪个问题：（）。
A. 求b数组去重后的长度
B. 求b数组的最长上升子序列
C. 求b数组的长度
D. 求b数组的最大值

答案： √√×DAB
解析：

程序大意：LCS问题，即最长公共子序列问题
28：LCS为1、2或1、3，长度为2
29：a[i][j]表示前i个a和前j个b的LCS长度，f[n][n]为最大值，必小于。
30：删去会导致为0
31：理解题意即可
32：排序后题意更换为最长公共元素个数，大于或等于
33: 题意，相当于给没理解题目的人一个提示了

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

（1）字符串解码

“行程长度编码”（Run-Length Encoding）是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符，压缩规则如下：

①如果原始字符串中一个字符连续出现N次（），在压缩字符串中表示为“字符+数字N”。例如，编码“A12”代表12个连续的字符A。
②如果原始字符串中一个字符只出现1次，在压缩字符串中表示为该字符本身。例如，编码“B”代表1个字符B。

以下程序实现读取压缩字符串并输出其原始的、解压后的形式，试补全程序。

#include <cctype> 
#include <iostream>
#include <string>
using namespace std;

int main(){
    string z; 
    cin >> z; 
    string s = ""; 
    for (int i=0; ①; ){ 
        char ch = z[i];
        if(isdigit(z[i+1])){
            int count=0; 
            i++;
            while (i<z.length() && isdigit(z[i])){
                count = ②; 
                i++;
            }
            for (int j=0; j<③; ++j){
                s += ch;
            }
        }else{
            s += ④;
            ⑤;
        }
    }
    cout << s << endl; 
    return 0;
}

33. ①处应填（）
A. i＜z.length()
B. i-1≥0
C. i+1＜z.length()
D. isdigit(z[i])

34. ②处应填（）
A. count + (z[i]-'0')
B. count * 10 + (z[i]-'0')
C. z[i]-'0'
D. count+1

35. ③处应填（）
A. count-1
B. count
C. 10
D. z[i]-'8'

36. ④处应填（）
A. z[i+1]
B. ch
C. z.back()
D. (char)z[i]+1

37. ⑤处应填（）
A. i--
B. i = i+2
C. i++
D. //不执行任何操作

答案： CBBBC
解析：

33：判断下一个字符是否是数字，防止越界
34：向后放数字，例如"12"+“0”=12*10+0=120
35：count为字符连续出现的次数
36：没有数字时直接添加ch
37：无后续数字时，索引向后移动

(2)精明与糊涂

有N个人，分为两类：

①精明人：永远能正确判断其他人是精明还是糊涂；
②糊涂人：判断不可靠，会给出随机的判断。

已知精明人严格占据多数，即如果精明人有k个，则满足k＞N/2。你只能通过函数query(i,j)让第i个人判断第j个人：返回true表示判断结果为“精明人”；返回false表示判断结果为“糊涂人”。目标是通过互相判断，找出至少一个百分之百能确定的精明人（无需关心query(i,j) 的内部实现）。

以下程序利用“精明人占多数”的优势，通过“消除”过程让人们互相判断并抵消，经过若干轮抵消后，最终留下的候选者必然属于多数派（精明人），试补全程序。

#include <iostream>
#include <vector> 
using namespace std;
int N; 
bool query(int i, int j);
int main(){ 
    cin >> N;
    int candidate = 0; 
    int count = ①;
    for(int i=1; i<N; ++i){
        if(②){ 
            candidate = i;
            count = 1;
        }else{
            ③{
                ④;
            }else{
                count++;
            }
        }
    }
    cout << ⑤ << endl;
    return 0;
}

①处应填（）
A. 0
B. 1
C. N
D. -1
②处应填（）
A. count < 0
B. count == 1
C. count == 0
D. query(candidate, i) == false
③处应填（）
A. query(candidate,i)==false
B. query(i,candidate)==true
C. query(candidate,i)==false && query(i,candidate)==false
D. query(candidate,i)==false ||query(i,candidate)==false
④处应填（）
A. count--
B. break
C. count++
D. candidate=i
⑤处应填（）
A. N-1
B. count
C. candidate
D. 0

答案： BCDAC
解析：

38：count=1表示当前候选者有效
39：当count=0，即没有有效候选者时将候选者更换为i，并重置count
40：至少有一个糊涂人
41：可以抵消
42：最后留下的是精明人

文章分类

一言

文章归档

最新文章