一、单项选择（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. 在计算机中，一个 ASCII 字符通常占用 1 个字节。则 1KB 的存储空间最多可以存储（ ）个 ASCII 字符。 {{ select(1) }}

• $1000$
• $1024$
• $2048$
• $8192$

2. 十进制小数 $0.625$ 对应的二进制小数为（ ）。 {{ select(2) }}

• $0.101$
• $0.110$
• $0.011$
• $0.1001$

3. 执行下列代码后，输出的结果是（ ）。

int a = 0, b = 1;
if (a && b++)
    b++;
cout << b;

{{ select(3) }}

• $0$
• $1$
• $2$
• $3$

4. 现有一张分辨率为 $1920\times1080$ 像素的 $24$ 位真彩色图像。要存储这张图像，需要的存储空间最接近（ ）。 {{ select(4) }}

• $2$ MB
• $4$ MB
• $6$ MB
• $8$ MB

5. 对于入栈顺序为 $1,2,3,4,5$ 的序列，下列（ ）不是合法的出栈序列。 {{ select(5) }}

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

6. 一个无向简单图有 $8$ 个顶点，每个顶点的度数都为 $3$，则该图有（ ）条边。 {{ select(6) }}

• $8$
• $12$
• $16$
• $24$

7. 一个盒子中有 $5$ 双不同颜色的袜子（共 $10$ 只，同一双的两只颜色相同），闭上眼睛至少取出（ ）只袜子，才能保证取出的袜子中有 $2$ 只颜色相同。 {{ select(7) }}

• $2$
• $5$
• $6$
• $9$

8. 用 $5$ 个权值 $5,6,7,8,15$ 构造哈夫曼树，该树的带权路径长度为（ ）。 {{ select(8) }}

• $82$
• $93$
• $104$
• $117$

9. 执行下列代码后，a 和 b 的值分别为（ ）。

int a = 5, b = 3;
a = a ^ b;
b = a ^ b;
a = a ^ b;

{{ select(9) }}

• a=3, b=5
• a=5, b=3
• a=0, b=8
• a=8, b=0

10. 已知递归函数定义为：

int f(int n) {
    if (n <= 1) return 1;
    if (n % 2 == 0) return f(n - 1) + f(n / 2);
    return 2 * f(n - 1) - f(n - 2);
}

则 f(8) 的返回值为（ ）。 {{ select(10) }}

• $13$
• $18$
• $21$
• $34$

11. 已知某二叉树的前序遍历为 FBADCEG，中序遍历为 ABCDFEG，则该二叉树的后序遍历为（ ）。 {{ select(11) }}

• ACDBGEF
• ACDBEGF
• ADCGBEF
• ACBDGEF

12. 用选择排序对数组 $\{5,3,4,1,2\}$ 进行升序排序，第一趟（选出最小元素与第一个元素交换）完成后，数组变为（ ）。 {{ select(12) }}

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

13. 把 $12$ 个完全相同的小球放入 $4$ 个不同的盒子中，要求每个盒子至少放 $1$ 个，共有（ ）种不同的放法。 {{ select(13) }}

• $165$
• $220$
• $286$
• $495$

14. 一个 $6\times7$ 的网格，左上角坐标为 $(1,1)$，右下角为 $(6,7)$。一个机器人从 $(1,1)$ 出发，每次只能向右或向下走一格，到达 $(5,6)$ 共有（ ）种不同的路径。 {{ select(14) }}

• $84$
• $126$
• $210$
• $252$

15. 给定一个初始为空的整数栈 $S$ 和一个空的队列 $P$。按顺序处理输入队列 $A: 6,3,9,4,1,8,5$。对于 $A$ 中的每一个数：如果该数是奇数，则将其压入栈 $S$；如果该数是偶数，且栈 $S$ 非空，则弹出一个栈顶元素加入队列 $P$ 末尾；如果该数是偶数且栈 $S$ 为空，则不进行任何操作。当 $A$ 中所有数都处理完毕后，队列 $P$ 的内容是（ ）。 {{ select(15) }}

• $9,1$
• $3,5$
• $9,1,3$
• $3,9,1$

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 A，错误填 B；除特殊说明外，判断题每题 2 分，选择题每题 3 分，共 40 分）

第 1 题

#include <iostream>
using namespace std;
const int N = 1000005;
int n, m, x, a[N];

int find(int x) {
    int l = 1, r = n, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        if (a[mid] <= x)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return a[l] == x ? l : -1;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) {
        cin >> x;
        cout << find(x) << ' ';
    }
    return 0;
}

数据保证 $1\le n,m\le 10^6$，$a[i]$ 在 int 范围内，每个询问的 $x$ 均为正整数。

16. find 函数使用的算法是二分查找。（ ） {{ select(16) }}

• 正确
• 错误

17. 若输入的数组 a 是单调不增的，则程序能对任意正整数 $x$ 正确输出 $x$ 第一次出现的下标（不存在时输出 -1）。（ ） {{ select(17) }}

• 正确
• 错误

18. 若输入的数组 a 是单调不减的，程序依然可以正确找到 $x$ 第一次出现的下标。（ ） {{ select(18) }}

• 正确
• 错误

19. 当输入为：

6 2
10 8 8 6 5 2
8 5

时，程序输出为（ ）。 {{ select(19) }}

• 2 5
• 2 6
• 3 5
• 2 4

20. （4 分）当输入的数组 a 单调不增且 $x$ 在数组中出现多次时，程序返回的是（ ）。 {{ select(20) }}

• $x$ 第一次出现的下标
• $x$ 最后一次出现的下标
• 任意一次出现的下标
• -1

第 2 题

#include <cstdio>
using namespace std;
int n, r, num[10005];
bool mark[10005];

void print() {
    for (int i = 1; i <= r; i++) printf("%d ", num[i]);
    printf("\n");
}

void search(int x) {
    for (int i = 1; i <= n; i++)
        if (!mark[i]) {
            num[x] = i;
            mark[i] = true;
            if (x == r) print();
            search(x + 1);
            mark[i] = false;
        }
}

int main() {
    scanf("%d%d", &n, &r);
    search(1);
    return 0;
}

数据保证 $1\le n,r\le 10000$。

21. 若 $n < r$，则程序没有任何输出。（ ） {{ select(21) }}

• 正确
• 错误

22. 程序结束时，对任意 $1\le i\le n$，mark[i] 均为 false。（ ） {{ select(22) }}

• 正确
• 错误

23. 此程序的时间复杂度为 $O(n)$。（ ） {{ select(23) }}

• 正确
• 错误

24. 若输入为 6 2，则 print 函数执行的次数为（ ）。 {{ select(24) }}

• $15$
• $30$
• $36$
• $60$

25. （4 分）若输入为 5 3，则输出的最后一行为（ ）。 {{ select(25) }}

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

第 3 题

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 305;
const int INF = 0x3f3f3f3f;
int n, stone[MAXN], sum[MAXN];
int dp[MAXN][MAXN];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> stone[i];
        sum[i] = sum[i - 1] + stone[i];
    }
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n; i++) dp[i][i] = 0;
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for (int k = i; k < j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
        }
    cout << dp[1][n] << endl;
    return 0;
}

数据保证 $1\le n\le 300$，$1\le stone[i]\le 300$。

26. 当输入为 2 和 1 2 时，程序输出的结果为 3。（ ） {{ select(26) }}

• 正确
• 错误

27. 当输入的 $n=1$ 时，程序会输出 0。（ ） {{ select(27) }}

• 正确
• 错误

28. （3 分）程序的时间复杂度为 $O(n^3)$。（ ） {{ select(28) }}

• 正确
• 错误

29. 下列输入中，程序输出结果与其他三项不同的是（ ）。 {{ select(29) }}

• 3 和 1 1 1
• 2 和 2 3
• 2 和 1 4
• 3 和 1 1 2

30. （4 分）输入为 4 和 3 1 4 2 时，程序输出的结果为（ ）。 {{ select(30) }}

• $18$
• $20$
• $22$
• $24$

三、完善程序（单选题，每小题 3 分，共计 30 分）

（1）区间覆盖

已知数轴上每个整数都算一个点，给出 $n$ 个闭区间，求它们一共覆盖了数轴上多少个整数点。

例如：区间 $[1,2]$ 和区间 $[2,3]$，一共覆盖了 $1,2,3$ 共 $3$ 个整数点。保证 $1\le n\le 10^6$，每个区间的端点 $st,ed$ 均为整数且 $-10^6\le st\le ed\le 10^6$。试补全程序。

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

const int MAXN = 1e6 + 5;

struct node {
    int st, ed;
} a[MAXN];

bool cmp(node a, node b) {
    return ①;
}

int n, ans;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].st >> a[i].ed;
    }
    sort(a, a + n, cmp);
    int ②;
    ③ {
        if (a[i].ed >= st) {
            ed = max(ed, a[i].ed);
            st = min(st, a[i].st);
        } else {
            ans += ④;
            st = a[i].st, ed = a[i].ed;
        }
    }
    cout << ⑤;
    return 0;
}

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

• a.st < b.st
• a.st > b.st
• a.ed < b.ed
• a.ed > b.ed

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

• st = a[0].st, ed = a[0].ed
• st = a[1].st, ed = a[1].ed
• st = a[n - 1].st, ed = a[n - 1].ed
• st = a[n].st, ed = a[n].ed

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

• for (int i = 1; i < n; i++)
• for (int i = 1; i <= n; i++)
• for (int i = n; i > 0; i--)
• for (int i = n - 1; i > 0; i--)

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

• ed - st
• ed - st + 1
• a[i].ed - a[i].st
• a[i].ed - a[i].st + 1

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

• ans
• ans + 1
• ans + ed - st
• ans + ed - st + 1

（2）火场逃生

在 $n\times m$ 的网格中，存在：

• F：初始着火点（可能有多个）；
• S：逃生者起点（唯一）；
• #：墙（火和人都无法通过）；
• .：可通行区域。

初始是第 0 秒。每秒钟，所有着火的格子先向四连通方向蔓延一格，然后逃生者可向四连通方向移动一格。如果逃生者移动到的格子已经着火，他会死亡。逃生者到达边界格子后即可安全离开网格（不再受火势影响），求所需的最短时间，若无法到达输出 -1。保证 $1\le n,m\le 1000$。试补全程序。

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

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, ①};

struct Node {
    int x, y, t;
};

int n, m;
char grid[MAXN][MAXN];
int ft[MAXN][MAXN];
bool vis[MAXN][MAXN];
queue<Node> fq;
queue<Node> q;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            ft[i][j] = INF;
            if (grid[i][j] == ②) {
                fq.push((Node){i, j, 0});
                ft[i][j] = 0;
            } else if (grid[i][j] == 'S') {
                q.push((Node){i, j, 0});
                vis[i][j] = true;
            }
        }

    while (!fq.empty()) {
        Node cur = fq.front();
        fq.pop();
        int i = cur.x, j = cur.y;
        for (int d = 0; d < 4; d++) {
            int ni = i + dirs[d][0], nj = j + dirs[d][1];
            if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] != '#' && ③) {
                ft[ni][nj] = ft[i][j] + 1;
                fq.push((Node){ni, nj, 0});
            }
        }
    }

    while (!q.empty()) {
        Node cur = q.front();
        q.pop();
        int i = cur.x, j = cur.y, t = cur.t;

        if (④) {
            cout << t + 1 << endl;
            return 0;
        }

        for (int d = 0; d < 4; d++) {
            int ni = i + dirs[d][0], nj = j + dirs[d][1];
            if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] != '#' && !vis[ni][nj] && ⑤) {
                vis[ni][nj] = true;
                q.push((Node){ni, nj, t + 1});
            }
        }
    }

    cout << -1 << endl;
    return 0;
}

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

• {0, 1}
• {1, 1}
• {-1, 1}
• {0, -1}

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

• 'F'
• 'S'
• '#'
• '.'

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

• ft[ni][nj] > ft[i][j]
• ft[ni][nj] > ft[i][j] + 1
• ft[ni][nj] != INF
• !vis[ni][nj]

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

• (i == 0 || i == n - 1) && (j == 0 || j == m - 1)
• (i >= 0 || i <= n - 1) && (j >= 0 || j <= m - 1)
• i == 0 || i == n - 1 || j == 0 || j == m - 1
• i != 0 || i != n - 1 || j != 0 || j != m - 1

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

• t < ft[ni][nj]
• t < ft[ni][nj] + 1
• t + 1 <= ft[ni][nj]
• t + 1 < ft[ni][nj]