一、单项选择题（共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⁴+3k³+2k²+k
• 4k³+3k²+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中度最大的点的度为（ ）。

Column	A	B	C	D	E
A	0	1	1	0	1
B	1	0			0
C		1	0	1	1
D	0	0	1	0
E	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(n log n)。
• 快速排序是基于交换的排序。
• sort函数是STL提供的快排函数，同时结合了堆排序、插入排序等技术。

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

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

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

• 12
• -12
• 24
• -24

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

• ACEGBDF
• ACGEBDF
• ABDFCEG
• ABCDEFG

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

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

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填T，错误填F；除特殊说明外，判断题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⁶的正整数，且满足l<=r，完成下面的判断题和单选题。

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

• T
• F

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

• T
• F

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

• T
• F

·单选题 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) }}

• T
• F

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

• T
• F

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

• T
• F

·单选题 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⁶的正整数，完成下面的判断题和选择题。 提示：伯特兰-切比雪夫定理：对任意n>1，存在质数p使得n<p<2n。

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

• T
• F

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

• T
• F

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

• T
• F

·单选题 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,...,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 <= a[i] && a[i] <= n
• 1 <= a[i] <= n
• 1 <= a[i] || a[i] <= 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],...,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]