GESP C++ 五 级 2025年12月真题（180 分钟，总分 100 分）

单选题（共 15 题，每题 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;
   _______________________     //在此处填入代码
   cout << endl;
}

{{ select(1) }}

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

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) {
       _______________________     //在此处填入代码
  }
 
   // 释放内存
   void clear() {
       Block* cur = tail;
       while (cur != nullptr) {
           Block* p = cur->prev;
           delete cur;
           cur = p;
      }
       tail = nullptr;
  }
};

{{ select(2) }}

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

3. 下面关于单链表和双链表的描述中，正确的是（   ）。

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

• 双链表删除指定节点是O(1)，单链表是O(1)
• 双链表删除指定节点是O(n)，单链表是O(1)
• 双链表删除指定节点是O(1)，单链表是O(n)
• 双链表删除指定节点是O(n)，单链表是O(n)

4. 假设我们有两个数 a=38 和 b=14，它们对模 m 同余，即 a ≡ b (mod m)。以下哪个值不可能是 m？

{{ select(4) }}

• 3
• 4
• 6
• 9

5. 下面代码实现了欧几里得算法。下面有关说法，错误的是（   ）。

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() 实现为迭代方式。
• 当a较大时，gcd1() 实现会多次调用自身，需要较多额外的辅助空间。
• 当a较大时，gcd1() 的实现比 gcd2() 执行效率更高。

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

{{ select(6) }}

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

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

vector<int> linear_sieve(int n) {
   vector<bool> is_prime(n +1, true);
   vector<int> primes;
   is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理
   for (int i = 2; i <= n; ++i) {
       if (is_prime[i]) {
           primes.push_back(i);
      }
       ________________________________ {    // 在此处填入代码
           is_prime[ i * primes[j] ] = 0;
           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. 下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是（  ）。

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

• 归并排序的平均复杂度是 O( n log n )。
• 归并排序需要 O(n) 的额外空间。
• 归并排序在最坏情况的时间复杂度是 O(n²)。
• 归并排序适合大规模数据。

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(log n)
• O(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;
}

{{ select(12) }}

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

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

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

• 上面两种实现方式的时间复杂度相同，都为O(n)
• 上面两种实现方式的空间复杂度相同，都为O(n)
• 上面两种实现方式的空间复杂度相同，都为O(1)
• 函数 factorial1() 的时间复杂度为 O(2ⁿ)，函数 factorial2() 的时间复杂度为O(n)

14. 给定有n个任务，每个任务有截止时间和利润，每个任务耗时 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;
}

{{ select(14) }}

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

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];
       _______________________         //在此处填入代码
  }
   if (carry) c.push_back(carry);
   return c;
}

{{ select(15) }}

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