2025 LUOGU 非专业级别能力认证第一轮

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

1. GNU GCC 是常用的 C/C++语言编译器。现需要使用 g++将 luogu.cpp 编译为可执行文件 luogu，可以使用编译命令（ ）。 {{ select(1) }}

• g++ -S luogu luogu.cpp
• g++ -S luogu.cpp luogu
• g++ -o luogu luogu.cpp
• g++ -o luogu.cpp luogu

2. 关于编译语言与解释语言，以下说法错误的是（ ）。 {{ select(2) }}

• C++语言是编译语言，需要先经过编译得到可执行程序，才能交由机器执行。
• 编译语言程序每一次执行都需要重新编译。
• 解释器负责将解释语言的源程序翻译为可以执行的机器代码。
• Python 是常见的解释语言。

3. 阅读下面的代码，若输入的 x 是 1 至 10 范围内的正整数，输出不可能是（ ）。

01 #include <iostream>
02 using namespace std;
03 int main() {
04    int x; cin >> x;
05    switch(x) {
06        case 1: { cout << "A"; break; }
07        case 3: { cout << "C"; }
08        default: { cout << "Q"; }
09        case 5: { cout << "E"; }
10    }
11    return 0;
12}

{{ select(3) }}

• A
• CQE
• QE
• Q

4. k(k>4)进制数4321与十进制数（ ）相等。 {{ select(4) }}

• 4321
• $4k^4+3k^3+2k^2+k$
• $4k^3+3k^2+2k+1$
• $10k$

5. 阅读以下代码片段。当代码片段执行完毕后，ans的值为（ ）。

01 int N = 10, ans = 0, x = 0;
02 for(int i = 1; i <= N; i++) {
03    for(int j = i + 1; j <= N; j++) {
04        ans += ++x;
05    }
06}

{{ select(5) }}

• 45
• 55
• 990
• 1035

6. 给定一个空栈，支持入栈和出栈操作。将1至10依次入栈，第一个出栈的数为8，则第二个出栈的数不可能为（ ）。 {{ select(6) }}

• 1
• 7
• 9
• 10

7. 有序表中有100个元素，使用二分法查找元素X。有（ ）个数可以通过恰好5次查找找到。 {{ select(7) }}

• 100
• 32
• 31
• 16

8. 下面的表格是无向图G的邻接矩阵，图G中度最大的点的度为（ ）。

	A	B	C	D	E
A	0	1	$1$	0	1
B	1	0	1	$0$	0
C	$1$	1	0	$1$	1
D	0	$0$	1	0	$1$
E	1	0	$1$	1	0

{{ select(8) }}

• 1
• 2
• 3
• 4

9. 8支队伍均分为第一组与第二组进行小组赛。A队和B队在同一组，而与C队不在同一组的分组方案数有（ ）种。 {{ select(9) }}

• 10
• 20
• 30
• 40

10. 将一根长度为3的木棍折为三段，当断点的位置在木棍中等概率分布时，三段木棍可以构成三角形的概率为（ ）。 {{ select(10) }}

• 1
• 0.5
• 0.25
• 0.125

11. 下列关于快速排序的说法中，不正确的是（ ）。 {{ select(11) }}

• 快速排序典型地应用了分治法的思想。
• 快速排序的最坏时间复杂度为 ($O(nlogn)$)。
• 快速排序是基于交换的排序。
• sort函数是STL提供的快排函数，同时结合了堆排序、插入排序等技术。

12. 关于整数的各种8位二进制编码方法，说法错误的是（ ）。 {{ select(12) }}

• -17的原码为10010001
• 22的补码为00010110
• -13的反码为11110010
• 以上说法存在错误

13. 表达式$(x-2x^{-1/2})^4$中，x的系数为（ ）。 {{ select(13) }}

• 12
• -12
• 24
• -24

14. 二叉树T的中序遍历为CGEADBF，后序遍历为GECDFBA，则其前序遍历为（ ）。 {{ select(14) }}

• ACEGBDF
• ACGEBDF
• ABDFCEG
• ABCDEFG

15. 2024年，来自谷歌DeepMind的米斯·哈萨比斯和约翰·江珀获得了（ ），以表彰他们在人工智能方面的贡献。 {{ select(15) }}

• 王选奖
• 图灵奖
• 诺贝尔奖
• 贝尔奖

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int main() {
05    int l, r;
06    cin >> l >> r;
07    int cnt = 0;
08    long long sum = 0;
09    for(int i = l; i <= r; ++i) {
10         if((i & (i - 1)) != 0) {
11            cnt += 1;
12            sum += i;
13        }
14    }
15    cout << cnt << " " << sum << endl;
16    return 0;
17}

假设输入的l和r均为不超过$10^6$的正整数，且满足$l \le r$，完成下面的判断题和单选题。

• 判断题

16. 当输入为2 5时，程序的输出为2 8。（ ） {{ select(16) }}

• √
• ×

17. 程序的输出总是两个正整数。（ ） {{ select(17) }}

• √
• ×

18. 将第8行的long long改为int，程序行为不变。（ ） {{ select(18) }}

• √
• ×

• 单选题

19. 当输入为1 100时，程序的输出为（ ）。 {{ select(19) }}

• 93 4923
• 92 4823
• 93 4823
• 92 4923

20. 当输入为10000 1000000时，程序的第一输出为（ ）。 {{ select(20) }}

• 989993
• 989994
• 989995
• 989996

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int main() {
05    int n, m;
06    cin >> n >> m;
07    vector<int> a(n);
08    for(int i = 0; i < n; ++i) {
09        cin >> a[i];
10    }
11    vector<int> dp(m + 1);
12    dp[0] = 0;
13    for(int i = 1; i <= m; ++i) {
14        int now = 0;
15        for(int j = 0; j < n; ++j) {
16            if(i >= a[j] && dp[i - a[j]] == 0) {
17                now = a[j];
18            }
19        }
20        dp[i] = now;
21    }
22    cout << dp[m] << endl;
23    return 0;
24}

假设输入的 n 和 m 均为不超过 1000 的正整数，输入的 a[i] 均为不超过 m 的正整数，完成下面的判断题和单选题。

• 判断题

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

• √
• ×

22. （2 分）当输入的数组 a 为 {1}且 m 为偶数时，程序的输出为 0。（ ） {{ select(22) }}

• √
• ×

23. 将第 16 行的条件 $i$ $\geqslant$ $a[j]$ && $dp[i - a[j]] == 0$ 改为 $dp[i - a[j]] == 0$，程序可能会产生编译错误。（ ） {{ select(23) }}

• √
• ×

• 单选题

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

• 0
• 1
• 2
• 3

25. 当输入为7 1000 1 2 3 4 5 6 7时，程序的输出为（ ）。 {{ select(25) }}

• 0
• 1
• 2
• 3

26. （4分）当输入的数组a为{1,2,3,4,5}时，有（ ）个符合数据范围的整数m使得输出为3。 {{ select(26) }}

• 165
• 166
• 167
• 168

(3)

01 #include<bits/stdc++.h>
02 using namespace std;
03
04 vector <int> primes;
05 int comp_by[2000005];
06 void sieve(int n) {
07    for(int x = 2; x <= n; x++) {
08        if(comp_by[x] == 0) {
09            primes.push_back(x);
10        for(int i = 0; i < primes.size(); i++) {
11
12            if(x * primes[i] > n) break;
13            comp_by[x * primes[i]] = primes[i];
14            if(x % primes[i] == 0) break;
15        }
16    }
17}
18 int main() {
19    freopen("input.txt", "w", stdout);
20    freopen("output.txt", "r", stdin);
21    int n;
22    cin >> n;
23    sieve(n);
24    for(int i = 1; i <= n; i++) 
25        cout << comp_by[i] << ' ';
26    return 0;
27}

假设输入的 n 是不超过 $10^6$的正整数，完成下面的判断题和选择题。

提示：伯特兰-切比雪夫定理：对任意 n > 1，存在质数 p 使得 n < p < 2n 。

• 判断题

27. 程序将从 input.txt 读入数据，输出到 output.txt。（ ） {{ select(27) }}

• √
• ×

28. 交换程序的第 12 行和第 13 行，不会导致数组越界。（ ） {{ select(28) }}

• √
• ×

29. 对于所有正整数 i，满足 $1 \leq i \leq n$ ，输出的第 i 个数是 0 当且仅当 i 是质数。（ ） {{ select(29) }}

• √
• ×

• 单选题

30. 该程序的主要流程最接近（ ）。 {{ select(30) }}

• 递归法
• 动态规划
• 埃拉托斯特尼筛
• 欧拉筛

31. 将程序的第 14 行移动到第 11 行，当输入为 1000000 时，输出的第（ ）个数会发生改变。 {{ select(31) }}

• 75
• 45
• 97
• 105

32. （4 分）当输入为 100 时，输出的所有数字之和为（ ）。 {{ select(32) }}

• 154
• 194
• 197
• 214

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

(1)（全排列检查）

给定长度为 n 的数组 a，判断其是否构成全排列。如果 $1, 2, \dots, n$ 都恰好在数组 a 中出现且仅出现一次，那么就称这个数组是一个全排列。

试补全程序。

01	#include<bits/stdc++.h>
02	using namespace std;
03	
04	bool is_permutation(vector<int> &a) {
05	    int n = ___①___;
06	    vector<int> count(__②__);
07	    for(int i = 0; i < n; i++) {
08	        if(__③___)
09	            count[a[i]]++;
10	        else
11	            ___④___;
12	    }
13	    for(int i = 1; i <= n; i++)
14	        if(count[___⑤___] > 1)
15	            return false;
16	    return true;
17	}
18	int main() {
19	    int n;
20	    cin >> n;
21	    vector<int> a(n);
22	    for(int i = 0; i < n; i++)
23	        cin >> a[i];
24	    if(is_permutation(a))
25	        cout << "The sequence is a permutation.";
26	    else
27	        cout << "The sequence is not a permutation.";
28	    return 0;
29	}

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

• a.length()
• a.size()
• a.back()
• a.capacity()

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

• 0
• n
• n + 1
• 1000000000

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

• $1 \le a[i]$ && $a[i] \le n$
• $1 \le a[i] \le n$
• $1 \le a[i] || a[i] \le n$
• $a[i] < 1 || a[i] > n$

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

• break
• continue
• return true
• return false

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

• i
• a[i]
• i - 1
• i / 2

(2)（跳跃）

给定一个数组 a[0], a[1], \dots, a[n-1]，每次跳跃从当前位置 x跳至位置a[x]。回答 q 次询问，每次给出 (x, k)，输出从 x 跳跃 k 次后的位置编号。

试补全程序。

01	#include <iostream>
02	using namespace std;
03	
04	const int N = 100010, LOG = 20;
05	int a[N], dp[N][LOG];
06	
07	int main() {
08	    int n, q;
09	    cin >> n >> q;
10	    for (int i = 0; i < n; i++) cin >> a[i];
11	    for (int i = 0; i < n; i++) {
12	        dp[i][0] = ___①__;
13	    }
14	    for (int k = 1; k < LOG; k++) {
15	        for (int i = 0; i < n; i++) {
16	            dp[i][k] = ___②__;
17	        }
18	    }
19		
20	    while (q--) {
21	        int x, k;
22	        cin >> x >> k;
23	        int u = x;
24	        for (int j = 0; j < LOG; j++) {
25	            if (___③__) {
26	                u = ___④__;
27	            }
28	        }
29	        cout << ___⑤__ << endl;
30	    }
31	    return 0;
32	}

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

• i
• a[i]
• 0
• dp[i][1]

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

• dp[dp[i][k - 1]][k - 1]
• dp[i][k - 1] + dp[i][k - 1]
• dp[i - 1][k - 1]
• dp[k - 1][i]

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

• k & j
• k >> j
• (k >> j) & 1
• (k >> j) ^ 1

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

• dp[j][u]
• dp[k][u]
• dp[u][j]
• a[u]

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

• u
• x
• k
• dp[u][0]