#1587. GESP-C++五级(2025-12)

GESP-C++五级(2025-12)

CCF GESP C++ 一级 (2025 年 12 月)

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

1. 对如下定义的循环单链表，横线处填写（ ）

// 循环单链表的结点
struct Node {
    int data; // 数据域
    Node* next; // 指针域
    Node(int d) : data(d), next(nullptr) {}
};

// 创建一个只有一个结点的循环单链表
Node* createList(int value) {
    Node* head = new Node(value);
    head->next = head;
    return head;
}

// 在循环单链表尾部插入新结点
void insertTail(Node* head, int value) {
    Node* p = head;
    while (p->next != head) {
        p = p->next;
    }
    Node* node = new Node(value);
    node->next = head;
    p->next = node;
}

// 遍历并输出循环单链表
void printList(Node* head) {
    if (head == nullptr) return;
    Node* p = head;
    do {
        cout << p->data << " ";
        p = p->next;
    } while (p != head);
    cout << endl;
}

while (p != nullptr) {
    cout << p->data << " ";
    p = p->next;
}

while (p->next != nullptr) {
    cout << p->data << " ";
    p = p->next;
}

do {
    cout << p->data << " ";
    p = p->next;
} while (p != head);

for (; p; p = p->next) {
    cout << p->data << " ";
}

{{ select(1) }}

  • 1
  • 2
  • 3
  • 4

2. 区块链技术是⽐特币的基础。在区块链中，每个区块指向前⼀个区块，构成链式列表，新区块只能接在链 尾，不允许在中间插⼊或删除。下⾯代码实现插⼊区块添加函数，则横线处填写（ ）。

//区块（节点）
struct Block {
    int index;              // 区块编号（高度）
    string data;            // 区块里保存的数据
    Block* prev;            // 指向前一个区块
    Block(int idx, const string& d, Block* p) : index(idx), data(d), prev(p) {}
};

// 区块链
struct Blockchain {
    Block* tail;

    // 初始化
    void init() {
        tail = new Block(0, "Genesis Block", nullptr);
    }

    // 插入新区块
    void addBlock(const string& data) {
        tail = new Block(tail->index + 1, data, tail);
    }

    // 释放内存
    void clear() {
        Block* cur = tail;
        while (cur != nullptr) {
            Block* p = cur->prev;
            delete cur;
            cur = p;
        }
        tail = nullptr;
    }
};

Block* newBlock = new Block(tail->index + 1, data, tail);
tail = newBlock->prev;

Block* newBlock = new Block(tail->index + 1, data, tail);
tail = newBlock;

Block* newBlock = new Block(tail->index + 1, data, tail->prev);
tail = newBlock;

Block* newBlock = new Block(tail->index + 1, data, tail->prev);
tail = newBlock->prev;

{{ select(2) }}

  • 1
  • 2
  • 3
  • 4

3. 下⾯关于单链表和双链表的描述中，正确的是（ ） 6 17 22

struct DNode {
    int data;
    DNode* prev;
    DNode* next;
};

// 在双链表中删除指定节点
void deleteNode(DNode* node) {
    if (node->prev) {
        node->prev->next = node->next;
    }
    if (node->next) {
        node->next->prev = node->prev;
    }
    delete node;
}

struct SNode {
    int data;
    SNode* next;
};

// 在单链表中删除指定节点
void deleteSNode(SNode* head, SNode* node) {
    SNode* prev = head;
    while (prev->next != node) {
        prev = prev->next;
    }
    prev->next = node->next;
    delete node;
}
}

{{ select(3) }}

  • 双链表删除指定节点是 ，单链表是
  • 双链表删除指定节点是 ，单链表是
  • 双链表删除指定节点是 ，单链表是
  • 双链表删除指定节点是 ，单链表是

4. 假设我们有两个数 和 ，它们对模 同余，即 。以下哪个值不可能是 ？

{{ select(4) }}

  • 3
  • 4
  • 6
  • 9

5. 下⾯代码实现了欧⼏⾥得算法。下⾯有关说法，错误的是（ ） 4

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

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

{{ select(5) }}

  • gcd1() 实现为递归⽅式。
  • gcd2() 实现为迭代⽅式。
  • 当 较⼤时， gcd1() 实现会多次调⽤⾃⾝，需要较多额外的辅助空间。
  • 当 较⼤时， gcd1() 的实现⽐ gcd2() 执⾏效率更⾼。

6. 唯⼀分解定理描述的内容是（ ）

{{ select(6) }}

  • 任何正整数都可以表⽰为两个素数的和。
  • 任何⼤于1的合数都可以唯⼀分解为有限个质数的乘积。
  • 两个正整数的最⼤公约数总是等于它们的最⼩公倍数除以它们的乘积。
  • 所有素数都是奇数。

7. 下述代码实现素数表的线性筛法，筛选出所有⼩于等于 的素数，则横线上应填的代码是( ) 4 16

vector<int> linear_sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false; // 0和1两个数特殊处理
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        ____________________ { // 在此处填入代码
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0)
                break;
        }
    }
    return primes;
}
}

{{ select(7) }}

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

8. 下列关于排序的说法，正确的是( )

{{ select(8) }}

  • 快速排序是稳定排序
  • 归并排序通常是稳定的
  • 插⼊排序是不稳定排序
  • 冒泡排序不是原地排序

9. 下⾯代码实现了归并排序。下述关于归并排序的说法中，不正确的是（ ） 11

void merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) {
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    for (int p = l; p <= r; p++) arr[p] = temp[p];
}

void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(arr, temp, l, mid);
    mergeSort(arr, temp, mid + 1, r);
    merge(arr, temp, l, mid, r);
}
}

{{ select(9) }}

  • 归并排序的平均复杂度是 。
  • 归并排序需要 的额外空间。
  • 归并排序在最坏情况的时间复杂度是 。
  • 归并排序适合⼤规模数据。

10. 下述C++代码实现了快速排序算法，最坏情况的时间复杂度是（ ）

int partition(vector<int>& arr, int low, int high) {
    int i = low, j = high;
    int pivot = arr[low]; // 以首元素为基准
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        while (i < j && arr[i] <= pivot) i++;
        if (i < j) swap(arr[i], arr[j]);
    }
    swap(arr[i], arr[low]);
    return i;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low >= high) return;
    int p = partition(arr, low, high);
    quickSort(arr, low, p - 1);
    quickSort(arr, p + 1, high);
}

{{ select(10) }}

  • O(n)O(n)
  • O(log⁡n)O(\log n)
  • O(n2)O(n^2)
  • O(nlog⁡n)O(n \log n)

11. 下⾯代码尝试在有序数组中查找第⼀个⼤于等于 x 的元素位置。如果没有⼤于等于 x 的元素，返回 arr.size() 。以下说法正确的是（ ）。

int lower_bound(vector<int>& arr, int x) {
    int l = 0, r = arr.size();
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}
}

{{ select(11) }}

  • 上述代码逻辑正确
  • 上述代码逻辑错误， while 循环条件应该⽤ l <= r
  • 上述代码逻辑错误， mid 计算错误
  • 上述代码逻辑错误，边界条件不对

12. ⼩杨要把⼀根长度为 L 的⽊头切成 K 段，使得每段长度⼩于等于 x 。已知每切⼀⼑只能把⼀段⽊头分成 两段，他⽤⼆分法找到满⾜条件的最⼩ x （ x 为正整数），则横线处应填写（ ）。

// 判断：在不超过 K 次切割内，是否能让每段长度 <= x
bool check(int L, int K, int x) {
    int cuts = (L - 1) / x;
    return cuts <= K;
}

// 二分查找最小可行的 x
int binary_cut(int L, int K) {
    int l = 1, r = L;
    while (l < r) {
        int mid = l + (r - l) / 2;
        _________________// 在此处填入代码
    }
    return l;
}

int main() {
    int L = 10; // 木头长度
    int K = 2; // 最多切 K 刀
    cout << binary_cut(L, K) << endl;
    return 0;
}

if (check(L, K, mid))
  r = mid;
else
  l = mid + 1;

if (check(L, K, mid))
  r = mid+1;
else
  l = mid + 1;

if (check(L, K, mid))
  r = mid + 1;
else
  l = mid - 1;

if (check(L, K, mid))
  r = mid + 1;
else
  l = mid;

{{ select(12) }}

  • 1
  • 2
  • 3
  • 4

13. 下⾯给出了阶乘计算的两种⽅式。以下说法正确的是（ ） 5

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

int factorial2(int n) {
    int acc = 1;
    while (n > 1) {
        acc = n * acc;
        n = n - 1;
    }
    return acc;
}
}

{{ select(13) }}

  • 上⾯两种实现⽅式的时间复杂度相同，都为
  • 上⾯两种实现⽅式的空间复杂度相同，都为
  • 上⾯两种实现⽅式的空间复杂度相同，都为
  • 函数 factorial1() 的时间复杂度为 ，函数 factorial2() 的时间复杂度为

14. 给定有 个任务，每个任务有截⽌时间和利润，每个任务耗时 1 个时间单位、必须在截⽌时间前完成，且每 个时间槽最多做 1 个任务。为了在规定时间内获得最⼤利润，可以采⽤贪⼼策略，即按利润从⾼到低排序，尽量安 排，则横线处应填写（ ）。

struct Task {
    int deadline; // 截止时间
    int profit;   // 利润
};

void sortByProfit(vector<Task>& tasks) {
    sort(tasks.begin(), tasks.end(),
        [](const Task& a, const Task& b) {
            return a.profit > b.profit;
        });
}

int maxProfit(vector<Task>& tasks) {
    sortByProfit(tasks);
    int maxTime = 0;
    for (auto& t : tasks) {
        maxTime = max(maxTime, t.deadline);
    }
    vector<bool> slot(maxTime + 1, false);
    int totalProfit = 0;
    for (auto& task : tasks) {
        for (int t = task.deadline; t >= 1; t--) {
            if (!slot[t]) {
                _______________ //在此处填入代码
                break;
            }
        }
    }
    return totalProfit;
}

slot[t] = true;
totalProfit += task.profit;

slot[t] = false;
totalProfit += task.profit;

slot[t] = true;
totalProfit = task.profit;

slot[t] = false;
totalProfit = task.profit;

{{ select(14) }}

  • 1
  • 2
  • 3
  • 4

15. 下⾯代码实现了对两个数组表⽰的正整数的⾼精度加法（数组低位在前），则横线上应填写（ ）

vector<int> add(vector<int> a, vector<int> b) {
    vector<int> c;
    int carry = 0;
    for (int i = 0; i < a.size() || i < b.size(); i++) {
        if (i < a.size()) carry += a[i];
        if (i < b.size()) carry += b[i];
        c.push_back(carry % 10);
        carry /= 10;
    }
    if (carry) c.push_back(carry);
    return c;
}

c.push_back(carry / 10);
carry %= 10;

c.push_back(carry % 10);
carry /= 10;

c.push_back(carry % 10);

c.push_back(carry);
carry /= 10;

{{ select(15) }}

  • 1
  • 2
  • 3
  • 4

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

1. 数组和链表都是线性表。链表的优点是插⼊删除不需要移动元素，并且能随机查找

{{ select(16) }}

  • 对
  • 错

2. 假设函数 gcd() 函数能正确求两个正整数的最⼤公约数，则下⾯的 lcm(a，b) 函数能正确找到两个正整 数 a 和 b 的最⼩公倍数。

int lcm(int a, int b) {
  return a / gcd(a, b) * b;
}

{{ select(17) }}

  • 对
  • 错

3. 在单链表中，已知指针 p 指向要删除的结点（⾮尾结点），想在 删除 p ，可⾏做法是⽤ p->next 覆盖 p 的值与 next ，然后删除 p->next 。

{{ select(18) }}

  • 对
  • 错

4. 在求解所有不⼤于 n 的素数时，线性筛法（欧拉筛）都应当优先于埃⽒筛法使⽤，因为线性筛法的时间复 杂度为 ，低于埃⽒筛法的 。

{{ select(19) }}

  • 对
  • 错

5. ⼆分查找仅适⽤于有序数据。若输⼊数据⽆序，当仅进⾏⼀次查找时，为了使⽤⼆分⽽排序通常不划算

{{ select(20) }}

  • 对
  • 错

6. 通过在数组的第⼀个、最中间和最后⼀个这3个数据中选择中间值作为枢轴（⽐较基准），快速排序算法可 降低落⼊最坏情况的概率。

{{ select(21) }}

  • 对
  • 错

7. 贪⼼算法在每⼀步都做出当前看来最优的局部选择，并且⼀旦做出选择就不再回溯；⽽分治算法将问题分解 为若⼲⼦问题分别求解，再将⼦问题的解合并得到原问题的解。

{{ select(22) }}

  • 对
  • 错

8. 以下 fib 函数计算第 n 项斐波那契数（ fib(0)=0 , fib(1)=1 ），其时间复杂度为

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

{{ select(23) }}

  • 对
  • 错

9. 递归函数⼀定要有终⽌条件，否则可能会造成栈溢出

{{ select(24) }}

  • 对
  • 错

10. 使⽤贪⼼算法解决问题时，通过对每⼀步求局部最优解，最终⼀定能找到全局最优解

{{ select(25) }}

  • 对
  • 错
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  3. Worker 0, 479ms
  4. Powered by Hydro v4.13.3 Community