CCF GESP C++ 五级 (2025 年 03 月)

一、单选题（每题 2 分，共 30 分）

第 1 题：链表不具备的特点是 ( )｡

{{ select(1) }}

• 可随机访问任何一个元素
• 插入､删除操作不需要移动元素
• 无需事先估计存储空间大小
• 所需存储空间与存储元素个数成正比

第 2 题：双向链表中每个结点有两个指针域 prev 和 next，分别指向该结点的前驱及后继结点｡设 p 指向链表中的一个结点，它的前驱结点和后继结点均非空｡要删除结点 p，则下述语句中错误的是 ( )｡

p->next->prev = p->next;
p->prev->next = p->prev;
delete p;

p->prev->next = p->next; 
p->next->prev = p->prev;
delete p;

p->next->prev = p->prev;
p->next->prev->next = p->next;
delete p;

p->prev->next = p->next;
p->prev->next->prev = p->prev; 
delete p;

{{ select(2) }}

• 1
• 2
• 3
• 4

第 3 题：假设双向循环链表包含头尾哨兵结点 (不存储实际内容)，分别为 head 和 tail，链表中每个结点有两个指针域 prev 和 next，分别指向该结点的前驱及后继结点｡下面代码实现了一个空的双向循环链表，横线上应填的最佳代码是 ( )｡

// 链表结点
template <typename T>
struct ListNode {
    T data;
    ListNode* prev;
    ListNode* next;
    // 构造函数 
    explicit ListNode(const T& val = T()) : data(val), prev(nullptr), next(nullptr) {}
};

struct LinkedList {
    ListNode<T>* head; 
    ListNode<T>* tail;
};

void InitLinkedList(LinkedList* list) {
    list->head = new ListNode<T>; 
    list->tail = new ListNode<T>; 
    ________________________// 在此处填入代码
};

list->head->prev = list->head;
list->tail->prev = list->head;

list->head->next = list->tail;
list->tail->prev = list->head;

list->head->next = list->tail;
list->tail->next = list->head;

list->tail->next = nullptr; 
list->head->next = list->tail;

{{ select(3) }}

• 1
• 2
• 3
• 4

第 4 题：用以下辗转相除法 (欧几里得算法) 求 gcd (84, 60) 的步骤中，第二步计算的数是 ( )｡

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

{{ select(4) }}

• 84 和 60
• 60 和 24
• 24 和 12
• 12 和 0

第 5 题：根据唯一分解定理（唯一分解定理，也称为算术基本定理，是数论中的一个核心定理。它表明，​每个大于1的自然数都可以唯一地分解为质数的乘积（不考虑质数的排列顺序）​），下面整数的唯一分解是正确的 ( )。

{{ select(5) }}

• 18=3×6
• 28=4×7
• 36=2×3×6
• 30=2×3×5

第 6 题：下述代码实现素数表的线性筛法，筛选出所有小于等于 n 的素数，横线上应填的最佳代码是 ( )。

vector<int> sieve_linear(int n){
    vector<bool> is_prime(n +1,true);
    vector<int> primes;
    if(n<2) return primes;

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

{{ select(6) }}

• j<primes.size()
• i * primes[j] <= n
• j < primes.size() && i * primes[j] <= n
• j <= n

第 7 题：在程序运行过程中，如果递归调用的层数过多，会因为 ( ) 引发错误｡

{{ select(7) }}

• 系统分配的栈空间溢出
• 系统分配的堆空间溢出
• 系统分配的队列空间溢出
• 系统分配的链表空间溢出

第 8 题：对下面两个函数，说法错误的是 ( )｡

int factorialA(int n) {
    if (n <= 1) return 1; 
    return n * factorialA(n-1);
}

int factorialB(int n) {
    if (n <= 1) return 1; 
    int res = 1;
    for(int i=2; i<=n; i++)
        res *= n;
}

{{ select(8) }}

• 两个函数的实现的功能相同｡
• 两个函数的时间复杂度均为 O(n)｡
• factorialA采用递归方式｡
• factorialB采用递归方式｡

第 9 题：下算法中，( ) 是不稳定的排序｡

{{ select(9) }}

• 选择排序
• 插入排序
• 归并排序
• 冒泡排序

第 10 题：考虑以下 C++ 代码实现的快速排序算法，将数据从小到大排序，则横线上应填的最佳代码是 ( )｡

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 基准值
    int i = low - 1;
    for (int j = low; j < high; j++) {
      _____________________// 在此处填入代码
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// 快速排序
void quickSort(vector<int>& arr, int low, int high) { 
    if (low < high) { 
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

if (arr[j] > pivot) {
    i++;
    swap(arr[i], arr[j]);
} 

if (arr[j] < pivot) {
    i++;
    swap(arr[i], arr[j]);
}

if (arr[j] < pivot) { 
    swap(arr[i], arr[j]);
    i++;
}

if (arr[j] == pivot) {
    i++;
    swap(arr[i], arr[j]);
}

{{ select(10) }}

• 1
• 2
• 3
• 4

第 11 题：若用二分法在 [1, 100] 内猜数，最多需要猜 ( ) 次｡

{{ select(11) }}

• 100
• 10
• 7
• 5

第 12 题：下面代码实现了二分查找算法，在数组 arr 找到目标元素 target 的位置，则横线上能填写的最佳代码是 ( )｡

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) { 
        _______________________// 在此处填入代码
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
        return -1;
    }
}

{{ select(12) }}

• int mid = left + (right - left) / 2;
• int mid = left;
• int mid = (left + right) / 2;
• int mid = right;

第 13 题：贪心算法的核心特征是 ( )｡

{{ select(13) }}

• 总是选择当前最优解
• 回溯尝试所有可能
• 分阶段解决子问题
• 总能找到最优解

第 14 题：函数int findMax(int arr[], int low, int high)计算数组中最大元素，其中数组arr从索引low到high，( ) 正确实现了分治逻辑｡

if (low == high)
    int mid = (low + high) / 2; 
    return arr[low];
    return arr[mid];

if (low >= high)
    int mid = (low + high) / 2; 
    return arr[low];
    int leftMax = findMax(arr, low, mid - 1); 
    int rightMax = findMax(arr, mid, high);
    return leftMax + rightMax;

if (low > high)
    return 0;
    int mid = low + (high - low) / 2; 
    int leftMax = findMax(arr, low, mid);
    int rightMax = findMax(arr, mid + 1, high); 
    return leftMax * rightMax;

if (low == high)
    return arr[low];
    int mid = low + (high - low) / 2;
    int leftMax = findMax(arr, low, mid);
    int rightMax = findMax(arr, mid + 1, high); 
    return (leftMax > rightMax)? leftMax : rightMax; 

{{ select(14) }}

• 1
• 2
• 3
• 4

第 15 题：小杨编写了一个如下的高精度乘法函数，则横线上应填写的代码为 ( )｡

vector<int> multiply(vector<int>& a, vector<int>& b) { 
    int m = a.size(), n = a.size(); 
    vector<int> c(m + n, 0);

    // 逐位相乘，逆序存储 
    for (int i = 0; i < m; i++) { 
        for (int j = 0; j < n; j++) {
            c[i + j] += a[i] * b[j];
        }
    }

    // 处理进位
    int carry = 0;
    for (int k = 0; k < c.size(); ++k) {
        _________________// 在此处填入代码
        c[k] = temp % 10; 
        carry = temp / 10;
    }
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;
}

{{ select(15) }}

• int temp = c[k];
• int temp = c[k] + carry;
• int temp = c[k] - carry;
• int temp = c[k] * carry;

二、判断题（每题2分，共20分）

第 1 题：单链表中删除某个结点 p (非尾结点)，但不知道头结点，可行的操作是将 p 的值设为p->next的值，然后删除p->next｡

{{ select(16) }}

• 对
• 错

第 2 题：链表存储线性表时要求内存中可用存储单元地址是连续的｡

{{ select(17) }}

• 对
• 错

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

{{ select(18) }}

• 对
• 错

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

{{ select(19) }}

• 对
• 错

第 5 题：递归函数必须具有一个终止条件，以防止无限递归｡

{{ select(20) }}

• 对
• 错

第 6 题：快速排序算法的时间复杂度与输入是否有序无关，始终稳定为 O(nlogn) 。

{{ select(21) }}

• 对
• 错

第 7 题：归并排序算法的时间复杂度与输入是否有序无关，始终稳定为O(nlogn) 。

{{ select(22) }}

• 对
• 错

第 8 题：二分查找适用于对无序数组和有序数组的查找｡

{{ select(23) }}

• 对
• 错

第 9 题：小杨有 100 元去超市买东西，每个商品有各自的价格，每种商品只能买 1 个，小杨的目标是买到最多数量的商品｡小杨采用的策略是每次挑价格最低的商品买，这体现了分治思想｡

{{ select(24) }}

• 对
• 错

第 10 题：归并排序算法体现了分治算法，每次将大的待排序数组分成大小大致相等的两个小数组，然后分别对两个小数组进行排序，最后对排好序的两个小数组合并成有序数组｡

{{ select(25) }}

• 对
• 错