一、单项选择题(每题 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. 十六进制数 $2 A_{1 6}$ 与二进制数 $1 0 1 0 1 1_{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$ 个结点恰好只有 $1$ 个孩子,则这棵树共有多少个结点?

{{ 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)

则 f(5) 的值为?

{{ 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) }}

• =
• &&
• +
• *

二、阅读程序

程序输入不超过数组或字符串定义的范围。判断题正确填“$\surd$”,错误填“$\times$”。

除特殊说明外,判断题每题 $1.5$ 分,选择题每题 $3$ 分,共 $40$ 分。其中第 $16\sim 18$ 题每题 $2$ 分,第 $32$ 题 $4$ 分。

阅读程序(一)

下面程序模拟约瑟夫问题: $n$ 个人围成一圈,从 $1$ 号开始报数,每报到 $k$ 的人出圈,直到只剩 $1$ 人,输出其编号。假设 $1 \leq n \leq 100$, $1 \leq k \leq 100$。

#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,每题 2 分)

(1) 当输入为 $5$ $2$ 时,程序输出为 $3$。

{{ select(16) }}

• 正确
• 错误

(2) 当 $k=1$ 时,程序一定输出 $n$。

{{ select(17) }}

• 正确
• 错误

(3) 每个人被删除后,报数计数器 $t$ 会被重新赋值为 $0$。

{{ select(18) }}

• 正确
• 错误

(4) 当输入为 $6$ $3$ 时,程序输出为?

{{ select(19) }}

• $1$
• $2$
• $5$
• $6$

(5) 当输入为 $7$ $3$ 时,程序输出为?

{{ select(20) }}

• $1$
• $3$
• $4$
• $7$

阅读程序(二)

假设 $1 \leq n,m \leq 10$,格子权值为整数。只能向右或向下走,求从 $(1,1)$ 到 $(n,m)$ 的最小权和。

#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;
}

(程序 2,每题 1.5 分)

(1) 从 $(1,1)$ 走到 $(n,m)$ 的路径权和一定包含 $a_{1,1}$ 与 $a_{n,m}$。

{{ select(21) }}

• 正确
• 错误

(2) 程序中的 $dp_{i,j}$ 表示从 $(1,1)$ 走到 $(i,j)$ 的最小路径权和。

{{ select(22) }}

• 正确
• 错误

(3) 若将转移中的 $\min$ 改为只使用上方格子 $dp_{i-1,j}$,程序输出总是不变。

{{ select(23) }}

• 正确
• 错误

(4) 若输入为:

3 3
1 3 1
1 5 1
4 2 1

程序输出为?

{{ select(24) }}

• $5$
• $6$
• $7$
• $8$

(5) 若输入为:

2 4
2 1 3 4
5 1 1 1

程序输出为?

{{ select(25) }}

• $5$
• $6$
• $7$
• $8$

(6) 该程序的时间复杂度为?

{{ select(26) }}

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

阅读程序(三)

假设输入表示一棵以 $1$ 为根的有根树,对任意 $i>1$ 都有 $1 \leq fa_i < i$。程序输出结点 $x$ 的深度和子树大小。

#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;
}

(程序 3,每题 1.5 分)

(1) 执行 dfs(1) 之后,一定有 $dep_1=1$。

{{ select(27) }}

• 正确
• 错误

(2) 若将 dep[1] = 1 改为 dep[1] = 0,程序输出的两个数都不变。

{{ select(28) }}

• 正确
• 错误

(3) 程序中的 $sz_x$ 表示以 $x$ 为根的子树大小(含 $x$ 自己)。

{{ select(29) }}

• 正确
• 错误

(4) 若输入为:

7
1 1 2 2 3 3
2

程序输出为?

{{ select(30) }}

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

(5) 若输入为:

9
1 1 2 2 4 4 5 5
4

程序输出为?

{{ select(31) }}

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

(6) 若输入为:

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;
}

(1) ① 处应填( )

{{ select(33) }}

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

(2) ② 处应填( )

{{ select(34) }}

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

(3) ③ 处应填( )

{{ select(35) }}

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

(4) ④ 处应填( )

{{ select(36) }}

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

(5) ⑤ 处应填( )

{{ select(37) }}

• continue
• return false
• i--
• break

完善程序(二)

下面程序求 $n \times m$ 网格中从 $(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;
}

(1) ① 处应填( )

{{ select(38) }}

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

(2) ② 处应填( )

{{ select(39) }}

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

(3) ③ 处应填( )

{{ 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

(4) ④ 处应填( )

{{ select(41) }}

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

(5) ⑤ 处应填( )

{{ select(42) }}

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