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

判断题（共 10 题，每题 2 分，共 20 分）

1. 有一个存储了 n 个整数的线性表，分别用数组和单链表两种方式实现。在已知下标（或结点指针）的前提下，数组的随机访问是O(1)，而在链表中已知某结点的指针时，在该结点之后插入一个新结点的操作也是O(1)。

{{ select(1) }}

• 正确
• 错误

2. 若数组 a 已按升序排列，则下面代码可以正确实现'在a中查找第一个大于等于x的元素的位置'。

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

{{ select(2) }}

• 正确
• 错误

3. 快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。

{{ select(3) }}

• 正确
• 错误

4. 若某算法满足递推式 T(n)=2T(n/2)+O(n)，则其时间复杂度为O( n log n)。

{{ select(4) }}

• 正确
• 错误

5. 在一个数组中，如果两个元素 a[i] 和 a[j] 满足i < j且a[i] > a[j]，则a[i]和a[j]是一个逆序对。下面代码可以正确统计数组a区间 [l,r] 内的逆序对总数。

long long cnt=0;
void merge_count(vector<int>& a, int l, int m, int r){
   int i = l, j = m + 1;
   while(i <= m && j <= r) {
       if(a[i] <= a[j]) i++;
       else {
           cnt += (m -  i+ 1);
           j++;
      }
  }
}

{{ select(5) }}

• 正确
• 错误

6. 根据唯⼀分解定理，如果⼤于1的整数不能被任何不超其平⽅根的质数整除，那么n 必定是质数。

{{ select(6) }}

• 正确
• 错误

7. 假设数组 a 的值域范围是 D，以下程序的时间复杂度是 O(n log n + n log D)。

bool check(int n, int a[], int k, int dist)
{
    int cnt = 1;
    int last = a[0];
    for (int i = 1; i < n; i++)
    {
        if (a[i] - last >= dist)
        {
            cnt++;
            last = a[i];
        }
    }
    return cnt >= k;
}

int solve(int n, int a[], int k)
{
    std::sort(a, a + n);
    int l = 0;
    int r = a[n - 1] - a[0];
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        if (check(n, a, k, mid))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

int main()
{
    int a[] = {1, 2, 8, 4, 9};
    int n = 5;
    int k = 3;
    std::cout << solve(n, a, k) << std::endl;
    return 0;
}

{{ select(7) }}

• 正确
• 错误

8. 若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。

{{ select(8) }}

• 正确
• 错误

9. 线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过"每个合数只被其最大质因子筛去"的策略，保证每个合数恰好被标记一次，从而实现O(n)的时间复杂度。

{{ select(9) }}

• 正确
• 错误

10. 任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。

{{ select(10) }}

• 正确
• 错误