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

第 1 题

以下关于存储器的说法中，错误的是（ ）。

{{ select(1) }}

• RAM 中的信息在断电后会丢失
• CPU 可以直接从硬盘中读取指令并执行
• 内存的访问速度通常比外存快
• ROM 是一种只读存储器

第 2 题

对于变量 $a=7,b=4$，表达式(a ^ b) & ((~a) | b)的结果是（ ）。

{{ select(2) }}

• 3
• 4
• 7
• 0

第 3 题

一个 8 位有符号整数采用二进制补码表示，其可以表示的最小十进制数是（ ）。

{{ select(3) }}

• −127
• −128
• −255
• −256

第 4 题

在 NOI Linux 终端中，要创建一个名为 "test" 的新目录，应该使用（ ）命令。

{{ select(4) }}

• new test
• create test
• mkdir test
• md test

第 5 题

$x$ 是正整数且在 int 范围内，则表达式 $(x \ \&\ (x-1)) == 0$ 可以用来判断一个无符号整数 $x$（ ）。

{{ select(5) }}

• 是偶数
• 是 2 的幂次
• 是 0
• 是奇数

第 6 题

在平均情况下，（ ）算法的时间复杂度最低。

{{ select(6) }}

• 冒泡排序
• 插入排序
• 快速排序
• 选择排序

第 7 题

以下代码的空间复杂度是（ ）。

int sum = 0;
for (int i = 0; i < n; i++) {
    int temp = i * 2;
    sum += temp;
}

{{ select(7) }}

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

第 8 题

一个项目团队有 12 名成员，团队内部任意两人都有过合作经历。这样的合作关系对应（ ）。

{{ select(8) }}

• 连通图
• 完全图
• 二分图
• 稀疏图

第 9 题

一个栈的入栈序列为 1,2,3,4,5,6。出栈序列中，3 是第二个出栈的元素。出栈序列（ ）是不可能的。

{{ select(9) }}

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

第 10 题

5 个男生和 3 个女生坐成一排，要求女生不相邻，且第一个和最后一个位置必须是男生，不同的排法有（ ）种。

{{ select(10) }}

• 1440
• 2160
• 2880
• 4320

第 11 题

已知二叉树的中序遍历序列为 DBEAC，后序遍历序列为 DEBCA，则前序遍历序列为（ ）。

{{ select(11) }}

• ABCDE
• ABDEC
• ABEDC
• ABECD

第 12 题

用数组存储完全二叉树，按从上到下、从左到右的顺序编号（从 1 开始），则节点 $i$ 的左子节点是（ ）。

{{ select(12) }}

• $2i$
• $2i+1$
• $i/2$
• $(i+1)/2$

第 13 题

以下关于 CPU（中央处理器）的描述中，正确的是（ ）。

{{ select(13) }}

• CPU 主要由存储器和控制器组成
• CPU 的性能仅由主频决定
• 多核 CPU 是指一个 CPU 中有多个运算器
• CPU 是计算机的"大脑"，负责所有的运算和控制

第 14 题

学校有 $n$ 门课程，部分课程有先修关系（必须先修 A 才能修 B）。现要判断课程安排是否合理，有没有循环依赖。这对应应图论中的（ ）问题。

{{ select(14) }}

• 最短路径
• 拓扑排序
• 最小生成树
• 负环

第 15 题

某哈夫曼树有 8 个叶节点，该树总共有（ ）个节点。

{{ select(15) }}

• 8
• 15
• 16
• 17

---

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

（1）

#include <iostream>
using namespace std;

int process(int n) {
    if (n == 0) return 0;
    return n % 2 + process(n / 2) * 10;
}

int main() {
    int num;
    cin >> num;
    int result = process(num);
    cout << result << endl;
    return 0;
}

判断题

第 16 题

输入 10 时，输出为 1010。

{{ input(16) }}

第 17 题

输入 1024 时，输出为 10000000000。

{{ input(17) }}

第 18 题

对于任意正整数 $n$，process(n) 的输出总是一个由 0 和 1 组成的数。

{{ input(18) }}

选择题

第 19 题

若输入 2025，则函数 process 被递归调用（ ）次（包括第一次调用）。

{{ select(19) }}

• 10
• 11
• 12
• 13

第 20 题

函数 process 的时间复杂度是（ ）。

{{ select(20) }}

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

第 21 题

程序能正常处理的最大输入值为（ ）。

{{ select(21) }}

• 1023
• 1024
• 10000000000
• $2^{31}-1$

（2）

#include <iostream>
#include <cmath>
#define MAX 100
using namespace std;

int digits[MAX+9];
void solve(int a, int b, int precision) {
    if (b == 0) {
        cout << "Error: Division_by_zero!" << endl;
        return;
    }
    if (precision > MAX) precision = MAX;
    if (precision < 0) precision = 0;

    bool negative = (a < 0 && b > 0) || (a > 0 && b < 0);
    a = abs(a);
    b = abs(b);
    digits[0]=a / b;
    int remainder = a % b;

    for (int i = 1; i <= precision+1; i++) {
        remainder *= 10;
        digits[i] = remainder / b;
        remainder %= b;
    }

    if (digits[precision+1] >= 5) {
        digits[precision]++;
    }
    for (int i = precision; i >= 1; i--) {
        if (digits[i] >= 10) {
            digits[i] -= 10;
            digits[i - 1]++;
        } else {
            break;
        }
    }

    if (negative) cout << "-";
    cout << digits[0] << cout << '.';
    for (int i = 1; i <= precision; i++) {
        cout << digits[i];
    }
    cout<<endl;
}

int main() {
    int a, b, prec;
    cin >> a >> b >> prec;
    solve(a, b, prec);
    return 0;
}
// 所有输入数据的绝对值均小于 1000

判断题

第 22 题

程序输出结果保留指定的小数位数，同时实现四舍五入，小数位的数量等于输入变量 prec 值的值。

{{ input(22) }}

第 23 题

若输入 2025 25 0，程序会输出 81。

{{ input(23) }}

第 24 题

若将程序中的 solve(a, b, prec); 替换成 cout << fixed << setprecision(prec) << (1.0*a/b) << endl;，其他部分不变，则当 prec 的输入值在 $[0,15]$ 区间时，输出结果是一样的。

{{ input(24) }}

选择题

第 25 题

如果输入 2026 26 4，则输出的结果是（ ）。

{{ select(25) }}

• 77.923
• 77.9230
• 77.9231
• 77.9232

第 26 题

如果输入的数据为 2026 0 -6，下列说法中正确的是（ ）。

{{ select(26) }}

• 程序会因为执行除以 0 的操作而出错，不能正常输出数据
• 程序不会报错，但不会输出具体数值，而是输出自定义的错误提示语
• 程序不会报错，可以正常输出结果，输出结果为 2026
• 程序不会报错，可以正常输出结果，输出结果为 -2026

（3）

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

int bSearch(vector<int>& a, int target) {
    int left = 0, right = a.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (a[mid] == target) {
            return mid;
        } else if (a[mid] > target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    int n, x;
    cin >> n >> x;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans = bSearch(a, x);
    cout << (ans!=-1 ? ans : -1) << endl;
    return 0;
}

判断题

第 27 题

如果输入 6 3 10 9 8 6 5 4，程序会输出 -1。

{{ input(27) }}

第 28 题

该程序使用二分法，在单调不升数组中查找某个数在整个数组中排在第几个位置。

{{ input(28) }}

第 29 题

要保证正常查找功能，输入必须从大到小排列，并且数值要连续。

{{ input(29) }}

选择题

第 30 题

如果输入 10 4 20 17 15 11 10 9 8 6 5 3，程序会输出（ ）。

{{ select(30) }}

• 11
• 10
• 8
• −1

第 31 题

如果输入单调不升数组，被查找的数值出现过多多次，则程序输出是（ ）。

{{ select(31) }}

• 匹配的最小的下标
• 匹配的最大的下标
• 任意一个匹配的下标都有可能
• −1

第 32 题

如果输入人 4 4 4 4 4 4，程序会输出（ ）。

{{ select(32) }}

• 0
• 1
• 2
• 3

---

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

（1）

给定一个整数数组和一个整数 $k$，程序找出数组中 $k$ 个不相邻元素（即任意两个被选元素在数组中不相邻）的最大和。

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

int solve(vector<int>& nums, int k) {
    int n = ①;
    vector<vector<int>> dp②;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (j == 1) {
                dp[i][j] = max③;
            } else {
                dp[i][j] = max(dp[i-1][j], ④);
            }
        }
    }
    return ⑤;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    cout << solve(nums, k) << endl;
    return 0;
}

第 33 题

①处应填（ ）。

{{ select(33) }}

• nums.size()-1
• nums.size()
• nums.length()-1
• nums.length()

第 34 题

②处应填（ ）。

{{ select(34) }}

• n, vector<int>(k, 0)
• n, vector<int>(k+1, 0)
• n+1, vector<int>(k, 0)
• n+1, vector<int>(k+1, 0)

第 35 题

③处应填（ ）。

{{ select(35) }}

• dp[i-1][j], nums[i-1]
• dp[i][j], nums[i-1]
• dp[i-1][j-1] + nums[i-1]
• dp[i][j] + nums[i-1]

第 36 题

④处应填（ ）。

{{ select(36) }}

• dp[i-1][j], nums[i-1]
• dp[i][j], nums[i-1]
• dp[i-2][j-1] + nums[i-1]
• dp[i][j] + nums[i-1]

第 37 题

⑤处应填（ ）。

{{ select(37) }}

• dp[n-1][k-1]
• dp[n][k-1]
• dp[n-1][k]
• dp[n][k]

（2）

给定一条长度为 L 的线段（L 为整数），以及 $n$ 个整数区间，每个区间有整数起始位置和结束位置。程序的目标是选择最少数量的区间，使得这些区间完全连续覆盖整个线段 $[0,L]$。如果无法完全覆盖，则输出 -1。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;

struct Interval { int s, e; } ivl[N];

bool cmp(Interval a, Interval b) {
    return a.s < b.s || ①;
}

int main() {
    int L, n;
    cin >> L >> n;

    for (int i = 0; i < n; i++) {
        cin >> ivl[i].s >> ivl[i].e;
    }
    ②

    int curr = 0;
    int cnt = 0;
    int i = 0;

    while (curr < L) {
        int mx_reach = curr;

        while (③) {
            if (ivl[i].e > mx_reach) {
                mx_reach = ivl[i].e;
            }
            i++;
        }

        if (④) {
            cout << -1 << endl;
            return 0;
        }
        cnt++;
        ⑤
    }

    cout << cnt << endl;
    return 0;
}

第 38 题

①处应填（ ）。

{{ select(38) }}

• a.s == b.s && a.e < b.e
• a.s == b.s && a.e <= b.e
• a.s == b.s && a.e != b.e
• a.s == b.s && a.e >= b.e

第 39 题

②处应填（ ）。

{{ select(39) }}

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

第 40 题

③处应填（ ）。

{{ select(40) }}

• i < n && ivl[i].s > curr
• i < n && ivl[i].s >= curr
• i < n && ivl[i].s <= curr
• i < n && ivl[i].s < curr

第 41 题

④处应填（ ）。

{{ select(41) }}

• i < n
• i > n
• mx_reach < curr
• mx_reach == curr

第 42 题

⑤处应填（ ）。

{{ select(42) }}

• curr = mx_reach;
• curr += mx_reach;
• curr = intervals[i].e;
• curr += intervals[i].e - intervals[i].s + 1;