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

1. 一个 $32$ 位无符号整数可以表示的最大值,最接近下列哪个选项?

{{ select(1) }}

• $4\times 10^{9}$
• $3\times 10^{10}$
• $2\times 10^{9}$
• $2\times 10^{10}$

2. 在 C++ 中,执行 int x = 255; cout << (x & (x - 1)); 后,输出的结果是?

{{ select(2) }}

• $255$
• $254$
• $128$
• $0$

3. 函数 calc(n) 的定义如下,则 calc(5) 的返回值是多少?

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

{{ select(3) }}

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

4. 用 $5$ 个权值 $10$、$12$、$15$、$20$、$25$ 构造哈夫曼树,该树的带权路径长度是多少?

{{ select(4) }}

• $176$
• $186$
• $196$
• $206$

5. 在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和,这个总和等于?

{{ select(5) }}

• 顶点数
• 边数
• 顶点数+边数
• 顶点数 $\times 2$

6. 从 $5$ 位男生和 $4$ 位女生中选出 $4$ 人组成一个学习小组,要求学习小组中男生和女生都有。有多少种不同的选举方法?

{{ select(6) }}

• $126$
• $121$
• $120$
• $100$

7. 假设 $a$、$b$、$c$ 都是布尔变量,逻辑表达式 (a && b) || (!c && a) 的值与下列哪个表达式不始终相等?

{{ select(7) }}

• a && (b || !c)
• (a || !c) && (b || !c) && (a || a)
• a && (!b || c)
• !(!a || !b) || (a && !c)

8. 已知 f[0]=1 ,f[1]=1 ,并且对于所有 $n\ge 2$ 有 f[n]=(f[n-1]+f[n-2])%7 ,那么 f[2025] 的值是多少?

{{ select(8) }}

• $2$
• $4$
• $5$
• $6$

9. 下列关于 C++ string 类的说法,正确的是?

{{ select(9) }}

• string 对象的长度在创建后不能改变
• 可以使用 + 运算符直接连接一个 string 对象和一个 char 类型的字符
• string 的 length() 和 size() 方法返回的值可能不同
• string 对象必须以 '\0' 结尾,且这个结尾符计入 length()

10. 考虑以下 C++ 函数:

void solve(int &a, int b) {
    a = a + b;
    b = a - b;
    a = a - b;
}
int main() {
    int x = 5, y = 10;
    solve(x, y);
}

在 main 函数调用 solve 后,$x$ 和 $y$ 的值分别是?

{{ select(10) }}

• $5$,$10$
• $10$,$5$
• $10$,$10$
• $5$,$5$

11. 一个 $8\times 8$ 的棋盘,左上角坐标为 $(1,1)$ ,右下角为 $(8,8)$ 。一个机器人从 $(1,1)$ 出发,每次只能向右或向下走一格。要到达 $(4,5)$ ,有多少种不同的路径?

{{ select(11) }}

• $20$
• $35$
• $56$
• $70$

12. 某同学用冒泡排序对数组 $\{6, 1, 5, 2, 4\}$ 进行升序排序,请问需要进行多少次元素交换?

{{ select(12) }}

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

13. 十进制数 $720$ 和八进制数 $270_8$ 的和用十六进制表示是多少?

{{ select(13) }}

• $388_{16}$
• $3DE_{16}$
• $288_{16}$
• $720_{16}$

14. 一棵包含 $1000$ 个结点的完全二叉树,其叶子结点的数量是多少?

{{ select(14) }}

• $499$
• $512$
• $500$
• $501$

15. 给定一个初始为空的整数栈 $S$ 和一个空的队列 $P$ 。按顺序处理输入的整数队列 $A$ : $7$,$5$,$8$,$3$,$1$,$4$,$2$ 。对于 $A$ 中的每个数:若为奇数则压入栈 $S$ ;若为偶数且栈 $S$ 非空,则弹出栈顶元素加入队列 $P$ 末尾;若为偶数且栈 $S$ 为空,则不操作。处理完毕后,队列 $P$ 的内容是什么?

{{ select(15) }}

• $5$,$1$,$3$
• $7$,$5$,$3$
• $3$,$1$,$5$
• $5$,$1$,$3$,$7$

二、阅读程序

阅读程序(一)

#include <algorithm>
#include <cstdio>
#include <cstring>
inline int gcd(int a, int b){
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int main(){
    int n;
    scanf("%d", &n);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            for (int k = j + 1; k <= n; ++k) {
                if (gcd(i, j) == 1 && gcd(j, k) == 1 && gcd(i, k) == 1) {
                    ++ans;
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

(1) 当输入为 $2$ 时,程序并不会执行第 $16$ 行的判断语句。

{{ select(16) }}

• 正确
• 错误

(2) 将第 $16$ 行中的 && gcd(i, k) == 1 删去不会影响程序运行结果。

{{ select(17) }}

• 正确
• 错误

(3) 当输入的 $n\ge 3$ 时,程序总是输出一个正整数。

{{ select(18) }}

• 正确
• 错误

(4) 将第 $7$ 行的 gcd(b, a%b) 改为 gcd(a, a%b) 后,程序可能出现的问题是:

{{ select(19) }}

• 输出的答案大于原答案
• 输出的答案小于原答案
• 程序有可能陷入死循环
• 可能发生整型溢出问题

(5) 当输入为 $8$ 时,输出为:

{{ select(20) }}

• $37$
• $42$
• $35$
• $25$

(6) 调用 gcd(36, 42) 会返回:

{{ select(21) }}

• $6$
• $252$
• $3$
• $2$

阅读程序(二)

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int n, k;
int a[200007];
int ans[200007];
int main(){
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    std::sort(a + 1, a + n + 1);
    n = std::unique(a + 1, a + n + 1) - a - 1;
    for (int i = 1, j = 0; i <= n; ++i) {
        for (; j < i && a[i] - a[j + 1] > k; ++j)
            ;
        ans[i] = ans[j] + 1;
    }
    printf("%d\n", ans[n]);
    return 0;
}

(1) 当输入为 $3$ $1$ 后输入 $3$ $2$ $1$ 时,输出结果为 $2$ 。

{{ select(22) }}

• 正确
• 错误

(2) 假设输入的 $n$ 为正整数,输出的答案一定小于等于 $n$ ,大于等于 $1$ 。

{{ select(23) }}

• 正确
• 错误

(3) 将第 $14$ 行的 n = std::unique(...) 删去后,有可能出现与原本代码不同的输出结果。

{{ select(24) }}

• 正确
• 错误

(4) 执行第 $18$ 行代码时,一定满足的条件不包括:

{{ select(25) }}

• j <= i
• a[i] - a[j] > k
• j <= n
• a[j] < a[i]

(5) 当输入 $n=100$ ,$k=2$ ,$a=\{1,2,\ldots,100\}$ 时,输出为:

{{ select(26) }}

• $34$
• $100$
• $50$
• $33$

(6) 若误删去第 $13$ 行的 std::sort(...) ,程序可能出现的问题有:

{{ select(27) }}

• 输出的答案比原本答案更大
• 输出的答案比原本答案更小
• 出现死循环行为
• 以上均可能发生

阅读程序(三)

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int f[5007][5007];
int a[5007], b[5007];
int n;
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            f[i][j] = std::max(f[i][j], std::max(f[i - 1][j], f[i][j - 1]));
            if (a[i] == b[j]) {
                f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
    }
    printf("%d\n", f[n][n]);
    return 0;
}

(1) 当输入 $4$ $1$ $2$ $3$ $4$ $1$ $3$ $2$ $2$ 时,输出为 $2$ 。

{{ select(28) }}

• 正确
• 错误

(2) 程序运行完毕后,对于所有 $1\le i,j\le n$ ,都一定有 $f[i][j] \le f[n][n]$ 。

{{ select(29) }}

• 正确
• 错误

(3) 将第 $18$ 行的 f[i][j] = std::max(f[i][j], std::max(f[i-1][j], f[i][j-1])) 删去后,不影响程序运行结果。

{{ select(30) }}

• 正确
• 错误

(4) 输出的答案满足的性质有:

{{ select(31) }}

• 小于等于 $n$
• 大于等于 $0$
• 不一定大于等于 $1$
• 以上均是

(5) 如果在第 $16$ 行循环前加上 std::sort(a+1, a+n+1); std::sort(b+1, b+n+1); ,则答案会:

{{ select(32) }}

• 变大或不变
• 变小或不变
• 一定变大
• 不变

(6) 如果输入的 $a=\{1,2,\ldots,n\}$ ,且 $b$ 数组中数字均为 $1\sim n$ 中的正整数,则上述代码等价于:

{{ select(33) }}

• 求 $b$ 数组去重后的长度
• 求 $b$ 数组的最长上升子序列
• 求 $b$ 数组的长度
• 求 $b$ 数组的最大值

三、完善程序

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

完善程序(一)

「行程长度编码」(Run-Length Encoding) 是一种无损压缩算法。如果字符连续出现 $N$ 次($N\ge 2$),压缩为「字符+数字 $N$」;如果只出现 $1$ 次,则表示为该字符本身。例如 A12 代表 $12$ 个连续的 A 。

请补全下面的解码程序。

#include <cctype>
#include <iostream>
#include <string>
using namespace std;
int main(){
    string z;
    cin >> z;
    string s = "";
    for (int i = 0; i < z.length(); ) {
        char ch = z[i];
        if (① && isdigit(z[i + 1])) {
            i++;
            int count = 0;
            while (i < z.length() && isdigit(z[i])) {
                count = ②;
                i++;
            }
            for (int j = 0; j < ③; ++j) {
                s += ch;
            }
        } else {
            s += ④;
            ⑤;
        }
    }
    cout << s << endl;
    return 0;
}

(1) ① 处应填( )

{{ select(34) }}

• i < z.length()
• i - 1 >= 0
• i + 1 < z.length()
• isdigit(z[i])

(2) ② 处应填( )

{{ select(35) }}

• count + (z[i] - '0')
• count * 10 + (z[i] - '0')
• z[i] - '0'
• count + 1

(3) ③ 处应填( )

{{ select(36) }}

• count - 1
• count
• 10
• z[i] - '0'

(4) ④ 处应填( )

{{ select(37) }}

• z[i+1]
• ch
• z.back()
• (char)z[i] + 1

(5) ⑤ 处应填( )

{{ select(38) }}

• i--
• i = i + 2
• i++
• 不执行任何操作

完善程序(二)

有 $N$ 个人,分为精明人(永远正确判断他人)和糊涂人(判断不可靠)。精明人严格占多数($k>N/2$)。通过函数 query(i,j) 让第 $i$ 个人判断第 $j$ 个人,找出一个一定能确定的精明人。

请补全下面的程序。

#include <iostream>
#include <vector>
using namespace std;
int N;
bool query(int i, int j);
int main(){
    cin >> N;
    int candidate = 0;
    int count = ①;
    for (int i = 1; i < N; ++i) {
        if (②) {
            candidate = i;
            count = 1;
        } else {
            if (③) {
                ④;
            } else {
                count++;
            }
        }
    }
    cout << ⑤ << endl;
    return 0;
}

(1) ① 处应填( )

{{ select(39) }}

• 0
• 1
• N
• -1

(2) ② 处应填( )

{{ select(40) }}

• count < 0
• count == 1
• count == 0
• query(candidate, i) == false

(3) ③ 处应填( )

{{ select(41) }}

• query(candidate, i) == false
• query(i, candidate) == true
• query(candidate, i) == false && query(i, candidate) == false
• query(candidate, i) == false || query(i, candidate) == false

(4) ④ 处应填( )

{{ select(42) }}

• count--
• break
• count++
• candidate = i

(5) ⑤ 处应填( )

{{ select(43) }}

• N-1
• count
• candidate
• 0