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

1. $(1ACF)_{16}$ 和 $(0456)_{16}$ 这两个十六进制数做加法的结果是（）

{{ select(1) }}

• $(1F25)_{16}$
• $(7975)_{10}$
• $(17455)_{8}$
• $(11110100111)_{2}$

2. 一个64位无符号长整型变量占用（）字节

{{ select(2) }}

• 32
• 4
• 16
• 8

3. 下列选项中，（）判断字符串s1是否为回文串，如果是就输出"yes"，否则输出"no"

int main() {
    string s1, s2;
    cin >> s1;
    s2 = s1;
    // 此处插入选项代码
    if (s1 == s2)
        cout << "yes";
    else
        cout << "no";
    return 0;
}

{{ select(3) }}

• reverse(s1.begin(), s1.end());
• reverse(s1[0], s1[s1.size()]);
• s1.reverse(begin(), end());
• reverse(s1, s1 + s1.size());

4. 已知x、y、z都是int类型的整数，$x=1$，$y=1$，$z=3$。那么执行bool ans = x + 1 || y && ++z后，x、y、z和ans的值各为多少？（）

{{ select(4) }}

• $x=2, y=0, z=4, ans=1$
• $x=2, y=1, z=3, ans=1$
• $x=2, y=1, z=3, ans=0$
• $x=2, y=0, z=4, ans=0$

5. 指针p指向变量a，q指向变量c。能够把c插入到a和b之间并形成新链表的语句组是（）

{{ select(5) }}

• p.next = q; q.next = p.next;
• p->next = &c; q->next = p->next;
• (*p).next = q; (*q).next = &b;
• a.next = c; c.next = b;

6. 以下哪个特性是数组和链表共有的？（）

{{ select(6) }}

• 动态分配
• 元素之间的次序关系
• 通过索引访问
• 存储连续

7. 下面关于哈夫曼树的描述中，正确的是（）

{{ select(7) }}

• 哈夫曼树一定是完全二叉树
• 哈夫曼树一定是平衡二叉树
• 哈夫曼树中权值最小的两个结点互为兄弟结点
• 哈夫曼树中左子结点小于父结点，右子结点大于父结点

8. 已知一棵二叉树有2025个结点，则其中至多有（）个结点有2个子结点

{{ select(8) }}

• 1010
• 1011
• 1012
• 1013

9. 下面的说法中正确的是（）

{{ select(9) }}

• 计算机网络按照拓扑结构分为星型、环型、总线型等
• 互联网的基础是OSI七层协议而不是TCP/IP协议族
• 现代计算机网络主要采用电路交换技术
• 10.10.1.1是D类IP地址

10. 下面关于图的说法中正确的是（）

{{ select(10) }}

• 所有点数为奇数的连通图，一定可以一笔画成
• 所有只有两个奇度点（其余均为偶度点）的连通图，一定可以一笔画成
• 哈密顿图一定是欧拉图，而欧拉图未必是哈密顿图
• 哈密顿图不一定是欧拉图，而欧拉图一定是哈密顿图

11. （）是一种选优搜索法，按选优条件向前搜索以达到目标。当搜索到某一步时，如果发现原先的选择并不优或者达不到目标，就后退一步重新选择

{{ select(11) }}

• 二分算法
• 动态规划
• 回溯法
• 贪心算法

12. 动态规划是将一个问题分解为一系列子问题后来求解，下面（）属于动态规划问题

{{ select(12) }}

• 多重背包
• 排队打水
• 有序数组找数
• 全排列

13. 设无向图G的邻接矩阵如下图所示，则G的顶点数和边数分别为（）

$$\begin{bmatrix}0&1&1&0&0\\1&0&0&1&1\\1&0&0&0&0\\0&1&0&0&1\\0&1&0&1&0\end{bmatrix} $$

{{ select(13) }}

• 4，5
• 5，8
• 4，10
• 5，5

14. 某条道路从东到西有8个路灯，巡查员为了维护方便，在每根灯杆上都安装了开关，第i个开关能够切换前i个灯的状态（$i=1\sim8$，灯开或关），一开始灯全是开的。巡查员通过控制开关一共能得到（）种不同灯的开或者关的组合状态

{{ select(14) }}

• 128
• 256
• 127
• 255

15. 某四位正整数abcd满足如下条件（a是正整数，b、c、d是非负整数）：$abcd=1^3+2^3+\cdots+n^3$，$abcd=(1+2+3+\cdots+n)^2$，$abcd=(ab+cd)^2$，这样的正整数abcd共有（）个

{{ select(15) }}

• 0
• 1
• 2
• 3

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

（1）

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 100 + 5;
04 int n, C, x, y, Len, L[N], r[N], cha[N];
05 char a[N];
06 int main() {
07     scanf("%d%d%s", &n, &C, a + 1);
08     Len = n;
09     for (int i = 1; i <= C; i++) {
10         scanf("%d%d", &L[i], &r[i]);
11         cha[i] = Len - L[i] + 1;
12         Len += r[i] - L[i] + 1;
13     }
14     scanf("%d", &x);
15     for (int i = C; i; i--)
16         if (x >= L[i] + cha[i] && x <= r[i] + cha[i])
17             x -= cha[i];
18     printf("%c\n", a[x]);
19     return 0;
20 }

输入保证$1 \leq l_i \leq r_i \leq n \leq 100$，$1 \leq c \leq 100$。回答以下问题。

判断题

16. 第17行最多会运行一次。（）

{{ select(16) }}

• 正确
• 错误

17. （2分）当程序运行至第19行时，x一定在$[1, n]$范围内。（）

{{ select(17) }}

• 正确
• 错误

18. 若将第3行改成const int N = 100;，一定不会出现数组越界问题。（）

{{ select(18) }}

• 正确
• 错误

选择题

19. 若输入4 2 mark 1 4 5 7，则输出为（）

{{ select(19) }}

• m
• a
• r
• k

20. （4分）若输入7 3 cream 1 2 3 3 4 2 9 11，则输出为（）

{{ select(20) }}

• m
• e
• a
• i

（2）

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 2e5 + 5;
04 int n, ans, a[N], cnt[20];
05 int main() {
06     scanf("%d", &n);
07     for (int i = 1; i <= n; ++i) {
08         scanf("%d", &a[i]);
09         for (int j = 0; j <= 14; ++j) {
10             cnt[j] += a[i] & 1;
11             a[i] /= 2;
12         }
13     }
14     for (int i = 1; i <= n; ++i) {
15         int sum = 0, x = 1;
16         for (int j = 0; j <= 14; ++j) {
17             if (cnt[j]) {
18                 sum += x;
19                 --cnt[j];
20             }
21             x *= 2;
22         }
23         ans += sum * sum;
24     }
25     return printf("%d\n", ans), 0;
26 }

已知$1 \leq n$，$a < 2^{15}$，完成下列各题。

判断题

21. 第10行可以写成cnt[j] += a[i] % 2。（）

{{ select(21) }}

• 正确
• 错误

22. 第23行一定不会溢出int上界。（）

{{ select(22) }}

• 正确
• 错误

23. 若输入为1 a₁，则输出为$a₁²$。（）

{{ select(23) }}

• 正确
• 错误

24. 若输入为3 1 3 5，则输出为51。（）

{{ select(24) }}

• 正确
• 错误

选择题

25. 该程序的时间复杂度为（）

{{ select(25) }}

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

26. 若输入为2 12 36 9，则程序运行至第13行时，cnt数组的和为（）

{{ select(26) }}

• 6
• 7
• 9
• 10

（3）

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 10005, M = 15;
04 char c[N];
05 int d, num[N], dp[N][M][2];
06 int dfs(int pos, int res, int sta) {
07     if (pos == 0)
08         return res == 0;
09     if (dp[pos][res][sta] != -1)
10         return dp[pos][res][sta];
11     int ret = 0, maxx = 9;
12     if (sta) maxx = num[pos];
13     for (int i = 0; i <= maxx; i++)
14         ret += dfs(pos - 1, (res + i) % d, sta && (i == maxx));
15     dp[pos][res][sta] = ret;
16     return ret;
17 }
18 int main() {
19     scanf("%s%d", c + 1, &d);
20     memset(dp, -1, sizeof(dp));
21     for (int i = 1; i <= strlen(c + 1); i++)
22         num[i] = c[strlen(c + 1) - i + 1] - '0';
23     printf("%d\n", dfs(strlen(c + 1), 0, 1) - 1);
24     return 0;
25 }

已知$1 \leq d < 10$，$1 \leq |c| \leq 10000$，完成下列各题。

判断题

27. 将程序中的第2行去除，程序依然能正常运行。（）

{{ select(27) }}

• 正确
• 错误

28. 该程序的时间复杂度为$O(|c|²)$。（）

{{ select(28) }}

• 正确
• 错误

选择题

29. 若将程序中的第15行去除，则程序的时间复杂度为（）

{{ select(29) }}

• $O(10^{|d|})$
• $O(100d|c|)$
• $O(10d|c|)$
• $O(10^{d|c|})$

30. 若输入为9 2，则输出为（）

{{ select(30) }}

• 1
• 2
• 4
• 7

31. 若输入为30 4，则输出为（）

{{ select(31) }}

• 3
• 4
• 6
• 7

32. （4分）若输入为2025 6，则输出为（）

{{ select(32) }}

• 240
• 256
• 280
• 338

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

（1）题目描述： 有一个长度为n的数组a，满足a[i]只能是0、1或2，一开始所有元素均为蓝色。可以执行如下操作：

• 用一枚硬币，把一个蓝色元素涂成红色；
• 选择一个不等于0的红色元素和一个与其相邻的蓝色元素，将所选的红色元素减少1，并将所选的蓝色元素涂成红色。 要将所有元素涂红，最少需要多少枚硬币？

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 2e5 + 5;
04 int n, pre[N], a[N], dp[N][3];
05 int main() {
06     scanf("%d", &n);
07     memset(dp, 0x3f, sizeof dp);
08     dp[0][0] = dp[0][1] = dp[0][2] = 0;
09     for (int i = 1; i <= n; i++)
10         scanf("%d", &a[i]);
11     ①;
12     for (int i = 1; i <= n; i++)
13         pre[i] = ②;
14     for (int i = 2; i <= n; i++) {
15         dp[i][a[i]] = min({③});
16         if (④)
17             dp[i][a[i] - 1] = 1 + min({⑤});
18     }
19     printf("%d", min({dp[n][0], dp[n][1], dp[n][2]}));
20 }

33. ①处应填（）

{{ select(33) }}

• dp[1][a[1] == 2] = 1
• dp[1][a[1] == 1] = 1
• dp[1][a[1] == 0] = 1
• dp[1][a[1]] = 1

34. ②处应填（）

{{ select(34) }}

• a[i] ? pre[i - 1] : i
• a[i] ? i : pre[i - 1]
• a[i] == 2 ?pre[i - 1] : i
• a[i] == 2 ? i : pre[i - 1]

35. ③处应填（）

{{ select(35) }}

• dp[i - 1][0] + 1, dp[i - 1][1], dp[i - 1][2]
• dp[i - 1][0] + 2, dp[i - 1][1] + 1, dp[i - 1][2]
• dp[i - 1][0] + 2, dp[i - 1][1], dp[i - 1][2]
• dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]

36. ④处应填（）

{{ select(36) }}

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

37. ⑤处应填（）

{{ select(37) }}

• dp[pre[i] - 1][0] + 1, dp[pre[i] - 1][1], dp[pre[i] - 1][2]
• dp[pre[i] - 1][0] + 2, dp[pre[i] - 1][1] + 1, dp[pre[i] - 1][2]
• dp[pre[i] - 1][0] + 2, dp[pre[i] - 1][1], dp[pre[i] - 1][2]
• dp[pre[i] - 1][0], dp[pre[i] - 1][1], dp[pre[i] - 1][2]

（2）题目描述： 给你一个长度为n（n≤300000）的整数数组a。 你可以执行以下操作：选择数组中的一个元素，并用其邻近元素的值替换它。 计算在执行上述操作最多k（k≤10）次的情况下，数组的总和可能达到的最小值。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 3e5 + 5;
04 int n, k, a[N], p[N][11], ans[N][11];
05 int main() {
06     scanf("%d%d", &n, &k);
07     for (int i = 1; i <= n; i++) {
08         scanf("%d", &a[i]);
09         ①;
10     }
11     for (int j = 1; j <= k; j++)
12         for (int i = 1; i + j <= n; i++)
13             p[i][j] = min(p[i][j - 1], a[i + j]);
14     for (int j = 1; j <= k; j++)
15         for (int i = 1; i + j <= n; i++)
16             ②;
17     for (int i = 1; i <= n; i++) {
18         ans[i][0] = ③;
19         for (int j = 1; j <= k; j++) {
20             ans[i][j] = min(ans[i - 1][j] + a[i], ans[i][j - 1]);
21             for (int h = 0; ④; h++)
22                 ans[i][j] = min(ans[i][j], ⑤);
23         }
24     }
25     printf("%d\n", ans[n][k]);
26     return 0;
27 }

38. ①处应填（）

{{ select(38) }}

• p[i][0] = i
• p[i][0] = a[i]
• p[i][i] = i
• p[i][i] = a[i]

39. ②处应填（）

{{ select(39) }}

• p[i][j] *= j
• p[i][j] *= (j + 1)
• p[i][j] *= i
• p[i][j] *= (i + 1)

40. ③处应填（）

{{ select(40) }}

• ans[i - 1][0] + a[i]
• ans[i - k][0] + p[i - k + 1][k]
• ans[i - 1][0] + a[i] * i
• ans[i - k][0] + p[i - k + 1][k] * k

41. ④处应填（）

{{ select(41) }}

• h <= i && h <= j
• h < i && h <= j
• h < i && h < j
• h <= i && h < j

42. ⑤处应填（）

{{ select(42) }}

• ans[i - h - 1][j - h] + p[i - h][h]
• ans[i - h][j - h] + p[i - h][h]
• ans[i][j - h] + p[i][h]
• ans[i][j - h] + p[i - h][h]