CSP-J 卷

C++ 表达式 ('1' + '1') 的值为 '2'。

在 C++ 语言中，do-while 循环不可能导致死循环，但 while 有可能。

在下面的 C++ 代码中，由于循环中的 continue 是无条件被执行，因此将导致死循环。

01for (int i = 1; i < 10; i++) continue;

在 C++ 代码中，不可以将变量命名为 cout，因为 cout 是 C++ 的关键字。

我们通常说的“内存”属于计算机中的（ ）。

在 C++ 代码中，假设 N 为正整数，则 N - N / 10 * 10 与 N % 10 都将获得 N 的个位数。（ ）

下面 C++ 代码执行后将输出 10。（ ）

01int i;
02for (i = 0; i < 10; i++)
03    continue;
04cout << i << endl;

求三色彩球的颜色。有数量无限的红（Red）绿（Green）蓝（Blue）三种彩球排成一行，每组先为 5 个红色球，随后 3 个绿色，最后为 2 个蓝色。每个球都有编号，从左到右依次为 1、2、3、......。输入整数代表编号，求该编号球的颜色。下面是 C++ 代码是实现，正确说法是（ ）。

01int N, remainder;
02cin >> N;
03remainder = N % 10; // remainder变量保存余数
04if ((1 <= remainder) && (remainder <= 5))
05    cout << "Red";
06else if ((6 <= remainder) && (remainder <= 8))
07    cout << "Green";
08else if ((remainder == 9) || (remainder == 0))
09    cout << "Blue";

下面 C++ 代码执行后其输出是（ ）。

01int tnt = 0;
02for (int i = 0; i < 10; i++)
03    if (i % 3)
04        tnt += 1;
05    else
06        tnt += 2;
07cout << tnt;

下面 C++ 代码执行后输出是（ ）。

01int i;
02for (i = 0; i < 10; i++){
03    if (i % 3 == 0)
04        continue;
05    cout << "0" << "#";
06}
07if (i >= 10)
08    cout << "1" << "#";

下面 C++ 代码执行后的输出是（ ）。

01int i,j;
02for (i = 0; i < 5; i++)
03    for (j = i; j > 0; j -= 1)
04        printf("%d-",j);

下列程序中，假设一个字符占用的内存空间是 $1$，ch 占用的内存空间是（ ）。

01char ch[] = "hello world";
02size_t ret=strlen(ch);
03cout<<ret<<endl;

下列程序最后输出的是（ ）。

01int a=65;
02cout<<tolower(a)<<endl;

想要计算从数字 n 到数字 m 之间（包含 n 和 m）有多少个数字 d 出现，下列程序哪个能够实现（ ）。

求小于等于 N 的素数的方法中，有一种方法是将所有从 $2$ 到它本身减 $1$ 的数都除一遍，如果不能整除，就是素数。下列哪个程序，体现了这种方法（ ）。

以下 C++ 代码中存在几处错误（ ）。

01#include <iostream>
02using namespace std;
03int main() {
04    const int SIZE = 5;
05    int arr[SIZE];
06    for (int i = 0; i <= SIZE; i++) {
07        arr[i] = i * 2;
08    }
09    cout << arr[SIZE] << endl;
10    return 0;
11}

以下关于 C++ 中 string 类和字符数组（char[]）的说法，错误的是（ ）。

某排序算法对如下数据排序（按 score 升序），则下面关于该排序算法稳定性的描述中，说法正确的是（ ）。

初始：(90,'A'), (90,'B'), (80,'C'), (90,'D')

排序后：(80,'C'), (90,'A'), (90,'B'), (90,'D')

下面代码试图把数组按升序进行“插入排序”，横线处应填写（ ）。

01void ins(int a[], int n){
02    for(int i = 1; i < n; i++){
03        int key = a[i];
04        int j = i-1;
05        while(j >= 0 && ____________){
06            a[j+1] = a[j];
07            j--;
08        }
09        a[j+1] = key;
10    }
11}

下列代码段的时间复杂度为（ ）。

01int cnt=0;
02for(int i=0; i<n; i++){
03    for(int j=0; j<n; j++){
04        if( (i+j) % 3 == 0) cnt++;
05    }
06}

下面哪种方式不能实现将字符串 Welcome to 2026! 输出重定向到文件 log.txt（ ）。

下列函数实现排行榜中单个元素的位置调整（类似插入排序的相邻搬移）。当某玩家分数增加，需将其向前移动时，while 循环的条件应为（ ）。

01struct Player{ int score; };
02void up(Player players[], int n, int idx){
03    Player cur = players[idx];
04    int i = idx;
05    while( ____________ ){
06        players[i] = players[i-1];
07        i--;
08    }
09    players[i] = cur;
10}

贪心算法是一种可以应用于所有问题的通用解决方案。

贪心算法的核心思想是（ ）？

下面哪句话最符合归并排序的思想？（ ）

在对长度为 $n$（$n\ge1$）的数组进行归并排序的过程中，mergeArray 函数（合并两个有序子数组的操作）被调用的次数是（ ）。

01const int MAXN = 100005;
02int a[MAXN];
03int tempArr[MAXN];
04
05void mergeArray(int left, int mid, int right) {
06    int i = left;      // 左半部分起点
07    int j = mid + 1;   // 右半部分起点
08    int k = left;      // 临时数组下标
09
10    while (i <= mid && j <= right) {
11        if (a[i] <= a[j]) {
12            tempArr[k++] = a[i++];
13        } else {
14            tempArr[k++] = a[j++];
15        }
16    }
17
18    while (i <= mid) {
19        tempArr[k++] = a[i++];
20    }
21
22    while (j <= right) {
23        tempArr[k++] = a[j++];
24    }
25
26    for (int p = left; p <= right; p++) {
27        a[p] = tempArr[p];
28    }
29}
30
31void mergeSort(int left, int right) {
32    if (left >= right) {
33        return;
34    }
35
36    int mid = left + (right - left) / 2;
37    mergeSort(left, mid);
38    mergeSort(mid + 1, right);
39    mergeArray(left, mid, right);
40}

小杨在学校义卖会上负责打包“零食盲盒”。每个盲盒重量不同，快递盒最多承重 limit 克，每个快递盒最多装两个盲盒。为了尽量少用快递盒，他采用如下策略：

（$1$）每次把最轻的盲盒和最重的盲盒尝试放在一起；

（$2$）如果两者重量之和不超过 limit，就一起装；

（$3$）否则，只能让最重的盲盒单独装一盒。

下面代码用于计算最少需要多少个快递盒，则横线处应填入的是（ ）。

01int minBoxes(vector<int>& w, int limit) {
02    sort(w.begin(), w.end());
03    int l = 0, r = w.size() - 1;
04    int boxes = 0;
05    while (l <= r) {
06        if (w[l] + w[r] <= limit) {
07            __________; // 在此处填入代码
08        } else {
09            r--;
10        }
11        boxes++;
12    }
13    return boxes;
14}

给定一棵二叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG，则这棵树的正确后序遍历结果是（ ）。

假设⼀个算法时间复杂度的递推式是 $T(n) = 2T(n-1)+1$，且 $T(0) =1$，那么这个算法的时间复杂度是（）。

下⾯程序的运⾏结果为（ ）。

01#include <iostream>
02#include <algorithm>
03
04bool check(int n, int a[], int k, int dist) {
05    int cnt = 1;
06    int last = a[0];
07
08    for (int i = 1; i < n; i++) {
09        if (a[i] - last >= dist) {
10            cnt++;
11            last = a[i];
12        }
13    }
14
15    return cnt >= k;
16}
17
18int solve(int n, int a[], int k) {
19    std::sort(a, a + n);
20
21    int l = 0;
22    int r = a[n - 1] - a[0];
23
24    while (l < r) {
25        int mid = (l + r + 1) / 2;
26
27        if (check(n, a, k, mid))
28            l = mid;
29        else
30            r = mid - 1;
31    }
32
33    return l;
34}
35
36int main() {
37    int a[] = {1, 2, 8, 4, 9};
38    int n = 5;
39    int k = 3;
40
41    std::cout << solve(n, a, k) << std::endl;
42    
43    return 0;
44}

下⾯程序的时间复杂度是（ ），假设数组 a 的值域范围是 D。

01#include <iostream>
02#include <algorithm>
03bool check(int n, int a[], int k, int dist) {
04    int cnt = 1;
05    int last = a[0];
06    for (int i = 1; i < n; i++) {
07        if (a[i] - last >= dist) {
08            cnt++;
09            last = a[i];
10        }
11    }
12    return cnt >= k;
13}
14int solve(int n, int a[], int k) {
15    std::sort(a, a + n);
16    int l = 0;
17    int r = a[n - 1] - a[0];
18    while (l < r) {
19        int mid = (l + r + 1) / 2;
20        if (check(n, a, k, mid))
21            l = mid;
22        else
23            r = mid - 1;
24    }
25    return l;
26}
27int main() {
28    int a[] = {1, 2, 8, 4, 9};
29    int n = 5;
30    int k = 3;
31    std::cout << solve(n, a, k) << std::endl;
32    return 0;
33}

某⼆叉树共有 $10$ 个结点，记为 $A\sim J$，已知它的先序遍历序列为：A B D H I E C F J G，中序遍历序列为：H D I B E A F J C G，则该⼆叉树的后序遍历序列是（ ）。

下面 schedule 函数的时间复杂度为（ ）。

01#include <algorithm>
02using namespace std;
03struct activity {
04    int id, start, end;
05};
06bool compare(activity a, activity b) {
07    return a.end < b.end;
08}
09int schedule(int n, activity * p) {
10    sort(p, p + n, compare);
11    int cnt = 0, end = 0;
12    for (int i = 0; i < n; i++) {
13        if (p[i].start >= end) {
14            end = p[i].end;
15            cnt++;
16        }
17    }
18    return cnt;
19}

下列代码片段的时间复杂度为（ ）。

01long long s = 0;
02for (int i = 1; i <= n; i++) {
03    for (int j = 1; j * j <= n; j++) {
04        s += i + j;
05    }
06}

某优化问题的答案是 $[1, M]$ 内的整数，存在单调判定函数 check(x)，且每次判定的时间复杂度为 $O(n)$。
使用二分答案求最小可行值，整体时间复杂度通常为（ ）。