---

1. 十进制的 160.5 相当于十六进制的（ ）。 {{ select(1) }}

• A0.8
• F.5
• 80.25
• 无限小数

---

2. 在具有 $2n$ 个节点的完全二叉树中，叶节点的个数为（ ）。 {{ select(2) }}

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

---

3. 6 个棋子围成一圈，每个棋子可染黑色或白色，通过旋转可重合的算一种方案，则一共有（ ）种着色方案。 {{ select(3) }}

• 32
• 20
• 16
• 14

---

4. 假设 $x$ 和 $y$ 是两个独立的随机实数变量，且它们都是从 $[0, 1]$ 的均匀分布里随机生成的，则 $\min(x,y)$ 的期望值是（ ）。 {{ select(4) }}

• $1/4$
• $1/3$
• $1/2$
• 不是有理数

---

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

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

---

6. 在单链表指针 p 指向的节点后，插入指针 s 指向的节点，正确的操作是（ ）。 {{ select(6) }}

• p->next = s; s->next = p->next;
• s->next = p->next; p->next = s;
• p->next = s; p->next = s->next;
• p->next = s->next; p->next = s;

---

7. 前缀表达式 + 3 * 2 + 5 12 的值是（ ）。 {{ select(7) }}

• 23
• 37
• 33
• 35

---

8. 若在某进制下 $7 \times 7 = 41$ 成立，那么在该进制下 $12 \times 12 =$（ ）。 {{ select(8) }}

• 144
• 100
• E4
• 81

---

9. 寄存器是（ ）的重要组成部分。 {{ select(9) }}

• 硬盘
• 高速缓存
• 内存
• 中央处理器（CPU）

---

10. 无向图 $G = (V,E)$，其中 $V = \{A_0,A_1,A_2,A_3,A_4\}$，$E = \{(A_0,A_1),(A_0,A_2),(A_0,A_3),(A_1,A_3)\}$。以 $A_0$ 为起点进行深度优先搜索，遍历顺序不可能是（ ）。 {{ select(10) }}

• $A_0,A_1,A_2,A_3$
• $A_0,A_1,A_3,A_2$
• $A_0,A_2,A_1,A_3$
• $A_0,A_3,A_1,A_2$

---

11. 双向链表的节点包含两个指针域，llink 和 rlink，分别指向其前驱节点和后继节点。设 p 指向链表中的一个节点，q 指向一待插入节点。现要求在 p 前插入 q，则正确的插入操作为（ ）。 {{ select(11) }}

• p->llink = q; q->rlink = p; p->llink->rlink = q; q->llink = p->llink;
• q->llink = p->llink; p->llink->rlink = q; q->rlink = p; p->llink = q;
• q->rlink = p; p->rlink = q; p->llink->rlink = q; q->llink = p->llink;
• p->llink->rlink = q; q->rlink = p; q->llink = p->llink; p->llink = q;

---

12. 有向图 $G=(V,E)$，其中 $V=\{A_0,A_1,A_2,A_3,A_4\}$，从顶点 $A_0$ 出发进行广度优先搜索（BFS），一种可行顺序是 $A_0,A_4,A_2,A_3,A_1$。我们以 $(x,y)$ 表示 $x$ 指向 $y$ 的有向边，则边集 $E$ 可能是（ ）。 {{ select(12) }}

• $\{(A_0,A_1),(A_0,A_2),(A_0,A_3),(A_0,A_4),(A_2,A_1),(A_2,A_3)\}$
• $\{(A_0,A_1),(A_0,A_3),(A_1,A_2),(A_2,A_3),(A_3,A_4)\}$
• $\{(A_0,A_1),(A_0,A_2),(A_0,A_4),(A_2,A_1),(A_2,A_3),(A_3,A_4)\}$
• $\{(A_0,A_1),(A_0,A_2),(A_0,A_3),(A_2,A_1),(A_2,A_3),(A_3,A_4)\}$

---

13. 一棵二叉树的前序遍历序列是 ABCDEFG，后序遍历序列是 CBFEGDA，则根节点的左子树的节点个数可能是（ ）。 {{ select(13) }}

• 0
• 2
• 4
• 6

---

14. 由3个 a、5个 b 和2个 c 构成的所有字符串中，包含子串 abc 的共有（ ）个。 {{ select(14) }}

• 840
• 820
• 800
• 780

---

15. 拓扑排序是指将将有向无环图 $G$ 中的所有顶点排成一个线性序列，使得对于图中任意一对顶点 $u$ 和 $v$，若从 $u$ 到 $v$ 有边，则 $u$ 在线性序列中出现在 $v$ 之前。这样的线性序列称为拓扑序列。对有向无环图 $G=(V,E)$，$V=\{1,2,3,4,5,6,7,8,9\}$，$E=\{(1,2),(1,5),(2,3),(3,4),(3,7),(4,6),(7,6),(8,9)\}$，可能的拓扑序列的个数为（ ）。 {{ select(15) }}

• 336
• 432
• 96
• 343

---

阅读程序（1）：

#include <iostream>
using namespace std;

int n;

int main() {
    cin >> n; // 保证输入为正整数
    int ans = n;
    for (int i = 2; i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            ans = ans / i * (i - 1);
        }
    }
    cout << ans << endl;
    return 0;
}

16. （1分）该算法的时间复杂度为 $O(n)$。 {{ select(16) }}

• 正确
• 错误

---

17. （1分）输出的数一定不会比 n 大。 {{ select(17) }}

• 正确
• 错误

---

18. 如果 $n > 2$，则输出一定是偶数。 {{ select(18) }}

• 正确
• 错误

---

19. 如果 $n$ 是素数，则输出就是 $n$。 {{ select(19) }}

• 正确
• 错误

---

20. 输入 1001 时，输出为（ ）。 {{ select(20) }}

• 1024
• 1000
• 720
• 512

---

21. 依次输入 $1 \sim 20$，则输出的最大值为（ ）。 {{ select(21) }}

• 10
• 12
• 15
• 18

---

阅读程序（2）：

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

int n, x[100];
string s[100];

int main() {
    while (cin >> s[++n]);
    n--;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < s[i].size(); j++)
            x[i] = x[i] * x[i] + s[i][j];
    int ans = n;
    for (int i = n; i >= 1; i--) {
        bool b = 0;
        for (int j = 1; j < i && !b; j++)
            if (x[i] == x[j]) b = true;
        ans = b;
    }
    cout << ans << endl;
    return 0;
}

22. 输入的时候如果有多行，则只会读入第一行。 {{ select(22) }}

• 正确
• 错误

---

23. 第二组 for 循环（int ans = n; 之后开始的）的时间复杂度可以优化到 $O(n \log n)$。 {{ select(23) }}

• 正确
• 错误

---

24. 如果只输入小写字母，且所有 s[i].size() <= 10，则 x[i] 最终的值都是正数。 {{ select(24) }}

• 正确
• 错误

---

25. 输入 in dzds left brain there is nothing left while in his right there is nothing right，并将第12行改为 x[i] = x[i] * x[i] * x[i] + s[i][j];，输出不会有变化。 {{ select(25) }}

• 正确
• 错误

---

26. 输入 in theory theory and practice are the same in practice they are not，输出为（ ）。 {{ select(26) }}

• 13
• 11
• 9
• 7

---

27. 以下描述中错误的是（ ）。 {{ select(27) }}

• 输出的时候，ans 的值一定不大于 n 的值
• 无须定义字符串数组也能实现同样的功能
• 输入长度为 10 的 10 个小写字母组成的单词，则输出概率最大的值是 10
• 设只输入小写字母且 s[i].size() <= 10，如果 s[j] != s[k]，则一定有 x[j] != x[k] ($1 \leq j < k \leq n$)

---

阅读程序（3）：

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

int a[1010][12], n, m, pw[12] = {1};

int main() {
    cin >> n >> m; // 保证 0 < n, m <= 1000
    for (int h = 1, p = 2; p <= n; p *= 2, h++) pw[h] = 2 * pw[h - 1];
    for (int i = 1; i <= n; i++) cin >> a[i][0];
    for (int h = 0; pw[h] <= n; h++)
        for (int i = 1; i <= n - pw[h] + 1; i++)
            a[i][h] = max(a[i][h - 1], a[i + pw[h - 1]][h - 1]);
    for (int i = 1, x, y, h; i <= m; i++) {
        cin >> x >> y; // 保证 1 <= x <= y <= n
        for (h = 0; pw[h] * 2 <= y - x + 1; ) h++;
        cout << max(a[x][h], a[y - pw[h] + 1][h]) << " "; // 利用幂等性
    }
    return 0;
}

28. 输入 $n = 100$ 时，数组 pw 中非零元素共有 7 个。 {{ select(28) }}

• 正确
• 错误

---

29. 对一组 $x = y$ 的输入，对应的输出就是 $x$。 {{ select(29) }}

• 正确
• 错误

---

30. 固定 $i$，则 a[i][h] 的值随 $h$ 单调不降，不考虑没被赋值过的位置。 {{ select(30) }}

• 正确
• 错误

---

31. 将倒数第5行中 for 循环的循环条件改为 pw[n + 1] <= y - x + 1，结果不会有变化。 {{ select(31) }}

• 正确
• 错误

---

32. 此程序的时间复杂度为（ ）。 {{ select(32) }}

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

---

33. 输入如下，输出为（ ）。

5 3
1 5 2 4 3
1 5
2 4
3 3

{{ select(33) }}

• 555
• 543
• 552
• 542

---

完善程序（1）：

#include <iostream>
using namespace std;

const int INF = 1000000;
struct node { int l, r, v; } a[100];
int n;

int check(int x, int lower_bound, int upper_bound) {
    if (x == 0) return 1;
    return ① && ② && check(③) && check(④);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].v >> a[i].l >> a[i].r;
    cout << check(⑤, -INF, INF) << endl;
    return 0;
}

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

• x > lower_bound
• x < lower_bound
• a[x].v > lower_bound
• a[x].v < lower_bound

---

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

• x > upper_bound
• x.v < upper_bound
• a[x].v > upper_bound
• a[x].v < upper_bound

---

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

• a[x].r, a[x].v, lower_bound
• a[x].r, lower_bound, a[x].v
• a[x].l, a[x].v, lower_bound
• a[x].l, lower_bound, a[x].v

---

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

• a[x].r, a[x].v, upper_bound
• a[x].r, upper_bound, a[x].v
• a[x].l, a[x].v, upper_bound
• a[x].l, upper_bound, a[x].v

---

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

• 0
• 1
• -1
• INF

---

完善程序（2）：

#include <iostream>
using namespace std;

int n, k, answerx, answery;
int a[5001][5001];

void FindKPosition() {
    int ①;
    while (j > 0) {
        if (a[n][j] < k) break;
        j--;
    }
    ②;
    while (a[i][j] != k) {
        while (③ && i > 1) i--;
        while (④ && j <= n) j++;
    }
    ⑤;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> a[i][j];
    cin >> k;
    FindKPosition();
    cout << answerx << " " << answery << endl;
    return 0;
}

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

• i=1, j=1
• i=1, j=n
• i=n, j=1
• i=n, j=n

---

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

• i++
• i--
• j++
• j--

---

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

• a[i-1][j] > k
• a[i][j] > k
• a[i-1][j] < k
• a[i][j] < k

---

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

• a[i][j+1] > k
• a[i][j] > k
• a[i][j+1] < k
• a[i][j] < k

---

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

• answerx = i, answery = j
• answerx = i, answery = j+1
• answerx = i-1, answery = j
• answerx = i-1, answery = j+1

---