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

1. 如果a和b都是char类型的变量，下列哪个语句不符合C++语法？（）

{{ select(1) }}

• b = ++a;
• b = 'a'++;
• b = 'a' + '1';
• b = a++;

2. 泛洪填充算法属于（）算法

{{ select(2) }}

• 贪心
• 二分
• 动态规划
• 搜索

3. 在下列代码的横线处填写（），可以使得输出是“5 8”

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x = 8, y = 5;
    x = x ^ y;
    y = x ^ y;
    // 横线处填写代码
    cout << x << " " << y << endl;
    return 0;
}

{{ select(3) }}

• x = x ^ y
• y = x ^ y
• a = x + y
• x = x + y

4. 小写字母a的ASCII码值为97，小写字母z的ASCII码值用八进制数表示为（）

{{ select(4) }}

• 170
• 174
• 172
• 171

5. 从n个正整数1，2，…，n中任意取出两个不同的数，若取出的两数之和等于5的概率为1/14，则n为（）

{{ select(5) }}

• 6
• 7
• 8
• 9

6. 下面不可以用作C++程序中的变量名的是（）

{{ select(6) }}

• cstr
• cint
• pops
• this

7. 设有n个数和m个桶，桶排序算法（桶内采用插入排序）在最坏情况下的时间复杂度是（）

{{ select(7) }}

• $O(nm)$
• $O(n + m)$
• $O(n^2)$
• $O(n \log n)$

8. 一个二维数组定义为long long a[5][8];，则这个二维数组占用内存空间的大小为（）字节

{{ select(8) }}

• 320
• 160
• 80
• 40

9. 下列关于C++语言中自定义函数的叙述，正确的是（）

{{ select(9) }}

• 自定义函数的参数可以是结构体类型
• 自定义函数的参数不能超过五个
• 自定义函数必须有返回值
• 自定义函数定义必须写在调用它的函数前面，否则会发生编译错误

10. 为了防范计算机病毒，保护个人隐私和信息安全，下列做法中正确的是（）

{{ select(10) }}

• 每六个月更换一次计算机的登录密码，密码采用大小写英文字母和数字混合的形式，位数多于8位
• 手机收到提示中奖的短信，点开链接看看是否真的中奖了
• 将个人的私密照片和视频发到同学间建立的QQ群
• 借用同学的U盘将下载的网络游戏安装包复制到自己的笔记本计算机中

11. 下列代码可以用来求最长上升子序列（LIS）的长度，如果输入是5 1 7 3 5 9，则输出是（）

#include <bits/stdc++.h>
using namespace std;
int a[2025], dp[2025];
int main() {
    int n, i, j, ret = -1;
    cin >> n;
    for (i = 1; i <= n; ++i) {
        cin >> a[i];
        dp[i] = 1;
    }
    for (i = 1; i <= n; ++i)
        for (j = 1; j < i; ++j)
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
    for (i = 1; i <= n; ++i) {
        ret = max(ret, dp[i]);
        cout << dp[i] << " ";
    }
    cout << ret << endl;
    return 0;
}

{{ select(11) }}

• 9 7 5 1 1 9
• 1 2 2 3 4 4
• 1 3 5 7 9 9
• 1 1 1 1 1 1

12. 已知逻辑表达式A=true，B=C=D=false，则以下逻辑表达式中取值为真的是（）

{{ select(12) }}

• $(C \land D \lor \neg A) \lor (A \land C \lor D)$
• $\neg ((A \land B \lor C) \land (D \lor B))$
• $(A \land (B \lor C \lor D)) \lor (A \land D)$
• $(A \lor (C \lor D)) \land (B \lor C)$

13. 某二叉树的前序遍历序列为ABDFCEGH，中序遍历序列为BFDAGEHC，则下列说法中正确的是（）

{{ select(13) }}

• 树的高度为3
• 节点A的右子树共有4个结点
• 树可能有4个叶子结点或者2个叶子结点
• 以上说法都不对

14. 设P为2~100范围内的质数，$p^3 + 7p^2$为完全平方数，则p的取值有（）种不同的可能

{{ select(14) }}

• 2
• 1
• 3
• 0

15. 在图的广度优先搜索中，既要维护一个标志数组来标志已访问的结点，还需使用（）结构存放结点以实现遍历

{{ select(15) }}

• 栈
• 堆
• 队列
• 哈希表

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

（1）

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 bool isvalid(string s) {
05     stack<char> stk;
06     for (char ch : s) {
07         if (ch == '(' || ch == '[' || ch == '{') {
08             stk.push(ch);
09         } else {
10             if (stk.empty()) {
11                 return false;
12             }
13             if (ch == ')' && stk.top() != '(') {
14                 return false;
15             }
16             if (ch == ']' && stk.top() != '[') {
17                 return false;
18             }
19             if (ch == '}' && stk.top() != '{') {
20                 return false;
21             }
22             stk.pop();
23         }
24     }
25     return stk.empty();
26 }
27
28 int main() {
29     string s;
30     cin >> s;
31     if (isvalid(s))
32         cout << "valid" << endl;
33     else
34         cout << "Invalid" << endl;
35     return 0;
36 }

判断题

16. 若程序输入({[]})，则程序输出valid。（）

{{ select(16) }}

• 正确
• 错误

17. 若将第10~12行代码删除，则程序依然可以正常运行。（）

{{ select(17) }}

• 正确
• 错误

18. 若删除头文件#include <bits/stdc++.h>，则只需要添加<iostream>头文件就可以通过编译。（）

{{ select(18) }}

• 正确
• 错误

选择题

19. 若输入(({{[]}))，则输出是什么？（）

{{ select(19) }}

• Valid
• Invalid
• invalid
• valid

20. 这个程序的时间复杂度是多少？（）

{{ select(20) }}

• $O(n)$
• $O(n^2)$
• $O(n \log n)$
• $O(n\sqrt{n})$

（2）

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

判断题

21. 若输入5 2 7 9 3 1，则输出为12。（）

{{ select(21) }}

• 正确
• 错误

22. 该程序求解的是类似“打家劫舍”的问题，其中dp数组的初值为dp[0] = a[0]，dp[1] = a[1]。（）

{{ select(22) }}

• 正确
• 错误

23. （2分）在主函数中，访问dp[n]不会发生越界错误。（）

{{ select(23) }}

• 正确
• 错误

选择题

24. 当输入的a数组为[2, 1, 1, 2]时，程序的输出为（）

{{ select(24) }}

• 1
• 2
• 3
• 4

25. 若将第13行改为dp[i] = max(dp[i - 1], dp[i - 2] - a[i]);，则当输入的a数组为{10, 1, 25, 3}时，程序的输出为（）

{{ select(25) }}

• 1
• 10
• 35
• 25

26. （4分）当输入的a数组为{0, 2, 3, 0, 5, 6, 0, 8, 9}时，程序的输出为（）

{{ select(26) }}

• 18
• 33
• 34
• 2

（3）

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int bfs(vector<vector<int>> grid) {
05     const int m = grid.size(), n = grid[0].size();
06     const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
07     using pii = pair<int, int>;
08     queue<pii> q;
09     vector<vector<bool>> vis(m + 1, vector<bool>(n + 1));
10     int ans = 0, tot = 0, cnt = 0;
11     for (int i = 0; i < m; i++)
12         for (int j = 0; j < n; j++) {
13             if (grid[i][j] == 2)
14                 q.push({i, j}), vis[i][j] = 1;
15             tot += (grid[i][j] != 0);
16         }
17     while (!q.empty()) {
18         int cur = q.size();
19         for (int i = 1; i <= cur; i++) {
20             auto u = q.front();
21             int x = u.first, y = u.second;
22             q.pop();
23             cnt++;
24             for (int j = 0; j < 4; j++) {
25                 int cx = x + dx[j], cy = y + dy[j];
26                 if (cx < 0 || cx >= m || cy < 0 || cy >= n || vis[cx][cy] || grid[cx][cy] == 0)
27                     continue;
28                 if (grid[cx][cy] == 1) {
29                     q.push({cx, cy}), vis[cx][cy] = 1;
30                 }
31             }
32         }
33         ans++;
34     }
35     if (tot == cnt)
36         return max(0, ans - 1);
37     else
38         return -1;
39 }
40
41 int main() {
42     int m, n;
43     vector<vector<int>> a(m, vector<int>(n));
44     for (int i = 0; i < m; i++)
45         for (int j = 0; j < n; j++)
46             cin >> a[i][j];
47     cout << bfs(a) << endl;
48     return 0;
49 }

判断题

27. 当输入的a数组为{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}时，程序的输出为4。（）

{{ select(27) }}

• 正确
• 错误

28. bfs函数的时间复杂度为$O(nm)$。（）

{{ select(28) }}

• 正确
• 错误

29. 由代码可知，格子中的一个2可以把八个方向上的1都变为2。（）

{{ select(29) }}

• 正确
• 错误

选择题

30. 当输入的a数组为{{2, 1, 1}, {0, 1, 1}, {1, 0, 1}}时，程序的输出为（）

{{ select(30) }}

• -1
• 2
• 3
• 4

31. （4分）如果删掉bfs函数中与vis数组相关的内容，不可能发生的结果是（）

{{ select(31) }}

• 不影响结果，答案依然正确
• 某个格子会重复进入队列，但答案依然正确
• 某个格子会重复进入队列，将得到不正确的答案
• 无法控制格子的入队次数，内存超限

32. 当输入的a数组为{{0, 2}}时，程序的输出为（）

{{ select(32) }}

• 0
• 1
• -1
• 发生运行时错误

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

（1）题目描述： 给定一个长度小于或等于10的只包含小写英文字母的字符串s，输出有多少个子串满足以“heavy”开头并且以“metal”结尾。

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int main() {
05     string s;
06     cin >> s;
07     long long cnt = ①, ans = 0;
08     string heavy = "heavy", metal = "metal";
09     for (int i = 4; ②; i++) {
10         auto cur = ③;
11         if (④)
12             cnt++;
13         else if (cur == "metal")
14             ⑤;
15     }
16     cout << ans << endl;
17     return 0;
18 }

33. ①处应填（）

{{ select(33) }}

• 0
• 1e9
• -1e9
• -2e9

34. ②处应填（）

{{ select(34) }}

• i < s.length()
• i \leq s.length()
• i < s.length() - 1
• i \geq s.length()

35. ③处应填（）

{{ select(35) }}

• s.substr(1, 5)
• s.substr(i - 5, 5)
• s.substr(i - 4, 5)
• s.substr(i - 5)

36. ④处应填（）

{{ select(36) }}

• cur == heavy
• cur == "heavy"
• cur != heavy
• cur != "heavy"

37. ⑤处应填（）

{{ select(37) }}

• ans++
• ans += cnt
• cnt += ans
• cnt++

（2）题目描述： 输入l和$r(1 \leq l \leq r \leq 10^{18})$。如果整数x的首位数字等于末位数字，那么称x是合法数字。例如101，477474，9是合法数字，而47，253，1020不是合法数字。输出$[l, r]$中有多少个合法数字？

01 #include <bits/stdc++.h>
02 using namespace std;
03 long long l, r;
04 long long fir(long long g) {
05     while (g >= 10)
06         ①;
07     return g;
08 }
09 long long fin(long long g) {
10     return g % 10;
11 }
12 long long solve(long long n) {
13     if (n <= 9)
14         return n;
15     else {
16         long long base = ②;
17         long long first = fir(n);
18         bool flag = ③;
19         return ④;
20     }
21 }
22 int main() {
23     cin >> l >> r;
24     cout << ⑤ << endl;
25     return 0;
26 }

38. ①处应填（）

{{ select(38) }}

• g /= 10
• g -= 10
• g \%= 10
• g ^= 10

39. ②处应填（）

{{ select(39) }}

• n \% 10 + 9
• n \% 10
• n / 10
• n / 10 + 9

40. ③处应填（）

{{ select(40) }}

• fir(n) < fin(n)
• fir(n) <= fin(n)
• fir(n) > fin(n)
• fir(n) >= fin(n)

41. ④处应填（）

{{ select(41) }}

• base + flag
• base
• flag
• base - flag

42. ⑤处应填（）

{{ select(42) }}

• solve(r)
• solve(l)
• solve(r) - solve(l - 1)
• solve(r) - solve(l)

---