一、单项选择题(共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²)
• O(nlogn)

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

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

• 

• 

• 

• 

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题

判断题

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

选择题

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

• Valid
• Invalid
• invalid
• valid

20. 这个程序的时间复杂度是多少？（ ） {{ select(20) }}

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

第2题

判断题

21. 若输入 5 2 7 9 3 1，则输出为 12。 ( ) {{ select(21) }}

• 正确
• 错误

22. 这段代码对应的状态转移方程为 dp[i] = max(dp[i-1], dp[i-2]+a[i]), i>=2; 初值为 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, 0, 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题

判断题

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^6$ 的只包含小写英文字母的字符串 s，输出有多少个子串满足以 heavy 开头并且以 metal 结尾。

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

int main() {
    string s;
    cin >> s;
    long long cnt = ①, ans = 0;
    for(int i = 4; ②; i++) {
        auto cur = ③;
        if(④)
            cnt++;
        else if(cur == "metal")
            ⑤;
    }
    cout << ans << endl;
    return 0;
}

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

• 0
• 1E9
• -1E9
• -2E9

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

• i < s.length()
• i <= s.length()
• i < s.length() - 1
• i >= s.length()

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

• s.substr(i, 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≤l≤r≤10^{18})。如果整数 x 的首位数字等于末位数字，那么称 x 是合法数字。例如 101,477474,9 是合法数字，而 47,253,1020 不是合法数字。输出 [l,r] 中有多少个合法数字？ （提示：考虑最低位和最高位之间的关系。）

#include <bits/stdc++.h>
using namespace std;
long long l,r;
long long fir(long long g) {
    while(g>=10) ①;
    return g;
}
long long fin(long long g) {
    return g%10;
}
long long solve(long long n) {
    if(n<=9)return n;
    else {
        long long base=(②);
        long long first=fir(n);
        bool flag=(③);
        return ④;
    }
}

int main() {
    cin>>l>>r;
    cout<<⑤<<endl;
    return 0;
}

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)