CSP-J 2025 初赛试题

一、单选题（每题 2 分，共 30 分）

1. 一个32位无符号整数可以表示的最大值，最接近下列哪个选项?()

{{ select(1) }}

• 4×10⁹
• 3×10¹⁰
• 2×10⁹
• 2×10¹⁰

2. 在C++ 中，执行int x= 255； cout<< (x & (x - 1))；后，输出的结果是?()

{{ select(2) }}

• 255
• 254
• 128
• 0

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);
}

{{ select(3) }}

• 5
• 6
• 7
• 8

4. 用5个权值10，12，15，20，25构造哈夫曼树，该树的带权路径长度是多少??()

{{ select(4) }}

• 176
• 186
• 196
• 206

5. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于?()

{{ select(5) }}

• 顶点数
• 边数
• 顶点数+边数
• 顶点数* 2

6. 从5位男生和4位女生中选出4 人组成一个学习小组，要求学习小组中男生和女生都有。有多少种不同的选举方法?()

{{ select(6) }}

• 126
• 121
• 120
• 100

7. 假设a，b，c 都是布尔变量， 逻辑表达式 (a && b)||(!c && a) 的值与下列哪个表达式不始终相等?()

{{ select(7) }}

• a && (b || !c)
• !(a || !c) && (b || !c) && (a || a)
• a && (!b || c)
• !(!a || !b) || (a && !c)

8. 已知f[0]=1，f[1]=1，并且对于所有n≥2有f[n]=(f[n-1]+f[n-2])% 7.那么f[2025]的值是多少?()

{{ select(8) }}

• 2
• 4
• 5
• 6

9. 下列关于 C++ string 类的说法， 正确的是?()

{{ select(9) }}

• string 对象的长度在创建后不能改变。
• 可以使用+运算符直接连接一个 string 对象和一个char类型的字符。
• string的length() 和 size() 方法返回的值可能不同。
• string 对象必须以'\0'结尾，且这个结尾符计入length()。

10. 考虑以下C++函数：在main函数调用solve后，x和y的值分别是?()

    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)；
    }

{{ select(10) }}

• 5，10
• 10，5
• 10，10
• 5，5

11. 一个8×8的棋盘，左上角坐标为(1，1)，右下角为(8，8) 。一个机器人从(1，1)出发，每次只能向右或向下走一格。要到达 (4，5)， 有多少种不同的路径?()

{{ select(11) }}

• 20
• 35
• 56
• 70

12. 某同学用冒泡排序对数组{6，1，5，2，4}进行升序排序，请问需要进行多少次元素交换?()

{{ select(12) }}

• 5
• 6
• 7
• 8

13. 十进制数$720_{10}$和八进制数$270_{8}$。 的和用十六进制表示是多少?()

{{ select(13) }}

• 388₁₆
• 3DE₁₆
• 288₁₆
• 990₁₆

14. 一棵包含1000个结点的完全二叉树，其叶子结点的数量是多少?()

{{ select(14) }}

• 499
• 512
• 500
• 501

15. 给定一个初始为空的整数栈S和一个空的队列P。我们按顺序处理输入的整数队列A： 7，5，8，3，1，4，2。对于队列A中的每一个数，执行以下规则：如果该数是奇数， 则将其压入栈S：如果该数是偶数，且栈S非空，则弹出一个栈顶元素，并加入到队列P的末尾；如果该数是偶数，且栈S为空， 则不进行任何操作。当队列A中的所有数都处理完毕后， 队列P的内容是什么?()

{{ select(15) }}

• 5，1，3
• 7，5，3
• 3，1，5
• 5，1，3，7

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填 ×；除特殊说明外，判断题 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) {//第16行
                    ++ans;
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

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

{{ select(16) }}

• 正确
• 错误

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

{{ select(17) }}

• 正确
• 错误

18. 当输入的n≥3的时候， 程序总是输出一个正整数。()

{{ select(18) }}

• 正确
• 错误

19. 将第7行的"gcd(b，a%b) "改为"gcd(a，a%b)"后， 程序可能出现的问题是()。

{{ select(19) }}

• 输出的答案大于原答案。
• 输出的答案小于原答案。
• 程序有可能陷入死循环。
• 可能发生整型溢出问题。

20. 当输入为8的时候，输出为()

{{ select(20) }}

• 37
• 42
• 35
• 25

21. 调用gcd(36，42)会返回()

{{ select(21) }}

• 6
• 252
• 3
• 2

（2）

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long

int n, k;
int a[20000];
int ans[200007];

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。()

{{ select(22) }}

• 正确
• 错误

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

{{ select(23) }}

• 正确
• 错误

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

{{ select(24) }}

• 正确
• 错误

25. 假设输入的a数组和k均为正整数，执行第18行代码时， 一定满足的条件不包括()。

{{ select(25) }}

• j<=i
• a[i]-a[j]>k
• j<=n
• a[j]<a[i]

26. 当输入的n=100、k=2、a={1，2，...，100}时，输出为()。

{{ select(26) }}

• 34
• 100
• 50
• 33

27. 假设输入的a数组和k均为正整数，但a数组不一定有序， 则若误删去第13行的"std：：sort(a+1，a+n+1)；"， 程序有可能出现的问题有()。

{{ select(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. 当输入"412341322"时，输出为2。()

{{ select(28) }}

• 正确
• 错误

29. 当程序运行完毕后，对于所有的1≤i，j≤n，都一定有f[i][j]<=f[n][n]。(()

{{ select(29) }}

• 正确
• 错误

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

{{ select(30) }}

• 正确
• 错误

31. 输出的答案满足的性质有()。

{{ select(31) }}

• 小于等于n
• 大于等于0
• 不一定大于等于1
• 以上均是

32. 如果在16行的循环前加上以下两行："std：：sort(a+1，a+n+1)； std：：sort(b+1，b+n+1)"， 则答案会()。

{{ select(32) }}

• 变大或不变
• 变小或不变
• 一定变大
• 不变

33. 如果输入的a={1，2，...，n}，而且b数组中数字均为1~n中的正整数，则上述代码等价于下面哪个问题( )。

{{ select(33) }}

• 求b数组去重后的长度
• 求b数组的最长上升子序列
• 求b数组的长度
• 求b数组的最大值

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

####（1）（字符串解码）“行程长度编码”（Run-Length Encoding）是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。压缩规则如下：i）如果原始字符串中一个字符连续出现 N 次（(N≥2)），在压缩字符串中它被表示为 “字符 + 数字 N”。例如，编码 “A12” 代表 12 个连续的字符 A。ii）如果原始字符串中一个字符只出现 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; i < z.length(); ) {
        char ch = z[i];
        if (①) { // 判断下一个字符是否为数字
            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;
}

34. ①处应填()

{{ select(34) }}

• i < z.length()
• i-1>=0
• i + 1 < z.length()
• isdigit(z[i])

35. ②处应填()

{{ select(35) }}

• count+ (z[i]- '0')
• count* 10 +(z[i]-'0')
• z[i]-'0'
• count + 1

36. ③处应填()

{{ select(36) }}

• count-1
• count
• 10
• z[i]-'0'

37. ④处应填()

{{ select(37) }}

• z[i+1]
• ch
• z.back()
• (char)z[i]+1

38. ⑤处应填()

{{ select(38) }}

• i--
• i=i+2
• i++
• //不执行任何操作

（2）（精明与糊涂）有 N 个人，分为两类：i）精明人：永远能正确判断其他人是精明还是糊涂；ii）糊涂人：判断不可靠，会给出随机的判断。已知精明人严格占据多数，即如果精明人有 k 个，则满足(k > N/2)。你只能通过函数query(i,j)让第 i 个人判断第 j 个人：返回 true 表示判断结果为 “精明人”；返回 false 表示判断结果为 “糊涂人”。你的目标是，通过这些互相判断，找出至少一个百分之百能确定的精明人。同时，你无需关心query(i,j)的内部实现。以下程序利用 “精明人占多数” 的优势。设想一个 “消除” 的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选者必然属于多数派，即精明人。例如，假设有三个人 0、1、2。如果 0 说 1 是糊涂人，而 1 也说 0 是糊涂人，则 0 和 1 至少有一个是糊涂人。程序将同时淘汰 0 和 1。由于三人里至少有两个精明人，我们确定 2 是精明人。试补全程序。

#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 {
            ③; // 判断是否抵消
            if (④) {
                count--;
                if (count == 0) {
                    candidate = i;
                    count = 1;
                }
            }
        }
    }
    cout << ⑤ << endl; // 输出最终候选者
    return 0;
}

39. ①处应填()

{{ select(39) }}

• 0
• 1
• N
• -1

40. ②处应填()

{{ select(40) }}

• (count < 0)
• (count == 1)
• (count==0)
• query(candidate， i) == false

41. ③处应填()

{{ select(41) }}

• query(candidate，i)==false
• query(i， candidate) == true
• query(candidate， i) == false && query(i， candidate) == false
• query(candidate， i) == false || query(i， candidate) == false

42. ④处应填()

{{ select(42) }}

• count--
• break
• count++
• candidate = i

43. ⑤处应填()

{{ select(43) }}

• N-1
• count
• candidate
• 0