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

1. 十进制数 2025 的十六进制表示是（ ）。 {{ select(1) }}

• 07D9
• 07E9
• 07F9
• 07F1

2. 以下关于计算机竞赛 IOI 的描述正确的是（ ）。 {{ select(2) }}

• IOI 非英语国家参赛选手可以在比赛中携带电子词典
• IOI 参赛选手可携带已关机的手机放在自己座位后面的包里
• IOI 参赛选手在比赛时间内去厕所的时候可携带手机
• IOI 全称是国际信息学奥林匹克竞赛

3. 以下不能用 ASCII 码表示的字符是（ ）。 {{ select(3) }}

• @
• ①
• ^
• ~

4. 设变量 s 为 double 型且已赋值，下列哪条语句能将 s 中的数值保留到小数点后一位，并将第二位四舍五入？（ ） {{ select(4) }}

• s = (x * 10 + 0.5) / 10.0
• s = s * 10 + 0.5 / 10.0
• s = (s / 10 + 0.5) * 10.0
• s = (int)(s * 10 + 0.5) / 10.0

5. 以下不属于 STL 链表中的函数的是（ ）。 {{ select(5) }}

• sort
• empty
• push_back
• resize

6. 小明写了一个程序，在这里用到的数据结构是（ ）。

#include <iostream>
using namespace std;
int k;
int f(int a)
{
    if(a-k > 0 && (a-k) % 2 == 0)
      return f((a+k)/2) + f((a-k)/2);
    else
      return 1;
}
int main()
{
    int n;
    cin >> n >> k;
    if((n+k) & 1)
    {
        cout << 1 << endl;
        return 0;
    }
    cout << f(n);
    return 0;
}

{{ select(6) }}

• 树
• 栈
• 链表
• 队列

7. 小明想求 n 个不同正整数的全排列，他设计的程序采用 DFS 方法的时间复杂度是（ ）。 {{ select(7) }}

• O(logn)
• O(n!)
• O(n^2)
• O(nlogn)

8. 在下列排序算法中，（ ）是不稳定的排序算法。 {{ select(8) }}

• 归并排序
• 插入排序
• 选择排序
• 冒泡排序

9. 一台 32 位操作系统的计算机运行 C++，下列说法中错误的是（ ）。 {{ select(9) }}

• double 类型的变量占用 8 字节内存空间
• bool 类型的变量占用 1 字节内存空间
• long long 类型变量的取值范围比 int 类型变量的大一倍
• char 类型的变量也可以作为循环变量

10. 若整型变量 n 的值为 25，则表达式 n & (n+1>>1) 的值是（ ）。 {{ select(10) }}

• 25
• 26
• 9
• 16

11. 一群学生参加学科夏令营，每名同学至少参加一个学科的考试。已知有 100 名学生参加了数学考试，50 名学生参加了物理考试，48 名学生参加了化学考试，学生总数是参加至少两门考试学生的两倍，也是参加三门考试学生数的三倍，则学生总数为（ ）。 {{ select(11) }}

• 90
• 96
• 108
• 120

12. 以下不是C++中的循环语句的是（ ）。 {{ select(12) }}

• while
• do...while
• for
• switch...case

13. 二叉树T，已知其后序遍历序列为4 2 7 5 6 3 1，中序遍历序列为4 2 1 5 7 3 6，则其前序遍历序列为（ ）。 {{ select(13) }}

• 1 2 5 7 6 3 4
• 1 2 4 3 5 7 6
• 1 4 2 7 5 3 6
• 1 4 7 2 3 5 6

14. 一个六位数是完全平方数，且最后三位数字都是4，这样的六位数有（ ）个。 {{ select(14) }}

• 2
• 3
• 4
• 5

15. 用三种颜色给1×4的长方形方格区域涂色，在每种颜色至少用1次的前提下，相邻方格不涂同一种颜色的概率为（ ）。 {{ select(15) }}

• 1/3
• 2/3
• 1/2
• 4/9

---

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

第1题

判断题

16. 若程序输入 5 -2 -1 -3 -6 4，则程序输出 4。 （ ） {{ select(16) }}

• 正确
• 错误

17. 对于第 17 行的代码，如果不判断(tot - v) % 2 == 0，则程序依然可以得到正确的结果。 （ ） {{ select(17) }}

• 正确
• 错误

18. 若将头文件<bits/stdc++.h>换为<iostream>，程序依然可以正常运行。（ ） {{ select(18) }}

• 正确
• 错误

选择题

19. 若输入 8 6 -31 50 -35 41 37 -42 13，则输出是（ ）。 {{ select(19) }}

• 13
• -35
• -31
• -100000

20. 如果去除第 19 行的代码，对于输入 4 2 3 5 10，输出是（ ）。 {{ select(20) }}

• 2
• 5
• 10
• -100000

第2题

假设第 17 行的 find 函数的时间复杂度为 O(log n)，substr 函数的时间复杂度视为 O(1)，完成下面的问题。

判断题

21. 若输入 3 abc aaaaa bcdef aabcdabc，则输出为 2。 （ ） {{ select(21) }}

• 正确
• 错误

22. 若将第 18 行中的 dp[i + 1] 改为 dp[i]，则可能出现编译错误。 （ ） {{ select(22) }}

• 正确
• 错误

23. （2 分）该程序的输出一定小于或等于输入的 n。 （ ） {{ select(23) }}

• 正确
• 错误

选择题

24. 当输入的 a 数组为 {"abababab", "ab"}, t="ababababa" 时，程序的输出为 ( )。 {{ select(24) }}

• 0
• 1
• 2
• 3

25. 若删除第 17 行的代码，则当输入的 a 数组为 {"abababab", "ab"}, t="ababa" 时，程序的输出为 ( )。 {{ select(25) }}

• 1
• 2
• 3
• 4

26. （4 分）这段代码的时间复杂度为 ( )。 {{ select(26) }}

• O(n)
• O(nlogn)
• O(n²)
• O(n²logn)

第3题

假设1≤n，presses≤4,回回答下面的问题。

判断题

27. 若输入为 2 1，则程序的输出为 3。 （ ） {{ select(27) }}

• 正确
• 错误

28. 对于第 7 行代码，变量 i 的上界为 16。 （ ） {{ select(28) }}

• 正确
• 错误

29. 对于任意的输入，程序的输出不会大于 8。 （ ） {{ select(29) }}

• 正确
• 错误

选择题

30. 当输入为 n=3,presses=2 时，程序的输出为（ ）。 {{ select(30) }}

• 5
• 6
• 7
• 8

31. (4 分) 若删除第 18~19 行的代码，当输入为 n=3, presses=2 时，程序的输出为（ ）。 {{ select(31) }}

• 1
• 2
• 3
• 4

32. 上述代码的时间复杂度为（ ）。 {{ select(32) }}

• O(1)
• O(logn)
• O(n)
• O(nlogn)

---

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

第1题

题目描述： 输入 n(1≤n≤2×105) 和长为 n 的数组 a (1≤a[i]≤n)。 你可以多次执行如下操作：选择两个下标 i 和 j，满足 a[i]=a[j]。删除下标 [i,j] 中的元素。删除后，数组长度减少 i-j+1。 输出你最多可以删除多少个数。

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

const int inf = 0x3f3f3f3f;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    vector<int> dp(n + 1), ①;
    for(int i = 1; i <= n; i++)
    {
        dp[i] = max(dp[i], ②);
        dp[i] = max(dp[i], ③);
        lst[a[i]] = max(lst[a[i]], ④);
    }
    cout << ⑤ << endl;
    return;
}

int main()
{
    int t = 1;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

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

• lst(n+1)
• lst(n+1, 0)
• lst(n+1, inf)
• lst(n+1, -inf)

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

• dp[i - 1]
• dp[i]-1
• dp[i+1]
• dp[i]+1

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

• lst[a[i]]
• lst[a[i]]+i+1
• lst[a[i]]+i
• lst[i]+i

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

• dp[i-1]-i
• dp[i-1]+i
• dp[i+1]-i
• dp[i+1]+i

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

• dp[1]
• dp[0]
• dp[n-1]
• dp[n]

第2题

题目描述： 输入 n (1≤n≤1×10^5) 和长为 n 的数组 a(0≤a[i]<2^20)。 输出最小的正整数 k，使得 a 的所有长为 k 的连续子数组的 OR 都相同。注意答案是一定存在的，因为 k=n 一定满足要求。

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 0;
    for(int i = 0; ①; i++)
    {
        int cnt = 0, lst = 0;
        for(int j = 1; j <= n; j++)
        {
            if(②)
                cnt++;
            else
                lst = ③, cnt = 0;
        }
        lst = max(lst, cnt);
        if(④)
            continue;
        ans = max(ans, lst + 1);
    }
    cout << ⑤ << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

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

• i < 20
• i <= 20
• i > 20
• i != 20

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

• !(a[i] & (1 << j))
• a[i] & (1 << j)
• a[j] & (1 << i)
• !(a[j] & (1 << i))

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

• min(lst, cnt)
• max(lst, cnt)
• cnt
• lst + cnt

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

• lst < n
• lst != n
• lst == n
• lst > n

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

• ans
• min(ans, n)
• min((ans==0?1:ans), n)
• (ans==0?1:ans)