一、单项选择题（共 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 范围内的正整数，输出不可能是（ ）。

#include <iostream>
using namespace std;
int main() {
    int x; cin >> x;
    switch(x) {
        case 1: { cout << "A"; break; }
        case 3: { cout << "C"; }
        default: { cout << "Q"; }
        case 5: { cout << "E"; }
    }
    return 0;
}

{{ 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 的值为（ ）。

int N = 10, ans = 0, x = 0;
for(int i = 1; i <= N; i++) {
    for(int j = i + 1; j <= N; j++) {
        ans += ++x;
    }
}

{{ 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			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})^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）阅读程序，完成第 16～20 题

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

int main() {
    int l, r;
    cin >> l >> r;
    int cnt = 0;
    long long sum = 0;
    for(int i = l; i <= r; ++i) {
        if((i & (i - 1)) != 0) {
            cnt += 1;
            sum += i;
        }
    }
    cout << cnt << " " << sum << endl;
    return 0;
}

假设输入的 l 和 r 均为不超过 $10^6$ 的正整数，且满足 l <= 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）阅读程序，完成第 21～26 题

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int> dp(m + 1);
    dp[0] = 0;
    for(int i = 1; i <= m; ++i) {
        int now = 0;
        for(int j = 0; j < n; ++j) {
            if(i >= a[j] && dp[i - a[j]] == 0) {
                now = a[j];
            }
        }
        dp[i] = now;
    }
    cout << dp[m] << endl;
    return 0;
}

假设输入的 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 >= 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）阅读程序，完成第 27～32 题

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

vector <int> primes;
int comp_by[2000005];
void sieve(int n) {
    for(int x = 2; x <= n; x++) {
        if(comp_by[x] == 0)
            primes.push_back(x);
        for(int i = 0; i < primes.size(); i++) {

            if(x * primes[i] > n) break;
            comp_by[x * primes[i]] = primes[i];
            if(x % primes[i] == 0) break;
        }
    }
}
int main() {
    freopen("input.txt", "w", stdout);
    freopen("output.txt", "r", stdin);
    int n;
    cin >> n;
    sieve(n);
    for(int i = 1; i <= n; i++)
        cout << comp_by[i] << ' ';
    return 0;
}

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

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

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

{{ select(27) }}

• 正确
• 错误

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

{{ select(28) }}

• 正确
• 错误

29. 对于所有正整数 $i$，满足 $1\le i\le 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）全排列检查（第 33～37 题）

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

试补全程序。

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

bool is_permutation(vector<int> &a) {
    int n =     ①    ;
    vector<int> count(    ②    );
    for(int i = 0; i < n; i++) {
        if(    ③    )
            count[a[i]]++;
        else
            ④    ;
    }
    for(int i = 1; i <= n; i++)
        if(count[    ⑤    ] > 1)
            return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    if(is_permutation(a))
        cout << "The sequence is a permutation.";
    else
        cout << "The sequence is not a permutation.";
    return 0;
}

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）跳跃（第 38～42 题）

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

试补全程序。

#include <iostream>
using namespace std;

const int N = 100010, LOG = 20;
int a[N], dp[N][LOG];

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) {
        dp[i][0] =     ①    ;
    }
    for (int k = 1; k < LOG; k++) {
        for (int i = 0; i < n; i++) {
            dp[i][k] =     ②    ;
        }
    }

    while (q--) {
        int x, k;
        cin >> x >> k;
        int u = x;
        for (int j = 0; j < LOG; j++) {
            if (    ③    ) {
                u =     ④    ;
            }
        }
        cout <<     ⑤     << endl;
    }
    return 0;
}

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]