---

1. 假设有以下定义：int a[5]={1,2,3,4,5}，$i = 3$，$*p = a$，$*q = a$；则不能正确执行的语句是（）。 {{ select(1) }}

• $i = *p + *q$
• $a = i$
• $*p = *(a + i)$
• $i = *p * *(q + 2)$

---

2. 下列不属于CPU的是（）。 {{ select(2) }}

• 海思麒麟990
• Intel酷睿i7
• 影驰RTX2070
• AMD Ryzen7

---

3. $(2019)_{10} + (2020)_8$ 的结果是（）。 {{ select(3) }}

• $(3049)_{10}$
• $(\mathrm{BF}3)_{10}$
• $(101111110001)_2$
• $(5765)_8$

---

4. 某二叉树的先序遍历序列和后序遍历序列正好相反，当且仅当该二叉树（）。 {{ select(4) }}

• 高度等于其节点数
• 任一节点无左子节点
• 任一节点无右子节点
• 空或只有一个节点

---

5. 若有定义 char x[] = "12345";，char y[] = {'1','2','3','4','5'};，则（）。 {{ select(5) }}

• x数组与y数组所占的内存空间相同
• x数组比y数组所占的内存空间大
• x数组比y数组所占的内存空间小
• x数组等价于y数组

---

6. 公共汽车起点站于每小时的10分、30分、55分发车，某乘客不知发车时间，在每小时的任一时刻随机到达车站，如果乘客到车站的时刻恰为发车时间就不能坐上此时发车的公共汽车，则乘客候车时间的数学期望（准确到秒）是（）。 {{ select(6) }}

• 8分40秒
• 15分20秒
• 22分30秒
• 10分25秒

---

7. 设要将序列Q,H,C,Y,P,A,M,S,R,D,F,X中的关键码按字母的升序重新排列，则（）是以第一个元素为分界元素的快速排序一趟扫描的结果。 {{ select(7) }}

• F,H,C,D,P,A,M,Q,R,S,Y,X
• P,A,C,S,Q,D,F,X,R,H,M,Y
• A,D,C,R,F,Q,M,S,Y,P,H,X
• H,C,Q,P,A,M,S,R,D,F,X,Y

---

8. 设 $G$ 是有 $n$ 个节点、$m$ 条边（$n\leq m$）的连通图，必须删去 $G$ 的（）条边才能使得 $G$ 变成一棵树。 {{ select(8) }}

• $m - n + 1$
• $m - n$
• $m + n + 1$
• $n - m + 1$

---

9. 将2个红球、1个蓝球、1个白球放到10个编号不同的盒子中去，每个盒子最多放一个球，有（）种放法。 {{ select(9) }}

• 5040
• 2520
• 1260
• 420

---

10. 一个家具公司生产桌子和椅子。现在有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要使用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要把木材用光），最多可以卖（）元钱。 {{ select(10) }}

• 140
• 150
• 160
• 170

---

11. 插入排序、冒泡排序、选择排序、快速排序的时间复杂度分别是（）。 {{ select(11) }}

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

---

12. 以下数据结构中，（）不是线性结构。 {{ select(12) }}

• 广义表
• 二叉树
• 队列
• 栈

---

13. 以下最短路径算法中，不能处理带有负边权值的是（）。 {{ select(13) }}

• Dijkstra
• Floyd
• Bellman-Ford
• SPFA

---

14. 栈 $S$ 最多能容纳4个元素。现有6个元素按1,2,3,4,5,6的顺序进栈，（）是可能的出栈序列。 {{ select(14) }}

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

---

15. 平面上有三条平行直线，每条直线上分别有7,5,6个点，且不同直线上的三个点都不在同一条直线上。以这些点为顶点，能组成（）个不同的四边形。 {{ select(15) }}

• 18
• 210
• 2250
• 4500

---

阅读程序（1）：

#include <cstdio>
using namespace std;

int findvall(int n) {
    int f;
    if (n == 0) return 1;
    else f = findvall(n/2);
    return n * f;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", findvall(n));
    return 0;
}

16. 将 findvall() 中的 if (n == 0) 改成 if (n == 1) 时，对于输入正整数n，输出不变。 {{ select(16) }}

• 正确
• 错误

---

17. 如果输入正整数n，输出的值一定小于或等于n。 {{ select(17) }}

• 正确
• 错误

---

18. 如果输入的n是负数，该程序会出现死循环。 {{ select(18) }}

• 正确
• 错误

---

19. 如果多次运行该程序，输入的n是单调递增的int类型整数，那么每次输出的结果也是一个严格单调递增的数列。 {{ select(19) }}

• 正确
• 错误

---

20. 若两次输入n的值相差1，输出的结果却是一个正数、一个负数，那么两次输入的n可能是下列选项中的（）。 {{ select(20) }}

• 不可能
• -6, -7
• -15, -16
• -23, -24

---

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

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

---

阅读程序（2）：

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

int main() {
    char str[60];
    int len, i, j, chr[26];
    char mmin = 'z';
    scanf("%s", str); // 保证输入仅含小写字母
    len = (int)strlen(str);
    for (i = len - 1; i >= 1; i--)
        if (str[i-1] < str[i]) break;
    if (i == 0) {
        printf("No_result!\n");
        return 0;
    }
    for (j = 0; j < i-1; j++) putchar(str[j]);
    memset(chr, 0, sizeof(chr));
    for (j = i; j < len; j++) {
        if (str[j] > str[i-1] && str[j] < mmin)
            mmin = str[j];
        chr[str[j]-'a']++;
    }
    chr[mmin-'a']--;
    chr[str[i-1]-'a']++;
    putchar(mmin);
    for (i = 0; i < 26; i++)
        for (j = 0; j < chr[i]; j++)
            putchar('a' + i);
    putchar('\n');
    return 0;
}

22. 输入的字符串长度应该在1..59范围内。 {{ select(22) }}

• 正确
• 错误

---

23. 如果输入的字符数组的所有字符是从大到小排好序的，那么程序会输出 No_result!。 {{ select(23) }}

• 正确
• 错误

---

24. 倒数第7行输出的 mmin 值为输入字符串里的ASCII码最小的那个字符。 {{ select(24) }}

• 正确
• 错误

---

25. 最后一组（二重）for循环是把剩下未输出的字符按照从小到大的顺序输出。 {{ select(25) }}

• 正确
• 错误

---

26. 如果输入的是 abcdzdcba，则第16行输出的是（ ）。 {{ select(26) }}

• abc
• abcd
• abcdz
• abcdzd

---

27. 如果程序输出是 ffghhghgh，则输入有可能是（ ）。 {{ select(27) }}

• ffghhghg
• ffghhhgg
• ffghhghhg
• ffghghgh

---

阅读程序（3）：

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

int a, mp[101][101];
int t[100003], y[100003], cnt;
int len = 2, dir = 3, die = 0;
const int dx[5] = {0, 0, -1, 0, 1};
const int dy[5] = {0, -1, 0, 1, 0};
int nx = 0, ny = 1, px = 1, py = 2;

int check(int x, int yy) {
    if (x < 1 || x > a || yy < 1 || yy > a) return 1;
    if (cnt + 1 - mp[x][yy] < len) return 1;
    return 0;
}

void work() {
    if (die) return;
    px += nx;
    py += ny;
    die = check(px, py);
    if (die) return;
    mp[px][py] = ++cnt;
}

void show() {
    for (int i = 1; i <= a; ++i) {
        for (int j = 1; j <= a; ++j) {
            if (mp[i][j] != 0 && mp[i][j] >= cnt - len + 1) putchar('o');
            else putchar('.');
        }
        puts("");
    }
}

int main() {
    memset(mp, 0xf0, sizeof(mp));
    mp[1][1] = ++cnt;
    mp[1][2] = ++cnt;
    int n, m, op, xx;
    char s[3];
    scanf("%d", &a);
    scanf("%d%d", &n, &m);
    while (n--) {
        scanf("%d%d", &op, &xx);
        if (op == 1) {
            t[xx] = 1;
            scanf("%s", s);
            if (s[0] == 'L') y[xx] = 1;
            else if (s[0] == 'U') y[xx] = 2;
            else if (s[0] == 'R') y[xx] = 3;
            else y[xx] = 4;
        } else {
            t[xx] = 2;
        }
    }
    for (int tm = 1; tm <= m; ++tm) {
        if (t[tm] == 1) {
            if (y[tm] % 2 != dir % 2) {
                dir = y[tm];
                nx = dx[y[tm]];
                ny = dy[y[tm]];
            }
        } else if (t[tm] == 2) {
            ++len;
        }
        work();
        if (die) break;
    }
    show();
    return 0;
}

28. 由程序代码可知，贪吃蛇的初始长度为2，蛇头和蛇尾分别在坐标[1,2]、[1,1]处。 {{ select(28) }}

• 正确
• 错误

---

29. check 函数是用来检测蛇是否吃到果实的。 {{ select(29) }}

• 正确
• 错误

---

30. 主函数中输入并存储的 y[xx] 表示在第xx秒按下了y键，y的取值为L、U、R、D之一，分别对应左、上、右、下四个方向按钮。 {{ select(30) }}

• 正确
• 错误

---

31. 当输入样例如下所示时，最终程序的运行结果表示贪吃蛇在第9秒过后就死亡了，因此最后贪吃蛇保持的是死亡前（第7秒过后）的位置。

10
10 20
2 1
2 2
2 3
2 4
2 5
1 6 R
1 7 D
1 8 L
1 9 U
2 10

{{ select(31) }}

• 正确
• 错误

---

32. （4分）若输入的地图边长为x，共执行n次操作（x>n），则该程序的时间复杂度为（ ）。 {{ select(32) }}

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

---

完善程序（1）：

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int MAXN = 1e3 + 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> P;
char s[MAXN][MAXN];
int n, m;
int dir[2][4] = {{1, -1, 0, 0}, {0, 0, 1, -1}};
int dis[2][MAXN][MAXN];

void bfs(int p, int a, int b) {
    memset(dis[p], INF, sizeof(dis[p]));
    dis[p][a][b] = 0;
    queue<pair<int, int>> q; q.push({a, b});
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int dx = x + dir[0][i], dy = y + dir[1][i];
            if (dx < 1 || dy < 1 || dx > n || dy > m || s[dx][dy] == '#') continue;
            if (①) {
                ②;
                ③;
            }
        }
    }
}

int main(void) {
    while (scanf("%d%d", &n, &m) != EOF) {
        int ans = INF;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (s[i][j] == 'S') bfs(0, i, j);
                else if (s[i][j] == 'E') ④;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (s[i][j] == 'K') ans = ⑤;
        if (ans == INF) ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}

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

• dis[p][dx][dy] > d
• dis[p][dx][dy] > d + 1
• dis[p][dx][dy] < d
• dis[p][dx][dy] < d + 1

---

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

• dis[p][dx][dy] = d
• dis[p][dx][dy] = d - 1
• dis[p][dx][dy] = d + 1
• dis[p][dx][dy] = 1

---

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

• q.push({dx, dy})
• q.push({dx, dy, d})
• q.push({dx, dy, d - 1})
• q.push({dx, dy, 1})

---

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

• bfs(0, j, i)
• bfs(1, j, i)
• bfs(0, i, j)
• bfs(1, i, j)

---

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

• min(ans, dis[0][i][j] + dis[1][i][j])
• min(ans, dis[0][j][i] + dis[1][j][i])
• min(ans, dis[0][i][j])
• min(ans, dis[1][i][j])

---

完善程序（2）：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mx = 1e6 + 10;
int n, a[mx];
ll k, sum, ans;

int main() {
    scanf("%d%lld", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    int r = 0;
    for (int i = 1; i <= n; ++i) {
        while (r < n) {
            if (①) ②;
            else break;
        }
        ③;
        if (i <= r) ④;
        else ⑤;
    }
    printf("%lld\n", ans);
    return 0;
}

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

• sum + a[r + 1] <= k
• sum + a[r] <= k
• sum + a[r + 1] < k
• sum + a[r] < k

---

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

• sum += a[r]
• sum += a[++r]
• sum += a[r++]
• sum += a[r + 1]

---

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

• ans += r - i + 1
• ans += r - i
• ans += r - j - 1
• ans += n - i + 1

---

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

• sum += a[i]
• sum = a[r]
• sum = a[i]
• sum -= a[i]

---

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

• r = ++i
• r = i--
• r = i++
• r = i

---