---

1. 在计算机系统中，操作系统的主要作用是（）。 {{ select(1) }}

• 将用高级语言编写的程序翻译成机器语言
• 管理和控制计算机的硬件与软件资源
• 进行科学计算
• 防范计算机病毒

---

2. 在NOI Linux中，使用 g++ 编译一个名为 main.cpp 的源文件，并指定生成的可执行文件名为 main，正确的命令是（）。 {{ select(2) }}

• g++ -o main main.cpp
• g++ main.cpp -o main
• g++ main.cpp main
• g++ main -o main.cpp

---

3. 对序列 {5,2,4,6,1,3} 进行直接插入排序，在完成前3个元素（5,2,4）的排序后，序列的状态是（）。 {{ select(3) }}

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

---

4. 对于变量 $x = 25$，$y = 7$，表达式 $(x \sim y) \& \sim(x \& y)$ 的结果是（）。 {{ select(4) }}

• 25
• 30
• 0
• 7

---

5. 下列几种排序算法中，在最坏情况下，（）的时间复杂度与其他三种不同。 {{ select(5) }}

• 冒泡排序
• 选择排序
• 插入排序
• 归并排序

---

6. 十六进制数 0xDEAD 与二进制数 11011110110101101 的关系是（）。 {{ select(6) }}

• 前者比后者大1
• 后者比前者大1
• 两者相等
• 前者是后者的两倍

---

7. 对几乎已经排好序的数据（只有少数元素位置不对）进行排序，（）算法最快。 {{ select(7) }}

• 快速排序
• 插入排序
• 归并排序
• 选择排序

---

8. 一个项目团队中，每个成员都与其他恰好3个成员有直接协作关系。如果团队有12人，那么协作关系总共有（）种。 {{ select(8) }}

• 18
• 36
• 12
• 4

---

9. 一个栈的入栈序列为1,2,3,4,5。出栈序列中，4是第一个出栈的元素。出栈序列（）是不可能的。 {{ select(9) }}

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

---

10. 从1,2,3,…,10中选出4个不同的数，使得其中任意两个数的差都不小于2，不同的选法有（）种。 {{ select(10) }}

• 35
• 70
• 84
• 120

---

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

for (int i = n; i >= 1; i /= 2)
    for (int j = 1; j <= i; j++)
        sum++;

{{ select(11) }}

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

---

12. 对长度为 $n$ 的有序数组进行二分查找，( )不是必须满足的条件。 {{ select(12) }}

• 数组元素必须连续存储
• 数组必须按关键字有序
• 必须能够随机访问元素
• 数据量 $n$ 最好较大

---

13. 一棵二叉树的前序遍历序列是 ABDECF，中序遍历序列是 DBEAFC，则其后序遍历序列是（）。 {{ select(13) }}

• DEBFCA
• DEBFAC
• DBEFCA
• DBECFA

---

14. 循环队列容量为10，front = 7，rear = 3，元素个数为（）。 {{ select(14) }}

• 4
• 5
• 6
• 7

---

15. 使用邻接表存储图，拓扑排序的时间复杂度是（）。 {{ select(15) }}

• $O(V)$
• $O(E)$
• $O(V + E)$
• $O(V^2)$

---

阅读程序（1）：

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

int solve(int n) {
    int sum = 0;
    for (int i = 1; i <= n / 2; i++)
        if (n % i == 0) sum += i;
    return sum;
}

int main() {
    int n;
    cin >> n;
    int sum = solve(n);
    if (sum == n) {
        cout << "perfect_number" << endl;
    } else if (sum > n) {
        cout << "abundant_number" << endl;
    } else {
        cout << "deficient_number" << endl;
    }
    return 0;
}

16. 函数 solve 计算的是 n 的所有因数之和。 {{ select(16) }}

• 正确
• 错误

---

17. 如果 n 是素数，那么 solve 的返回值总是 1。 {{ select(17) }}

• 正确
• 错误

---

18. 当 $n = 496$ 时，程序会输出 perfect_number。 {{ select(18) }}

• 正确
• 错误

---

19. n 的取值区间为 [10,100] 时，第一个输出 abundant_number 的 n 是（）。 {{ select(19) }}

• 10
• 12
• 28
• 72

---

20. n 的取值区间为 [1,1000] 时，关于完全数（perfect_number），以下说法中正确的是（）。 {{ select(20) }}

• 所有完全数都是奇数
• 所有完全数都是偶数
• 完全数可以是素数
• 完全数的个数是无限的

---

阅读程序（2）：

#include <bits/stdc++.h>
using namespace std;
const int N = 10009;
int n, nums[N];

int solve() {
    int res = n;
    for (int i = 0; i < n; i++) {
        res ^= i;
        res ^= nums[i];
    }
    return res;
}

int main() {
    cin >> n;
    // 保证输入的n个数在0..n范围内，且互不相同
    for (int i = 0; i < n; i++) cin >> nums[i];
    cout << solve() << endl;
    return 0;
}

21. 若输入 5 1 2 3 4 5，则输出结果是 0。 {{ select(21) }}

• 正确
• 错误

---

22. 本题输入 nums 数组的数据可以是无序的。 {{ select(22) }}

• 正确
• 错误

---

23. 程序功能是判断 n 个数是不是连续的，如果不是连续的，则输出其中缺失的数。 {{ select(23) }}

• 正确
• 错误

---

24. （4分）若输入 7 7 1 6 2 5 3 0，则输出结果是（）。 {{ select(24) }}

• 0
• 3
• 4
• 8

---

25. （4分）算法利用的最主要的性质是（）。 {{ select(25) }}

• 异或的交换律和结合律
• 异或的交换律和分配律
• 异或的结合律和分配律
• 异或的交换律和幂零性

---

阅读程序（3）：

#include <bits/stdc++.h>
using namespace std;
const int N = 100009;
const int INF = 1e8 - 1;
int a[N];

int main() {
    int n, x;
    cin >> n >> x;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a+n, less<int>());

    int left = 0, right = n - 1, p = n;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (a[mid] > x) {
            p = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    cout << p << " ";
    if (p < n) cout << a[p] << endl;
    else cout << INF << endl;
    return 0;
}

26. 该程序使用二分查找，找到第一个大于或等于 $x$ 的元素的下标和数值。 {{ select(26) }}

• 正确
• 错误

---

27. 当输入 7 8 0 9 2 7 8 7 6 时，程序输出为 7 9。 {{ select(27) }}

• 正确
• 错误

---

28. 数组排序后，也可以使用 upper_bound(a, a+n, x) - a 得到 p 的数值。 {{ select(28) }}

• 正确
• 错误

---

29. （4分）当输入 8 7 3 4 4 5 5 6 6 7 时，程序输出为（）。 {{ select(29) }}

• 7 7
• 8 7
• 8 9999999
• 8 99999999

---

30. （4分）对于输入的 n 个数的序列，下列说法中正确的是（）。 {{ select(30) }}

• 序列中的元素可以从大到小有序
• 序列中的元素可以从小到大有序
• 序列中的元素可以无序
• 以上说法都正确

---

完善程序（1）：

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

ll steps = 0;

void hanoi(int n, char A, char B, char C) {
    if (n == 1) {
        cout << A << "->" << C << endl;
        ①
    } else {
        hanoi(n - 1, A, C, B);
        ②
        steps++;
        ③
    }
}

int main() {
    int n;
    cin >> n;
    if (n <= 0) {
        cout << 0 << endl;
        ④
    }
    ⑤
    cout << steps << endl;
    return 0;
}

31. ①处应填（）。 {{ select(31) }}

• return;
• steps = 1;
• steps++;
• steps = n;

---

32. ②处应填（）。 {{ select(32) }}

• cout << A << "->" << B << endl;
• cout << A << "->" << C << endl;
• cout << B << "->" << C << endl;
• cout << C << "->" << B << endl;

---

33. ③处应填（）。 {{ select(33) }}

• hanoi(n - 1, A, B, C);
• hanoi(n - 1, A, C, B);
• hanoi(n - 1, B, A, C);
• hanoi(n - 1, B, C, A);

---

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

• break;
• continue;
• n = 0;
• return 0;

---

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

• hanoi(1, 'A', 'B', 'C');
• hanoi(n, 'A', 'B', 'C');
• hanoi(1, 'A', 'C', 'B');
• hanoi(n, 'A', 'C', 'B');

---

完善程序（2）：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1009;
const ll INF = 1e9;
vector<int> to[N], w[N];
int n, m;
ll d[N];   // d[i] = i 号顶点到当前 MST 的最小边权
bool ok[N]; // ok[i] = i 号顶点是否在当前 MST 中

void add(int u, int v, int k) {
    to[u].push_back(v);
    to[v].push_back(u);
    w[u].push_back(k);
    w[v].push_back(k);
}

ll Prim() {
    ①
    ll ans = 0;
    d[1] = 0;

    for (int k = 1; k <= n; k++) {
        int u = ②;
        for (int i = 1; i <= n; i++)
            if (③) u = i;
        ok[u] = 1;
        ans += ④;

        for (int i = 0; i < to[u].size(); i++) {
            int v = to[u][i], cost = w[u][i];
            if (⑤) d[v] = cost;
        }
    }
    return ans;
}

int main() {
    cin >> n >> m;
    int u, v, k;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> k;
        add(u, v, k);
    }
    cout << Prim() << endl;
    return 0;
}

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

• fill(d, d+n+1, -1);
• fill(d, d+n+1, INF);
• fill(d, d+n+2, -1);
• fill(d, d+n+2, INF);

---

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

• -1
• 0
• n
• n+1

---

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

• d[i] < d[u]
• d[i] > d[u]
• !ok[i] && d[i] < d[u]
• ok[i] && d[i] < d[u]

---

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

• u
• d[u]
• k
• d[k]

---

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

• !ok[v] && cost < d[v]
• !ok[v] && cost > d[v]
• ok[v] && cost < d[v]
• ok[v] && cost > d[v]

---