CSP-J 卷

早期计算机内存不够大，可以将字库固化在一个包含只读存储器的扩展卡中插入计算机主板帮助处理汉字。

神威·太湖之光超级计算机是中国自主研制的超级计算机，在全球超级计算机 TOP500 排行榜中多次荣膺榜首。

C++ 表达式 int(3.14) 的值为 3。

C++ 语句 cout << (2, 3, "23") 的输出为 2, 3, 23。

C++ 的循环语句 for (int i = 0; i < 10; i += 2) 表示 i 从 0 开始到 10 结束但不包含 10，间隔为 2。

以下奖项与计算机领域最相关的是（ ）。

下面的哪一个不是操作系统名字？（ ）

C++ 语句 cout << ((10 <= N <= 12)? "true":"false") 中，假设整型变量 N 为 12，则其输出为 true。原因是执行 10 <= N 后其值为 true，true 与 12 相比仍然是 true。（ ）

C++ 表达式 (sqrt(N) * sqrt(N)) == N 中的 N 如果为正整数，则表达式的值为 true，相当于开平方后平方是本身。（ ）

下面 C++ 执行后将输出 3*2=6。（ ）

01int a=2, b = 3;
02a=a-b;
03b=a+b;
04a=b-a;
05printf("%d*%d=%d\n", a, b, a*b);

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

01int i;
02for (i = 1; i < 10; i++){
03    break;
04    continue;
05}
06cout << i << endl;

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

01for (int i = 0; i < 5; i++)
02    for(int j = 0; j < i; j++)
03        printf("OK\n");

将下面 C++ 代码中的 for 循环中的 i = 1 调整为 i = 0 的输出结果相同。（ ）

01int tnt = 0;
02for (int i = 1; i < 5; i++) // i=1
03    tnt += i;
04cout << tnt;

以下关于 C++ 变量作用域的说法，错误的是（ ）。

关于以下代码的说法正确的是（ ）。

01int reversed = 0;
02while (x != 0) {
03    int digit = x % 10;
04    x /= 10;
05    reversed = reversed * 10 + digit;
06}

以下 C++ 代码试图查找数组中的最大值，划线处应填入（ ）。

01#include <iostream>
02using namespace std;
03int findMax(int arr[], int size) {
04    int maxVal = ____________; // 划线处
05    for (int i = 1; i < size; i++) {
06        if (arr[i] > maxVal) {
07            maxVal = arr[i];
08        }
09    }
10    return maxVal;
11}

以下关于 C++ 函数的说法，正确的是（ ）。

辗转相除法用于求两个整数的最大公约数。

插入排序的时间复杂度是 $O(N \log N)$。

二分查找要求被搜索的序列是有序的，否则无法保证正确性。

分治算法的典型应用之一是归并排序，其时间复杂度为 $O(N \log N)$。

$5$ 个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（ ）种不同排列方法。

一个班级有 10 个男生和 12 个女生。如果要选出一个 3 人的小组，并且小组中必须至少包含 1 个女生，那么有多少种可能的组合？（ ）

假设有序表中有 1000 个元素，则用二分法查找元素 X 最多需要比较（ ）次。

在下面 C++ 代码中，由于删除了变量 ptr，因此 ptr 所对应的数据也随之删除，故执行下述代码时，将报错。

01int* ptr = new int(10);
02cout << *ptr << endl;
03delete ptr;
04cout << ptr << endl;

有若干根木头，长度存于 wood。每切一刀可以把一段木头分成两段。函数 check(wood, K, x) 返回：用不超过 K 刀，能否使所有木段长度都不超过 x。下面代码使用二分答案查找最小可行的 x，横线处应填（ ）。

01int binary_cut(vector<int>& wood, int K) {
02    int l = 1;
03    int r = 0;
04    for (int len : wood) r = max(r, len);
05    while (l < r) {
06        int mid = l + (r - l) / 2;
07        if (check(wood, K, mid))
08            ________________; // 在此处填入代码
09        else l = mid + 1;
10    }
11    return l;
12}

下面代码段实现了快速排序的划分操作（以首元素为基准），横线处代码应填入（ ）。

01int partition(vector<int>& arr, int low, int high) {
02    int pivot = arr[low];
03    int i = low, j = high;
04    while (i < j) {
05        while (i < j && arr[j] >= pivot) j--;
06        while (i < j && arr[i] <= pivot) i++;
07        if (i < j) swap(arr[i], arr[j]);
08    }
09    ________________; // 在此处填入代码
10    return i;
11}

以下（ ）没有涉及C++语言的面向对象特性支持。

有$6$个元素，按照6,5,4,3,2,1的顺序进入栈S，下列（ ）的出栈序列是不能出现的（ ）。

下面代码判断队列的第一个元素是否等于a，并删除该元素，横向上应填写（ ）。

01#include <iostream>
02#include <queue>
03using namespace std;
04
05bool is_front_equal(std::queue<int>& q, int a) {
06    bool is_equal = false;
07    if (!q.empty()) {
08        ____________ // 在此处填入代码
09    }
10    return is_equal;
11}

假设字母表{a,b,c,d,e}在字符串出现的频率分别为10%，15%，30%，16%，29%。若使用哈夫曼编码方式对字母进行二进制编码，则字符abcde分别对应的一组哈夫曼编码的长度分别为（ ）。

编者注：官方原题此处写作abcdef，但题目只给出了字母a至e及其五项频率；本题按题意修正为abcde。

以下C++代码实现 $n$ 位的格雷码，则横线上应填写（ ）。

01#include <iostream>
02#include <vector>
03#include <string>
04using namespace std;
05// 生成 n 位的格雷码
06vector<string> generate_graycode(int n) {
07    vector<string> graycode_list;
08    if (n <= 0) {
09        return graycode_list;
10    }
11
12    // 初始1位格雷码
13    graycode_list.push_back("0");
14    graycode_list.push_back("1");
15
16    // 迭代生成 n 位的格雷码
17    for (int i = 2; i <= n; i++) {
18        int current_size = graycode_list.size();
19
20        for (int j = current_size - 1; j >= 0; j--) {
21            graycode_list.push_back("1" + graycode_list[j]);
22        }
23
24        for (int j = 0; j < current_size; j++) {
25            ____________ // 在此处填入代码
26        }
27    }
28
29    return graycode_list;
30}

下列选项中，哪个可能是下图的深度优先遍历序列（ ）。

要判断⽆向图的连通性，在深度优先搜索和⼴度优先搜索中选择，深度优先的平均时间复杂度更低。

从$32$名学生中选出$4$人分别担任班长、副班长、学习委员和组织委员，老师要求班级综合成绩排名最后的$4$名学生不得参选班长或学习委员（仍可以参选副班长和组织委员），则共有 $P(30,4)$ 种不同的选法。