该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

一、单项选择题(本题 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)

1   #include <iostream>
2   using namespace std;
3   const int N = 1e5+10;
4   int a[N];
5   int main() {
6       int n, cnt = 1, max_cnt = 0;
7       cin >> n;
8       for (int i = 1; i <= n; i ++) {
9           cin >> a[i];
10      }
11
12      for (int i = 2; i <= n; i ++) {
13          if (a[i] == a[i - 1] + 1) {
14              cnt ++;
15              max_cnt = max(cnt, max_cnt);
16          } else {
17              cnt = 1;
18          }
19      }
20      cout << max_cnt;
21      return 0;
22  }

假设输入的n是不超过$10^5$的正整数，且输入的$a_i$满足，$1 < a_i \le 10^9$，完成下面的判断题和选择题:

判断题

22. 将程序的第12行中for循环的int i = 2改为int i = 1，从$1$开始循环，最终的输出结果有可能发生改变。( ) {{ select(22) }}

• 正确
• 错误

23. 去掉第12行和第19行的大括号后不影响程序正确性( ) {{ select(23) }}

• 正确
• 错误

24. 将第6行的mac_cnt的初始值改为1，不影响程序正确性( ) {{ select(24) }}

• 正确
• 错误

选择题

25. 给定输入数据

9
1 9 2 5 6 7 3 4 5

程序中，在循环内部的第17行，cnt将重置为数值1。请问对于上面的输入数据，cnt在在第17行将重置多少次？( )。{{ select(25) }}

• 3
• 4
• 5
• 6

26. 给定输入数据

9
7 8 3 5 6 7 2 3 3

程序输出：( )。{{ select(26) }}

• 3
• 4
• 5
• 6

(3)

1	#include<iostream>
2	#include<cstring>
3	using namespace std;
4	const int t=1e6+10;
5	int a[t],b[t],stack[t],len=0;
6	bool empty() {
7		bool q = len;
8		return !q;
9	}
10	int top() {
11		return stack[len-1];
12	}
13	void push(int num) {
14		stack[len]=num;
15		len++;
16		return ;
17	}
18	void pop() {
19		len--;
20		stack[len]=0;
21		return ;
22	}
23	void show() {
24		for(int i=0; i<len; i++) {
25			cout<<stack[i]<<"";
26		}
27		return ;
28	}
29	int main() {
30		int t;
31		cin>>t;
32		while(t--) {
33			int n;
34			cin>>n;
35			for(int i=0; i<n; i++) cin>>a[i];
36			for(int i=0; i<n; i++) cin>>b[i];
37			int i=0,j=0;
38			while(i<n&&j<n) {
39				push(a[i]);
40				i++;
41				while(top()==b[j]) {
42					j++;
43					pop();
44					if(empty()) break;
45				}
46			}
47			if(empty()) cout<<"Yes\n";
48			else cout<<"No\n";
49			memset(a,0,sizeof(a));
50			memset(b,0,sizeof(b));
51			memset(stack,0,sizeof(stack));
52			len=0;
53		}
54		return 0;
55	}

假设输入的数据$n、a_i$都是不超过$100000$的正整数，$t<=100$,完成下面的判断题和单选题：

判断题

27. 将empty函数的返回值修改为int，程序的输出结果可能会改变。( ){{ select(27) }}

• 正确
• 错误

28. 将第$51$行的代码memset(stack,0,sizeof(stack));更换为for(int i=0;i<n;i++) stack[i]=0;，程序的输出结果不会被改变。（ ）{{ select(28) }}

• 正确
• 错误

29. 该程序中，变量len的值不可能为负数。( ){{ select(29) }}

• 正确
• 错误

30. 把第2行中引用的头文件<cstring>替换成<string.h>，程序可以正常运行，在输入数据相同的情况下，输出结果不变。（ ）{{ select(30) }}

• 正确
• 错误

选择题

31. 若将第$47$行的if(empty())替换为 ( )，则程序的输出结果不变。{{ select(31) }}

• if(len)

• if(i == n)

• if(len == n)

• if(j == n)

32. 输入如下数据的时候，程序会输出。( )

2
3
1 2 3
3 1 2
5
1 5 4 2 3
5 1 2 4 3

{{ select(32) }}

• Yes
  No
  

• Yes
  Yes
  

• No
  Yes
  

• No
  No
  

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

(1)(质数中的质数)问题：如果一个质数，在质数列表中的编号也是质数，那么就称之为质数中的质数。共询问$t$次，每次输入一个正整数 $n$ ，请输出大于等于$n$ 的最小的质数中的质数是多少。($n \le 10^{6},t\le 10^6$)。试补全程序。

#include<iostream>
#include<cstring>
using namespace std;
#define T 10000010
const int len=T/2;
int a[T],b[len],index=1; 
void screening(int n){
	int index=1;
	____①____;
	for(int i=0;i*i<=n;i++){ 
		if(a[i]==0){
			for(____②____){ 
				a[j]=1;
			}
		}
	}
}
void creatlist(){
	int cnt=0;
	for(int i=2;i<=T;i++){
		if(____③____){  
			cnt++;
			if(a[cnt]==0) b[index++]=i;	  
		} 
	}
}
int main(){
	int t,n;
	screening(T);
	creatlist();
	cin>>t;
	while(t--){
		cin>>n; 
		for(____④_____){ 
			if(___⑤____){ 
				cout<<b[i]<<"\n";
				break;
			}
		}
	}	
	return 0;
}

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

• a[1],a[0]=0
• a[1],a[0]=1
• a[1]=a[0]=0
• a[1]=a[0]=1

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

• int j=2*i;j<=n;i++
• int j=i;j<=n;j++
• int j=i*i;j<=n;j+=i
• int j=i*i;j*j<=n;j+=i

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

• a[i]==0
• cnt==0
• a[i]!=0
• cnt!=0

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

• int i=2;i*i<=n;i++
• int i=1;i<index;i++
• int i=2;i<=index;i++
• int i=1;i*i<=n;i++

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

• b[i]==n
• b[i]>=n
• b[i]<n
• b[i]!=n

(2) (选择卡牌) 问题: 给定 $n$ 张卡牌，每张卡牌$i$都有自己的强度$a_i$和价格$c_i$，对于两张卡牌 $i, j$，
如果$i$的强度更高 $a_i > a_j$ 且价格更低 $c_i < c_j$，那么卡牌 $j$ 将会被丢弃。一直重复以上操作，问最后剩下的牌是哪些，先输出剩余卡牌的数量，然后输出剩余卡牌的序号。
($2\ \leq\ N\ \leq\ 2\ \times\ 10^5$,$1\ \leq\ A_i,\ C_i\ \leq\ 10^9$)。试补全程序。

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

struct node {
    int a,c,id;
    friend bool operator < (node a,node b){
        if(a.a==b.a)____①______;
        return a.a<b.a;
    }
}p[200000+10];
bool vis[200000+10];
stack<__②__> st;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
        cin>>p[i].a>>p[i].c;
        p[i].id=i;
	}
	___③_____;
	for(int i=1;i<=n;i++){
        while(!st.empty()&&___④_____){
            vis[____⑤____]=1;
            st.pop();
        }
        st.push(p[i]);
	}
	cout<<st.size()<<endl;
	for(int i=1;i<=n;i++){
        if(!vis[i])cout<<i<<' ';
	}
	return 0;
}

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

• return a.c<b.c
• return a.c>b.c
• return a.id<b.id
• return a.id>b.id

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

• node
• int
• p
• bool

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

• sort(a);
• sort(a+1,a+1+n,cmp);
• sort(a,a+n);
• sort(a+1,a+1+n);

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

• st.top().c>p[i].c
• st.top().c<p[i].c
• st.top().c>=p[i].c
• st.top().c<=p[i].c

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

• st.top().a
• p[i].id
• st.top().id
• i