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

第 1 题

在 NOI Linux 的终端中，要列出当前目录下所有文件和文件夹的详细信息（包括权限、大小、修改时间等），应该使用命令（ ）。

{{ select(1) }}

• ls
• ls -l
• ls -a
• ls -s

第 2 题

在计算机网络中，IP 地址 192.168.1.1 属于（ ）地址。

{{ select(2) }}

• A 类
• B 类
• C 类
• D 类

第 3 题

在 C++ 中，表达式 !(5 > 3) && (4 <= 4) || (2 != 2) 的结果是（ ）。

{{ select(3) }}

• true
• false
• 1
• 编译错误

第 4 题

关于单向链表，以下描述中正确的是（ ）。

{{ select(4) }}

• 可以随机访问任意位置的元素
• 插入和删除元素的时间复杂度都是 $O(1)$
• 需要连续的存储空间
• 每个节点包含数据和指向下一个节点的指针

第 5 题

对于有 $n$ 个节点的二叉树，其最小高度是（ ）。

{{ select(5) }}

• $\lfloor\log_2 n\rfloor$
• $\lfloor\log_2(n+1)\rfloor-1$
• $n-1$
• 1

第 6 题

将十进制小数 100.25 转换为二进制数，结果是（ ）。

{{ select(6) }}

• 1010100.01
• 1100100.11
• 1100100.01
• 1010100.11

第 7 题

（考试成绩排序）场景：老师需要对全班 50 名学生的成绩排序，要求相同分数的学生保持原来的相对顺序。下列排序算法中最合适的是（ ）。

{{ select(7) }}

• 快速排序
• 堆排序
• 归并排序
• 选择排序

第 8 题

突然断电后，数据不会丢失的存储设备是（ ）。

{{ select(8) }}

• 内存
• 缓存
• 固态硬盘
• 寄存器

第 9 题

使用深度优先搜索（DFS）遍历一个 $n$ 行 $m$ 列的矩阵。从左上角开始搜索，每次只能向右或向下移动一个位置。在搜索过程中，需要使用一个栈来维护当前搜索路径上的已访问位置。为了确保能够完整遍历矩阵的遍历，栈的大小至少为（ ）。（注：本题不考虑栈空间的大小限制）

{{ select(9) }}

• $\max(n,m)$
• $m+n$
• $m+n-1$
• $n*m$

第 10 题

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

int n, i = 1;
cin >> n;
while (i < n) {
    i = i * 3;
}

{{ select(10) }}

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

第 11 题

某城市有 8 个交通枢纽，如果要建设一个完全图式的道路网络，使得任意两个枢纽之间都有直达道路，需要建设（ ）条道路。

{{ select(11) }}

• 28
• 64
• 16
• 7

第 12 题

从 5 个不同的红球和 3 个不同的蓝球中，至少取 1 个球，最多取 4 个球，且红球和蓝球都必须至少取一个，不同的取法有（ ）种。

{{ select(12) }}

• 120
• 125
• 180
• 210

第 13 题

二叉树的节点按照先从上往下、后从左往右的顺序（对比"先行后列"的表达方式）进行编号，（ ）遍历方式可以按升序输出二叉搜索树的所有节点。

{{ select(13) }}

• 前序
• 中序
• 后序
• 层次

第 14 题

一个时间复杂度为 $O(n^3)$ 的算法，当 $n$ 从 100 增大到 200 时，运行时间大约变为原来的（ ）倍。

{{ select(14) }}

• 2
• 4
• 8
• 16

第 15 题

一段时长 10 分钟的视频，分辨率为 1080P（$1920\times1080$），帧率为 30 帧/秒，颜色深度为 24 位。如果压缩比为 50:1，则压缩后的文件大小约为（ ）。

{{ select(15) }}

• 1.2GB
• 2.1GB
• 2.24GB
• 104.3GB

---

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

（1）

#include <iostream>
using namespace std;
int solve(int x, int y) {
    if (y == 0) return x;
    if (x < y) swap(x, y);
    if (x % y) swap(x, y);
    return solve(y, x - y);
}
int main() {
    int a, b;
    cin >> a >> b;
    int k = solve(a, b);
    cout << a/k << "/" << b/k << endl;
    return 0;
}
// 输入的 a 和 b 是不大于 10000 的正整数

判断题

第 16 题

函数 solve(int x, int y) 计算 $x$ 和 $y$ 的最大公约数。

{{ input(16) }}

第 17 题

把第 5 行代码去掉，程序会正常输出，但结果数值可能不对。

{{ input(17) }}

第 18 题

如果输入的值为 160 和 115，则程序的输出结果为 23/32。

{{ input(18) }}

选择题

第 19 题

如果输入 1817 和 299，则输出为（ ）。

{{ select(19) }}

• 1817/299
• 97/13
• 79/23
• 79/13

第 20 题

如果输入 $x$, $y$ 为 $1..10000$ 中随机生成的数，则程序的平均时间复杂度为（ ）。

{{ select(20) }}

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

（2）

#include <iostream>
using namespace std;
int main() {
    int n, sum = 0;
    cin >> n;
    int arr[100];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (arr[j] > arr[i]) {
                cnt++;
            }
        }
        sum += (cnt == 1) * arr[i];
    }
    cout << sum << endl;
    return 0;
}
// 输入的所有数为绝对值均不大于 1000 的整数

判断题

第 21 题

若输入数组为 [5, 3, 8, 2]，则程序输出为 5。

{{ input(21) }}

第 22 题

数组中可能存在多个元素满足条件，程序会将它们全部累加。

{{ input(22) }}

第 23 题

如果程序输出为 0，则数组中的所有有元素一定都相等。

{{ input(23) }}

选择题

第 24 题

若输入数组为 [9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2]，则输出为（ ）。

{{ select(24) }}

• −2
• −1
• 8
• 9

第 25 题

该程序计算的是数组中（ ）。

{{ select(25) }}

• 第二大元素的值
• 所有比平均值大的元素之和
• 所有满足"恰好有一个元素比它大"的元素之和
• 最大元素和最小元素的和

（3）

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

int n, k, ans = 0;
vector<int> nums;
vector<bool> used;

void dfs(int pos, int sum, int count) {
    if (count == k) {
        if (sum % 2 == 0) {
            ans++;
        }
        return;
    }
    if (pos >= n) return;

    if (!used[pos]) {
        used[pos] = true;
        dfs(pos + 1, sum + nums[pos], count + 1);
        used[pos] = false;
    }

    dfs(pos + 1, sum, count);
}

int main() {
    cin >> n >> k;
    nums.resize(n);
    used.resize(n, false);

    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

判断题

第 26 题

如果输入数据中存在重复数字，则重复数字的数量不会影响输出结果。

{{ input(26) }}

第 27 题

去掉 nums.resize(n); 和 used.resize(n, false); 这两行代码，不会影响程序的正常运行。

{{ input(27) }}

第 28 题

如果 $n=10,k=2,n$ 个数为 $1\sim10$ 的任意排列，则输出结果是 $2C_{10}^{2}$。

{{ input(28) }}

选择题

第 29 题

如果输入人的 $k$ 为 0，则程序的输出结果为（ ）。

{{ select(29) }}

• 0
• 1
• C. 需要结合数组的值，才能计算结果
• 以上都不对

第 30 题

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

{{ select(30) }}

• $O(n)$
• $O(n^2)$
• $O(2^n)$
• $O(n^k)$

---

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

（1）

归并排序算法通过递归地将数组不断地分割为更小的子数组，然后将这些子数组合并成有序数组，最终完成整个数组的排序。该排序为稳定排序，且时间复杂度较低。

#include <iostream>
#define N 100009
using namespace std;
int n;
int a[N],L[N],R[N];
void merge(int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    for (int i = 0; i < n1; i++)
        L[i] = a[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = a[①];
    int i = 0, j = 0, k = l;
    while (②) {
        if (L[i] <= R[j]) {
            a[k] = L[i++];
        } else {
            a[k] = R[j++];
        }
        ++k;
    }
    while (i < n1) {
        a[k++] = L[i++];
    }
    while (j < n2) {
        a[k++] = R[j++];
    }
}
void mSort(int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mSort(left, mid);
        mSort(mid + 1, right);
        merge(③);
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    mSort(④);
    for (int i = 0; i < n-1; i++) {
        cout << a[i] << " ";
    }
    cout << ⑤ << endl;
    return 0;
}

第 31 题

①处应填（ ）。

{{ select(31) }}

• j
• j+1
• m+j
• m+1+j

第 32 题

②处应填（ ）。

{{ select(32) }}

• i < n && j < n
• i <= n && j <= n
• i < n1 && j < n2
• i <= n1 && j <= n2

第 33 题

③处应填（ ）。

{{ select(33) }}

• mid, left, right
• right, left, mid
• left, mid, right
• left, right, mid

第 34 题

④处应填（ ）。

{{ select(34) }}

• 0, n-1
• 0, n
• 1, n-1
• 1, n

第 35 题

⑤处应填（ ）。

{{ select(35) }}

• " " << a[n-1]
• a[n-1]
• " " << a[n]
• a[n]

（2）

波动动序列指序列中的元素值交替上升和下降，最长波动子序列是已有的序列中满足这种波动性质的最长子序列。

#include <iostream>
#include <vector>
#include <algorithm>
#define N 1009
using namespace std;
int n;
int dp[N][2];
int main() {
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    ①
    for (int i = 1; i < n; i++) {
        for (int j = 0; ②; j++) {
            if (③) {
                int tmp = dp[j][1] + 1;
                if (tmp > dp[i][0]) {
                    dp[i][0] = tmp;
                }
            }
            else if (nums[i] < nums[j]) {
                int tmp = ④;
                if (tmp > dp[i][1]) {
                    dp[i][1] = tmp;
                }
            }
        }
    }
    int max_Len = 1;
    for(int i = 1; i < n; i++){
        max_Len = max(max_Len, ⑤);
    }
    cout << max_Len << endl;
    return 0;
}

第 36 题

①处应填（ ）。

{{ select(36) }}

• memset(dp, 1, sizeof(dp))
• memset(dp, 0x3f, sizeof(dp))
• fill(dp, dp + n * 2, 1)
• fill(dp[0], dp[0] + n * 2, 1)

第 37 题

②处应填（ ）。

{{ select(37) }}

• j < n
• j <= n
• j < i
• j <= i

第 38 题

③处应填（ ）。

{{ select(38) }}

• nums[i] > nums[j]
• nums[i] >= nums[j]
• nums[j] > nums[i]
• nums[j] >= nums[i]

第 39 题

④处应填（ ）。

{{ select(39) }}

• dp[i][0] + 1
• dp[i][1] + 1
• dp[j][0] + 1
• dp[j][1] + 1

第 40 题

⑤处应填（ ）。

{{ select(40) }}

• dp[i][0]
• dp[i][1]
• max(dp[i][0], dp[i][1])
• min(dp[i][0], dp[i][1])