一、单项选择题

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

【第 1 题】

在 Linux 系统中，如果你想显示当前工作目录的路径，应该使用哪个命令?（ ）。 {{ select(1) }}

• pwd
• cd
• ls
• echo

【第 2 题】 假设一个长度为 $n$ 的整数数组中每个元素值互不相同，且这个数组是无序的。 要找到这个数组中最大元素的时间复杂度是多少？（ ）

{{ select(2) }}

• $O(n)$
• $O(\log n)$
• $O(n \log n)$
• $O(1)$

【第 3 题】

在 C++ 中，以下哪个函数调用会造成栈溢出？（ ）

{{ select(3) }}

• int foo() { return 0; }
• int bar() { int x = 1; return x; }
• void baz() { int a[1000]; baz(); }
• void qux() { return; }

【第 4 题】

在一场比赛中，有 $10$ 名选手参加，前三名将获得金、银、铜牌。若不允许并列，且每名选手只能获得一枚奖牌，则不同的颁奖方式共有多少种？（ ）

{{ select(4) }}

• $120$
• $720$
• $504$
• $1000$

【第 5 题】

下面哪个数据结构最适合实现先进先出（FIFO）的功能？（ ） {{ select(5) }}

• 栈
• 队列
• 线性表
• 二叉搜索树

【第 6 题】

已知 $f(1)=1$，且对于 $n \ge 2$ 有 $f(n)=f(n-1)+f(\lfloor n/2 \rfloor)$，则 $f(4)$ 的值为？

{{ select(6) }}

• $4$
• $5$
• $6$
• $7$

【第 7 题】

假设有一个包含 n 个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？ （ ） {{ select(7) }}

• 所有顶点的度数均为偶数
• 该图连通
• 该图存在一个欧拉回路
• 该图的边数是奇数

【第 8 题】

对数组进行二分查找的过程中，以下哪个条件必须满足？（ ） {{ select(8) }}

• 数组必须是有序的
• 数组必须是无序的
• 数组长度必须是 2 的幂
• 数组中的元素必须是整数

【第 9 题】 考虑一个自然数 $n$ 以及一个模数 $m$，你需要计算 $n$ 的逆元（即 $n$ 在模 $m$ 意义下的逆元）。以下哪种算法最为适合？（ ）

{{ select(9) }}

• 使用暴力法逐次尝试
• 使用扩展欧几里得算法
• 使用快速幂算法
• 使用线性筛法

【第 10 题】 在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。如果哈希表中有 $n$ 个键值对，表的装载因子为 $a$ ($0 < a \leq 1$)。在使用开放地址法来解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为？（ ） {{ select(10) }}

• $O(1)$
• $O(\log n)$
• $O(1/(1 - \alpha))$
• $O(n)$

【第 11 题】

假设有一棵 $h$ 层的完全二叉树，该树最多包含多少个结点？（ ） {{ select(11) }}

• $2^h - 1$
• $2^{h+1} - 1$
• $2^h$
• $2^{h+1}$

【第 12 题】

设有一个 $10$ 个顶点的完全图，每两个顶点之间都有一条边。至少有多少个长度为 $4$ 的环？（ ）

{{ select(12) }}

• $120$
• $210$
• $630$
• $5040$

【第 13 题】 对于一个整数 $n$，定义 $f(n)$ 为 $n$ 的各位数字之和，问使得 $f(f(x)) = 10$ 的最小自然数 $x$ 是多少？（ ）

{{ select(13) }}

• $29$
• $199$
• $299$
• $399$

【第 14 题】 设有一个长度为 $n$ 的 $01$ 字符串，其中有 $k$ 个 $1$。每次操作可以交换相邻的两个字符。在最坏情况下将这 $k$ 个 $1$ 移到字符串最右边所需要的交换次数是多少？（ ） {{ select(14) }}

• $k$
• $k \times (k - 1)/2$
• $(n - k) \times k$
• $(2n - k - 1) \times k/2$

【第 15 题】

如图是一张包含 $7$ 个顶点的有向图，如果要删除其中一些边，使得从节点 $1$ 到节点 $7$ 没有可行路径，并且删除的边数最少，请问总共有多少种可行的删除边的集合？（ ）。

{{ select(15) }}

• 1
• 2
• 3
• 4

二、阅读程序

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

阅读程序（一）

01 #include <iostream>
02 using namespace std;
03
04 const int N = 1000;
05 int c[N];
06
07 int logic(int x, int y) {
08     return (x & y) ^ ((x ^ y) | (~x & y));
09 }
10
11 void generate(int a, int b, int *c) {
12     for (int i = 0; i < b; i++)
13         c[i] = logic(a, i) % (b + 1);
14 }
15 
16 void recursion(int depth, int *arr, int size) {
17     if (depth <= 0 || size <= 1) return;
18     int pivot = arr[0];
19     int i = 0, j = size - 1;
20     while (i <= j) {
21         while (arr[i] < pivot) i++;
22         while (arr[j] > pivot) j--;
23         if (i <= j) {
24             int temp = arr[i];
25             arr[i] = arr[j];
26             arr[j] = temp;
27             i++; j--;
28         }
29     }
30     recursion(depth - 1, arr, j + 1);
31     recursion(depth - 1, arr + i, size - i);
32 }
33
34 int main() {
35     int a, b, d;
36     cin >> a >> b >> d;
37     generate(a, b, c);
38     recursion(d, c, b);
39     for (int i = 0; i < b; ++i) cout << c[i] << " ";
40     cout << endl;
41 }

假设输入的所有数都为不超过 1000 的正整数，完成下面的判断题和单选题：

判断题

16. 当 $1000 \ge d \ge b$ 时，输出的序列是有序的。 {{ select(16) }}

• 正确
• 错误

17. 当输入 $5\ 5\ 1$ 时，输出为 $1\ 1\ 5\ 5\ 5$ 。 {{ select(17) }}

• 正确
• 错误

18. 假设数组 $c$ 长度无限制，该程序所实现的算法的时间复杂度是 $O(b)$ 的。 {{ select(18) }}

• 正确
• 错误

单选题

19. 函数 int logic(int x, int y) 的功能是（ ）。 {{ select(19) }}

• 按位与
• 按位或
• 按位异或
• 以上都不是

20. 当输入为 10 100 100 时，输出的第 100 个数是？（ ）。 {{ select(20) }}

• 91
• 94
• 95
• 98

阅读程序（二）

01 #include <iostream>
02 #include <string>
03 using namespace std;
04
05 const int P = 998244353, N = 1e4 + 10, M = 20;
06 int n, m;
07 string s;
08 int dp[1 << M];
09
10 int solve() {
11     dp[0] = 1;
12     for (int i = 0; i < n; ++i) {
13         for (int j = (1 << (m - 1)) - 1; j >= 0; --j) {
14             int k = (j << 1) | (s[i] - '0');
15             if (j != 0 || s[i] == '1')
16                 dp[k] = (dp[k] + dp[j]) % P;
17         }
18     }
19     int ans = 0;
20     for (int i = 0; i < (1 << m); ++i) {
21         ans = (ans + 1ll * i * dp[i]) % P;
22     }
23     return ans;
24 }
25
26 int solve2() {
27     int ans = 0;
28     for (int i = 0; i < (1 << n); ++i) {
29         int cnt = 0;
30         int num = 0;
31         for (int j = 0; j < n; ++j) {
32             if (i & (1 << j)) {
33                 num = num * 2 + (s[j] - '0');
34                 cnt++;
35             }
36         }
37         if (cnt <= m) (ans += num) %= P;
38     }
39     return ans;
40 }
41
42 int main() {
43     cin >> n >> m;
44     cin >> s;
45     if (n <= 20) {
46         cout << solve2() << endl;
47     }
48     cout << solve() << endl;
49     return 0;
50 }

假设输入的 $s$ 是包含 $n$ 个字符的 01 串，完成下面的判断题和单选题。

判断题

21. 假设数组 dp 长度无限制，函数 solve() 所实现的算法的时间复杂度是 $O(n \times 2^{m})$。

    {{ select(21) }}

• 正确
• 错误

22. 输入 11 2 10000000001 时，程序输出两个数 32 和 23。 {{ select(22) }}

• 正确
• 错误

23. （2 分）在 $n \le 10$ 时，solve() 的返回值始终小于 $4^{10}$。

{{ select(23) }}

• 正确
• 错误

单选题

24. 当 $n = 10$ 且 $m = 10$ 时，有多少种输入使得两行的结果完全一致？（ ） {{ select(24) }}

• 1024
• 11
• 10
• 0

25. 当 $n \le 6$ 时，solve() 的最大可能返回值为（ ）？ {{ select(25) }}

• 65
• 211
• 665
• 2059

26. 若 $n = 8, m = 8$，solve 和 solve2 的返回值的最大可能差值为（ ）？ {{ select(26) }}

• 1477
• 1995
• 2059
• 2187

阅读程序（三）

01 #include <iostream>
02 #include <cmath>
03 using namespace std;
04
05 int customFunction(int a, int b) {
06    if (b == 0) {
07        return a;
08    }
09    return a + customFunction(a, b - 1);
10 }
11
12 int main() {
13    int x, y;
14    cin >> x >> y;
15    int result = customFunction(x, y);
16    cout << pow(result, 2) << endl;
17    return 0;
18 }

判断题

27. 当输入为“2 3”时，customFunction（2,3）的返回值为“64”。

    {{ select(27) }}

• 正确
• 错误

28. 当 b 为负数时，customFunction（a，b）会陷入无限递归。 {{ select(28) }}

• 正确
• 错误

29. 当 b 的值越大，程序的运行时间越长。 {{ select(29) }}

• 正确
• 错误

单选题

30. 当输入为“5 4”时，customFunction(5,4) 的返回值为（ ）。 {{ select(30) }}

• 5
• 25
• 250
• 625

31. 如果输入x = 3 和 y = 3，则程序的最终输出为（ ）。 {{ select(31) }}

• 27
• 81
• 144
• 256

32. （4分）若将customFunction函数改为“return a ＋ customFunction(a-1，b-1)；并输入“3 3”，则程序的最终输出为（ ）。 {{ select(32) }}

• 9
• 16
• 25
• 36

三、程序填空

（单选题，每小题 3 分，共计 30 分）

程序填空(一)

1. (判断平方数) 问题：给定一个正整数 n，判断这个数是不是完全平方数，即存在一个正整数 x 使得 x 的平方等于 n。 试补全程序

#include <iostream>
#include <vector>
using namespace std;
bool isSquare(int num)
{
    int i = ①;
    int bound = ②;
    for (; i <= bound; ++i)
    {
        if (③)
        {
            return ④;
        }
    }
    return ⑤;
}
int main()
{
    int n;
    cin >> n;
    if (isSquare(n))
    {
        cout << n << " is a Square number" << endl;
    }
    else
    {
        cout << n << " is not a Square number" << endl;
    }

    return 0;
}

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

• 1
• 2
• 3
• 4

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

• (int)floor(sqrt(num)-1)
• (int)floor(sqrt(num))
• floor(sqrt(num/2))-1
• floor(sqrt(num/2))

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

• num=2*i
• num== 2*i
• num=i*i
• num==i*i

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

• num= 2*i
• num==2*i
• true
• false

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

• num= i*i
• num!=2*I
• true
• False

完善程序(二)

2.（汉诺塔问题）给定三根柱子，分别标记为A、B和C。初始状态下，柱子A上有若干个圆盘，这些圆盘从上到下按从小到大的顺序排列。任务是将这些圆盘全部移到柱子c上，且必须保持原有顺序不变。在移动过程中，需要遵守以不规则： 1．只能从一根柱子的顶部取出圆盘，并将其放入另一根柱子的顶部。 2．每次只能移动一个圆盘 3．小圆盘必须始终在大圆盘之上。

试补全程序

#include <bits/stdc++.h>
using namespace std;
void move(char src, char tgt)
{
    cout << "从柱子" << src << "挪到柱子上" << tgt << endl;
}
void dfs(int i, char src, char tmp, char tgt)
{
    if (i == ①)
    {
        move(②);
        return;
    }
    dfs(i - 1, ③);
    move(src, tgt);
    dfs(⑤, ④);
}
int main()
{
    int n;
    cin >> n;
    dfs(n, 'A', 'B', 'C');
    return 0;
}

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

• 0
• 1
• 2
• 3

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

• src,tmp
• src,tgt
• tmp,tgt
• tgt,tmp

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

• src,tmp,tgt
• src, tgt, tmp
• tgt, tmp, src
• tgt, src, tmp

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

• src, tmp, tgt
• tmp,src, tgt
• src, tgt,tmp
• tgt,src,tmp

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

• 0
• 1
• i-1
• i