一、单项选择题(每题 2 分,共 30 分)

1. 阅读下面代码,输出结果是?

int a = 7, b = 3;
cout << a / b * b + a % b;

{{ select(1) }}

• $6$
• $7$
• $8$
• $10$

2. 十六进制数 $2 A_{1 6}$ 与二进制数 $1 0 1 0 1 1_{2}$ 的和对应的十进制值是?

{{ select(2) }}

• $83$
• $84$
• $85$
• $86$

3. 阅读下面代码,输出结果是?

int x = 0, y = 1;
if (x && ++y) {
    y += 10;
}
cout << y;

{{ select(3) }}

• $0$
• $1$
• $2$
• $11$

4. 阅读下面代码,输出结果是?

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

{{ select(4) }}

• gori
• gorit
• lgo
• orit

5. 如果一棵二叉树高度为 $h$ ,根结点高度为 $1$ ,则高度至少为多少时,二叉树最多可以包含不少于 $2026$ 个结点?

{{ select(5) }}

• $9$
• $10$
• $11$
• $12$

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

• =
• &&
• +
• *

二、阅读程序

二、阅读程序

程序输入不超过数组或字符串定义的范围。

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

阅读程序(一)

假设输入字符串非空,只包含小写字母。

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


string cal(string s) {
    string t;


    for (int i = 0; i < s.size(); i++) {
        if (!t.empty() && t.back() == s[i])
            t.pop_back();
        else
            t += s[i];
    }


    if (t.empty())
        return "EMPTY";
    return t;
}


int main() {
    string s;
    cin >> s;
    cout << cal(s) << endl;
    return 0;
}

(程序 $1$ ,每题 $2$ 分)

(1) 当输入为 abba 时,程序输出为 EMPTY。

{{ select(16) }}

• 正确
• 错误

(2) 当输入为 aabbcc 时,程序输出为 EMPTY。

{{ select(17) }}

• 正确
• 错误

(3) 若输入字符串长度为奇数,程序不可能输出 EMPTY。

{{ select(18) }}

• 正确
• 错误

(4) 当输入为 abbaca 时,程序输出为?

{{ select(19) }}

• EMPTY
• ca
• ba
• aca

(5) 设输入字符串长度为 $n$ ,该程序的时间复杂度为?

{{ select(20) }}

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

阅读程序(二)

假设 $1≤n≤10$ ,$1≤m≤100$ ,且所有 $ci$ 均为正整数。

#include <iostream>
using namespace std;


int c[15], dp[105];


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


    for (int i = 1; i <= n; i++)
        cin >> c[i];


    dp[0] = 1;


    for (int i = 1; i <= n; i++) {
        for (int j = c[i]; j <= m; j++) {
            dp[j] += dp[j - c[i]];
        }
    }


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

(程序 $2$ ,每题 $1.5$ 分)

(1) 程序执行过程中, $dp_0$ 的值始终为 $1$ 。

{{ select(21) }}

• 正确
• 错误

(2) 程序统计的是使用若干个数凑出 $m$ 的有序方案数。

{{ select(22) }}

• 正确
• 错误

(3) 若将第二层循环改为从 $m$ 到 $c_i$ 递减枚举,则每个 $c_i$ 最多只能使用一次。

{{ select(23) }}

• 正确
• 错误

(4) 若输入为:

3 5
1 2 5

程序输出为?

{{ select(24) }}

• $3$
• $4$
• $5$
• $6$

(5) 若输入为:

2 6
2 3

程序输出为?

{{ select(25) }}

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

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

{{ select(26) }}

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

阅读程序(三)

假设输入表示一棵以 $1$ 为根的有根树,且对任意 $i > 1$ ,都有 $1 ≤fa_i< i$ 。

#include <iostream>
using namespace std;


int fa[105], dep[105];


int lca(int x, int y) {
    while (dep[x] > dep[y])
        x = fa[x];


    while (dep[y] > dep[x])
        y = fa[y];


    while (x != y) {
        x = fa[x];
        y = fa[y];
    }


    return x;
}


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


    fa[1] = 0;
    dep[1] = 1;


    for (int i = 2; i <= n; i++) {
        cin >> fa[i];
        dep[i] = dep[fa[i]] + 1;
    }


    cin >> x >> y;


    int z = lca(x, y);
    cout << z << " " << dep[x] + dep[y] - 2 * dep[z] << endl;


    return 0;
}

(程序 $3$ ,每题 $1.5$ 分)

(1) 若输入的 $x$ 和 $y$ 相等,则程序输出的第二个数一定为 $0$ 。

{{ select(27) }}

• 正确
• 错误

(2) 程序输出的第二个数表示 $x$ 到 $y$ 的简单路径上经过的边数。

{{ select(28) }}

• 正确
• 错误

(3) 若将 dep[1] = 1 改为 dep[1] = 0 ,程序输出的第二个数一定不变。

{{ select(29) }}

• 正确
• 错误

(4) 若输入为:

7
1 1 2 2 3 3
4 5

程序输出为?

{{ select(30) }}

• 1
  2
  

• 2
  2
  

• 2
  3
  

• 4
  0
  

(5) 若输入为:

7
1 1 2 2 3 3
4 6

程序输出为?

{{ select(31) }}

• 1
  4
  

• 2
  3
  

• 3
  3
  

• 4
  6
  

(6) 若输入为:

9
1 1 2 2 4 4 5 5
6 9

程序输出为?

{{ select(32) }}

• 1
  5
  

• 2
  4
  

• 4
  4
  

• 5
  3
  

三、完善程序

三、完善程序

单项选择题,每题 $3$ 分,共 $30$ 分。

完善程序(一)

下面程序计算 $a^{b} \mod p$ ,其中 $b$ 为非负整数, $p$ 为正整数。请补全程序。

#include <iostream>
using namespace std;


using ll = long long;


ll pw(ll a, ll b, ll p) {
    ll r = 1 % p;
    a %= p;


    while (b > 0) {
        if (①)
            r = ②;

        a = ③;
        b = ④;
    }

    return ⑤;
}


int main() {
    ll a, b, p;
    cin >> a >> b >> p;


    cout << pw(a, b, p) << endl;
    return 0;
}

(1) ① 处应填( )

{{ select(33) }}

• b == 0
• b % 2 == 1
• a % 2 == 1
• p % 2 == 1

(2) ② 处应填( )

{{ select(34) }}

• r + a
• r * a % p
• a * a % p
• b * a % p

(3) ③ 处应填( )

{{ select(35) }}

• a + a
• a * b % p
• a * a % p
• r * r % p

(4) ④ 处应填( )

{{ select(36) }}

• b - 1
• b + 1
• b * 2
• b / 2

(5) ⑤ 处应填( )

{{ select(37) }}

• a
• b
• p
• r

完善程序(二)

下面程序使用 Floyd 算法求无向带权图中两点之间的最短距离。若两点不连通,输出 $‐1$ 。请补全程序。

#include <iostream>
using namespace std;


const int INF = 1000000000;


int d[105][105];


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


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = ①;
        }
    }


    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        if (②)
            d[u][v] = d[v][u] = w;
    }


    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (③)
                    d[i][j] = ④;
            }
        }
    }


    int s, t;
    cin >> s >> t;

    if (⑤)
        cout << -1 << endl;
    else
        cout << d[s][t] << endl;


    return 0;
}

(1) ① 处应填( )

{{ select(38) }}

• i == j ? 0 : INF
• i == j ? INF : 0
• 0
• INF

(2) ② 处应填( )

{{ select(39) }}

• w > d[u][v]
• w < d[u][v]
• u == v
• d[u][v] == 0

(3) ③ 处应填( )

{{ select(40) }}

• d[i][j] < d[i][k] + d[k][j]
• d[i][k] + d[k][j] < d[i][j]
• d[i][k] < d[k][j]
• d[i][j] == INF

(4) ④ 处应填( )

{{ select(41) }}

• d[i][j]
• d[i][k]
• d[k][j]
• d[i][k] + d[k][j]

(5) ⑤ 处应填( )

{{ select(42) }}

• d[s][t] == 0
• d[s][t] == INF
• s == t
• d[s][t] < INF