2024年12月 GESP C++ 4级

下面的语句中，（ ）正确定义了一个计算浮点数的平方的函数，并成功调用该函数。

下面代码的描述中，正确的是（ ）。

void n_chars(char c, int n) {
    while (n-- > 0)
        cout << c;
}
char my_char = 'w';
int times = 5;
n_chars(my_char, times);

给定以下代码，

void func(int& x) {
    x = x * 2;
}
int a = 5;
func(a);

执行上述代码后，变量 $a$ 的值为（ ）。

运行下面代码，屏幕上输出是（ ）。

double* p_arr = new double [3];
p_arr[0] = 0.2;
p_arr[1] = 0.5;
p_arr[2] = 0.8;
p_arr += 1;
cout << p_arr[0] << endl;
p_arr -= 1;
delete p_arr;

运行下面代码片段后，$x$ 和 *p 的结果分别是（ ）。

int x = 20;
int* p = &x;
*p = *p + 2;

下面的描述中，（ ）不能正确定义一个名为 Student 的结构体以及一个包含 $20$ 个元素的结构数组。

假定整型是 $32$ 位，对一个 $2$ 行 $3$ 列的二维整数数组 array，假设数组第一个元素在内存中的地址为 $0x7ffee4065820$，则第 $2$ 行第 $2$ 个元素的地址 &array[1][1] 为（ ）。

int array[2][3] = {
    {0, 1, 2},
    {3, 4, 5}
};

下面（ ）正确定义二维数组。

下面代码采用递推算法来计算斐波那契数列，则横线上应填写（ ）。

int fib(int n) {
    if (n == 0 || n == 1)
        return n;
    int f1 = 0;
    int f2 = 1;
    int result = 0;
    for (int i = 2; i <= n; i++) {
        ________________________________ // 在此处填入代码
    }
    return result;
}

下面关于排序算法（冒泡排序、插入排序和选择排序）的描述中，不正确的是（ ）。

冒泡排序的第一轮操作是从左到右遍历数组，通过两两比较相邻元素，将当前最大的元素移动到末尾。给定数组 $arr[]=\{4,1,3,1,5,2\}$，执行第一轮冒泡排序后数组 $arr$ 中的内容为（ ）。

给定如下代码，其时间复杂度为（ ）。

int cellRecur(int n) {
    if (n == 1)
        return 1;
    return cellRecur(n - 1) + cellRecur(n - 1) + 1;
}

下面代码实现了插入排序函数，则横线上应填写（ ）。

void insertion_sort(vector<int> &nums) {
    for (int i = 1; i < nums.size(); i++) {
        ________________________________ { // 在此处填入代码
            while (j >= 0 && nums[j] > base)
                nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = base;
    }
}

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

运行下面的代码，将出现什么情况？（ ）

double hmean(double a, double b) {
    if (a == -b)
        throw runtime_error("Runtime error occurred");
    return 2.0 * a * b / (a + b);
}
int main() {
    double x = 10;
    double y = -10;
    try {
        int result = hmean(x, y);
        cout << "hmean: " << result << endl;
    }
    catch (const runtime_error& e) {
        cout << "Caught: " << e.what() << endl;
    } catch (...) {
        cout << "Caught an unknown exception." << endl;
    }
    return 0;
}

在 C++ 中，下面代码可以正确定义指针和初始化指针。

int* ptr;
*ptr = 10;

一个函数必须在调用之前既声明又定义。

函数参数可以通过值传递、引用传递和指针传递，这样函数内对参数的修改可以直接修改传入变量的值。

int arr[3][] 是一个正确的二维数组的声明。

递推是一种通过已知的初始值和递推公式，逐步求解目标值的算法。

某算法的递推关系式为 $T(n)=2T(n-1)+1$（$n$ 为正整数）及 $T(1)=1$，则该算法的时间复杂度为 O(2n)O(2^n)O(2n)。

冒泡排序的平均时间复杂度为 O(n2)O(n^2)O(n2) ，但最优情况下为 $O(n)$ 。

冒泡排序和插入排序都是稳定的排序算法。

选择排序是稳定的排序算法。

在 C++ 语言中，如果一个函数可能抛出异常，那么一定要在 try 子句里调用这个函数。

试题名称：Recamán

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

小杨最近发现了有趣的 Recamán 数列，这个数列是这样生成的：

• 数列的第一项 a1a_1a1​ 是 $1$；
• 如果 ak−1−ka_{k-1}-kak−1​−k 是正整数并且没有在数列中出现过，那么数列的第 $k$ 项 aka_kak​ 为 ak−1−ka_{k-1}-kak−1​−k，否则为 ak−1+ka_{k-1}+kak−1​+k。

小杨想知道 Recamán 数列的前 $n$ 项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。

输入格式

第一行，一个正整数 $n$。

输出格式

一行，$n$ 个空格分隔的整数，表示 Recamán 数列的前 $n$ 项从小到大排序后的结果。

样例输入 #1

5

样例输出 #1

1 2 3 6 7

样例输入 #2

8

样例输出 #2

1 2 3 6 7 12 13 20

说明/提示

样例解释

对于样例 1，$n=5$：

• a1=1a_1=1a1​=1；
• a1−2=−1a_1-2=-1a1​−2=−1，不是正整数，因此 a2=a1+2=3a_2=a_1+2=3a2​=a1​+2=3；
• a2−3=0a_2-3=0a2​−3=0，不是正整数，因此 a3=a2+3=6a_3=a_2+3=6a3​=a2​+3=6；
• a3−4=2a_3-4=2a3​−4=2，是正整数，且没有在数列中出现过，因此 a4=a3−4=2a_4=a_3-4=2a4​=a3​−4=2；
• a4−5=−3a_4-5=-3a4​−5=−3，不是正整数，因此 a5=a4+5=7a_5=a_4+5=7a5​=a4​+5=7。

a1,a2,a3,a4,a5a_1,a_2,a_3,a_4,a_5a1​,a2​,a3​,a4​,a5​ 从小到大排序的结果为 $1,2,3,6,7$。

数据范围

对于所有数据点，保证 $1\le n\le 3000$。

试题名称：字符排序

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

小杨有 $n$ 个仅包含小写字母的字符串 s1,s2,…,sns_1,s_2,\ldots,s_ns1​,s2​,…,sn​，小杨想将这些字符串按一定顺序排列后拼接到一起构成字符串 $t$。小杨希望最后构成的字符串 $t$ 满足：

• 假设 tit_iti​ 为字符串 $t$ 的第 $i$ 个字符，对于所有的 $j<i$ 均有 tj≤tit_j\le t_itj​≤ti​。两个字符的大小关系与其在字母表中的顺序一致，例如 $\text{e}<\text{g}<\text{p}<\text{s}$。

小杨想知道是否存在满足条件的字符串排列顺序。

输入格式

第一行包含一个正整数 $T$，代表测试数据组数。

对于每组测试数据，第一行包含一个正整数 $n$，含义如题面所示。

之后 $n$ 行，每行包含一个字符串 sis_isi​。

输出格式

对于每组测试数据，如果存在满足条件的排列顺序，输出（一行一个）$\text{1}$，否则输出（一行一个） $\text{0}$。

样例输入 #1

3
3
aa
ac
de
2
aac
bc
1
gesp

样例输出 #1

1
0
0

说明/提示

样例解释

对于第一组测试数据，一种可行的排列顺序为 $\text{aa}+\text{ac}+\text{de}$，构成的字符串 $t$ 为 $\text{aaacde}$，满足条件。

对于全部数据，保证有 $1\le T,n\le 100$，每个字符串的长度不超过 $10$。