一、单项选择题(本题 15 小题，每小题 2 分，共 30 分)

1. 工人 A 和工人 B 在制造厂工作。工人 A 每小时可以制造 8 个鼠标或 3 个键 盘，而工人 B 每小时可以制造 5 个鼠标或 5 个键盘。在一个工作日 8 小时内，A 和 B 通过合理调配，最多可以制造出( )个键鼠套装。{{ select(1) }}

• 43
• 48
• 40
• 46

2. 一个盒子里有一定数量的糖果。小雷和小星轮流拿糖果，每次可以拿 1 个、2 个，或者 3 个，拿走最后一个糖果的人获胜。如果小雷先拿，那么在糖果总数为( )个时小星将最终获胜。{{ select(2) }}

• 1052
• 105
• 677
• 大于 3 的偶数时

3. 下列不属于计算机人工智能应用领域的是( )。{{ select(3) }}

• 在线订餐
• 自动驾驶
• 机器翻译
• 手机制造

4. 下列叙述中不正确的是( )。{{ select(4) }}

• 所谓算法就是计算方法
• 程序是算法的一种实现方式
• 算法有可能是不会终止的程序
• 算法设计需要考虑算法的执行时间

5. 在网站链接https://oj.qdturing.com 中，.com被称作( ) {{ select(5) }}

• 传输语言
• 顶级域名
• 编码格式
• 传输协议

6. 一个篮子中有 45 个苹果、40个橙子和 42 个梨子。一个人每次从篮子中随机 抽取一个水果，至少经过( )次后，篮子中某种水果的数量才可能不足10个。{{ select(6) }}

• 31
• 28
• 25
• 35

7. 两位同学讨论关于太阳能的问题。小安认为太阳能是不实用的，因为天气常常阴雨绵绵，经常无法获得太阳能。小星认为太阳能是实用的，因为太阳能是一种清洁的能源。{{ select(7) }}

• 小安提出的观点;小星提出的事实
• 小安和小星提出的都是事实
• 小安提出的都是事实;小星提出的是观点
• 小安和小星提出的都是观点

8. 下列编程语言中属于解释性语言的是( )。{{ select(8) }}

• C++
• Pascal
• Python
• C

9. 与十进制数 63.75 相对应的 16 进制数是( )。{{ select(9) }}

• 3F.C
• 3E.A
• 40.2
• 3C.F

10. 以下哪个选项不是结构化程序设计方法的特点( )?{{ select(10) }}

• 模块化
• 面向对象
• 顺序性
• 自顶向下

11. 设循环队列中，数组的下标范围为 0~m - 1，头尾指针分别为 f 和 r。若当前队列中有 n 个元素，则下列等式中成立的是( )。{{ select(11) }}

• r-f=n
• r-f+1=n
• (r-f+1)%m=n
• (r-f+m)%m=n

12. 设栈 S 的初始状态为空，元素 a,b,c,d,e,f 依次入栈 S，出栈的序列为 b,d,c,f,e,a，则栈 S 的容量至少应该是( )。 {{ select(12) }}

• 3
• 4
• 5
• 6

13. 如果根结点的深度记为 1，则一棵恰有 2023 个叶子结点的二叉树的深度可能是( )。{{ select(13) }}

• 9
• 10
• 11
• 12

14. 前缀表达式+4×2+5(空格)12 的值是( )。 {{ select(14) }}

• 24
• 26
• 38
• 13

15. 有 75 个人围成一圈，从第一个人开始报数，每次数到第 4 个人出列。最后一个出列的人在初始队列中的编号是( )。{{ select(15) }}

• 17
• 26
• 52
• 73

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

(1)

01  #include <bits/stdc++.h>
02  using namespace std;
03  typedef long long ll;
04  int main() {
05      int m, n;
06      cin >> m >> n;
07      vector<int> a(m);
08      for (int i = 0; i < m; ++i) cin >> a[i];
09      sort(a.begin(), a.end());
10      double ans = 1e18;
11      for (int i = 0; i + n <= m; ++i) {
12          double sum = 0;
13          for (int j = i; j < i + n; ++j) sum += a[j]; 
14          double D = 0;
15          for (int j = i; j < i + n; ++j)
16              D += (a[j] - sum / n) * (a[j] - sum / n); 
17          ans = min(ans, D);
18      }
19      cout << ll(floor(ans)) << endl; 
20      return 0;
21  }

假设输入的 m、n、a[i]均是不超过 10000 的自然数，完成下面的判断题:

判断题

16. 将第7行替换成int a[m];，程序行为不变。( ) {{ select(16) }}

• 正确
• 错误

17. 由于 m、n、a[i]的数值都不大，且都为整数，所以将 12 行的 double 改成ll，程序行为不变。( ) {{ select(17) }}

• 正确
• 错误

18. 程序总是输出一个整数。( ) {{ select(18) }}

• 正确
• 错误

19. 当输入为“5 3”和“1 2 3 4 5”时，输出为“2”。( ) {{ select(19) }}

• 正确
• 错误

20. 该算法最准确的时间复杂度分析结果为 O(mlogm+mn)。 {{ select(20) }}

• 正确
• 错误

选择题

21. 当输入为“10 3”和“14 1 10 11 22 16 3 23 8 17”时，输出为( )。{{ select(21) }}

• “4”
• “36”
• “125”
• “90”

(2)

01  #include<bits/stdc++.h> 
02  using namespace std; 
03  #define int long long 
04  const int N=1005;
05  const int mod=1e9+7; 
06  int T,n,f[N],sum[N]; 
07  signed main(){
08      for(int i=1;i<N;i++){ 
09          while(++f[i]) if(i%f[i]) break; 
10          sum[i]=(sum[i-1]+f[i])%mod;
11      }
12      scanf("%lld",&T); 
13      while(T--){
14          scanf("%lld",&n);
15          printf("%lld\n",sum[n]); 
16      }
17      return 0;
18  }

假设输入的 T 是不超过 1000 的自然数，完成下面的判断题和选择题:

判断题

22. 第7行的signed替换成unsigned，对程序没什么影响。( ) {{ select(22) }}

• 正确
• 错误

23. 当输入的 n 为“10”时，f[10] = 3。( ) {{ select(23) }}

• 正确
• 错误

24. n越大，f[n]和sum[n]的值越接近。( ) {{ select(24) }}

• 正确
• 错误

25. 第9行的“%”替换成“/”，可以加快程序的执行效率。( ){{ select(25) }}

• 正确
• 错误

单选题

26. 当输入为“1 10”时，输出为( )。{{ select(26) }}

• “21”
• “36”
• “26”
• “42”

27. 当输入为“2 15 30”时，输出分别为( )。{{ select(27) }}

• “41”和“82”
• “40”和“82”
• “52”和“102”
• “56”和“100”

(3)

01  #include <bits/stdc++.h>
02  using namespace std; 
03  const int N = 50010;
04  int n, m;
05  vector<int> e[N]; 
06  int main()
07  {
08      cin >> n >> m;
09      for (int i = 1; i <= m; ++i) {
10          int op, a, b;
11          cin >> op >> a >> b; 
12          if (op == 1) {
13              e[a].push_back(b);
14              e[b].push_back(a); 
15          }
16          else {
17              int ok = 0;
18              queue<int> q; 
19              q.push(a);
20              vector<int> vis(n + 1, 0); 
21              while (!q.empty()) {
22                  int u = q.front(); 
23                  q.pop();
24                  if (u == b) {
25                      ok = 1;
26                      break; 
27                  }
28                  for (auto v : e[u]) { 
29                      if (!vis[v])
30                          vis[v] = 1, q.push(v); 
31                  }
32              }
33              cout << (ok ? "Yes" : "No") << endl; 
34          }
35      }
36      return 0; 
37  }

假设输入的 n,m 是不超过 20000 的自然数，完成下面的判断题和选择题:

判断题

28. 从第13、14行可以看出，建成的图为无向图。( ) {{ select(28) }}

• 正确
• 错误

29. 程序中建图的方式称为“链式前向星”。( ) {{ select(29) }}

• 正确
• 错误

30. 程序中混合使用了DFS和BFS搜索方式。( ) {{ select(30) }}

• 正确
• 错误

31. 本程序的输出是表明a,b两点之间是否有边直接相连。( ) {{ select(31) }}

• 正确
• 错误

32. 本程序如果不使用 vis[]，会大大增加运行时间，但不会出错。( ) {{ select(32) }}

• 正确
• 错误

单选题

33. 该算法最准确的时间复杂度分析结果为( )。 {{ select(33) }}

• O(mn)
• O(n(n+m))
• O(m(n+m))
• O(m*m)

34. 当建成的图为一棵树时，输出结果( )。 {{ select(34) }}

• 只可能是Yes
• 只可能是No
• Yes和No都有可能
• 不确定

当输入为

3 6
1 1 2
2 2 3
1 2 1
2 1 3
1 3 1
2 3 1

，输出是( )。

A.

No
Yes
No

B.

Yes
No
No

C.

No
No
Yes

D.

Yes
Yes
No

{{ select(35) }}

• A
• B
• C
• D

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

(1)(枚举正方形) 给定 n 个二维平面点，选择一个与坐标轴平行的边长为 L 的正方形，使得内部点的数量最大。

试补全枚举程序。

01  #include <cstdio> 
02  #include <algorithm> 
03  using namespace std; 
04  const int N = 100 + 5; 
05  const int inf = 0x3f3f3f3f; 
06  struct node{
07      int x;
08      int y; 
09  } e[N];
10  int main(){
11      int n, L, ans = 0;
12      scanf("%d%d", &n, &L);
13      int a = inf, b = inf, c = -inf, d = -inf; 
14      for (int i = 1; i <= n; i++){
15          scanf("%d%d", &e[i].x, &e[i].y);
16          ①
17          ②
18      }
19      for (int i = a; i <= ③; i++)
20          for (int j = b; j <= ④; j++){ 
21              int nowAns = 0;
22              for (int k = 1; k <= n; k++)
23                  if (⑤) 
24                      nowAns++;
25              ans = max(ans, nowAns); 
26          }
27      printf("%d\n", ans);
28      return 0; 
29  }

36. ① 处应填( ) {{ select(36) }}

• a=max(a,e[i].x), b=max(b,e[i].y);
• a=max(c,e[i].x), b=max(d,e[i].y);
• c=min(c,e[i].x), d=min(d,e[i].y);
• c=max(c,e[i].x), d=max(d,e[i].y);

37. ② 处应填( ) {{ select(37) }}

• a=max(a,e[i].x), b=max(b,e[i].y);
• a=min(a,e[i].x), b=min(b,e[i].y);
• c=max(c,e[i].x), d=min(d,e[i].y);
• c=min(c,e[i].x), d=min(d,e[i].y);

38. ③ 处应填( ) {{ select(38) }}

• a+L
• c
• d
• b+L

39. ④ 处应填( ) {{ select(39) }}

• b+L
• c
• d
• a+L

40. ⑤ 处应填( ) {{ select(40) }}

• e[k].x>=i && e[k].x<=i+L && e[k].y>=j && e[k].y<=j+L
• e[k].x>=i && e[k].x<=j+L && e[k].y>=j && e[k].y<=i+L
• e[k].x>=i && e[k].x<=L && e[k].y>=j && e[k].y<=L
• e[k].x>=i && e[k].x<=j && e[k].y>=j && e[k].y<=i

(2)(区间重叠) 给定 n 个左闭右开的区间，求最多有多少个区间互相重叠。

试补全程序。

01  #include <bits/stdc++.h> 
02  using namespace std; 
03  int main()
04  {
05      int n;
06      cin >> n;
07      vector<int> s(n), t(n), id(n); 
08      for (int i = 0; i < n; ++i)
09          cin >> s[i] >> t[i];
10      for (int i = 0; i < n; ++i) id[i] = i;
11      sort(id.begin(), id.end(), [&](int x, int y) { return s[x] < s[y]; });//使用匿名函数(lambda 表达式)简化代码
12      int k = 0;
13      vector<int> f(n, -1);
14      for (int i = 0; i < n; ++i) {
15          int ok = 0;
16          for (int j = 0; j < ①; ++j) {
17              if (f[j] <= ②) { 
18                  ok = 1;
19                  f[j] = ③;
20                  break; 
21              }    
22          }
23          if (!ok) { 
24              f[k] = ④;
25              ⑤;
26          }
27      }
28      cout << k << endl; 
29      return 0;
30  }

41. ① 处应填( ) {{ select(41) }}

• n
• i
• id[i]
• k

42. ② 处应填( ) {{ select(42) }}

• s[id[i]]
• f[i]
• t[id[i]]
• f[k]

43. ③ 处应填( ) {{ select(43) }}

• f[k]
• f[i]
• t[id[i]]
• s[id[i]]

44. ④ 处应填( ) {{ select(44) }}

• k
• s[id[i]]
• t[id[i]]
• id[i]

45. ⑤ 处应填( ) {{ select(45) }}

• f[k]++
• k++
• f[j]++
• id[i]++