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. 在 $\mathrm{C++}$ 中，表达式“！(5>3）&&（4<=4）||（2！=2）”的结果是（）。 {{ select(3) }}

• true
• false
• 1
• 编译错误

---

4. 关于单向链表，以下描述中正确的是（）。 {{ select(4) }}

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

---

5. 对于有 $n$ 个节点的二叉树，其最小高度是（）。 {{ select(5) }}

• $\lceil \log_2 n\rceil$
• $\lceil \log_2(n+1)\rceil -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 \times 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

---

阅读程序（1）：

#include <iostream>
using namespace std;

int solve(int x, int y) {
    if (y == 0) return x;
    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的最大公约数。 {{ select(16) }}

• 正确
• 错误

---

17. 把第5行代码去掉，程序会正常输出，但结果数值可能不对。 {{ select(17) }}

• 正确
• 错误

---

18. 如果输入的值为160和115，则程序的输出结果为23/32。 {{ select(18) }}

• 正确
• 错误

---

19. （4分）如果输入1817和299，则输出为（ ）。 {{ select(19) }}

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

---

20. （4分）如果输入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。 {{ select(21) }}

• 正确
• 错误

---

22. 数组中可能存在多个元素满足条件，程序会将它们全部累加。 {{ select(22) }}

• 正确
• 错误

---

23. 如果程序输出为0，则数组中的所有元素一定都相等。 {{ select(23) }}

• 正确
• 错误

---

24. （4分）若输入数组为[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. 如果输入数据中存在重复数字，则重复数字的数量不会影响输出结果。 {{ select(26) }}

• 正确
• 错误

---

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

• 正确
• 错误

---

28. 如果 $n=10$，$k=2$，n个数为1~10的任意排列，则输出结果是 $2C_5^2$。 {{ select(28) }}

• 正确
• 错误

---

29. 如果输入的 $k$ 为0，则程序的输出结果为（ ）。 {{ select(29) }}

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

---

30. （4分）程序的时间复杂度是（ ）。 {{ select(30) }}

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

---

完善程序（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])

---