C++GESP5级202409解析

wrong_here_why · 2024-11-07 21:24:01 · 算法·理论

选择题

1. 关于链表和数组的描述，错误的是（C）。

• A. 数组大小固定，链表大小可动态调整。 正确，数组大小在定义时确定，而链表可以根据需要动态添加或删除节点。
• B. 数组支持随机访问，链表只能顺序访问。 正确，数组可以通过下标直接访问元素，而链表需要从头节点开始顺序查找。
• C. 存储相同数目的整数，数组比链表所需的内存多。 错误，数组存储元素时不需要额外的指针空间，而链表每个节点需要存储数据以及指向下一个节点的指针，因此内存占用更大。
• D. 数组插入和删除元素效率低，链表插入和删除元素效率高。 正确，数组插入和删除元素需要移动大量元素，而链表只需要修改指针指向即可。

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

• A. p->next->prev = s; s->prev = p; p->next = s; s->next = p->next; 错误，指针指向错误，会导致s节点指向自身。
• B. p->next->prev = s; p->next = s; s->prev = p; s->next = p->next; 错误，指针指向错误，会导致s节点指向自身。
• C. s->prev = p; s->next = p->next; p->next = s; p->next->prev = s; 错误，指针指向错误，会导致s节点指向自身。
• D. s->next = p->next; p->next->prev = s; s->prev = p; p->next = s;正确，正确修改了指针指向，完成了插入操作。

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

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

• A. sumA体现了迭代的思想。 正确，sumA函数使用循环迭代计算结果。
• B. SumB采用的是递归方式。 正确，sumB函数调用自身进行计算，属于递归方式。
• C. SumB函数比SumA的时间效率更高。 错误，sumB函数的递归调用会带来额外的函数调用开销，时间效率低于sumA函数。
• D. 两个函数的实现的功能相同。 正确，两个函数都实现了计算1到n的和的功能。

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

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

• A. 20 错误，20不是12的倍数，不符合函数返回条件。
• B. 12 错误，12不是20的倍数，不符合函数返回条件。
• C. 4 正确，函数计算的是最大公约数，20和12的最大公约数为4。
• D. 2 错误，2不是20和12的最大公约数。

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

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

• A. for (int j = i; j <= n; j++) 错误，应该从i的倍数开始筛除，而不是从i开始。
• *B. for (int j = i i; j <= n; j++)** 错误，应该每次增加i，而不是1。
• *C. for (int j = i i; j <= n; j += i**) 正确，从i的平方开始，每次增加i，筛除i的倍数。
• D. for (int j = i; j <= n; j += i) 错误，应该从i的倍数开始筛除，而不是从i开始。

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

vector<int> sieve_linear(int n) {
  vector<bool> is_prime(n + 1, true);
    vector<int> primes; 3 4 5 6 7 8
  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;
}

• *A. for (int j = 0; j < primes.size() && i primes[j] <= n; j++)** 正确，遍历已找到的素数，筛除i的倍数。
• *B. for (int j = 1; j < primes.size() && i j <= n; j++)** 错误，j应该从0开始。
• *C. for (int j = 2; j < primes.size() && i primes[j] <= n; j++)** 错误，j应该从0开始。
• D. 以上都不对 错误，选项A是正确的。

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

#include <iostream>
#include <vector>
vector<int> get_prime_factors(int n) {
  vector<int> factors;
  while (n % 2 == 0) {
    factors.push_back(2);
    n /= 2;
  }
  for (int i = 3; i * i <= n; i += 2) {
    while (n % i == 0) {
      factors.push_back(i);
      n /= i;
    }
  }
  if (n > 2) {
    factors.push_back(n);
  }
  return factors;
}

• A. O(n) 错误，算法时间复杂度并非线性。
• B. O(n^2)$ 错误，算法时间复杂度并非平方级别。
• C. O(sqrt(n)) 正确，算法主要步骤是遍历从2到sqrt(n)的数，时间复杂度为O(sqrt(n))。
• D.O(n \log n) 错误，算法时间复杂度并非对数级别。

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

作者被名字骗了一开始以为是快速幂

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

• A. O(n) 正确，算法时间复杂度线性。
• B. O(n^2) 错误，算法时间复杂度并非平方级别。
• C. O(\log n) 错误，算法时间复杂度没有退化。
• D. O(n \log n) 错误，算法时间复杂度并非对数级别。

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

• A. 快速排序对于此类输入的表现最好，因为数组已经排序。 错误，选择已排序数组第一个元素作为基准会导致每次划分都只划分出一个元素，效率极低。
• B. 快速排序对于此类输入的时间复杂度是 O(n \log n)。 错误，由于每次划分都只划分出一个元素，算法退化成了 O(n^2)。
• C. 快速排序对于此类输入的时间复杂度是 O(n^2 )。 正确，选择已排序数组第一个元素作为基准会导致每次划分都只划分出一个元素，算法退化成了 O(n^2 )。
• D. 快速排序无法对此类数组进行排序，因为数组已经排序。 错误，快速排序可以处理已排序数组，但效率极低。

10. 考虑以下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); 4

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

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

• A. n 错误，每次递归调用会分成两个子数组，调用次数远大于n。
• B.n \log n 正确，归并排序的时间复杂度为 O(n \log n)，merge 函数的调用次数与 log n 成正比。
• C. n^2 错误，算法时间复杂度并非平方级别。
• D. log n 错误，merge 函数的调用次数与 \log n 成正比，而不是等于 \log n。

11. 现在有 n 个人要过河，每只船最多载2人，船的承重为100kg。下列代码中，数组 weight 中保存有 n 个人 的体重（单位为kg），已经按从小到大排好序，代码输出过河所需要的船的数目，采用的思想为（B）。

int i, j;
int count = 0;
for (i = 0, j = n - 1; i < j; j--) {     
  if (weight[i] + weight[j] <= 100) {         
  i++;     
  }     
  count++;
}
printf("过河的船数：%d\n", count);

• A. 枚举算法 错误，枚举算法会尝试所有可能的组合，效率较低。
• B. 贪心算法 正确，算法每次选择体重最轻和最重的两个人过河，保证船的承重不超过100kg，并尽量减少过河次数。
• C. 迭代算法 错误，算法并非简单的迭代过程。
• D. 递归算法 错误，算法没有使用递归。

12. 关于分治算法，以下哪个说法正确 (A)？

• A. 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。 正确，这是分治算法的基本思想。
• B. 归并排序不是分治算法的应用。 错误，归并排序是典型的分治算法应用。
• C. 分治算法通常用于解决小规模问题。 错误，分治算法通常用于解决大规模问题。
• D. 分治算法的时间复杂度总是优于 O(n^2)。 错误，分治算法的时间复杂度取决于子问题的规模和合并子问题的代价。

13. 根据下述二分查找法，在排好序的数组 1，3，6，9，17，31，39，52，61，79 中查找数值 31 ，循环 while (left <= right) 执行的次数为（C）。

int binary_search(vector<int>& nums, int target) {
  int left = 0;
  int right = nums.size() - 1;

  while (left <= right) {
    int mid = left + (right - left) / 2;

    if (nums[mid] == target) {
      return mid;
    }
    else if (nums[mid] < target) {
      left = mid + 1;
    }
      else {
        right = mid - 1;
      }
  }

  return -1; // 如果找不到目标元素，返回-1
}

• A. 1 错误，第一次循环mid为4，不等于目标值。
• B. 2 错误，第二次循环mid为6，不等于目标值。
• C. 3 正确，第三次循环mid为5，等于目标值。
• D. 4 错误，第三次循环就找到了目标值。

14. 以下关于高精度运算的说法错误的是(C).

• A. 高精度计算主要是用来处理大整数或需要保留多位小数的运算。 正确，高精度计算可以处理超出标准数据类型范围的数值。
• B. 大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过 减法得到新的被除数，并累加商。 正确，这是大整数除法的基本思想。
• C. 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。 错误，高精度乘法的运算时间与两个整数的位数都有关。
• D. 高精度加法运算的关键在于逐位相加并处理进位。 正确，高精度加法需要逐位相加并处理进位。

• 15. 当 n=7 时，下面函数的返回值为（C）

  int fun(int n) {
  if (n == 1) return 1;
  else if (n >= 5) return n * fun(n - 2);
  else return n * fun(n - 1);
  }

选项 A. 105

• 错误。 选项 A 的值小于 210，不符合函数 fun(n) 的计算结果。

选项 B. 840

• 错误。 选项 B 的值大于 210，且无法通过 fun(n) 的递归调用计算得到。

选项 C. 210

• 正确。 正如解析中所述，通过递归调用和计算，当 n = 7 时，fun(n) 的返回值确实为 210。

选项 D. 420

• 错误。 选项 D 的值大于 210，且无法通过 fun(n) 的递归调用计算得到。

判断题

1. 在操作系统中，需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU将切换到下 一个进程。这种循环操作可以通过环形链表来实现。

• 正确。 环形链表可以形成一个闭环，方便地实现进程的循环调度。

2. 找出自然数n 以内的所有质数，常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中线性筛法效率更 高。

• 正确。 线性筛法的时间复杂度优于埃氏筛法。

3. 唯一分解定理表明任何一个大于1 的整数都可以唯一地分解为素数之和。

• 错误。 唯一分解定理表明任何一个大于1 的整数都可以唯一地分解为素数的乘积。

4. 贪心算法通过每一步选择局部最优解，从而一定能获得最优解。

• 错误。 贪心算法并不总能获得全局最优解，例如最优装载问题。

5. 快速排序和归并排序的平均时间复杂度均为 O(n \log n)，且都是稳定排序。

• 错误。 快速排序不是稳定排序，归并排序是稳定排序。

6. 插入排序的时间复杂度总是比快速排序低。

• 错误。 插入排序的时间复杂度在最坏情况下为 O(n^2)，而快速排序的平均时间复杂度为 O(n \log n)。

7. 引入分治策略往往可以提升算法效率。一方面，分治策略减少了操作数量；另一方面，分治后有利于系统的 并行优化。

• 正确。 分治策略可以将问题分解成更小的子问题，提高算法效率，并方便并行计算。

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

• 正确。 二分查找依赖于有序序列的性质，否则无法确定查找范围。

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

• 正确。 递归调用会增加函数调用的栈帧，可能导致栈空间不足。

10. 对于已经定义好的标准数学函数sin(x)，应用程序中的语句 y=sin(sin(x)); 是一种递归调用。

• 错误。 这不是递归调用，而是函数嵌套调用。