GESP 2024年3月_C++五级试卷

第1题中级 2.0分单选

唯一分解定理描述的内容是（）？

A. 任意整数都可以分解为素数的乘积

B. 每个合数都可以唯一分解为一系列素数的乘积

C. 两个不同的整数可以分解为相同的素数乘积

D. 以上都不对

第2题中级 2.0分单选

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

A. 在每一步选择中都做当前状态下的最优选择

B. 在每一步选择中都选择局部最优解

C. 在每一步选择中都选择全局最优解

D. 以上都对

第3题中级 2.0分单选

下面的C++代码片段用于计算阶乘。请在横线处填入（），实现正确的阶乘计算。

A. return n * factorial(n - 1);

B. return factorial(n - 1) / n;

C. return n * factorial(n);

D. return factorial(n / 2) * factorial(n / 2);

第4题中级 2.0分单选

下面的代码片段用于在双向链表中删除一个节点。请在横线处填入（），使其能正确实现相应功能。

A. if (current->next != nullptr) current->next->prev = current->prev;

B. current->prev->next = current->next;

C. delete current->next;

D. current->prev = current->next;

第5题中级 2.0分单选

辗转相除法也被称为（）

A. 高斯消元法

B. 费马定理

C. 欧几里德算法

D. 牛顿迭代法

第6题中级 2.0分单选

下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是（）？

A. O(n)

B. O(2^n)

C. O(n²)

D. O(log n)

第7题中级 2.0分单选

下面的代码片段用于将两个高精度整数进行相加。请在横线处填入（），使其能正确实现相应功能。

A. result = to_string(sum % 10) + result;

B. result = to_string(carry % 10) + result;

C. result = to_string(sum / 10) + result;

D. result = to_string(sum % 10 + carry) + result;

第8题中级 2.0分单选

给定序列：1，3，6，9，17，31，39，52，61，79，81，90，96。使用以下代码进行二分查找查找元素82时，需要循环多少次，即最后输出的times值

A. 2

B. 5

C. 3

D. 4

第9题中级 2.0分单选

下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改，使其能正确实现相应功能。（）

A. num < 2 应该改为 num <= 2

B. 循环条件 i * i < num 应该改为 i * i <= num

C. 循环条件应该是 i <= num

D. 循环体中应该是 if (num % i != 0)

第10题中级 2.0分单选

在埃拉托斯特尼筛法中，要筛选出不大于n的所有素数，最外层循环应该遍历什么范围（）？

A. for (int i = 2; i <= n; ++i)

B. for (int i = 1; i < n; ++i)

C. for (int i = 2; i <= sqrt(n); ++i)

D. for (int i = 1; i <= sqrt(n); ++i)

第11题中级 2.0分单选

素数的线性筛法时间复杂度为（）。

A. O(n)

B. O(n log n)

C. O(n log log n)

D. O(√n)

第12题中级 2.0分单选

归并排序的基本思想是（）。

A. 动态规划

B. 分治

C. 贪心算法

D. 回溯算法

第13题中级 2.0分单选

在快速排序中，选择的主元素（pivot）会影响算法的（）。

A. 不影响

B. 时间复杂度

C. 空间复杂度

D. 时间复杂度和空间复杂度

第14题中级 2.0分单选

递归函数在调用自身时，必须满足（），以避免无限递归？

A. 有终止条件

B. 函数参数递减（或递增）

C. 函数返回值固定

D. 以上都对

第15题中级 2.0分单选

假设给定链表为: 1->3->5->7，若调用searchValue(head, 5)，函数返回值为（）。

A. 返回1

B. 返回0

T. 正确

F. 错误

第26题中级 25.0分编程

成绩排序

有N名同学，每名同学有语文、数学、英语三科成绩。你需要按如下规则对所有同学的成绩从高到低排序： 1. 比较总分，高者靠前； 2. 如果总分相同，则比较语文和数学两科总分，高者靠前； 3. 如果仍相同，则比较语文和数学两科的最高分，高者靠前； 4. 如果仍相同，则二人并列。你需要输出每位同学的排名，如遇多人并列，则他们排名相同，并留空后面的名次。

【输入格式】

第一行一个整数N，表示同学的人数。
接下来N行，每行三个非负整数分别表示该名同学的语文、数学、英语成绩。

【输出格式】

输出N行，按输入同学的顺序，输出他们的排名。

【样例输入】

<img src="/static/uploads/images/4aa5bebc36.png" style="max-width:35%;border-radius:6px;margin:8px 0;" />
【样例输出】

1
3
4
4
2
6
对于所有测试点，保证1<=N<=10^4。

第27题中级 25.0分编程

B-smooth数

小杨同学想寻找一种名为B-smooth数的正整数。如果一个正整数的最大质因子不超过B，则该正整数为B-smooth数。小杨同学想知道，对于给定的n和B，有多少个不超过n的B-smooth数。

【输入格式】

第一行包含两个正整数n和B，含义如题面所示。

【输出格式】

输出一个非负整数，表示不超过n的B-smooth数的数量。

【样例输入】

10 3
【样例输出】

7
【样例解释】

在不超过10的正整数中，3-smooth数有1,2,3,4,6,8,9，共7个。
对于全部数据，保证有1<=n<=10^6，1<=B<=10^6。

GESP 2024年3月_C++五级试卷

试卷题目预览

唯一分解定理描述的内容是（ ）？

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

下面的C++代码片段用于计算阶乘。请在横线处填入（ ），实现正确的阶乘计算。

下面的代码片段用于在双向链表中删除一个节点。请在横线处填入（ ），使其能正确实现相应功能。

辗转相除法也被称为（ ）

下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是（ ）？

下面的代码片段用于将两个高精度整数进行相加。请在横线处填入（ ），使其能正确实现相应功能。

给定序列：1，3，6，9，17，31，39，52，61，79，81，90，96。使用以下代码进行二分查找查找元素82时，需要循环多少次，即最后输出的times值

下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改，使其能正确实现相应功能。（ ）

在埃拉托斯特尼筛法中，要筛选出不大于n的所有素数，最外层循环应该遍历什么范围（ ）？

素数的线性筛法时间复杂度为（ ）。

归并排序的基本思想是（ ）。

在快速排序中，选择的主元素（pivot）会影响算法的（ ）。

递归函数在调用自身时，必须满足（ ），以避免无限递归？

假设给定链表为: 1->3->5->7，若调用searchValue(head, 5)，函数返回值为（ ）。

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

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

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

使用贪心算法解决问题时，每一步的局部最优解一定会导致全局最优解。

分治算法的核心思想是将一个大问题分解成多个相同或相似的子问题进行解决，最后合并得到原问题的解。

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

素数表的埃氏筛法和线性筛法的时间复杂度都是O(n)。

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

单链表和双链表都可以在常数时间内实现在链表头部插入或删除节点的操作。

在C语言中，递归的实现方式通常会占用更多的栈空间，可能导致栈溢出。