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

1. 深度优先搜索时，控制与记录搜索过程的数据结构是（ ）。

{{ select(1) }}

• 队列
• 栈
• 链表
• 哈希表

2. 计算机的中央处理器的组成部件是（ ）。

{{ select(2) }}

• 控制器和存储器
• 运算器和存储器
• 控制器、存储器和运算器
• 运算器和控制器

3. 一个正整数在十六进制下有 200 位，则它在二进制下最多可能有（ ）位。

{{ select(3) }}

• 801
• 798
• 799
• 800

4. 一个由 2025 个元素组成的数组已经从小到大排好序，采用二分查找，最多需要（ ）次能够判断是否存在所查找的元素。

{{ select(4) }}

• 2025
• 12
• 11
• 10

5. 无向完全图 G 有 10 个顶点，它有（ ）条边。

{{ select(5) }}

• 45
• 90
• 72
• 36

6. 在 8 位二进制补码中，10110110 表示的是十进制下的（ ）。

{{ select(6) }}

• -202
• -74
• 202
• 74

7. 某市有 2025 名学生参加编程竞赛选拔，试卷中有 20 道选择题，每题答对得 5 分，答错或者不答得 0 分，那么至少有（ ）名同学得分相同。

{{ select(7) }}

• 99
• 98
• 97
• 96

8. 以下哪个操作运算符优先级最高？（ ）

{{ select(8) }}

• 66
• |
• <<.
• ++

9. 如果根结点的深度是1，则一棵恰好有2025个叶子结点的二叉树的深度不可能是（ ）。

{{ select(9) }}

• 11
• 12
• 13
• 2025

10. 现代通用计算机之所以可以表示比较大或者比较小的浮点数，是因为使用了（ ）。

{{ select(10) }}

• 原码
• 补码
• 反码
• 阶码

11. 在C++语言中，一个数组定义为int a[6] = {1, 2, 3, 4, 5, 6};，一个指针定义为int * p = &a[3];，则执行a[2] = *p;后，数组a中的值会变为（ ）。

{{ select(11) }}

• {1, 2, 4, 4, 5, 6}
• {2, 2, 3, 4, 5, 6}
• {1, 2, 2, 4, 5, 6}
• {1, 2, 3, 4, 5, 6}

12. 下面的C++代码执行后的输出是（ ）。

01 #include <bits/stdc++.h>
02 using namespace std;
03 int print(int x)
04 {
05     cout << x << "$";
06     if(1==x || 2==x)
07     return x;
08     else
09     return print(x-1) + print(x-2);
10 }
11 int main()
12 {
13     cout<< print(4)<< endl;
14     return 0;
15 }

{{ select(12) }}

• 4$3$2$2$4
• 4$3$2$2$15$
• 4$3$2$1$2$4
• 4$3$2$1$2$5

13. 小明在一个图书馆送书，第1天送1本，第2天送2本，第3天送3本……第n天送n本，他准备累计送到图书馆的书的总数能整除106就停止，那么小明应连续送（ ）天。

{{ select(13) }}

• 50
• 51
• 52
• 53

14. 7 + 77 + 777 + ⋯ + 77...77（共 2025 个连续的 7）的和的末 2 位数是（ ）。

{{ select(14) }}

• 45
• 55
• 65
• 75

15. 在无重复数字的五位数 a1a2a3a4a5 中，若 a1<a2, a2>a3, a3<a4, a4>a5，则称该五位数为波形数，如 89674 就是一个波形数，由 1, 2, 3, 4, 5 组成的没有重复数字的五位数是波形数的概率是（ ）。

{{ select(15) }}

• 1/5
• 1/6
• 2/15
• 1/3

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 using i64 = long long;
04
05 i64 check(const string &s, int p)
06 {
07   return (p>=1 && ((s[p-1]-'0')*10 + (s[p]-'0'))%4==0)?1ll*p:ll0;
08 }
09
10 int main()
11 {
12
13   string s;
14   cin >> s;
15   i64 ans = 0;
16   for(int i = 0; i < s.length(); i++)
17     ans += ((s[i] - '0') % 4 == 0);
18   for(int i = s.length() - 1; i >= 0; i--)
19     ans += check(s, i);
20   cout << ans << endl;
21   cout << check("114514", 3) << endl;
22   return 0;
23 }

假设$(1 leq s.length() leq 3 times 10^5)$，回答下面的问题。

判断题

16. 若程序输入 124，则程序输出 4（换行）0。 （ ）

{{ select(16) }}

• 正确
• 错误

17. 对于这段代码，check("1234510", 2)的返回值为 2。 （ ）

{{ select(17) }}

• 正确
• 错误

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

{{ select(18) }}

• 正确
• 错误

选择题

19. 若输入 5810438174，则输出是（ ）。

{{ select(19) }}

• 7（换行）0
• 8（换行）0
• 9（换行）0
• 10（换行）0

20. 下面哪个选项是正确的？（ ）

{{ select(20) }}

• 把 check 函数中的第一个参数 const 去掉也可以正常运行

• 把 check 函数中的 p >= 1 去掉依然可以得到正确的答案

• check 函数用来判断由 s[p-1]和 s[p]组成的两位数是否为 4 的倍数

• 整段程序的时间复杂度为 $(O(nlog n))$

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 string calc(string s, string t)
05 {
06   const int n = s.size();
07   if(t.size() > s.size())
08     return "";
09   unordered_map<char, int> mp;
10   int cnt = t.size();
11   for(auto v: t)
12     mp[v]++;
13   string ans;
14   int len = 0x3f3f3f3f;
15   for(int i = 0, j = 0; i < n; i++)
16   {
17     if(mp[s[i]] > 0)
18       cnt--;
19     mp[s[i]]--;
20     if(cnt == 0)
21     {
22       while(mp[s[j]] < 0)
23         mp[s[j++]]++;
24       int len = i - j + 1;
25       if(ans.empty() || ans.size() > len)
26         ans = s.substr(j, len);
27       mp[s[j++]]++;
28       cnt++;
29     }
30   }
31   return ans;
32 }
33
34 int main()
35 {
36   string s, t;
37   cin >> s >> t;
38   cout << calc(s, t) << endl;
39   return 0;
40 }

判断题

21. 若输入 ADOBECODEBANC ABC，则输出为 BANC。 （ ）

{{ select(21) }}

• 正确

• 错误

22. calc 函数中的变量 j 只会增大，不会减小。 （ ）

{{ select(22) }}

• 正确

• 错误

23. (2 分) 若删除第 14 行中的 len 变量，程序将不能正常运行。 （ ）

{{ select(23) }}

• 正确

• 错误

选择题

24. 当输入为 a aa 时，程序的输出为（ ）。

{{ select(24) }}

• "a"

• "aa"

• ""

• "-1"

25. 若删除第 22 行代码，则当输入为 cabwefgewcwaefgcf cae 时，程序的输出为（ ）。

{{ select(25) }}

• "cwae"

• "abwe"

• "cabwe"

• "fgewc"

26. (4 分) 设 n=s.size(), m=t.size(), 则这段程序的时间复杂度为（ ）。

{{ select(26) }}

• $( O(n) )$

• $( O(m) )$

• $( O(m+n) )$

• $( O((m+n)log n) )$

(3)

01 #include <iostream>
02 #include <cstdio>
03 #include <algorithm>
04
05 using namespace std;
06
07 const int N = 1e5 + 10;
08 int n, s, cnt, ans, res;
09 int a[N], b[N];
10
11 bool check(int mid)
12 {
13   for(int i = 1; i <= n; i++)
14     b[i] = a[i] + i * mid;
15   sort(b + 1, b + 1 + n);
16   res = 0;
17   for(int i = 1; i <= mid && res <= s; i++)
18     res += b[i];
19   return res <= s;
20 }
21
22 int main()
23 {
24   scanf("%d%d", &n, &s);
25   for(int i = 1; i <= n; i++)
26   scanf("%d", &a[i]);
27   int l = 0, r = n;
28   while(l <= r)
29   {
30     int mid = (l + r) >> 1;
31     if(check(mid)) cnt = mid, ans = res, l = mid + 1;
32     else r = mid - 1;
33   }
34   printf("%d %d\n", cnt, ans);
35   return 0;
36 }

判断题

27. 若输入4 100 1 2 5 6，则程序的输出为4 54。 （ ）

{{ select(27) }}

• 正确

• 错误

28. 对于任意的输入，cnt 的一个必定合法的取值为 n。 （ ）

{{ select(28) }}

• 正确

• 错误

29. 这个程序的时间复杂度为$( O(n log n) )$。 （ ）

{{ select(29) }}

• 正确

• 错误

选择题

30. 当输入为 3 11 2 3 5 时，程序的输出为（ ）。

{{ select(30) }}

• 1 11

• 2 11

• 3 8

• 0 0

31. 代码中 check 函数的作用是什么？（ ）

{{ select(31) }}

• 判断当前数组是否有序

• 检查是否能从数组中选出 mid 个数，使得它们的总和小于或等于 s

• 判断数组的所有元素是否大于某个值

• 计算数组元素的平均值

32. （4 分）变量 cnt 和 ans 的作用分别是什么？（ ）

{{ select(32) }}

• cnt 记录满足条件的最大 mid 值，ans 记录对应的总和

• cnt 记录数组的长度，ans 记录数组中的最大值

• cnt 表示排序后的最小值索引，ans 记录当前结果的最小值

• cnt 表示满足条件的元素个数，ans 记录最终的目标值

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

(1) 题目描述：

有 r 组数据，每组数据输入 $n (1 <=n <= 10^6)$ 和长为 n 的数组 a $(1<= a[i] <= 10^6)$。

你可以执行如下操作任意次：选择 a[i] 和 a[j] $((i neq j))$，以及 a[i] 的一个因子 x。

然后执行 a[i] / = x 和 a[j] *= x。能否使 a 中所有元素都相同？

输出 YES 或 NO。

01 #include <bits/stdc++.h>
02 using namespace std;
03 #define maxn 500005
04 int a[maxn];
05 map<int,int>q;
06 void check(int x)
07 {
08   for (int i = 2; i <= ①; i ++)
09   {
10     while(x % i == 0)
11     {
12       q[i] ++;
13       x /= i;
14     }
15   }
16   if(x > 1) ②;
17 }
18 void solve()
19 {
20   int n;
21   cin >> n;
22   ③;
23   for (int i = 1;i <= n;i ++)
24   {
25     scanf("%d",&a[i]);
26     ④;
27   }
28   for (auto i:q)
29   {
30     int k = i.second;
31     if(⑤)
32     {
33       cout << "NO"<<endl;
34       return;
35     }
36   }
37   cout << "YES"<<endl;
38   return;
39 }
40 int main()
41 {
42   int T = 1;
43   cin >> T;
44   while (T --)
45   {
46     solve();
47   }
48   return 0;
49 }

33. ①处应填（ ）。

{{ select(33) }}

• sqrt(x)

• pow(x, 2)

• pow(x, 3)

• log(x)

34. ②处应填（ ）。

{{ select(34) }}

• q[x]--

• q[x] /= 2

• q[x]++

• q[x] *= 2

35. ③处应填（ ）。

{{ select(35) }}

• q.clear()

• q. erase(q.begin())

• q.swap(a)

• q. erase(q.end())

36. ④处应填（ ）。

{{ select(36) }}

• check(q)

• check(a)

• check(a[i])

• check(a[i-1])

37. ⑤处应填（ ）。

{{ select(37) }}

• k / n == 0

• k / n != 0

• k % n == 0

• k % n != 0

(2) 题目描述：

输入 $( n (1 leq n leq 1 times 10^6))$ ，表示有 n 座激光塔。然后输入 n 行，每行有两个数 p[i] $(0 ≤ p[i] ≤ 1×10^6) 和 k[i] (1≤k[i]≤1×10^6)$，分别表示第 i 座激光塔的位置和威力。 保证所有激光塔的位置互不相同。

游戏规则：按照 p[i] 从大到小依次激活激光塔。当一座激光塔被激活时，它会摧毁它左侧所有满足 p[i]-p[j]≤k[i] 的激光塔 j。被摧毁的激光塔无法被激活。 在游戏开始前，你可以在最右边的激光塔的右侧，再添加一座激光塔，位置和威力由你决定。 你希望被摧毁的激光塔的数量尽量少。输出这个最小值。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N=1000000;
04 const int M=1000000;
05 const int inf=2147483647;
06 struct beacon
07 {
08   int pos;
09   int power;
10 };
11 int n,ans=inf,dp[M+5];
12 beacon beacons[M+5];
13 bool cmp(beacon a,beacon b)
14 {
15   return ①;
16 }
17 int main()
18 {
19   cin>>n;
20   for(int i=1;i<=n;++i)
21   {
22     cin>>beacons[i].pos>>beacons[i].power;
23   }
24   sort(beacons+1,beacons+n+1,cmp);
25   ②;
26   for(int i=2;i<=n;++i)
27   {
28     beacon find;
29     find.pos=max(0, ③);
30     int destroy=④-(beacons+1);
31     dp[i]=dp[destroy];
32     dp[i]+=(i-destroy-1);
33   }
34   for(int i=1;i<=n;++i)
35   {
36     int destruction=⑤;
37     if(destruction<ans) ans=destruction;
38   }
39   cout<<ans<<endl;
40   return 0;
41 }

38. ①处应填（ ）。

{{ select(38) }}

• a.power < b.power

• a.pos > b.pos

• a.pos < b.pos

• a.power > b.power

39. ②处应填（ ）。

{{ select(39) }}

• dp[1] = 0

• dp[1] = inf

• dp[1] = 1

• dp[1] = -inf

40. ③处应填（ ）。

{{ select(40) }}

• beacons[i].pos

• beacons[i].power

• beacons[i].pos + beacons[i].power

• beacons[i].pos - beacons[i].power

41. ④处应填（ ）。

{{ select(41) }}

• lower_bound(beacons+1,beacons+n,find,cmp)

• upper_bound(beacons+1,beacons+n+1,find,cmp)

• lower_bound(beacons+1,beacons+n+1,find,cmp)

• upper_bound(beacons+1,beacons+n,find,cmp)

42. ⑤处应填（ ）。

{{ select(42) }}

• n-dp[i]

• dp[i]-i

• dp[i]

• dp[i]+n-i