---

1. 今有一空栈 $S$ ，对下列待进栈的数据元素序列1,2,3,4,5,…进行以“进栈、进栈、出栈、进栈、进栈、出栈”为一轮的操作，一直操作下去，那么在2019轮操作后， $S$ 的栈顶元素为（）。 {{ select(1) }}

• 10090
• 10094
• 10100
• 10086

---

2. 对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找，等概率的情况下，查找成功的平均查找长度（平均比较次数）是（）。 {{ select(2) }}

• 35/11
• 34/11
• 3
• 34/10

---

3. 以下选项中各有三个数，其中第一个为八进制数，第二个为十进制数，第三个为十六进制数。以下选项中三个数相同的是（）。 {{ select(3) }}

• 120 82 50
• 144 100 68
• 300 200 C8
• 176 210 103F2

---

4. 将{2,6,10,17}分别存储到某个地址区间为0~10的哈希表中，如果哈希函数 $h(x) = （）$，将不会产生冲突。 {{ select(4) }}

• $x \bmod 11$
• $x^2 \bmod 11$
• $2x \bmod 11$
• $\lfloor \sqrt{x} \rfloor \bmod 11$

---

5. 二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么有12个顶点的二分图至多有（）条边。 {{ select(5) }}

• 18
• 24
• 36
• 66

---

6. 有一个含有 $k$ 个不同的数的数组 $S = \{x_1,x_2,\dots,x_k\}$ 。若在 $S$ 中有一个数 $x_i$ ( $1< i< k$ )使得 $x_1< x_2< \dots < x_i > x_{i+1} > \dots >x_k$ ，则称 $x_i$ 为 $S$ 的“峰顶”， $S$ 称为单峰的。下面有几行伪代码，请将a~e五处代码填入算法之中，使得算法能正确找到 $S$ 的峰顶。

a. S[mid] < S[mid+1] b. S[mid] > S[mid+1] c. Search(1, mid-1) d. Search(mid+1, k) e. return S[mid]

Search(1,k) {
    mid = k/2
    if (S[mid] > S[mid-1] && ___) {
        ...
    } else if (S[mid] > S[mid-1] && ___) {
        ...
    } else {
        ...
    }
}

正确的填空顺序是( )。 {{ select(6) }}

• a,c,b,d,e
• a,d,b,c,e
• b,e,a,d,c
• b,e,a,c,d

---

7. 如果不在快速排序中引入随机化, 可能导致的后果是( )。 {{ select(7) }}

• 数组访问越界
• 陷入死循环
• 排序结果错误
• 排序时间退化为平方级

---

8. 二进制数-1101010的补码是( )。 {{ select(8) }}

• 0010101
• 10010110
• 10010101
• 01101010

---

9. 设二进制数 $x$ 的值是11001101。若想通过 $x \& y$ 运算使 $x$ 中的低4位不变, 高4位清零, 则 $y$ 的二进制数是( )。 {{ select(9) }}

• 11110000
• 00001100
• 00001111
• 00000010

---

10. 循环链表的主要优点是( )。 {{ select(10) }}

• 不需要头指针
• 已知某个节点的位置后, 能很容易地找到它的直接前驱节点
• 在进行删除操作后, 能保证链表不断开
• 从表中任一节点出发都能遍历整个链表

---

11. 若某算法的计算时间表示为递推关系式 $T(N) = N + T(N / 2)$ , 则该算法的时间复杂度为( )。 {{ select(11) }}

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

---

12. 若某算法的计算时间表示为递推关系式 $T(n) = 3T(n / 4) + n \log_2 n$ , 则该算法的时间复杂度为( )。 {{ select(12) }}

• $O(n)$
• $O(n \log_2 n)$
• $O(n \log_2^2 n)$
• $O(n \log_3^2 n)$

---

13. 由5个不同的节点构成的无根树有( )种。 {{ select(13) }}

• 3125
• 125
• 32
• 1024

---

14. 2019年10月14日是星期一, 1978年10月14日是( )。 {{ select(14) }}

• 星期日
• 星期五
• 星期一
• 星期六

---

15. 有9个顶点的简单无向连通图最多有( )条边。 {{ select(15) }}

• 40
• 81
• 72
• 36

---

阅读程序（1）：

#include <iostream>
using namespace std;
int n,m,i,j,a,b,head,tail,ans;
int graph[100][100];
int degree[100];
int len[100];
int queue[100];
int main() {
    cin >> n >> m;
    for (i=0; i<n; i++)
        for (j=0; j<n; j++) graph[i][j] = 0;
    for (i=0; i<n; i++) degree[i] = 0;
    for (i=0; i<m; i++) {
        cin >> a >> b;
        graph[a][b]=1;
        degree[b]++;
    }
    tail = 0;
    for (i=0; i<n; i++)
        if (!degree[i]) {
            queue[tail] = i;
            tail++;
        }
    head=0;
    while (tail < n) {
        for (i=0; i<n; i++)
            if (graph[queue[head]][i] == 1) {
                degree[i]--;
                if (degree[i] == 0) {
                    queue[tail] = i;
                    tail++;
                }
            }
        ++head;
    }
    ans = 0;
    for (i=0; i<n; i++) {
        a = queue[i];
        len[a] = 1;
        for (j=0; j<n; j++)
            if (graph[j][a] == 1 && len[j] + 1 > len[a])
                len[a] = len[j] + 1;
        if (len[a] > ans) ans = len[a];
    }
    cout << ans << endl;
    return 0;
}

16. 输入时若将 degree[b]++ 改为 degree[a]++，则运行结果不变。（） {{ select(16) }}

• 正确
• 错误

---

17. 该程序的时间复杂度是 $O(n)$ 。（） {{ select(17) }}

• 正确
• 错误

---

18. 删除主函数开头对 graph 和 degree 执行清零操作的代码，程序输出不变。（） {{ select(18) }}

• 正确
• 错误

---

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

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

{{ select(19) }}

• 正确
• 错误

---

20. graph 存储的是（）。 {{ select(20) }}

• 用邻接矩阵存储的图结构
• 每个节点的入度
• 拓扑排序结果
• 以各节点为终点的最长路径长度

---

21. 这个程序使用了（）。 {{ select(21) }}

• 基数排序
• 归并排序
• 拓扑排序
• 堆排序

---

阅读程序（2）：

#include <iostream>
#include <cstring>
#define LL long long
using namespace std;
LL l, r, f[12][10][10][2][2][2], a[20];
LL Dfs(LL now, LL p, LL pp, LL _4, LL _8, LL top, LL hw) {
    if (_4 && _8) return 0;
    if (!now) return hw;
    if (!top && f[now][p][pp][_4][_8][hw] != -1)
        return f[now][p][pp][_4][_8][hw];
    LL Up = top ? a[now] : 9;
    LL ret(0);
    for (LL i=0; i<=Up; ++i)
        ret += Dfs(now-1, i, p, _4|(i==4), _8|(i==8),
                   top && (i == Up), hw|(i==pp && i==p));
    if (!top) f[now][p][pp][_4][_8][hw] = ret;
    return ret;
}

inline LL Solve(LL x) {
    LL tot(0);
    while (x) {
        a[++tot] = x%10;
        x /= 10;
    }
    if (tot != 11) return 0;
    LL ret(0);
    for (LL i=1; i<=a[tot]; ++i)
        ret += Dfs(tot-1, i, 0, (i==4), (i==8), i==a[tot], 0);
    return ret;
}

int main() {
    cin >> l >> r;
    memset(f, -1, sizeof(f));
    cout << Solve(r) - Solve(l-1) << endl;
    return 0;
}

22. 同时包含4和8的数都不可能被统计。 {{ select(22) }}

• 正确
• 错误

---

23. 相邻数位中，超过3个数位相同的数都不可能被统计。 {{ select(23) }}

• 正确
• 错误

---

24. 下列选项中，（ ）是合法（可能会被统计）的数。 {{ select(24) }}

• 2323234823
• 1015400080
• 2333333333
• 10010012022

---

25. 当输入 12121284000 1212121285550 时，程序输出结果为（ ）。 {{ select(25) }}

• 5
• 457
• 455
• 6

---

阅读程序（3）：

#include <iostream>
using namespace std;

int main() {
    int n, i, j, x, y, nx, ny;
    int a[40][40];
    for (i=0; i<40; i++)
        for (j=0; j<40; j++) a[i][j] = 0;
    cin >> n;
    y = 0;
    x = n-1;
    n = 2 * n - 1;
    for (i=1; i<=n*n; i++) {
        a[y][x] = i;
        ny = (y-1+n) % n;
        nx = (x+1) % n;
        if ((y == 0 && x == n-1) || a[ny][nx] != 0)
            y = y + 1;
        else {
            y = ny; x = nx;
        }
    }
    for (j=0; j<n; j++) cout << a[0][j] << " ";
    cout << endl;
    return 0;
}

26. 输入n时，输出的数字个数为2n。 {{ select(26) }}

• 正确
• 错误

---

27. 输入1时，结果为1。 {{ select(27) }}

• 正确
• 错误

---

28. 若输入3，则输出是（）。 {{ select(28) }}

• 17 24 1 8 15
• 1 8 24 17 15
• 15 24 17 8 1
• 24 17 8 1 15

---

29. 若输入5，则输出的个数是（）。 {{ select(29) }}

• 6
• 9
• 8
• 5

---

30. 若输入4，则输出结果的总和是（）。 {{ select(30) }}

• 175
• 200
• 150
• 120

---

31. 若输入2，则输出是（）。 {{ select(31) }}

• 8 6 1
• 8 1 6
• 6 1 8
• 1 8 6

---

完善程序（1）：

#include <cstdio>
using namespace std;
const int MAXN = 1025;
int a[MAXN][MAXN], m;

int main() {
    scanf("%d", &m);
    int n = 1 << m, k = 1, half = 1;
    ①;
    while (k <= m) {
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half; j++) {
                a[i][j+half] = ③;
            }
        }
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half; j++) {
                a[i+half][j] = ④;
                a[i+half][j+half] = a[i][j];
            }
        }
        ⑤;
        k++;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            printf("%d", a[i][j]);
        putchar('\n');
    }
    return 0;
}

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

• a[0][1] = 1
• a[0][0] = 1
• a[1][0] = 1
• a[1][1] = 1

---

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

• i
• i+half
• j
• j+half

---

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

• a[i][j] - half
• a[i][j+1] - half
• a[i][j] + half
• a[i][j+1] + half

---

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

• a[i][j+half]
• a[i+half][j+half]
• a[i+half][j]
• a[i][j]

---

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

• half = 1
• half = 2
• half += 2
• half -= 2

---

完善程序（2）：

#include <bits/stdc++.h>
using namespace std;
int fa[30001], front[30001], num[30001], x, y, i, j, n, T, ans;
char ins;

int find(int n) {
    if (fa[n] == n) return fa[n];
    int fn = find(fa[n]);
    ①;
    return fa[n] = fn;
}

int main() {
    cin >> T;
    for (i=1; i<=30000; ++i) {
        fa[i] = i;
        ②;
        num[i] = 1;
    }
    while (T--) {
        cin >> ins >> x >> y;
        int fx = find(x), fy = find(y);
        if (ins == 'M') {
            front[fx] += num[fy];
            fa[fx] = fy;
            ③;
            num[fx] = 0;
        }
        if (ins == 'C') {
            if (④)
                cout << "-1" << endl;
            else
                cout << ⑤ << endl;
        }
    }
    return 0;
}

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

• front[n] += front[fa[n]]
• front[n] += front[n]
• front[fa[n]] += front[n]
• front[fa[n]] += front[fa[n]]

---

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

• front[i] = 1
• front[i] = 0
• front[i] = i
• front[fa[i]] = 0

---

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

• num[fx] += num[fy]
• num[fy] += num[fy]
• num[fx] += num[fx]
• num[fy] += num[fx]

---

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

• fx > fy
• fx == fy
• fx < fy
• fx != fy

---

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

• abs(front[x] - front[y]) - 1
• abs(front[x] - front[y]) + 1
• abs(front[num[x]] - front[num[y]]) - 1
• abs(front[num[x]] - front[num[y]]) + 1

---