GESP-C++五级(2024-06)
CCF GESP C++ 五级 (2024 年 06 月)
一、单选题（每题 2 分，共 30 分）
1. 下面C++代码用于求斐波那契数列，该数列第1、2项为1，以后各项均是前两项之和。函数fibo()属于（）？
int fibo(int n) {
if (n <= 0)
return 0;
if (n == 1 || n == 2)
return 1;
int a = 1, b = 1, next;
for (int i = 3; i <= n; i++) {
next = a + b;
a = b;
b = next;
}
return next;
}
{{ select(1) }}
- 枚举算法
- 贪心算法
- 迭代算法
- 递归算法
2. 下面C++代码用于将输入金额换成最少币种组合方案，其实现算法是（）？
#include <iostream>
#include <vector>
using namespace std;
#define N_COINS 7
int coins[N_COINS] = {100, 50, 20, 10, 5, 2, 1};//货币面值,单位相同
int coins_used[N_COINS];
void find_coins(int money) {
for (int i = 0; i < N_COINS; i++) {
coins_used[i] = money / coins[i];
money = money % coins[i];
}
return;
}
int main() {
int money;
cin >> money; //输入要换算的金额
find_coins(money);
for (int i = 0; i < N_COINS; i++)
cout << coins_used[i] << endl;
return 0;
}
{{ select(2) }}
- 枚举算法
- 贪心算法
- 迭代算法
- 递归算法
3. 小杨采用如下双链表结构保存他喜欢的歌曲列表：
struct dl_node {
string song;
dl_node* next;
dl_node* prev;
};
小杨想在头指针为head的双链表中查找他喜欢的某首歌曲，采用如下查询函数，该操作的时间复杂度为（）？
dl_node* search(dl_node* head, string my_song) {
dl_node* temp = head;
while (temp != nullptr) {
if (temp->song == my_song)
return temp;
temp = temp->next;
}
return nullptr;
}
{{ select(3) }}
- O(1)
- O(n)
- O(logn)
- O(n^2)
4. 小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲，他将其作为链表的第一首歌曲，则下面横线上应填入的代码为（）？
void insert(dl_node *head, string my_song) {
p = new dl_node;
p->song = my_song;
p->prev = nullptr;
p->next = head;
if (head != nullptr) {
_____________________________ // 在此处填入代码
}
head = p;
}
{{ select(4) }}
- head->next->prev = p;
- head->next = p;
- head->prev = p;
- 触发异常，不能对空指针进行操作。
5. 下面是根据欧几里得算法编写的函数，它计算的是 a 与 b 的（）？
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
{{ select(5) }}
- 最小公倍数
- 最大公共质因子
- 最大公约数
- 最小公共质因子
6. 欧几里得算法还可以写成如下形式：
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
{{ select(6) }} 下面有关说法，错误的是（）？
- 本题的 gcd() 实现为递归方式。
- 本题的 gcd() 代码量少，更容易理解其辗转相除的思想。
- 当 a 较大时，本题的 gcd() 实现会多次调用自身，需要较多额外的辅助空间。
- 当 a 较大时，相比上题中的 gcd() 的实现，本题的 gcd() 执行效率更高。
7. 下述代码实现素数表的线性筛法，筛选出所有小于等于 n 的素数，则横线上应填的代码是（）？
vector<int> linear_sieve(int n) {
vector<bool> is_prime(n + 1, true);
vector<int> primes;
is_prime[0] = is_prime[1] = 0; // 0和1两个数特殊处理
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
primes.push_back(i);
}
_____________________// 在此处填写代码
is_prime[i * primes[j]] = 0;
if (i % primes[j] == 0)
break;
}
return primes;
}
{{ select(7) }}
- for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
- for (int j = 0; j <= sqrt(n) && i * primes[j] <= n; j++)
- for (int j = 0; j <= n; j++)
- for (int j = 1; j <= sqrt(n); j++)
8. 上题代码的时间复杂度是（）？
{{ select(8) }}
- O(n^2)
- O(nlogn)
- O(nloglogn)
- O(n)
9. 为了正确实现快速排序，下面横线上的代码应为（）？
void qsort(vector<int>& arr, int left, int right) {
int i, j, mid;
int pivot;
i = left;
j = right;
mid = (left + right) / 2; // 计算中间元素的索引
pivot = arr[mid]; // 选择中间元素作为基准值
do {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
swap(arr[i], arr[j]); // 交换两个元素
i++;
j--;
}
} (_____________);// 在此处填写
if (left < j) qsort(arr, left, j); // 对左子数组
if (i < right) qsort(arr, i, right); // 对右子数组
}
{{ select(9) }}
- while (i <= mid)
- while (i < mid)
- while (i < j)
- while (i <= j)
10. 关于分治算法，以下哪个说法正确？
{{ select(10) }}
- 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。
- 归并排序不是分治算法的应用。
- 分治算法通常用于解决小规模问题。
- 分治算法的时间复杂度总是优于 O(nlog(n))。
11. 根据下述二分查找法，在排好序的数组 1, 3, 6, 9, 17, 31, 39, 52, 61, 79, 81, 90, 96 中查找数值 82，和 82 比较的数组元素分别是（）？
int binary_search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1; // 如果找不到目标元素，返回-1
}
{{ select(11) }}
- 52, 61, 81, 90
- 52, 79, 90, 81
- 39, 79, 90, 81
- 39, 79, 90
12. 要实现一个高精度减法函数，则下面代码中加划线应该填写的代码为（）？
//假设a和b均为正数，且a表示的数比b大
vector<int> minus(vector<int> a, vector<int> b) {
vector<int> c;
int len1 = -size();
int len2 = -size();
int i, t;
for (i = 0; i < len2; i++) {
if (a[i] < b[i]) { // 借位
________________// 在此处填写代码
a[i] += 10;
}
t = a[i] - b[i];
c.push_back(t);
}
for (; i < len1; i++)
c.push_back(a[i]);
len3 = -size();
while (c[len3 - 1] == 0) {//去除前导0
c.pop_back();
len3--;
}
return c;
}
{{ select(12) }}
- a[i + 1]--;
- a[i]--;
- b[i + 1]--;
- b[i]--;
13. 设 A 和 B 是两个长度为 n 的有序数组，现将 A 和 B 合并成一个有序数组，归并排序算法在最坏情况下至少要做（）次比较？
{{ select(13) }}
- n^2
- nlogn
- 2n−1
- n
14. 给定如下函数：则当 n=7 时，函数返回值为（）？
int fun(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return fun(n - 2) - fun(n - 1);
}
{{ select(14) }}
- 0
- 1
- 21
- -11
15. 给定如下函数（函数功能同上题，增加输出打印）： 则当 n=4 时，屏幕上输出序列为（）？
int fun(int n) {
cout<< n << " ";
if (n == 1) return 1;
if (n == 2) return 2;
return fun(n - 2) - fun(n - 1);
}
{{ select(15) }}
- 4 3 2 1
- 1 2 3 4
- 4 2 3 1 2
- 4 2 3 2 1
二、判断题（每题2分，共20分）
1. 如果将双向链表的最后一个结点的下一项指针指向第一个结点，第一个结点的前一项指针指向最后一个结点，则该双向链表构成循环链表。
{{ select(16) }}
- 对
- 错
2. 数组和链表都是线性表，链表的优点是插入删除不需要移动元素，并且能随机查找。
{{ select(17) }}
- 对
- 错
3. 链表的存储空间物理上可以连续，也可以不连续。
{{ select(18) }}
- 对
- 错
4. 找出自然数 n 以内的所有质数，常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中埃氏筛法效率更高。
{{ select(19) }}
- 对
- 错
5. 唯一分解定理表明任何一个大于1的整数都可以唯一地表示为一系列质数的乘积，即质因数分解是唯一的。
{{ select(20) }}
- 对
- 错
6. 贪心算法通过每一步选择局部最优解来获得全局最优解，但并不一定能找到最优解。
{{ select(21) }}
- 对
- 错
7. 归并排序和快速排序都采用递归实现，也都是不稳定排序。
{{ select(22) }}
- 对
- 错
8. 插入排序有时比快速排序时间复杂度更低。
{{ select(23) }}
- 对
- 错
9. 在进行全国人口普查时，将其分解为对每个省市县乡来进行普查和统计。这是典型的分治策略。
{{ select(24) }}
- 对
- 错
10. 在下面C++代码中，由于删除了变量 ptr，因此 ptr 所对应的数据也随之删除，故执行下述代码时，将报错。
int* ptr = new int(10);
cout << *ptr << endl;
delete ptr;
cout << ptr << endl;
{{ select(25) }}
- 对
- 错
相关
在下列比赛中: