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

1. 下列 C++ 数据类型中,能够精确存储 $10^{18}+1$ 这个整数的是?

{{ select(1) }}

• float
• long long
• double
• int

2. 十六进制数 $2F5$ 转换为八进制数是?

{{ select(2) }}

• $1364$
• $1635$
• $1405$
• $1365$

3. 执行下列 C++ 代码,输出是?

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

{{ select(3) }}

• $9$
• $10$
• $7$
• $6$

4. 初始时栈为空,将 $1$、$2$、$3$、$4$ 依次入栈,入栈过程中允许随时出栈。下列出栈序列中不可能出现的是?

{{ select(4) }}

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

5. 一棵有 $100$ 个结点的完全二叉树,其中叶子结点个数是?

{{ select(5) }}

• $49$
• $50$
• $64$
• $51$

6. 执行下列代码后 $s$ 的值是?

int s = 0;
for (int i = 1; i <= 100; i++)
    if (i % 3 == 0 || i % 5 == 0)
        s += i;

{{ select(6) }}

• $3048$
• $2733$
• $2318$
• $2418$

7. 上楼梯每步可上 $1$ 级、$2$ 级或 $3$ 级,从地面(可视为第 $0$ 级)走到第 $8$ 级台阶共有多少种不同走法?

{{ select(7) }}

• $44$
• $121$
• $149$
• $81$

8. 下图为 $5\times 5$ 网格,行号、列号均从 $0$ 开始,# 为障碍,. 为可通行格:

S..#.
...#.
...#.
##..E
...#.

从 S 出发做广度优先搜索(BFS):初始时把 S 入队;每次取出队首格子,按「上、下、左、右」(上 = 行号减 $1$,下 = 行号加 $1$,左 = 列号减 $1$,右 = 列号加 $1$)的顺序遍历它的四个相邻格子,越界、障碍或已访问的格子跳过,其余格子标记为已访问并入队。当 E 第一次入队时,已经入队过的格子(含 S 和 E)共有多少个?

{{ select(8) }}

• $15$
• $12$
• $14$
• $13$

9. 满足 $1\le n\le 100$ 且 $\gcd(n,60)=6$ 的正整数 $n$ 共有多少个?

{{ select(9) }}

• $8$
• $6$
• $4$
• $5$

10. 某国硬币面值为 $1$ 元、$4$ 元、$6$ 元且数量不限,凑出 $9$ 元最少需要多少枚?

{{ select(10) }}

• $3$
• $4$
• $5$
• $2$

11. 执行下列代码,输出是?

int a[5] = {1, 3, 5, 7, 9};
int *p = a + 2;
*(p - 1) = p[0] + p[2];
p[1] = *(a + 1) - a[0];
cout << a[1] << "," << a[3];

{{ select(11) }}

• $14,13$
• $8,13$
• $14,7$
• $14,2$

12. 在含 $1000$ 个互不相同元素的升序数组中,用二分法查找给定值(返回元素位置或报告不存在),最坏情况下需要与数组元素比较多少次?

{{ select(12) }}

• $500$
• $9$
• $11$
• $10$

13. 数组 $a[1..n]$ 的前缀和数组 $s$(即 $s[i]=a[1]+a[2]+\cdots+a[i]$)满足 $s[i]=3i^2+i$。则 $a[10]$ 的值是?

{{ select(13) }}

• $252$
• $310$
• $58$
• $61$

14. 数轴上有 $7$ 个点,坐标分别为 $1,3,4,7,10,15,20$。在数轴上选取一个整数坐标点 $P$,使 $P$ 到这 $7$ 个点的距离之和最小,这个最小距离和是?

{{ select(14) }}

• $37$
• $42$
• $40$
• $38$

15. 一个无向图有 $10$ 个顶点,其中 $4$ 个顶点的度为 $3$,其余顶点的度均为 $4$,则该图的边数是?

{{ select(15) }}

• $36$
• $18$
• $17$
• $20$

二、阅读程序

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

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

阅读程序(一)

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int x = 1, y = 1;
    while (n > 0) {
        if (n % 2 == 0) {
            ++x;
        } else {
            ++x;
            ++y;
        }
        n = n / 2;
    }
    cout << x << ' ' << y << endl;
    return 0;
}

以下问题均假定输入的 $n$ 为不超过 $2^{31}-1$ 的非负整数。

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

{{ select(16) }}

• 正确
• 错误

(2) 将第 $11$ 行的 ++x; 删除后,程序输出的两个数一定相等。

{{ select(17) }}

• 正确
• 错误

(3) 假设输入为非负整数,则程序输出的第一个数一定不小于第二个数。

{{ select(18) }}

• 正确
• 错误

(4) 将第 $7$ 行的 while (n > 0) 改为 while (n >= 0) 后,程序可能出现的问题是?

{{ select(19) }}

• 陷入死循环
• 输出结果比原来大
• 输出结果比原来小
• 输出结果不受影响

(5) 当输入为 $6$ 时,输出为?

{{ select(20) }}

• $3$ $3$
• $4$ $2$
• $4$ $3$
• $5$ $2$

(6) 若输入 $n$ 依次取遍 $0,1,2,\dots,2^{31}-1$ 中的所有整数,则程序输出的第二个数恰好为 $2$ 的次数为?

{{ select(21) }}

• $16$
• $30$
• $31$
• $32$

阅读程序(二)

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int a[100007], b[100007], c[100007], carry[100007];
string input_str;
int a_len, b_len;
int main() {
    cin >> input_str;
    a_len = input_str.size();
    for (int i = 0; i < a_len; i++) {
        a[i] = input_str[a_len - i - 1] - '0';
    }
    cin >> input_str;
    b_len = input_str.size();
    for (int i = 0; i < b_len; i++) {
        b[i] = input_str[b_len - i - 1] - '0';
    }
    carry[0] = 0;
    for (int i = 0; i < max(a_len, b_len) + 1; i++) {
        c[i] = a[i] + b[i] + carry[i];
        if (c[i] >= 10) {
            carry[i + 1] = 1;
            c[i] -= 10;
        } else {
            carry[i + 1] = 0;
        }
    }
    for (int i = max(a_len, b_len); i >= 0; i--) {
        cout << c[i];
    }
    cout << endl;
    return 0;
}

本题输入的两个数均为非负整数,位数不超过 $100000$,可能包含前导零。

(1) 当输入为 $123$ $456$ 时,程序输出为 $0579$。

{{ select(22) }}

• 正确
• 错误

(2) 假设输入的两个数均不含前导零,则程序输出的结果也一定不会含有前导零。

{{ select(23) }}

• 正确
• 错误

(3) 将第 $21$ 行改为 c[i] = a[i] + b[i]; 后,程序输出的结果一定比原来的结果小。

{{ select(24) }}

• 正确
• 错误

(4) 当输入为 $12345$ $678$ 时,输出为?

{{ select(25) }}

• $012923$
• $013023$
• $13023$
• $130230$

(5) 将第 $22$ 行的 if (c[i] >= 10) 改为 if (c[i] > 10) 后,当输入为 $95$ $15$ 时,输出为?

{{ select(26) }}

• $01010$
• $110$
• $140$
• $1410$

(6) 假设输入的两个数均为 $n$ 位正整数(不含前导零),且它们的和小于 $10^n$,则程序输出的字符串一定满足?

{{ select(27) }}

• 第一个字符一定不为 $0$
• 长度一定为 $n$
• 长度一定为 $n+1$,且第一个字符为 $0$
• 长度可能为 $n+2$

阅读程序(三)

#include <iostream>
using namespace std;
bool check_prime(int x) {
    if (x <= 1) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
int n;
void search_result(int x) {
    if (!check_prime(x)) return;
    if (x >= n) {
        cout << x << endl;
        return;
    }
    for (int i = 0; i <= 9; i++) {
        search_result(x * 10 + i);
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= 9; i++) search_result(i);
    return 0;
}

(1) 当输入为 $10$ 时,程序的输出共有 $10$ 行。

{{ select(28) }}

• 正确
• 错误

(2) 若输入的 $n$ 不大于 $5$,则程序的输出中一定包含 $5$。

{{ select(29) }}

• 正确
• 错误

(3) 若输入的 $n$ 大于 $10$,将第 $17$ 行的 for (int i = 0; i <= 9; i++) 改为 for (int i = 1; i <= 9; i += 2) 后,程序的输出结果一定不变。

{{ select(30) }}

• 正确
• 错误

(4) 当输入为 $24$ 时,程序输出的第 $3$ 行为?

{{ select(31) }}

• $23$
• $29$
• $31$
• $239$

(5) 下列关于该程序输出的说法中,正确的是?

{{ select(32) }}

• 输出的数一定按照从小到大的顺序排列
• 随着输入 $n$ 的增大,输出的行数一定不会增加
• 输出的数的个位数字只可能是 $3$ 或 $7$
• 输出的每个大于等于 $10$ 的数,十进制下删去它的末位数字后得到的数一定是质数

(6) 当输入为 $200$ 时,程序输出的行数为?

{{ select(33) }}

• $12$
• $13$
• $14$
• $15$

三、完善程序

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

完善程序(一)

（进制减半）给定 $n,m$,再给定一个 $mn$ 进制下的数 $A$,其各个数位上的数按照从高位到低位的顺序给出,请将其转换为 $n$ 进制,并同样按照从高位到低位的顺序输出。

输入第一行依次为 $n$、$m$ 和 $A$ 的位数 $d$,接下来 $d$ 个数 $a_d,a_{d-1},...,a_1$ 从高位到低位描述各个数位。

数据满足 $2\le n,m\le 10$, $1\le d\le 18$, $0\le A<2^{63}$，对于所有的 $1\leq i \leq d$, $0\leq a_i\leq mn$。

以下程序按 “逐位除以 $n$ ” 的方法完成进制转换。请补全程序。

#include <iostream>

constexpr int N = 100005;
long long b[N];

int main() {
    long long n, m, d;
    std::cin >> n >> m >> d;
    int len = 1;
    for (int i = 0; i < d; i++) {
        long long x;
        std::cin >> x;
        for (int j = len; j >= 1; j--)
            b[j] = ①;
        b[0] = ②;
        len++;
        for (int j = 0; j < len; j++) {
            if (b[j] >= n) {
                b[j + 1] += ③;
                b[j] = ④;
                if (j + 1 == len) len++;
            }
        }
    }
    while (⑤) len--;
    for (int i = len - 1; i >= 0; i--)
        std::cout << b[i] << ' ';
    return 0;
}

(1) ① 处应填( )

{{ select(34) }}

• b[j] * n
• b[j] * m
• b[j - 1] * n
• b[j - 1] * m

(2) ② 处应填( )

{{ select(35) }}

• x * n
• x
• 0
• m

(3) ③ 处应填( )

{{ select(36) }}

• b[j] / m
• b[j] % n
• b[j] % m
• b[j] / n

(4) ④ 处应填( )

{{ select(37) }}

• b[j] / m
• b[j] % n
• b[j] % m
• b[j] / n

(5) ⑤ 处应填( )

{{ select(38) }}

• len > 0 && b[len - 1] == 0
• len > 0 && b[0] == 0
• len > 1 && b[len - 1] == 0
• len > 1 && b[0] == 0

完善程序(二)

（平衡分割）给定一个长度为 $n$ 的字符串,其中每个字符都是一个十六进制数位。例如,字符串 016A 表示十进制下的四个数 $0,1,6,10$。

现在请选择 $k$ 个($k$ 是你选定的数)切分位置 $p_1,p_2,\dots,p_k$,其中 $1\le k<n$,且 $1\le p_1<p_2<\cdots<p_k<n$。再令 $p_0=0$, $p_{k+1}=n$。

对于每个 $0\le i\le k$,计算第 $p_i+1$ 个数到第 $p_{i+1}$ 个数的平均值,记作 $b_i$。你的目标是使 $b_0,b_1,\dots,b_k$ 中最大值与最小值之差尽可能小,并输出这个最小值。

其中 $2\le n\le 20$。输入字符串中的字符只可能是 $0$–$9$ 或 $A$–$F$。本题假定字符采用 ASCII 编码。输出答案时保留小数点后 $6$ 位。

以下程序通过递归枚举所有可能的连续分段方案。请补全程序。

#include <algorithm>
#include <iomanip>
#include <iostream>
using namespace std;
constexpr int N = 25;
int n, a[N];
char s[N];
double ans = 1e100;
int value(char c) { return ①; }
void split(int l, int cnt, double mnb, double mxb) {
    if (l > n) {
        if (cnt == 0) return;
        ans = min(ans, mxb - mnb);
        return;
    }
    int sum = 0;
    for (②) {
        sum += a[r];
        double nwb = ③;
        split(④);
    }
}
int main() {
    cin >> n >> s + 1;
    for (int i = 1; i <= n; ++i)
        a[i] = value(s[i]);
    split(⑤);
    cout << fixed << setprecision(6) << ans;
    return 0;
}

(1) ① 处应填( )

{{ select(39) }}

• c - (c < '9' ? '0' : 'A' - 10)
• c - (c < 'A' ? '0' : 'A' - 10)
• c - (c < 'A' ? 'A' - 10 : '0')
• c - (c < 'A' ? '0' : 'A' + 10)

(2) ② 处应填( )

{{ select(40) }}

• int r = l + 1; r <= n; ++r
• int r = l; r < n; ++r
• int r = l; r <= n; r += 2
• int r = l; r <= n; ++r

(3) ③ 处应填( )

{{ select(41) }}

• sum / (r - l + 1) * 1.0
• sum * 1.0 / (r - l) + 1
• sum * 1.0 / (r - l + 1)
• (sum - a[r]) * 1.0 / (r - l + 1)

(4) ④ 处应填( )

{{ select(42) }}

• r + 1, cnt + (r < n), min(mnb, nwb), max(mxb, nwb)
• r + 1, cnt + (r <= n), min(mnb, nwb), max(mxb, nwb)
• r + 1, cnt + (r < n), max(mnb, nwb), min(mxb, nwb)
• r + 1, cnt + (r <= n), max(mnb, nwb), min(mxb, nwb)

(5) ⑤ 处应填( )

{{ select(43) }}

• 0, 0, 1e100, -1e100
• 0, 0, -1e100, 1e100
• 1, 0, -1e100, 1e100
• 1, 0, 1e100, -1e100