理论卷2024年9月GESP等级认证(C++) · 五级

GESP C++ 5级 2024.09

满分 100 · 及格 60 · 时长 60 分钟 · 共 27 题 (单选15 / 判断10 / 编程题2)

试卷阅览 · 免费预览前 10 题 · 交卷后可查看答案与解析

单选题号 #12078

分值 2

下面关于链表和数组的描述，错误的是（）。

数组大小固定，链表大小可动态调整。

数组支持随机访问，链表只能顺序访问。

存储相同数目的整数，数组比链表所需的内存多。

数组插入和删除元素效率低，链表插入和删除元素效率高。

单选题号 #12079

分值 2

通过（）操作，能完成在双向循环链表结点 $p$ 之后插入结点 $s$ 的功能（其中 $next$ 域为结点的直接后继， $prev$ 域为结点的直接前驱）。

p->next->prev = s; s->prev = p; p->next = s; s->next = p->next;

p->next->prev = s; p->next = s; s->prev = p; s->next = p->next;

s->prev = p; s->next = p->next; p->next = s; p->next->prev = s;

s->next = p->next; p->next->prev = s; s->prev = p; p->next = s;

单选题号 #12080

分值 2

对下面两个函数，说法错误的是（）。

int sumA(int n) {
 int res = 0;
 for (int i = 1; i <= n; i++) {
 res += i;
 }
 return res;
}

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

$sumA$ 体现了迭代的思想。

$SumB$ 采用的是递归方式。

$SumB$ 函数比 $SumA$ 的时间效率更高。

两个函数的实现的功能相同。

单选题号 #12081

分值 2

有如下函数 fun ，则 fun(20, 12) 的返回值为（）。

int fun(int a, int b) {
 if (a % b == 0)
 return b;
 else
 return fun(b, a % b);

$20$

$12$

$4$

$2$

单选题号 #12082

分值 2

下述代码实现素数表的埃拉托斯特尼筛法，筛选出所有小于等于 $n$ 的素数，则横线上应填的最佳代码是( )。

void sieve_Eratosthenes(int n) {
 vector is_prime(n + 1, true);
 vector primes;

 for (int i = 2; i * i <= n; i++) {
 if (is_prime[i]) {
 primes.push_back(i);
 ________________________________ { // 在此处填入代码
 is_prime[j] = false;
 }
 }
 }

 for (int i = sqrt(n) + 1; i <= n; i++) {
 if (is_prime[i]) {
 primes.push_back(i);
 }
 }

 return primes;
}

for (int j = i; j <= n; j++)

for (int j = i * i; j <= n; j++)

for (int j = i * i; j <= n; j += i)

for (int j = i; j <= n; j += i)

单选题号 #12083

分值 2

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

vector sieve_linear(int n) {
 vector is_prime(n + 1, true);
 vector primes;

 for (int i = 2; i <= n / 2; i++) {
 if (is_prime[i])
 primes.push_back(i);
 ________________________________ { // 在此处填入代码
 is_prime[i * primes[j]] = 0;
 if (i % primes[j] == 0)
 break;
 }
 }

 for (int i = n / 2 + 1; i <= n; i++) {
 if (is_prime[i])
 primes.push_back(i);
 }

 return primes;
}

for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)

for (int j = 1; j < primes.size() && i * j <= n; j++)

for (int j = 2; j < primes.size() && i * primes[j] <= n; j++)

以上都不对

单选题号 #12084

分值 2

下面函数可以将 $n$ 的所有质因数找出来，其时间复杂度是（）。

#include 
#include 

vector get_prime_factors(int n) {
 vector factors;

 while (n % 2 == 0) {
 factors.push_back(2);
 n /= 2;
 }

 for (int i = 3; i * i 2) {
 factors.push_back(n);
 }

 return factors;
}

$O(n^2)$

$O(nlogn)$

$O(\sqrt(n)logn)$

$O(n)$

单选题号 #12085

分值 2

现在用如下代码来计算 $x^n$ （ $n$ 个 $x$ 相乘），其时间复杂度为（）。

double quick_power(double x, unsigned n) {
 if (n == 0) return 1;
 if (n == 1) return x;
 return quick_power(x, n / 2) * quick_power(x, n / 2) * ((n & 1) ? x : 1);
}

$O(n)$

$O(n^2)$

$O(logn)$

$O(nlogn)$

单选题号 #12086

分值 2

假设快速排序算法的输入是一个长度为 $n$ 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项（）描述的是在这种情况下的快速排序行为。

快速排序对于此类输入的表现最好，因为数组已经排序。

快速排序对于此类输入的时间复杂度是 $O(nlogn)$ 。

快速排序对于此类输入的时间复杂度是 $O(n^2)$ 。

快速排序无法对此类数组进行排序，因为数组已经排序。

单选题号 #12087

分值 2

考虑以下 C++ 代码实现的归并排序算法：

void merge(int arr[], int left, int mid, int right) {
 int n1 = mid - left + 1;
 int n2 = right - mid;

 int L[n1], R[n2];

 for (int i = 0; i < n1; i++)
 L[i] = arr[left + i];
 for (int j = 0; j < n2; j++)
 R[j] = arr[mid + 1 + j];

 int i = 0, j = 0, k = left;
 while (i < n1 && j < n2) {
 if (L[i] <= R[j]) {
 arr[k] = L[i];
 i++;
 }
 else {
 arr[k] = R[j];
 j++;
 }
 k++;
 }

 while (i < n1) {
 arr[k] = L[i];
 i++;
 k++;
 }

 while (j < n2) {
 arr[k] = R[j];
 j++;
 k++;
 }
}

void merge_sort(int arr[], int left, int right) {
 if (left < right) {
 int mid = left + (right - left) / 2;

 merge_sort(arr, left, mid);
 merge_sort(arr, mid + 1, right);

 merge(arr, left, mid, right);
 }
}

对长度为 $n$ 的数组 $arr$ ，挑用函数 merge_sort(a, 0, n-1) ，在排序过程中 merge 函数的递归调用次数大约是
（）。

$O(1)$

$O(n)$

$O(logn)$

$O(nlogn)$

🔒

已解锁前 10 题

第 11~27 题（共 17 题）可在考试中作答

本卷为普通试卷：注册用户每题扣 1 积分（每日登录送 30 体验积分），交卷后查看答案与解析