---

1. 在以下各项中，（ ）不是CPU的组成部分。 {{ select(1) }}

• 控制器
• 运算器
• 寄存器
• 主板

---

2. $(2017)_{8} + (1234)_{10}$ 的结果是（ {{ select(2) }}

• $(8E2)_{16}$
• $(100011100001)_{2}$
• $(8E0)_{16}$
• $(100011100011)_{2}$

---

3. 设 $\mathrm{A} = \mathrm{B} = \mathrm{true}$，$\mathrm{C} = \mathrm{D} = \mathrm{false}$，则下列逻辑运算表达式的值为假的是（ ）。 {{ select(3) }}

• $(!A \&\& B)||(C \&\& D||A)$
• $!((A \&\& B)||C)\&\&D$
• $A\&\&(B||C||D)$
• $(A\&\&(D||C))\&\&B$

---

4. 已知一个栈的入栈序列为 $1,\dots,n$，出栈序列为 $p_1,\dots,p_n$，若 $p_1 = n$，则 $p_i =$（ ）。 {{ select(4) }}

• i
• $n-i$
• $n-i+1$
• 不确定

---

5. 设 $S =$ "abbcce"，其不同的非空子串有（ ）个。 {{ select(5) }}

• 19
• 17
• 16
• 18

---

6. 在 $\mathrm{C++}$ 中，$125 ^ 2 =$（ ）。 {{ select(6) }}

• 127
• 128
• 15625
• 126

---

7. 设某算法的计算时间表示为递推关系式 $T(n) = 2T(n / 2) + n$（$n$ 为正整数），且 $T(0) = 1$，则该算法的时间复杂度为（ ）。 {{ select(7) }}

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

---

8. 下列有关二叉树的叙述（设根节点为第1层）中，不正确的是（ ）。 {{ select(8) }}

• 二叉树的深度为 $k$，那么最多有 $2^{k} - 1$ 个节点
• 在二叉树的第 $i$ 层上，最多有 $2^{i} - 1$ 个节点
• 完全二叉树一定是满二叉树
• 堆是完全二叉树

---

9. 下列排序算法中，平均时间复杂度是 $O(n^{2})$ 的是（ ）。 {{ select(9) }}

• 快速排序
• 插入排序
• 归并排序
• 堆排序

---

10. 下列图中一定可以进行黑白着色，使得相邻节点的颜色不同的是（ ）。 {{ select(10) }}

• 树
• 基环树
• 连通图
• 欧拉图

---

11. 下列不是操作系统的是（ ）。 {{ select(11) }}

• Linux
• Windows
• Android
• WPS

---

12. 下列关于算法的叙述中，错误的是（ ）。 {{ select(12) }}

• 算法代表着用系统的方法描绘解决问题的策略机制
• 一个算法的好坏，只需要从时间复杂度这一方面进行考虑
• 一个算法必须具有有穷性、可行性、正确性、输入和输出
• 对于一些 NP 完全问题，现在未能找到有效的算法来解决

---

13. 下列叙述中正确的是（ ）。 {{ select(13) }}

• 线性表是线性结构
• 栈与队列是非线性结构
• 线性链表是非线性结构
• 二叉树是线性结构

---

14. 链表的（ ）操作需要 $O(n)$ 时间复杂度实现。 {{ select(14) }}

• 插入
• 定位
• 删除
• 合并

---

15. 在 NOI 比赛中，不可以带入考场的是（ ）。 {{ select(15) }}

• 键盘
• 空白纸张
• U 盘
• 铅笔

---

阅读程序（1）：

#include <iostream>
using namespace std;

int n, k, ans;

int main() {
    cin >> n >> k; // 保证 n, k 是非负整数，且在 int 范围内
    int ans = 0;
    while (n) {
        if (n % k > 0) ans++;
        n /= k;
    }
    cout << ans << endl;
    return 0;
}

16. （1分）把 n % k > 0 改成 n % k 不影响程序运行结果。（ ） {{ select(16) }}

• 正确
• 错误

---

17. 输入的 k 需要大于 1，否则程序可能无法正常运行。（ ） {{ select(17) }}

• 正确
• 错误

---

18. 输入的 n 需要大于 0，否则程序可能无法正常运行。（ ） {{ select(18) }}

• 正确
• 错误

---

19. 该算法的时间复杂度为 $O(\log n)$ 。（ ） {{ select(19) }}

• 正确
• 错误

---

20. 输入 125 5 时，输出结果为（ ）。 {{ select(20) }}

• 1
• 2
• 3
• 4

---

21. 当 n 在 int 范围内时，输出的位数最大值为（ ）。 {{ select(21) }}

• 29
• 30
• 31
• 32

---

阅读程序（2）：

#include <iostream>
using namespace std;

int equationCount(int n, int m) {
    if (n == 1 || m == 1) return 1;
    if (n < m) return equationCount(n, n);
    if (n == m) return 1 + equationCount(n, n - 1);
    return equationCount(n, m - 1) + equationCount(n - m, m);
}

int main() { // 本题不需要考虑数值溢出的可能性
    int n;
    cin >> n;
    cout << equationCount(n, n) << endl;
    return 0;
}

22. （1分）输入的n必须为正整数，否则程序无法正常运行。 {{ select(22) }}

• 正确
• 错误

---

23. 去掉 if (n == m) return 1 + equationCount(n, n - 1); 这句，对输出无影响。（ ） {{ select(23) }}

• 正确
• 错误

---

24. 若主函数改为调用 equationCount(n, n + 1)，不影响程序运行结果。 {{ select(24) }}

• 正确
• 错误

---

25. 去掉 if (n < m) return equationCount(n, n); 这句，对输出无影响。 {{ select(25) }}

• 正确
• 错误

---

26. 输入7时，输出结果为（ ）。 {{ select(26) }}

• 12
• 13
• 14
• 15

---

27. 该算法的时间复杂度为（ ）。 {{ select(27) }}

• $O(\log n)$
• $O(n)$
• $O(n^{2})$
• 以上都不是

---

阅读程序（3）：

#include <iostream>
using namespace std;
const int maxn = 100000;
int a[maxn], b[maxn], n;

int Search(int num, int low, int high) {
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (num >= b[mid]) low = mid + 1;
        else high = mid - 1;
    }
    return low;
}

int main() {
    int len, pos;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    b[1] = a[1];
    len = 1;
    for (int i = 2; i <= n; i++) {
        if (a[i] >= b[len]) {
            b[++len] = a[i];
        } else {
            pos = Search(a[i], 1, len);
            b[pos] = a[i];
        }
    }
    cout << len << endl;
    return 0;
}

28. 输入的 $a[i]$ 必须在 $[1,n]$ 范围内。 {{ select(28) }}

• 正确
• 错误

---

29. 把 if (num >= b[mid]) low = mid + 1; 中的 mid+1 改成 mid，不影响程序运行结果。 {{ select(29) }}

• 正确
• 错误

---

30. 当数组 a 单调不降时，输出为 1。 {{ select(30) }}

• 正确
• 错误

---

31. 数组 b 内的元素始终单调不降。 {{ select(31) }}

• 正确
• 错误

---

32. 若输入以下数据，则输出为（ ）。

20
1 2 0 1 2 1 9 3 1 8 4 1 7 5 1 6 6 1 5 7 1 4 8 1 3 9 1 2 10 1 1

{{ select(32) }}

• 1
• 10
• 11
• 20

---

33. 该算法的时间复杂度为（ ）。 {{ select(33) }}

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

---

完善程序（1）：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000000
#define N 2005
#define M 2000005

int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') { f = -1; ch = getchar(); }
        while (ch >= '0' && ch <= '9') {
            x = x * 10 + ch - '0'; ch = getchar();
        }
    }
    return x * f;
}

int n, m;
int h[N], s[N], q[N];
int u[M], d[M], L[M], R[M], C[M], X[M];

void del(int c) {
    ①
    ②
    for (int i = d[c]; i != c; i = d[i])
        for (int j = R[i]; j != i; j = R[j])
            u[d[j]] = d[u[j]] = j, s[C[j]]--;
}

void add(int c) {
    L[R[c]] = R[L[c]] = c;
    for (int i = u[c]; i != c; i = u[i])
        for (int j = L[i]; j != i; j = L[j])
            u[d[j]] = d[u[j]] = j, s[C[j]]++;
}

void link(int r, int c) {
    static int size = 0; size++;
    X[size] = r; C[size] = c;
    s[c]++;
    d[size] = d[c];
    u[size] = c;
    u[d[size]] = d[u[size]] = size;
    if (h[r] == -1) h[r] = L[size] = R[size] = size;
    else {
        R[size] = R[h[r]];
        L[size] = h[r];
        L[R[size]] = R[L[size]] = size;
    }
}

bool dance(int k) {
    if (R[0] == 0) {
        printf("%d", k);
        for (int i = 1; i <= k; i++) printf("%d", X[q[i]]);
        puts("");
        return 1;
    }
    int mn = inf, c;
    for (int i = R[0]; i; i = R[i])
        if (s[i] < mn) mn = s[i], c = i;
    ③
    for (int i = d[c]; i != c; i = d[i]) {
        q[k + 1] = i;
        for (int j = R[i]; j != i; j = R[j]) ④
        if (dance(k + 1)) return 1;
        for (int j = L[i]; j != i; j = L[j]) ⑤
    }
    add(c);
    return 0;
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 0; i <= m; i++) {
            d[i] = u[i] = i;
            L[i + 1] = i; R[i] = i + 1; s[i] = 0;
        }
        R[m] = 0; size = m;
        int x, y;
        for (int i = 1; i <= n; i++) {
            h[i] = -1;
            x = read();
            while (x--) {
                y = read();
                link(i, y);
            }
        }
        if (!dance(0)) puts("NO");
    }
    return 0;
}

34. ①处应填（ {{ select(34) }}

• L[L[c]] = R[c];
• L[R[c]] = L[c];
• R[L[c]] = R[c];
• R[R[c]] = L[c];

---

35. ②处应填（ {{ select(35) }}

• L[L[c]] = R[c];
• L[R[c]] = L[c];
• R[L[c]] = R[c];
• R[R[c]] = L[c];

---

36. ③处应填（ {{ select(36) }}

• del(c);
• add(c);
• del(mn);
• add(mn);

---

37. ④处应填（ {{ select(37) }}

• add(j);
• del(j);
• add(C[j]);
• del(C[j]);

---

38. ⑤处应填（ {{ select(38) }}

• add(j);
• del(j);
• add(C[j]);
• del(C[j]);

---

完善程序（2）：

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

const int inf = 0x3f3f3f3f;
const int maxn = 1005;
struct Node { int to, w, next; } edge[maxn * 2];
int head[maxn], tot, n, dis[maxn];
bool vis[maxn];
int que[maxn], first, last;

void init() {
    memset(head, -1, sizeof(head));
    tot = 0;
}

void addedge(int u, int v, int w) {
    edge[tot].to = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot++;
}

int BFS(int u) {
    first = last = 0;
    memset(dis, inf, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[u] = 0; vis[u] = 1;
    que[last++] = u;
    while (①) {
        u = que[first++];
        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if (②) {
                vis[v] = 1;
                que[last++] = v;
                ③
            }
        }
    }
    int tmp = 1;
    for (int i = 2; i <= n; i++)
        if (④) tmp = i;
    return tmp;
}

int main() {
    int u, v, w, s, t;
    cin >> n;
    init();
    for (int i = 1; i < n; i++) {
        cin >> u >> v >> w;
        addedge(u, v, w);
        addedge(v, u, w);
    }
    s = BFS(1);
    ⑤
    cout << dis[t] << endl;
    return 0;
}

39. ①处应填（ {{ select(39) }}

• first < last
• first <= last
• first < last - 1
• last == n

---

40. ②处应填（ {{ select(40) }}

• !vis[v]
• vis[v]
• vis[u]
• dis[v]

---

41. ③处应填（ {{ select(41) }}

• dis[v] = dis[u] + 1;
• dis[v] = dis[u] + edge[i].w;
• dis[u] = dis[v] + 1;
• dis[u] = dis[v] + edge[i].w;

---

42. ④处应填（ {{ select(42) }}

• dis[i] < dis[tmp]
• dis[i] < tmp
• dis[i] > dis[tmp]
• dis[i] == tmp

---

43. ⑤处应填（ {{ select(43) }}

• t = BFS(1);
• t = BFS(t);
• s = BFS(t);
• t = BFS(s);

---