一、单项选择题（共 15 题，每题 2 分，共计 30 分）

1. 下列哪个不是操作系统？（ ）
   {{ select(1) }}

• Android
• Windows
• Linux
• QQ

2. 小K是一名摄影爱好者，他购买了一个容量为1TB的移动硬盘，用于存储图片。若每张图片的平均大小为5MB，则该硬盘大约可以存储多少张这样的图片？（ ）
   {{ select(2) }}

• $2 \times 10^4$
• $2 \times 10^5$
• $2 \times 10^6$
• $2 \times 10^7$

3. 以下关于进制转换的描述中，不正确的是？（ ）
   {{ select(3) }}

• 二进制数1111转换为十进制数是15
• 十进制数31转换为十六进制数是1F
• 十六进制数64转换为二进制数是10100110
• 八进制数22转换为十进制数是20

4. $(11)_2 + (11)_8$的结果是？（ ）
   {{ select(4) }}

• $(22)_{10}$
• $(111)_2$
• $(C)_{16}$
• $(22)_8$

5. 已知中级表达式：$(A + B) * C - D$，其中$A、B、C、D$为操作数。以下哪个后缀表达式是正确的？（ ）
   {{ select(5) }}

• A B + C * D -
• A B C + * D -
• A B + C D * -
• A B C * + D -

6. 在C++语言中，二维数组a[10][20]从内存地址1000开始存储，每个元素占4字节。假设按行优先顺序存储，请问a[5][10]的地址是多少？（ ）
   {{ select(6) }}

• 1424
• 1444
• 1420
• 1440

7. 序列1,2,3,4,5依次进入一个初始为空的栈中（1第一个进入栈），在每个元素入栈后，可以随时进行出栈操作（也可以是空操作）。以下哪个选项不可能是从栈中弹出的序列？（ ）
   {{ select(7) }}

• 1,2,3,4,5
• 5,4,3,2,1
• 2,1,5,4,3
• 3,1,2,4,5

8. 对下图进行深度优先遍历（DFS），从顶点1出发，不可能的访问顺序是（ ）

{{ select(8) }}

• 1,3,5,2,4
• 1,2,3,5,4
• 1,2,4,3,5
• 1,3,2,5,4

9. 用数字0、1、2、3、4、5组成没有重复数字的四位数，其中千位数字不能为0，而且不能出现“250”形式（如1250、2503）。这样的四位数共有多少个？（ ）
   {{ select(9) }}

• 240
• 294
• 300
• 288

10. 一个4×5的网格，从左上角A走到右下角B(只能沿着向右或向下的方向走)共有多少种方案？（ ）

{{ select(10) }}

• 10
• 15
• 20
• 35

11. 下列代码片段运行后输出结果为22，则输入的正整数k的最大值为（ ）。

int n=1,s=1,k;
cin>>k;
while(n<k){
    s=(s<<1)+n;
    n=n*(n+1);
}
cout<<s;

{{ select(11) }}

• 41
• 42
• 43
• 86

12. 如果根节点深度记为1，则一棵恰好有2025个度（儿子节点数量）为1的节点的二叉树深度最少可以是多少？（ ）
    {{ select(12) }}

• 11
• 12
• 13
• 14

13. 小H的作业有8道题目，小H做对了5道，而且恰好有3道是连续做对的，请问总共有多少种可能的情况？（ ）
    {{ select(13) }}

• 24
• 12
• 36
• 25

14. 以下C++递归函数的输出是什么？（ ）

#include<bits/stdc++.h>
using namespace std;
int f(int i) {
    if (i == 1) return 1;
    return i * f(i - 1);
}
int main() {
    cout << f(5);
    return 0;
}

{{ select(14) }}

• 1
• 5
• 24
• 120

15. 以下排序算法中，哪一种是非基于比较的排序算法？（ ）
    {{ select(15) }}

• 冒泡排序
• 选择排序
• 插入排序
• 计数排序

二、阅读程序（判断题答题纸正确填√，错误填×；判断题答题卡正确涂A，错误涂B；除了特殊说明外，判断题2分，单选题3分，共40分）

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 int gcd(int a, int b) {
04     if (b == 0) return a;
05     return gcd(b, a % b);
06 }
07 int main() {
08     int x, y;
09     scanf("%d%d",&x,&y);
10     printf("%d\n",gcd(x, y));
11     return 0;
12 }

判断题：

16. (1分)在递归函数gcd中，当b等于0时，函数返回a，递归结束。（ ） {{ select(16) }}

• 正确
• 错误

17. 在递归调用gcd(b,a % b)时，a % b的值小于b。（ ） {{ select(17) }}

• 正确
• 错误

18. 递归函数gcd(a,b)能够正确的求出任意两个整数的最大公约数。（ ） {{ select(18) }}

• 正确
• 错误

单选题：

19. 当输入为24和18时，程序的输出是（ ） {{ select(19) }}

• 6
• 12
• 18
• 24

20. 当输入为11和3时，递归函数gcd被调用的次数（包括第一次调用）是（ ） {{ select(20) }}

• 2
• 3
• 4
• 5

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N=2e5+5;
04 int n,m,ans;
05 int a[N];
06 int main() {
07     cin>>n>>m;
08     for(int i=1;i<=n;i++) cin>>a[i];
09     sort(a+1,a+n+1);
10     for(int i=n;i>=1;i--) {
11         if(a[i]>=0) ans++;
12         else{
13             if(m>=abs(a[i])){
14                 m-=abs(a[i]);
15                 ans++;
16             }else{
17                 break;
18             }
19         }
20     }
21     cout<<ans;
22     return 0;
23 }

保证输入的n不超过$10^5$，且$-10^6 \le a[i],m \le 1-^6$，完成下面的判断题和单选题

判断题：

21. (1分)将第一行#include<bits/stdc++.h>改成#include<iostream>不会影响程序正常运行。（ ） {{ select(21) }}

• 正确
• 错误

22. 变量ans记录的是a序列中非负数的个数。（ ） {{ select(22) }}

• 正确
• 错误

23. 如果a序列有小于0的元素，程序运行结束后m的值一定发生变化。（ ） {{ select(23) }}

• 正确
• 错误

单选题：

24. 该程序时间复杂度为（ ） {{ select(24) }}

• $O(n)$
• $O(nlogn)$
• $O(n^2)$
• 不确定

25. 对于以下输入数据，执行完程序后，a数组的值为（ ）

5 5
1 -3 -6 5 -2

{{ select(25) }}

• [1,-3,-6,5,-2]
• [-6,-3,-2,1,5]
• [-6,0,0,1,5]
• [5,1,-2,-3,-6]

26. 对于以下输入数据，输出结果为（ ）

8 100
-91 30 -20 233 -30 -50 -50 -20

{{ select(26) }}

• 4
• 5
• 6
• 8

(3)

01 #include<bits/stdc++.h>
02 using namespace std;
03 int n;
04 int f1(int n){
05     int res=0;
06     for(int i=2;i<=n;i+=2){
07         int j=i;
08         while(j%2==0){
09             res++;
10             j/=2;
11         }
12     }
13     return res;
14 }
15 int f2(int n){
16     int res=0;
17     while(n){
18         n/=5;
19         res+=n;
20     }
21     return res;
22 }
23 int main(){
24     cin>>n;
25     cout<<min(f1(n),f2(n));
26     return 0;
27 }

保证输入的n不超过$10^5$，完成下面的判断题和单选题

判断题：

27. 将第8行的j%2==0改为!(j & 1)程序功能不变。（ ） {{ select(27) }}

• 正确
• 错误

28. f2函数一定比f1函数运行速度快。（ ） {{ select(28) }}

• 正确
• 错误

29. 该程序能求出$n! (=1*2*3*...*n)$结果中零的个数。（ ） {{ select(29) }}

• 正确
• 错误

单选题：

30. 下面说法正确的是（ ） {{ select(30) }}

• f2(n)的值一定小于f1(n)的值
• 第25行如果改为输出f2(n)，程序结果不会发生改变
• f1函数的作用是求1到n中所有能被2整除的数的个数
• 如果输入n为负整数，程序会陷入死循环

31. 如果输入的n=20，则f1(n)的值为（ ） {{ select(31) }}

• 2
• 10
• 17
• 18

32. 对于以下输入数据，输出结果为（ ）

1000

{{ select(32) }}

• 200
• 248
• 249
• 252

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

(1) 最大平均分

小明按顺序做了 $n$ 道题目，第$i$道题目的得分 $a[i]$ 为一个 0 到 10000 之间的整数，将这 $n$ 道题的最低得分去掉，取剩下的题目的得分的平均分作为最终成绩。

小明想要最终成绩尽可能高，他可以去掉前 $k(1 \le k \le n-2)$道题目，只做并计算后面的 $n-k$ 道题目的最终成绩。小明想知道所有的可以使得他获得最高的最终成绩的 $k$的值，如果有多个$k$则从小到大输出。

数据范围满足 $1 \le n \le 10^5 ,0 \le a[i] \le 10^4$

提示：可以利用后缀和与后缀最小值模拟计算。

试补全程序

01 #include <iostream>
02 using namespace std;
03 const int N = 2e5+5;
04 int a[N],n,suf[N],minn[N];
05 int ans[N];
06 int main(){
07     ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
08     cin>>n;
09     for(int i=1;i<=n;i++) cin>>a[i];
10     minn[n+1]=1e9;
11     for(int i=n;i>=1;i--) {
12         ①;
13         ②;
14     }
15     double maxn=-1;
16     int cnt=0;
17     for(int i=1;i<=③;i++) {
18         double tmp=④;
19         if(tmp==maxn) {
20             ans[++cnt]=i;
21         }else if(tmp>maxn) {
22             maxn=tmp;
23             ⑤;
24             ans[cnt]=i;
25         }
26     }
27     for(int i=1; i<=cnt; i++) cout<<ans[i]<<"\n";
28     return 0;
29 }

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

• suf[i]=a[i]
• suf[i]=suf[i+1]+a[i]
• suf[i]=suf[i+1]-a[i]
• suf[i]=suf[i-1]+a[i]

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

• minn[i]=max(minn[i+1],a[i])
• minn[i]=min(minn[i+1],a[i])
• minn[i]=min(minn[i],a[i])
• minn[i]=max(minn[i],a[i])

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

• n-1
• n
• n+1
• n-2

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

• (suf[i]-minn[i+1])/(n-i)
• (suf[i+1]-minn[i+1])/(n-i-1)
• 1.0*(suf[i]-minn[i])/(n-i-1)
• 1.0*(suf[i+1]-minn[i+1])/(n-i-1)

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

• cnt=0
• cnt++
• cnt=1
• cnt--

(2) 背包问题

现有$n$件物品（编号为$1,2,...,n$），其中第$i$件物品的重量为$w[i]$，价值为$v[i]$。现在让你从中选择若干件物品装进你的背包。背包的容量为$sw$，要求你所选物品的总重量不能超过$sw$。请计算你的背包能装物品价值总和的最大值。

所有输入均为整数，数据范围限制：$1\le n \le 100；1\le sw \le 10^9 ；1 \le w[i] \le sw；1 \le v[i] \le 10^3$

试补全程序

01 #include<stdio.h>
02 #include<iostream>
03 #include<cstring>
04 using namespace std;
05 const int N=110;
06 ①;
07 int w[N],v[N];
08 int n,sw,sv=0;
09 int main(){
10     scanf("%d%d",&n,&sw);
11     for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]),sv+=v[i];
12     memset(f,0x3f,sizeof(f));
13     ②;
14     for(int i=1;i<=n;i++)
15         for(int j=0;③;j++)
16             f[i][j]=f[i-1][j];
17             if(j>=v[i]) f[i][j]=④;
18         }
19     int ans=0;
20     for(int i=sv;i>0;i--)
21         if(⑤){
22             ans=i;
23             break;
24         }
25     printf("%d\n",ans);
26     return 0;
27 }

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

• int f[N][1000000001]
• int f[N][N*1000]
• long long f[N][1000000001]
• long long f[N][N*1000]

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

• f[0][0]=0x3f3f3f3f
• f[0][0]=0x3f3f3f3f3f3f3f3f
• f[0][0]=0
• f[0][0]=1

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

• j<sv
• j<=sw
• j<sw
• j<=sw

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

• min(f[i][j],f[i-1][j-v[i]]+w[i])
• min(f[i][j],f[i-1][j-w[i]]+v[i])
• max(f[i][j],f[i-1][j-v[i]]+w[i])
• max(f[i][j],f[i-1][j-w[i]]+v[i])

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

• f[n][i]<sv
• f[n][i]<=sv
• f[n][i]<sw
• f[n][i]<=sw