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

1. 以下可以用作c++程序变量名的是（） {{ select(1) }}

• hello
• bool
• 001
• static

2. 一个unsigned long long类型的变量占用的字节数是（）
   {{ select(2) }}

• 32
• 64
• 4
• 8

3. 给定一个字符串，计算把它修改为回文字符串的最小修改次数，下列位置正确的是（）

int f(string &s) {
    int n = s.size(), cnt = 0;
    for(int i = 0;i < n / 2; ++i) {
        if(____1____) 
            ____2____;
    }
    return cnt;
}

{{ select(3) }}

• 1处填入s[i] == s[n - i - 1]，2处填入cnt += 1
• 1处填入s[i] == s[n - i - 1]，2处填入cnt += 2
• 1处填入s[i] != s[n - i - 1]，2处填入cnt += 1
• 1处填入s[i] != s[n - i - 1]，2处填入cnt += 2

4. 下列选项中，不是线性数据结构的一项是（） {{ select(4) }}

• 链表
• 二叉树
• 栈
• 队列

5. 计算机的中央处理器cpu的组成部件是（） {{ select(5) }}

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

6. 已知小写字母a的ASCII码是97，则小写字母x的ASCII码是（） {{ select(6) }}

• 119
• 120
• 121
• 122

7. 现在有10枚除了颜色外完全相同小球被放进盒子里。其中5枚小球被涂成蓝色，3枚小球被涂成绿色，2枚小球被涂成紫色。从中任意拿取两枚小球，小球颜色不同的概率是（）
   {{ select(7) }}

• 29/90
• 17/30
• 31/45
• 11/15

8. 关于二分算法，下列说法中错误的是（） {{ select(8) }}

• 二分算法可以用于二分查找、二分答案等应用
• n个数的随机序列，先排序，再进行二分查找，总时间复杂度为O(log(n))
• 二分算法的左右区间可以左闭右闭，也可以左闭右开
• 二分算法是典型的使用分治思想的算法

9. 已知一个序列的前缀和数组为{10, 15, 14, 18, 20}，下列说法正确的是（）
   {{ select(9) }}

• 原序列中的元素均为正整数
• 原序列是一个升序的序列
• 原序列中没有数字小于5
• 原序列中的所有数字都不相同

10. 已知int a[5] = {1, 2, 3, 4, 5};，下列访问数组元素错误的是（） {{ select(10) }}

• a[0]
• a[5]
• *(a+2)
• *(a+4)

11. 在下面各个世界顶级奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是（）
    {{ select(11) }}

• 沃尔夫奖
• 诺贝尔奖
• 菲尔茨奖
• 图灵奖

12. 对于一个有10个节点的有向连通图，若每个点的入度不小于1且不大于2，该图中节点连通，且没有重边和自环，则每个点的出度最多为（） {{ select(12) }}

• 1
• 2
• 9
• 10

13. 已知递归函数定义为：

int f(int x) {
    if(x <= 1) return 1;
    else return 2 * f(x-1) + f(x-2);
}

则f(6)的返回值为（）
{{ select(13) }}

• 40
• 41
• 99
• 239

14. 已知一个8位二进制数的原码为 1111 1001，则这个数字对应的补码是（）
    {{ select(14) }}

• 1000 0111
• 1000 0001
• 1111 0110
• 0000 0110

15. 在互联网中，每台连网的设备都必须由唯一的IP地址，下列格式正确的IP地址是（） {{ select(15) }}

• 8.8.8.8
• 200.1.258.4
• 232,100,2,88
• 223.112.8:8

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

（一）阅读下列程序，回答问题。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

int func(int x, int y) {
    if(!x || !y) return 0;
    if(x > y) {
        return func(x- 1, y) + 1;
    } else {
        return func(x, y- 2) + 1;
    }
}

int main() {
    int a, b; cin >> a >> b;
    cout << func(a, b);
    return 0;
}

其中保证输入的两个数都是int范围内的整数。

判断题

16. 当输入a = 5, b = 6时，程序输出的结果为5。（） {{ select(16) }}

• 正确
• 错误

17. 当输入a, b 中存在负数时，存在可能的情形，使得程序可以正常运行（） {{ select(17) }}

• 正确
• 错误

18. 当a和b至少有一者为零时，存在可能的情形，使得程序输出不为零。（） {{ select(18) }}

• 正确
• 错误

选择题

19. （4分）当y = 1时，x取何值可以使得程序打印100。（） {{ select(19) }}

• 99
• 100
• 101
• 102

（二）阅读下列程序，回答问题。

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

vector<int> f(int n) {
    if (n < 2) return {};
    vector<bool> ok(n + 1, true);  // 注释1
    vector<int> ask;  
    vector<int> test(n + 1, 0);               
    ok[0] = ok[1] = false;    
    for (int i = 2; i <= n; ++i) {
        if (ok[i]) {
            ask.push_back(i);
        }
        for (int p : ask) {
            if (i * p > n) break;       
            ok[i * p] = false; 
            test[i * p]++;
            if (i % p == 0) break;      
        }
    }
    for(int p : test) if(p > 1) cout << "wow\n"; 
    return ask;
}

int main() {
    int n; cin >> n;
    vector<int> a = f(n);
    for (int p : a) cout << p << " ";
    return 0;
}

该代码接收一个不大于$10^6$的正整数。据此回答问题。

判断题

20. （3分）这份代码的复杂度为$O(nlog(n))$。 {{ select(20) }}

• 正确
• 错误

21. （3分）不存在任何合法的输入，使得该代码首先输出wow。 {{ select(21) }}

• 正确
• 错误

22. 注释1所在语句若改为 vector<bool> ok(n + 1);，其效果并无实际区别。 {{ select(22) }}

• 正确
• 错误

23. 该代码输出的数字部分至多只有一个数字是偶数。 {{ select(23) }}

• 正确
• 错误

选择题

24. （4分）对于输入100，最后一个输出的整数是（） {{ select(24) }}

• 99
• 97
• 95
• 93

（三）阅读下列程序，回答问题。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
int n, num[N], temp[N];

ll f(int x, int y) {
    if(x >= y) return 0; 
    int mid = (x + y) / 2;
    ll result = 0;
    result += f(x, mid); 
    result += f(mid + 1, y);
    int cnt = 0;
    int l = x, r = mid + 1;
    while(l <= mid || r <= y) { 
        if(r > y || (l <= mid && num[l] <= num[r])) { 
            temp[++cnt] = num[l]; 
            l++;
            result += (r - (mid + 1));
        } else { 
            temp[++cnt] = num[r]; 
            r++;
        }
    }
    for(int i = 1;i <= cnt; ++i) 
        num[x + i- 1] = temp[i];
    return result;
}

int main() {
    cin >> n;
    for(int i = 1;i <= n; ++i)
        cin >> num[i];
    cout << f(1, n);
    return 0;
}

程序接收第一行一个正整数n，接下来一行n个正整数$1 \le num_i \le 10^5$。

判断题

25. 若给出下列输入，程序运行的结果为1。（）

2
2 1

{{ select(25) }}

• 正确
• 错误

26. （3分）在给定数据范围下，程序不可能输出0。（） {{ select(26) }}

• 正确
• 错误

27. （3分）程序的复杂度是$O(nlog^2(n))$。（） {{ select(27) }}

• 正确
• 错误

选择题

28. （4分）对于n = 2时，一共可以构造（）种不同的合法输入，使得程序运行的结果为1。
    {{ select(28) }}

• 4999950000
• 4999999999
• 5000000000
• 5000050000

29. （4分）下列输入的正确结果是（）

8
2 2 3 3 1 1 4 4

{{ select(29) }}

• 4
• 6
• 8
• 12

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

（一）完善程序第一题

给定一个长度为$n$的序列$a_1 \sim a_n$，要求找到一个区间$[x, y]$，使得$y- x + 1 \ge m$，并使得$ans = \frac{\sum_{i=x}^y(a_i)}{y- x + 1}$尽量大。四舍五入保留2位小数给出$ans$。其中$1 \le n, m \le 10^5, 0 \le |a_i| \le 10^3$。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
double a[N], b[N];
int n, m;

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    double left =-1e9, right = 1e9;
    while(____1____ >= 0.001) { 
        double ret = 1e9;
        bool ok = 0;
        double mid = ____2____; 
        for(int i = 1;i <= n; ++i) {
            ____3____; 
            ____4____; 
            if(b[i] > ret) ok = 1;
        }
        if(ok) ____5____; 
        else right = mid;
    }
    cout << fixed << setprecision(2) << right << endl;
    return 0;
}

30. 1 处应填入（） {{ select(30) }}

• right- left
• left- right
• left + right
• (left + right) / 2

31. 2 处应填入（） {{ select(31) }}

• left + right / 2
• (left + right) * 0.5
• left * 0.5 + right
• right- (right- left) / 3

32. 3 处应填入（） {{ select(32) }}

• b[i] = b[i] + a[i]- mid
• b[i] = b[i-1] + (a[i] / mid)
• b[i] = a[i]- mid[i]
• b[i] = b[i-1] + a[i]- mid

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

• if(i >= m) ret = min(ret, b[i-m])
• if(i >= m) ret = max(ret, b[i])
• if(i >= m) ret = min(ret, b[i])
• if(i >= m) ret = max(ret, b[i-m])

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

• right = mid
• left = mid + 0.001
• left = mid
• right = mid- 0.001

（二）完善程序第二题 现在有两个字符串A和B，你可以对这两个串做下列三种操作之一：

• 删除一个字符；
• 插入一个字符；
• 将一个字符改为另一个字符。 A,B 均只包含小写字母。现在要求你让A和B变得相同。求最少的操作次数。两个字符串长度均小于1000.

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int dp[N][N], n, m;
string A, B;

int main() {
    cin >> A >> B;
    n = A.size(), m = B.size();
    A = '#' + A; B = '#' + B;

    for(int i = 1;i <= m; ++i)
        dp[0][i] = i;
    for(int i = 1;i <= n; ++i)
        ____1____; // 填空1

    for(int i = 1;i <= n; ++i) {
        for(int j = 1;j <= m; ++j) {
            if(A[i] == B[j]) 
                dp[i][j] = ____2____; // 填空2
            else {
                int p;
                p = ____3____; // 填空3
                p = min(p, dp[i- 1][j- 1]); 
                ____4____; // 填空4
            }
        }
    }
    cout << ____5____; // 填空5
    return 0;
}

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

• dp[0][i] = i
• dp[i][0] = dp [i-1][0]
• dp[i][0] = 0
• dp[i][0] = i

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

• dp[i- 1][j- 1]
• dp[i- 1][j] + 1
• dp[i][j- 1] + 1
• min (dp[i- 1][j], dp[i][j- 1])

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

• dp[i- 1][j] + dp[i][j- 1]
• min(dp[i][j- 1], dp[i- 1][j])
• max(dp[i][j- 1], dp[i- 1][j])
• dp[i- 1][j]

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

• dp[i][j] = p + 1
• dp[i][j] = p
• dp[i][j] = min(p, dp[i- 1][j- 1])
• dp[i][j] = p + 2

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

• dp[0][0]
• dp[n][m]
• dp[m][n]
• min(dp[n][m], dp[m][n])