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

1. $(2025)_8 + (2025)_{16}$ 和以下哪个选项相等（ ）。

{{ select(1) }}

• $(9244)_{10}$
• $(2100222)_4$
• $(10010000111010)_2$
• $(234A)_{16}$

2. 以下（ ）函数声明是合法的。

{{ select(2) }}

• int Bubblesort(char a[][],int n)
• int Bubblesort(char a[10][],int n)
• int Bubblesort(char a[][20],int n)
• int Bubblesort(char [,] a,int n)

3. 已知 int n;，下列表达式中不符合语法的是（ ）。

{{ select(3) }}

• &n+8
• n++9
• 15+n
• n- -7

4. 设循环队列中数组的下标范围是 $0\sim n-1$，其头尾指针分别为 $f$ 和 $r$，则其元素个数为（ ）。

{{ select(4) }}

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

5. 后缀表达式 1 2 + 3 * 14 7 / -（ ）。

{{ select(5) }}

• 1 + 2 * 3 - 14 / 7
• - * 1 + 2 3 / 14 7
• - * + 1 2 3 / 14 7
• - 1 + 2 * 3 14 / 7

6. 给定一棵二叉树，其前序遍历结果为 abdecfg，中序遍历结果为 debacfg，则这棵树的后序遍历结果为（ ）。

{{ select(6) }}

• edbgfca
• edgbfca
• debgfca
• dbegfca

7. 关于二叉树的说法不正确的是（ ）。

{{ select(7) }}

• 完全二叉树一定是满二叉树
• 满二叉树一定是完全二叉树
• 对于任意一棵二叉树，如果其叶结点数为 $N_0$，而度数为 $2$ 的结点总数为 $N_2$，则 $N_0=N_2+1$
• 在二叉树中，第 $i$ 层的结点总数不超过 $2^{i-1}$

8. 对于给定的代码，调用 f(5,6) 得到的结果是（ ）。

int f(int n,int m)
{
    if(n == 1) return 1;
    if(m == 1) return n;
    return f(n-1,m) + f(n,m-1);
}

{{ select(8) }}

• $126$
• $210$
• $240$
• $256$

9. 三个互不相等的正整数的最大公约数为 $2$，最小公倍数为 $2000$，那么这样的不同的正整数组的个数为（ ）。

{{ select(9) }}

• $42$
• $48$
• $50$
• $52$

10. 下列是关于数据结构的说法不正确的是（ ）。

{{ select(10) }}

• 数据结构是带有结构的数据元素的集合
• 线性表的线性存储结构优于链式存储结构
• 队列是一个先进先出的线性表
• 队列是只能在一端插入，另一端删除的线性表

11. 用 $d=(a_1,a_2,\ldots,a_5)$，表示无向图 $G$ 的 $5$ 个顶点的度数，下面给出的哪些组 $d$ 值合理（ ）。

{{ select(11) }}

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

12. 编号为 $1$ 到 $13$ 的纸牌顺时针排成一圈，有人从编号为 $1$ 的牌从数字 $1$ 开始顺时针数下去，$1,2,3,\ldots$，一圈又一圈，问当数到数字 $n$，所在的纸牌编号为（ ）。

{{ select(12) }}

• n % 13
• (n - 1) % 13 + 1
• (n + 1) % 13 - 1
• (n - 1) % 13

13. 已知无向图 $G$ 含有 $16$ 条边，其中度为 $4$ 的顶点个数为 $3$，度为 $3$ 的顶点个数为 $4$，其他顶点的度均小于 $3$。$G$ 所含的顶点个数至少是（ ）。

{{ select(13) }}

• $10$
• $11$
• $13$
• $15$

14. 给定一个正整数 $N=8934632178$，现决定依次删除其中 $6$ 个数位上的数字（每次删除一个数位上的数字），每次删除后按原来的次序组成一个新数 $M$ 的值均是当前状态下的最小数，则第四次应该删除的数字是（ ）。

{{ select(14) }}

• $3$
• $4$
• $6$
• $8$

15. 下面关于指针的说法正确的是（ ）。

{{ select(15) }}

• 在 $64$ 位计算机中一个指针变量占 $8$ 字节
• 指针运算实际上是地址操作、只能取地址和间接访问，不能进行加减运算
• 数组名是指向数组元素的指针变量
• 指针只可以静态申请内存空间

二、阅读程序（判断题1分，选择题3分，共计40分）

判断题正确填 T，错误填 F。

第1题

void solve(int n, int a[])
{
    while (true)
    {
        bool found = false;
        for (int i = 0; i + 1 < n; ++i)
        {
            if (a[i] > a[i+1])
            {
                found = true;
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
        if (not found) {
            break;
        }
    }
}

判断题

16. solve 可能会进入死循环（ ）。

{{ select(16) }}

• 正确
• 错误

17. 当 n=5，a = [1, 2, 3, 4, 5] 时，while 循环只运行一次（ ）。

{{ select(17) }}

• 正确
• 错误

18. 当 n=5，a = [5, 4, 3, 2, 1] 时，while 循环运行两次（ ）。

{{ select(18) }}

• 正确
• 错误

19. 当 solve 结束后，a 数组降序（ ）。

{{ select(19) }}

• 正确
• 错误

选择题

20. 当输入为 n=5，a = [3, 1, 4, 1, 5] 时，程序结束时，a=（ ）。

{{ select(20) }}

• [1, 3, 1, 4, 5]
• [5, 4, 3, 1, 1]
• [1, 1, 3, 4, 5]
• [3, 1, 4, 1, 5]

21. 程序交换 a[i] 与 a[i+1] 的次数（ ）。

{{ select(21) }}

• 小于数组 a 的逆序对数量
• 等于数组 a 的逆序对数量
• 大于数组 a 的逆序对数量
• 与数组 a 的逆序对数量无关

22. 程序的时间复杂度是（ ）。

{{ select(22) }}

• $\Theta(n\log n)$
• $\Theta(\log n)$
• $\Theta(n)$
• $\Theta(n^2)$

第2题

long long solve(long long n)
{
    long long c = 0;
    long long p = 1;
    long long t = 0;
    while (n > 0)
    {
        int d = n % 10;
        n /= 10;
        if (d > 0)
        {
            c += n * p;
        }
        else
        {
            c += (n-1) * p;
            c += t + 1;
        }
        t += d * p;
        p *= 10;
    }
    return c;
}

判断题

23. 运行过程中，t 与 c 两个变量将会越来越大（ ）。

{{ select(23) }}

• 正确
• 错误

24. 若将程序中所有的 10 改成 8，程序的返回值不会变大（ ）。

{{ select(24) }}

• 正确
• 错误

选择题

25. 当输入 n=99 时，程序输出（ ）。

{{ select(25) }}

• $9$
• $10$
• $99$
• $101$

26. 变量 p 在程序中的作用是（ ）。

{{ select(26) }}

• 记录当前处理位的位权
• 记录当前处理位的位数
• 记录已处理数字的个数
• 记录目标数字的个数

27. 程序的时间复杂度是（ ）。

{{ select(27) }}

• $\Theta(1)$
• $\Theta(\log n)$
• $\Theta(n)$
• $\Theta(n^2)$

第三题

#include<iostream>

int n, q;
char op[200000];
long long p[200000];
long long d[200000];
long long mod = 1000000007;

void solve1(long long a[])
{
    for (int i = 0; i < n; ++i)
        a[i] = 0;
    for (int i = 0; i < q; ++i) {
        if (op[i] == '+') {
            a[p[i]] += d[i];
            a[p[i]] %= mod;
        }
        else if (op[i] == '*') {
            for (int j = 0; j < n; ++j) {
                a[j] *= d[i];
                a[j] %= mod;
            }
        }
    }
}

void solve2(long long a[])
{
    for (int i = 0; i < n; ++i)
        a[i] = 0;

    long long f = 1;
    for (int i = q-1; i >= 0; i--) {
        if (op[i] == '+') {
            a[p[i]] += d[i] * f;
            a[p[i]] %= mod;
        }
        else if (op[i] == '*') {
            f *= d[i];
            f %= mod;
        }
    }
}

判断题

28. solve1 与 solve2 的功能相同（ ）。

{{ select(28) }}

• 正确
• 错误

29. 当全部 op[i] = * 时，solve1 数组 a 恒为 $0$（ ）。

{{ select(29) }}

• 正确
• 错误

30. 当全部 op[i] = + 时，solve2 数组 a 不等于 $0$（ ）。

{{ select(30) }}

• 正确
• 错误

31. solve1 的执行时间一定比 solve2 长（ ）。

{{ select(31) }}

• 正确
• 错误

选择题

32. 已知 n=2，q=3，操作序列顺序为：

+ 1 5
* 2
+ 3 3
* 4
+ 0 1
* 1
+ 4 6

solve1 和 solve2 中数组 a 的结果分别为（ ）。

{{ select(32) }}

• [1, 40, 0, 12, 6]，[1, 40, 0, 12, 6]
• [1, 40, 0, 12, 6]，[6, 12, 0, 40, 1]
• [0, 10, 0, 3, 6]，[6, 3, 0, 10, 0]
• [1, 5, 0, 3, 6]，[1, 5, 0, 3, 6]

33. 当 op[i] 全为 *，且 d[i] 均为 $2$ 时，solve2 中 f 的最终值为（ ）。

{{ select(33) }}

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

34. 程序 solve1 的时间复杂度是（ ）。

{{ select(34) }}

• $\Theta(n)$
• $\Theta(q)$
• $\Theta(n+q)$
• $\Theta(nq)$

35. 程序 solve2 的时间复杂度是（ ）。

{{ select(35) }}

• $\Theta(n)$
• $\Theta(q)$
• $\Theta(n+q)$
• $\Theta(nq)$

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

第1题

炼制一块合金，该合金需要 $a$ 克黄金与 $b$ 克白银。商店里有 $n$ 块材料，第 $i$ 块材料含有 $x_i$ 克黄金与 $y_i$ 克白银，且含有 $w_i$ 克杂质。

请问应该使用哪些材料，将它们炼制在一起，才能使得合金中黄金与白银含量不少于给定的要求，且杂质总和最小。所有材料均不可切割。输入数据保证所要求的合金一定可以炼成。

int n, a, b;
int x[maxn], y[maxn], w[maxn];
int mem[maxn][maxm][maxm];
bool cache[maxn][maxm][maxm];
const int INF = 1000000000;
int dfs(int k, int i, int j) {
    if (____(1)____) return 0;
    if (____(2)____) return INF;
    if (cache[k][i][j]) return mem[k][i][j];

    int ni = ____(3)____;
    int nj = ____(4)____;
    int giveup = ____(5)____;
    int pickup = ____(6)____;

    cache[k][i][j] = true;
    return mem[k][i][j] = std::min(giveup,pickup);
}
int main() {
    std::cin >> n >> a >> b;
    for (int i = 0; i < n; ++i)
        std::cin >> x[i] >> y[i] >> w[i];

    std::cout << ____(7)____ << "\n";
    return 0;
}

36. (1) 处应填（ ）。

{{ select(36) }}

• i >= a && j >= b
• i >= a || j >= b
• i == 0 || j == 0
• i == 0 && j == 0

37. (2) 处应填（ ）。

{{ select(37) }}

• k == 0
• k == n - 1
• k == n
• i == 0 || j == 0 || k == 0

38. (3)(4) 处应填（ ）。

{{ select(38) }}

• std::min(i, a)，std::min(j, b)
• std::min(i, a) - x[k]，std::min(j, b) - y[k]
• std::min(i - x[k], a)，std::min(j - y[k], b)
• std::min(i + x[k], a)，std::min(j + y[k], b)

39. (5)(6) 处应填（ ）。

{{ select(39) }}

• dfs(k + 1, i, j)，dfs(k + 1, ni, nj)
• dfs(k + 1, ni, nj)，dfs(k + 1, ni, nj)
• dfs(k + 1, i, j)，dfs(k + 1, ni, nj) + w[k]
• dfs(k + 1, ni, nj)，dfs(k + 1, ni, nj) + w[k]

40. (7) 处应填（ ）。

{{ select(40) }}

• dfs(0, a, b)
• dfs(0, 0, 0)
• dfs(n - 1, 0, 0)
• dfs(n - 1, a, b)

第2题

给定一个整数序列 $a_1,a_2,\ldots,a_n$，对该序列的所有子区间，分别算出它们的中位数，并且将这些中位数组成一个新序列，输出这个新序列的中位数。

所谓一个序列的中位数，就是将这个序列排序后，排名在最中间的数字，如果序列的长度是偶数，规定中位数是排名最居中的两个数之中偏大的数。

#include<iostream>
const int maxn = 1000000;
int a[maxn];
int b[maxn];
int s[maxn + 1];
int n;
long long total;

long long merge(int begin, int mid, int end) {
    int buffer[end - begin];
    auto i = begin;
    auto j = mid;
    auto k = 0;
    long long sum = 0;
    while (i < mid and j < end) {
        if (s[i] <= s[j]) {
            buffer[k++] = s[i++];
            sum += ____(1)____;
        }
        else {
            buffer[k++] = s[j++];
        }
    }
    while (i < mid) buffer[k++] = s[i++];
    while (j < end) buffer[k++] = s[j++];
    for (int x = begin, k = 0; x < end; ++x, ++k)
        s[x] = buffer[k];
    return sum;
}
long long merge_sort(int begin, int end) {
    auto length = end - begin;
    if (____(2)____) return 0;
    auto mid = begin + length / 2;
    auto front = merge_sort(begin, mid);
    auto back = merge_sort(mid, end);
    auto cross = merge(begin, mid, end);
    return ____(3)____;
}

bool predicate(int key) {
    for (int i = 0; i < n; ++i) {
        if (____(4)____)
            b[i] = 1;
        else
            b[i] = -1;
        s[i+1] = s[i] + b[i];
    }
    long long num = ____(5)____;
    return ____(6)____;
}
int main() {
    std::cin >> n;
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    total = (long long)n * (n + 1) / 2;

    int begin = 0;
    int end = 1000000001;
    while (true) {
        int length = ____(7)____;
        if (length == 1) break;
        auto mid = ____(8)____;
        if (predicate(mid))
            begin = mid;
        else
            end = mid;
    }
    std::cout << ____(9)____ << "\n";
}

41. (1) 处应填（ ）。

{{ select(41) }}

• k
• end - k
• end - i + 1
• end - j

42. (2)(3) 处应填（ ）。

{{ select(42) }}

• length == 0，front + back - cross
• length <= 1，front + back + cross
• length == 0，front + back + cross
• length <= 1，front + back - cross

43. (4)(5) 处应填（ ）。

{{ select(43) }}

• a[i] > key，merge_sort(0, n)
• a[i] < key，merge_sort(0, n + 1)
• a[i] < key，merge_sort(0, n)
• a[i] > key，merge_sort(0, n + 1)

44. (6) 处应填（ ）。

{{ select(44) }}

• num < total
• num < (total + 1) / 2
• num >= total
• num >= (total + 1) / 2

45. (7)(8)(9) 处应填（ ）。

{{ select(45) }}

• end - begin，(end + begin) / 2，begin
• end - begin + 1，begin + length / 2，begin
• end - begin + 1，(end + begin) / 2，end
• end - begin，begin + length / 2，end