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

---

1. 阅读下面代码，输出结果是？

int x = 1;

for (int i = 1; i <= 4; i++)
    x = x * 2 + i;

cout << x;

{{ select(1) }}

• 31
• 42
• 46
• 63

---

2. 十六进制数 $2A_{16}$ 与二进制数 $101011_2$ 的和对应的十进制值是？

{{ select(2) }}

• 83
• 84
• 85
• 86

---

3. 阅读下面代码，输出结果是？

int x = 0, y = 0;
if (++x || ++y)
    cout << x << " " << y;

{{ select(3) }}

• 0 0
• 1 0
• 1 1
• 2 1

---

4. 阅读下面代码，输出结果是？

string s = "algorithm";
cout << s.substr(2, 4);

{{ select(4) }}

• gori
• gorit
• lgo
• orit

---

5. 如果一棵二叉树有 9 个叶子结点、7 个只有一个孩子的结点，则这棵二叉树共有多少个结点？

{{ select(5) }}

• 22
• 23
• 24
• 25

---

6. 一个不含重边和自环的无向图有 5 个顶点，若用邻接矩阵表示，矩阵中最多可能有多少个非零元素？

{{ select(6) }}

• 10
• 15
• 20
• 25

---

7. 有向无环图中有边 $(1,4), (2,4), (3,4)$。该图共有多少种不同的拓扑排序？

{{ select(7) }}

• 3
• 6
• 12
• 24

---

8. 下列关于队列的说法，正确的是？

{{ select(8) }}

• 队列是后进先出的数据结构
• 队列只能使用链表实现
• 队列常用于广度优先搜索
• 队列中的元素必须按大小有序

---

9. 有 5 本不同的书排成一排，其中指定的两本书不能相邻，共有多少种排列方式？

{{ select(9) }}

• 48
• 60
• 72
• 96

---

10. 递归函数定义如下：

f(1)=1
f(n)=2*f(n-1)+1  (n>=2)

{{ select(10) }}

• 15
• 31
• 32
• 63

---

11. C++ 中 priority_queue<int> 默认情况下，队首元素是？

{{ select(11) }}

• 最早加入的元素
• 最晚加入的元素
• 当前最小的元素
• 当前最大的元素

---

12. 下面代码片段的时间复杂度是？

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j *= 2)
        cout << i + j << endl;

{{ select(12) }}

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

---

13. 对含有 4096 个元素的有序数组进行二分查找，最坏情况下最多需要比较多少次？

{{ select(13) }}

• 11
• 12
• 13
• 14

---

14. 有 5 个字符，其出现频率分别为 $3, 4, 5, 6, 20$。若使用哈夫曼编码，则频率为 3 的字符编码长度为？

{{ select(14) }}

• 1
• 2
• 3
• 4

---

15. 在 C++ 表达式中，下列运算符通常优先级最高的是？

{{ select(15) }}

• =
• &&
• +
• *

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

阅读程序（一）

#include <iostream>
using namespace std;

int a[105];

int main() {
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++)
        a[i] = 1;

    int p = 0, c = 0, t = 0;

    while (c < n - 1) {
        p++;
        if (p > n)
            p = 1;

        if (!a[p])
            continue;

        t++;

        if (t == k) {
            a[p] = 0;
            c++;
            t = 0;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (a[i])
            cout << i << endl;
    }

    return 0;
}

假设 $1 \le n \le 100$，$1 \le k \le 100$。

判断题

---

16. 当输入为 5 2 时，程序输出为 3。

{{ select(16) }}

• 正确
• 错误

---

17. 当 $k = 1$ 时，程序输出一定为 $n$。

{{ select(17) }}

• 正确
• 错误

---

18. 每次有一个位置被删除后，变量 $t$ 都会被重新赋值为 0。

{{ select(18) }}

• 正确
• 错误

单项选择题

---

19. 当输入为 6 3 时，程序输出为？

{{ select(19) }}

• 1
• 2
• 5
• 6

---

20. 当输入为 7 3 时，程序输出为？

{{ select(20) }}

• 1
• 3
• 4
• 7

阅读程序（二）

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

int a[15][15], dp[15][15];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    dp[1][1] = a[1][1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1)
                continue;

            if (i == 1)
                dp[i][j] = dp[i][j - 1] + a[i][j];
            else if (j == 1)
                dp[i][j] = dp[i - 1][j] + a[i][j];
            else
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}

假设 $1 \le n, m \le 10$，输入的所有 $a_{ij}$ 均为正整数。

判断题

---

21. 程序输出的路径代价包含起点 $(1, 1)$ 和终点 $(n, m)$ 的权值。

{{ select(21) }}

• 正确
• 错误

---

22. 程序中的 $dp_{ij}$ 表示从 $(1, 1)$ 走到 $(i, j)$ 的最小代价。

{{ select(22) }}

• 正确
• 错误

---

23. 程序允许从一个格子向上或向左移动。

{{ select(23) }}

• 正确
• 错误

单项选择题

---

24. 若输入为：

3 3
1 3 1
1 5 1
4 2 1

{{ select(24) }}

• 5
• 6
• 7
• 8

---

25. 若输入为：

2 4
2 1 3 4
5 1 1 1

{{ select(25) }}

• 5
• 6
• 7
• 8

---

26. 该程序的时间复杂度为？

{{ select(26) }}

• $O(n)$
• $O(m)$
• $O(nm)$
• $O(n^2 m)$

阅读程序（三）

#include <iostream>
using namespace std;

int ch[105][105], c[105];
int sz[105], dep[105];

void dfs(int u) {
    sz[u] = 1;

    for (int i = 1; i <= c[u]; i++) {
        int v = ch[u][i];
        dep[v] = dep[u] + 1;
        dfs(v);
        sz[u] += sz[v];
    }
}

int main() {
    int n, x;
    cin >> n;

    for (int i = 2; i <= n; i++) {
        int f;
        cin >> f;
        ch[f][++c[f]] = i;
    }

    dep[1] = 1;
    dfs(1);

    cin >> x;
    cout << dep[x] << " " << sz[x] << endl;

    return 0;
}

假设输入表示一棵以 1 为根的有根树，且对任意 $i > 1$，父亲编号都小于 $i$。

判断题

---

27. 程序执行完 dfs(1) 后，$sz_1$ 一定等于 $n$。

{{ select(27) }}

• 正确
• 错误

---

28. 程序中根结点 1 的深度为 $0$。

{{ select(28) }}

• 正确
• 错误

---

29. $sz_x$ 表示以 $x$ 为根的子树中结点数量，并且包含 $x$ 本身。

{{ select(29) }}

• 正确
• 错误

单项选择题

---

30. 若输入为：

7
1 1 2 2 3 3
2

{{ select(30) }}

• 1 3
• 2 3
• 3 2
• 2 7

---

31. 若输入为：

9
1 1 2 2 4 4 5 5
4

{{ select(31) }}

• 2 3
• 2 7
• 3 3
• 4 1

---

32. 若输入为：

9
1 1 2 2 4 4 5 5
2

{{ select(32) }}

• 1 9
• 2 3
• 2 7
• 3 7

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

完善程序（一）

下面程序使用冒泡排序将数组从小到大排序。若某一轮没有发生交换，则提前结束排序。请补全程序。

#include <iostream>
using namespace std;

int a[1005];

void bub(int n) {
    for (int i = 0; i < n - 1; i++) {
        bool ok = true;

        for (int j = 0; j < ①; j++) {
            if (②) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                ③;
            }
        }

        if (④)
            ⑤;
    }
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    bub(n);

    for (int i = 0; i < n; i++)
        cout << a[i] << " ";

    return 0;
}

---

33. ① 处应填？

{{ select(33) }}

• n
• n - 1
• n - 1 - i
• i

---

34. ② 处应填？

{{ select(34) }}

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

---

35. ③ 处应填？

{{ select(35) }}

• ok = true
• ok = false
• i++
• j--

---

36. ④ 处应填？

{{ select(36) }}

• ok
• !ok
• i == n - 1
• a[i] == a[i + 1]

---

37. ⑤ 处应填？

{{ select(37) }}

• continue
• return false
• i--
• break

完善程序（二）

下面程序求一个由 . 和 # 构成的网格中，从 $(1, 1)$ 到 $(n, m)$ 的最短步数。每次可以向上下左右移动一格，只能经过 .。若无法到达，输出 -1。请补全程序。

#include <iostream>
using namespace std;

char s[105][105];
int d[105][105];
int qx[10005], qy[10005];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> s[i][j];
            d[i][j] = -1;
        }

    int hd = 0, tl = 0;

    if (s[1][1] == '.') {
        ①;
        qx[tl] = 1;
        qy[tl++] = 1;
    }

    while (②) {
        int x = qx[hd];
        int y = qy[hd];
        hd++;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (③ && s[nx][ny] == '.' && ④) {
                d[nx][ny] = ⑤;
                qx[tl] = nx;
                qy[tl++] = ny;
            }
        }
    }

    cout << d[n][m] << endl;
    return 0;
}

---

38. ① 处应填？

{{ select(38) }}

• d[1][1] = 0
• d[1][1] = 1
• d[n][m] = 0
• d[n][m] = 1

---

39. ② 处应填？

{{ select(39) }}

• hd > tl
• hd < tl
• hd == tl
• tl == 0

---

40. ③ 处应填？

{{ select(40) }}

• nx >= 0 && nx <= n && ny >= 0 && ny <= m
• nx >= 1 && nx < n && ny >= 1 && ny < m
• nx >= 1 && nx <= n && ny >= 1 && ny <= m
• nx > n || ny > m

---

41. ④ 处应填？

{{ select(41) }}

• d[nx][ny] == -1
• d[nx][ny] != -1
• d[x][y] == -1
• d[x][y] > d[nx][ny]

---

42. ⑤ 处应填？

{{ select(42) }}

• d[x][y]
• d[x][y] - 1
• d[nx][ny] + 1
• d[x][y] + 1