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

1. 下列编程语言中，不属于解释型语言的是（）{{ select(1) }}

• Javascript
• C++
• Lua
• Python

2. 编译器的主要功能是（）{{ select(2) }}

• 在计算机和外围设备之间进行输入和输出
• 控制和管理计算机硬件与软件资源
• 解释计算机指令以及处理计算机软件中的数据
• 将源语言翻译成目标语言

3. 设 x,y 是布尔变量，下列各组逻辑表达式中，总等价的是（）{{ select(3) }}

• $x\wedge y$ 和 $x\vee y$
• $x\wedge y$ 和 $\neg((\neg x)\vee (\neg y))$
• $x\wedge(\neg y)$ 和 $x\vee y$
• $x\wedge(\neg y)$ 和 $(\neg x)\vee y$

4. 现有一段时长为 $10\,\mathrm{s}$ 的动画，动画每秒有 $20$ 帧画面，每帧均为分辨率为 $64 \times 64$ 像素的 16 色位图。若不对图像进行压缩，则要存储这段动画至少需要多少存储空间？（）{{ select(4) }}

• $20\,\mathrm{KB}$
• $40\,\mathrm{KB}$
• $400\,\mathrm{KB}$
• $800\,\mathrm{KB}$

5. 以交换两个相邻元素作为基本操作，将 $n$ 个元素的顺序反转，至少需要的交换次数为（）{{ select(5) }}

• $n-1$
• $n-2$
• $n(n - 1) / 2$
• $n(n + 1) / 2$

6. 设 $A$ 是 $n$ 个整数的数组，考虑下面的算法：

   Foo(A[1..n]):
     1. X ← 1, Y ← A[1]
     2. for i = 2 to n do
     3.   X ← X + 1
     4.   Y ← Y + A[i]
     5. return Y / X
   

   则算法 Foo 的输出是（）{{ select(6) }}

• $A$ 数组的平均值
• $A$ 数组的最大值
• $A$ 数组的中位数
• $A$ 数组的极差

7. 把 $6$ 个相同的球放进 $4$ 个不同的盒子里，允许有的盒子空着不放，则一共有（）种不同的方案{{ select(7) }}

• $C_{9}^{3}$
• $C_{9}^{4}$
• $C_{6}^{3}$
• $C_{10}^{4}$

8. $2024$ 个结点的完全二叉树有（）个叶子结点{{ select(8) }}

• $1010$
• $1008$
• $1012$
• $1014$

9. 表达式 a+(b+c)*(d+e) 的后缀表达式为（），其中 + 和 * 是运算符{{ select(9) }}

• a + b + c * d + e
• + a * + b c + d e
• a b c + d e + * +
• + + * + a b c d e

10. 假设采用 $n$ 位二进制反码来表示数，能表示（）个不同的数{{ select(10) }}

• $2^n-1$
• $2^n$
• $2^{n-1}-1$
• $2^{n-1}$

11. $5$ 个小朋友站成一排，要求甲不站在第一个，且乙和丙的位置不相邻，则一共有（）种站法{{ select(11) }}

• $36$
• $48$
• $60$
• $72$

12. 下列排序算法中，不稳定的排序（即，排序完成后，权值相同的对象的先后顺序有可能颠倒）是（）{{ select(12) }}

• 插入排序
• 快速排序
• 冒泡排序
• 归并排序

13. 以 a 为起点，对下面的无向图进行广度优先遍历，得到的遍历序列不可能是（）{{ select(13) }}

• a b c d f e
• a c f d e b
• a b d c e f
• a c d b f e

14. 由 $3$ 个 a、$3$ 个 b、$1$ 个 c 构成的所有字符串中，包含子串 abc 的有（）个{{ select(14) }}

• $36$
• $48$
• $30$
• $72$

15. 下列链表中，其逻辑结构属于非线性结构的是（）{{ select(15) }}

• 二叉链表
• 循环链表
• 双向链表
• 带链的栈

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

(1)

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

char str[1001];
char res[1001];

int main() {
    cin >> str + 1;
    int n = strlen(str + 1);
    int p = 0;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || str[i] != str[i - 1]) {
            res[p] = str[i], p = p + 1;
            res[p] += 'a' - 'A';
        }
    }
    cout << res;
    return 0;
}

16. 程序执行完成后，p 总是大于 n。（）{{ select(16) }}

• 对
• 错

17. 若输入的字符包含 'A'，则输出的字符总包含 'A'。（）{{ select(17) }}

• 对
• 错

18. 将第 14 行的 i == 1 || str[i] != str[i - 1] 改为 str[i] != str[i - 1]，程序运行结果不变。（）{{ select(18) }}

• 对
• 错

19. 将第 15 行的 res[p] = str[i], p = p + 1; 改为 res[p++] = str[i];，程序运行结果不变。（）{{ select(19) }}

• 对
• 错

20. 当输入的字符串为 AABBCC 时，输出的字符串为（）{{ select(20) }}

• ABC
• aabbcc
• A26B26C26
• abc

21. 当输入的字符串为（）时，输出的字符串长度和输入的一样{{ select(21) }}

• CBAA
• DDDDFGG
• SMOKEY
• RUSTISBEEEEST

(2)

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

int n, k;

int func(vector <int> &nums) {
    int ret = 0;
    for(int i = n; i > k; i--) {
        if(nums[i] > nums[i - k]) {
            swap(nums[i], nums[i - k]);
            ret++;
        }
    }
    return ret;
}

int main() {
    cin >> n >> k;
    vector <int> a(n + 1, 0);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    int counter = 0, previous = -1;
    while(counter != previous){
        previous = counter;
        counter += func(a);
    }
    for(int i = 1; i <= n; i++)
        cout << a[i] << ",";
    cout << endl << counter << endl;
    return 0;
}

22. 当输入的 k 为 1，程序将 a 从小到大排序。（）{{ select(22) }}

• 对
• 错

23. 在题目限制的输入规模下，counter 可能会溢出。（）{{ select(23) }}

• 对
• 错

24. 当输入为“8 1 1 9 2 3 4 6 8 7”，输出共有 18 个可见字符。（）{{ select(24) }}

• 对
• 错

25. 当输入的 k 为 1，该程序的排序方法最接近（）{{ select(25) }}

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

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

• $O(n + k^2)$
• $O(n^2)$
• $O(nk)$
• $O(n^2/k)$

27. 当输入为“8 3 1 5 2 6 3 7 4 8”，输出的第一行第三个数字为（）{{ select(27) }}

• 2
• 6
• 7
• 8

(3)

#include <iostream>
using namespace std;

const int MAXN = 100;

int n, k, a[MAXN];
int ans;
int perm[MAXN];
bool used[MAXN];
int tmp[MAXN], tmp2[MAXN];

bool check() {
    for (int i = 1; i <= n; i++) tmp[i] = i;
    for (int i = 1; i <= k; i++) {
        for (int i = 1; i <= n; i++) tmp2[i] = tmp[perm[i]];
        for (int i = 1; i <= n; i++) tmp[i] = tmp2[i];
    }
    for (int i = 1; i <= n; i++) {
        if (tmp[i] != a[i]) return false;
    }
    return true;
}

void dfs(int now) {
    if (now > n) {
        if (check()) ans++;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            perm[now] = i;
            dfs(now + 1);
            used[i] = false;
        }
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    ans = 0;
    for (int i = 1; i <= n; i++) used[i] = false;
    dfs(1);
    cout << ans;
    return 0;
}

假设输入的 $n$ 是不超过 $12$ 的正整数，$k$ 是不超过 $10^9$ 的正整数，a[1..n] 是 $1\dots n$ 的一个排列（即 $1\dots n$ 均恰好在 a[1..n] 中出现一次），完成下面的题目。

28. 若输入的 $k$ 为 $1$，则不论 $n$ 为何值，输出总是为 $1$。（）{{ select(28) }}

• 对
• 错

29. 若输入的 $n$ 为 $6$，要使输出的数最大，$k$ 的值至少为 $60$。（）{{ select(29) }}

• 对
• 错

30. 将第 15 至 16 行替换为下面一行代码，程序运行结果不变。（）

    for (int i = 1; i <= n; i++) tmp[i] = tmp[perm[i]];
    

{{ select(30) }}

• 对
• 错

31. 程序输出 ans 时，check 函数一共被调用了（）次{{ select(31) }}

• $n$
• $n^2$
• $n!$
• $n^n$

32. 若输入为 4 2 3 4 1 2，则输出为（）{{ select(32) }}

• $0$
• $1$
• $2$
• $3$

33. （4 分）若输入为 6 2 1 2 3 4 5 6，则输出为（）{{ select(33) }}

• $70$
• $72$
• $74$
• $76$

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

(1)（互质数对）

给定正整数 $n$，按从小到大的顺序输出 $n$ 以内与 $n$ 互质的所有正整数 $x$。例如，当 $n=12$ 时，$x$ 可以为 $1,5,7,11$。

输入包含一个正整数 $n$，保证 $1\le n\le 10^5$。

提示：先找出 $n$ 的所有不为 $1$ 的因子并存放在数组 a 中，然后从小到大枚举 $x$ 并判断 $n$ 和 $x$ 是否有公因子。

试补全程序。

#include <iostream>
using namespace std;

int n;
int cnt;
int a[1000];

void init() {
    int i;
    cnt = 0;
    for (i = 2; i * i < n; i++) {
        if (__(1)__) {
            a[cnt++] = i;
            __(2)__;
        }
    }
    if (__(3)__) a[cnt++] = i;
    if (n != 1) a[cnt++] = n;
}

int main() {
    cin >> n;
    init();
    for (int x = 1; x <= n; x++) {
        bool flag = true;
        for (int i = __(4)__; i < cnt; i++) {
            if (__(5)__) {
                flag = false;
                break;
            }
        }
        if (flag) cout << x << ' ';
    }
    return 0;
}

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

• i % n == 0
• i % n != 0
• n % i == 0
• n / i == 0

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

• a[cnt++] = n - i
• a[cnt++] = n / i
• break
• continue

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

• i == n
• i * i == n
• i * i > n
• i + i == n

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

• 0
• 1
• 2
• x

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

• n % i == 0
• x % i == 0
• n % a[i] == 0
• x % a[i] == 0

(2)（时间安排）

有一个长度为 $n$ 的递增整序列 $a_{1\dots n}$。你需要将它划分成尽可能少的若干个子序列，使得同个子序列内相邻两项不超过 $d$。请给出这个划分。第一行一个整数 $k$ 表示划分的子序列数，然后一行 $n$ 个整数 $b_i$ 表示第 $i$ 个数被划分进第 $b_i$ 个子序列。

输入第一行两个正整数 $n, d$。

接下来一行 $n$ 个整数 $a_i$。

保证 $1\le n\le 2 \cdot 10^5$，$a_i, d\le10^9$。

提示：贪心地划分，使得每个子序列尽可能长。

试补全程序。

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 200005;

int n, d, ans;
int a[MAXN], v[MAXN];

int solve(int p) {
    int L = 0, R = n, MID, ANS = n + 1;
    while(__(3)__) {
        MID = (L + R) / 2;
        if(__(4)__) {
            ANS = MID;
            L = MID + 1;
        } else {
            R = __(5)__;
        }
    }
    if(ANS > n) {
        return 0;
    }
    return ANS;
}

int main() {
	cin >> n >> d;
	for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    int cnt = 0;
    while(cnt < n) {
        for(int i = __(1)__; i <= n; ++i) {
            if(vis[i] == 0) {
                ++ans; ++cnt;
                vis[i] = ans;
                int p = __(2)__, cur;
                while(cur = solve(p)) {
                    ++cnt;
                    vis[cur] = ans;
                    p = a[cur] + d;
                }
                break;
            }
        }
	}
    cout << ans << endl;
    for(int i = 1; i <= n; ++i) {
        cout << vis[i] << " ";
    }
	return 0;
}

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

• 1
• 0
• ans + 1
• ans

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

• a[i]
• d
• ans
• a[i] + d

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

• L <= R
• L < R
• L != R
• L + 1 < R

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

• a[MID] <= p
• a[MID] >= p
• a[MID] > p
• a[MID] < p

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

• MID
• MID + 1
• ANS
• MID - 1