GESP C++ 5级 2024.06

下面 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;
}

下面 C++ 代码用于将输入金额换成最少币种组合方案，其实现算法是( )。

#include 
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 > money; //输入要换算的金额
 find_coins(money);
 
 for (int i = 0; i < N_COINS; i++)
 cout << coins_used[i] << endl;
 
 return 0;
}

小杨采用如下双链表结构保存他喜欢的歌曲列表：

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;
}

小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲，他将其作为链表的第一首歌曲，则下面横线上应填入的代码为（ ）。

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;
}

下面是根据欧几里得算法编写的函数，它计算的是 $a$ 与 $b$ 的（ ）。

int gcd(int a, int b) {
 while (b != 0) {
 int temp = b;
 b = a % b;
 a = temp;
 }
 return a;
}

欧几里得算法还可以写成如下形式:

int gcd(int a, int b) {
 return b == 0 ? a : gcd(b, a % b);
}

下面有关说法，错误的是（ ）。

下述代码实现素数表的线性筛法，筛选出所有小于等于 $n$ 的素数，则横线上应填的代码是( )。

vector linear_sieve(int n) {
 vector is_prime(n + 1, true);
 vector 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;
}

上题代码的时间复杂度是（ ）

为了正确实现快速排序，下面横线上的代码应为（ ）。

void qsort(vector& 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) 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); // 对右子数组进行快速排序
}

关于分治算法，以下哪个说法正确？