GESP2024年12月认证C++5级真题

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

第 2 题 在循环单链表中，节点的 next 指针指向下个节点，最后个节点的 next 指针指向（ ）

第 3 题 为了方便链表的增删操作，一些算法生成个虚拟头节点，方便统一删除头节点和其他节点。下代码实现 了删除链表中值为 val 的节点，横线上应填的最佳代码是( )。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

struct LinkedNode {
    int val;
    LinkedNode* next;
    LinkedNode(int val):val(val), next(nullptr){}
};

void removeElements(LinkedNode* head, int val) {
    if (head == nullptr) {
    return;
}
    LinkedNode* cur;
    LinkedNode* dummyHead = new LinkedNode(0); //虚拟头节点
    ________________________________ // 在此处填入代码
    while(cur ->next!= nullptr) {
        if(cur->next->val == val) {
            LinkedNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
            tmp = nullptr;
}
     else {
            cur = cur ->next;
     }
}
     head = dummyHead->next;
     delete dummyHead;
     dummyHead = nullptr;
}

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

int fibA(int n) { 
    if (n <= 1) return n; 
    int f1 = 0, f2 = 1; 
    for (int i = 2; i <= n; ++i) { 
        int temp = f2; 
        f2 = f1 + f2; 
        f1 = temp; 
    } 
    return f2; 
} 

int fibB(int n) {  
    if (n <= 1) return n; 
    return fibB(n - 1) + fibB(n - 2); 
}

第 5 题 两块长形地的长宽分别为 24和36米 ，要将它们分成正形的块，使得正形的尺尽可能大。杨 采如下的辗转相除函数 gcd(24, 36) 来求正形分块的边长，则函数 gcd 调顺序为（ ）。

int gcd(int a, int b) { 
    int big = a > b ? a : b; 
    int small = a < b ? a : b; 
    if (big % small == 0) { 
        return small; } return gcd(small, big % small); }

第 6 题 唯一分解定理表明，每个大于1的自然数可以唯一地写成若个质数的乘积。下面函数将自然数n的所有质因素找出来，横线上能填写的最佳代码是（ ）。

#include vector get_prime_factors(int n) { 
    vector factors; 
    if (n <= 1) { 
        cout << "输入的数必须是大于1的正整数" << endl; 
        return; 
     } 
     while (n % 2 == 0) { 
        factors.push_back(2); n /= 2; 
     } 
     ________________________________ { // 在此处填入代码 
        while (n % i == 0) { 
             factors.push_back(i); 
             n /= i; 
         } 
     } 
     if (n > 2) { 
     factors.push_back(n); 
    } 
     return factors; 
}

第 7 题 下述代码实现素数表的埃拉托尼(埃)筛法，筛选出所有小于等于n 的素数。

vector 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); 
        for (int j = i * i; j <= n; j += i) { 
            is_prime[j] = false; 
           } 
        }
    } 
    for (int i = sqrt(n) + 1; i <= n; i++) { 
        if (is_prime[i]) { 
             primes.push_back(i); 
        } 
      } 
   return primes; 
}

第 8 题 下述代码实现素数表的线性筛法，筛选出所有于等于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); 
        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) { 
            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;
}

第 9 题 考虑以下C++代码实现的快速排序算法：

int partition(vector& arr, int left, int right) { 
    int pivot = arr[right]; // 基准值 
    int i = left - 1; 
    for (int j = left; j < right; j++) { 
        if (arr[j] < pivot) { 
            i++; 
            swap(arr[i], arr[j]); 
        } 
   } 
   swap(arr[i + 1], arr[right]); 
   return i + 1; } 
// 快速排序 
void quickSort(vector& arr, int left, int right) { 
    if (left < right) { 
        int pi = partition(arr, left, right); 
        quickSort(arr, left, pi - 1); 
        quickSort(arr, pi + 1, right); 
    } 
}

以下关于快速排序的说法，正确的是（ ）。

第 10 题 下关于归并排序，描述正确的是（ ）。

第 11 题 给定个长度为 的有序数组 nums ，其中所有元素都是唯一的。下面的函数返回数组中元素 target 的索 引。

int binarySearch(vector &nums, int target, int left, int right) { 
    if (left > right) { 
       return -1; 
    } 
    int middle = left + ((right - left) / 2); 
    if (nums[middle] == target) { 
        return middle; 
    } 
    else if (nums[middle] < target) { 
         return binarySearch(nums, target, middle + 1, right); 
    } 
    else 
         return binarySearch(nums, target, left, middle - 1); 
    } 
}

int Find(vector &nums, int target) {
int n = nums.size();
return binarySearch(nums, target, 0, n – 1);
}

关于上述函数，描述不正确的是（ ）。

第 12 题 给定个长度为 的有序数组 nums ，其中可能包含重复元素。下面的函数返回数组中某个元素 target 的 左边界，若数组中不包含该元素，则返回 −1 。例如在数组 nums = [5,7,7,8,8,10] 中查找 target=8 ，函数返回8在数组中的左边界的索引为 3。则横线上应填写的代码为（ ）。

int getLeftBoundary(vector& nums, int target) { 
    int left = 0; 
    int right = nums.size() - 1; 
    while (left < right) { 
        int middle = left + ((right - left) / 2); 
        if (target <= nums[middle]) 
           ________________________________ // 在此处填入代码 
        else left = middle+1; 
      } 
      return nums[left]==target?left:-1; 
}

第 13 题 假设有多个孩子，数组 g 保存所有孩子的胃口值。有多块饼干，数组 s 保存所有饼干的尺寸。小杨给孩子们发饼干，每个孩子最多只能给一块饼干。饼干的尺寸大于等于孩的胃时，孩子才能得到满足。小杨的目标是尽可能满足越多数量的孩子，因此打算采用贪心算法来找出能满足的孩的数目，则横线上应填写的代码为（ ）。

int cooki4children(vector& g, vector& s) { 
    sort(g.begin(), g.end()); 
    sort(s.begin(), s.end()); 
    int index = s.size() - 1; // 饼干数组下标 
    int result = 0; 
    for (int i = g.size() - 1; i >= 0; i--) { 
        if (index >= 0 && s[index] >= g[i]) { 
            ________________________________ // 在此处填入代码 
        } 
     } 
 return result; 
}

第 14 题 关于分治算法，以下说法中不正确的是（ ）。

第 15 题 杨编写了个如下的精度减法函数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

vector<int> highPrecisionSubtract(vector<int> a, vector<int> b) {
    vector<int> result;
    int borrow = 0;
    for (int i = 0; i < a.size(); ++i) {
      int digitA = a[i];
      int digitB = i < b.size() ? b[i] : 0;
      int diff = digitA - digitB - borrow;
      if (diff < 0) {
        diff += 10;
        borrow = 1;
     }
     else {
      borrow = 0;
}
      result.push_back(diff);
}
    while (result.size() > 1 && result.back() == 0) {
       result.pop_back();
}
     return result;
}

第 16题 单链表只支持在表头进插入和删除操作。

第 17 题 线性筛相对于埃拉托斯特尼筛法，每个合数只会被它的最小质因数筛去次一次，因此效率更高。

第 18 题 任何个大于1的自然数都可以分解成若个不同的质数的乘积，且分解式是唯一的。

第 19题 贪心算法通过每步选择当前最优解，从而一定能获得全局最优解。

第 20 题 递归算法必须有一个明确的结束条件，否则会导致无限递归并可能引发栈溢出。

第21题 快速排序和归并排序的平均时间复杂度均为O(nlogn) ，且都是稳定排序。

第 22 题 快速排序的时间复杂度总比插入排序的时间复杂度低。

第 23题 二分查找仅适于数组不适合链表，因为二分查找需要跳跃式访问元素，链表中执跳跃式访问的效率低。

第 24 题 对有序数组 {5,13,19,21,37,56,64,75,88,92,100} 进分查找，成功查找元素 19 的较次数是2。

第25题 递归函数每次调时，系统都会为新开启的函数分配内存，以存储局部变量、调地址和其他信息 等，导致递归通常迭代更加耗费内存空间。