GESP 客观题评测系统

2026-03-Level-5

试卷解析总览，可直接查看每题答案与解析。

单选题（每题 2 分）

第 1 题（单选题）

关于单链表、双链表和循环链表，下列说法正确的是（）。

在单链表中，若已知任意结点的指针，则可以在 O(1) 时间内删除该结点。

循环链表中一定不存在空指针。

在循环双链表中，尾结点的 next 指针一定为 nullptr。

在带头结点的循环单链表中，判定链表是否为空只需判断头结点的 next 是否指向自身。

正确答案D

解析详情

【答案】D

【考点】链表的基本性质与操作

【解析】对于 A，单链表删除结点需要知道其前驱结点，仅已知当前结点指针无法在 O(1) 内完成。对于 B，若循环链表为空（且无头结点），头指针可能为 nullptr。对于 C，循环双链表的尾结点 next 应指向头结点。对于 D，带头结点的循环单链表为空时，头结点的 next 指针指向头结点自身，表述正确。

【易错点】容易忽视空链表或带头结点链表的特殊边界情况。

第 2 题（单选题）

双向循环链表中要在结点 p 之前插入新结点 s（均非空），以下指针操作正确的是（）。

s -> next = p;
p -> prev = s;
q -> next = s;
s -> prev = q;

s -> prev = p;
s -> next = p -> next;
p -> next -> prev = s;
p -> next = s;

s -> next = p;
s -> prev = p->prev;
p -> prev -> next = s;
p -> prev = s;

s -> next = p;
s -> prev = nullptr;
p -> prev = s;

正确答案C

解析详情

【答案】C

【考点】双向链表的插入操作

【解析】在双向循环链表中插入结点 s 到 p 之前，需要修改四个指针：s 的前后指针，以及 p 和 p 的原前驱结点的指针。步骤为：1. 设置 s 的 next 指向 p；2. 设置 s 的 prev 指向 p->prev；3. 将 p 原前驱结点的 next 指向 s；4. 将 p 的 prev 指向 s。选项 C 严格遵循此逻辑且顺序正确。

【易错点】指针修改顺序错误可能导致原前驱结点丢失。

第 3 题（单选题）

下面函数用“哑结点”统一处理删除单向链表中的头结点与中间结点。横线处应填（）。

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

Node* eraseAll(Node* head, int x){
    Node dummy(0);
    dummy.next = head;
    Node* cur = &dummy;
    while(cur->next){
        if(cur->next->val == x){
            Node* del = cur->next;
            delete del;
        }else cur = cur->next;
    }
    return dummy.next;
}

cur = cur->next;

cur->next = del->next;

del->next = cur->next;

cur->next = nullptr;

正确答案B

解析详情

【答案】B

【考点】单链表删除结点

【解析】删除结点 `del`（即 `cur->next`）时，必须使当前结点 `cur` 的 `next` 指向 `del` 的下一个结点。即 `cur->next = del->next`。这样在执行 `delete del` 后，链表的连续性得以保持。哑结点的使用避免了对删除头结点的特殊判断。

【易错点】在删除结点前未正确维护链表指针，导致断链。

第 4 题（单选题）

对如下代码实现的欧几里得算法（辗转相除法），执行 gcd(48, 18) 得到的调用序列为（）。

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

gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0)

gcd(48,18) -> gcd(30,18) -> gcd(12,18)

gcd(48,18) -> gcd(18,30) -> gcd(30,6)

gcd(48,18) -> gcd(12,18) -> gcd(6,12)

正确答案A

解析详情

【答案】A

【考点】递归与欧几里得算法

【解析】执行过程： 1. gcd(48, 18)，b=18!=0，调用 gcd(18, 48%18) 即 gcd(18, 12)； 2. gcd(18, 12)，b=12!=0，调用 gcd(12, 18%12) 即 gcd(12, 6)； 3. gcd(12, 6)，b=6!=0，调用 gcd(6, 12%6) 即 gcd(6, 0)； 4. gcd(6, 0)，b=0，返回 a=6。调用序列为 A 所示内容。

【易错点】混淆求余运算的顺序或参数传递位置。

第 5 题（单选题）

下面代码实现了欧拉（线性）筛，横线处应填写（）。

vector<int> euler_sieve(int n) {
    vector<bool> is_composite(n + 1, false);
    vector<int> primes;

    for (int i = 2; i <= n; i++) {
        if (!is_composite[i])
            primes.push_back(i);

        for (int j = 0; _____ && (long long)i * primes[j] <= n; j++) {
            is_composite[i * primes[j]] = true;

            if (i % primes[j] == 0)
                break;
        }
    }
    return primes;
}

j <= n;

j < sqrt(n);

j < primes.size();

j < i;

正确答案C

解析详情

【答案】C

【考点】线性筛（欧拉筛）算法

【解析】在线性筛的内层循环中，通过 `primes[j]` 遍历已找到的质数。循环变量 `j` 作为 `primes` 的下标，其范围应限制在 `0` 到 `primes.size() - 1` 之间，即 `j < primes.size()`，以防数组越界。配合 `i % primes[j] == 0` 的判断，保证每个合数只被其最小质因子筛去。

【易错点】下标越界或混淆循环控制变量的含义。

第 6 题（单选题）

埃氏筛中将内层循环从 j = i*i 开始而不是 j = 2*i 的主要原因是（）。

vector<int> eratosthenes_sieve(int n) {
    vector<bool> is_composite(n + 1, false);
    vector<int> primes;

    for (int i = 2; i <= n; i++) {
        if (is_composite[i]) continue;

        primes.push_back(i);

        for (long long j = (long long)i * i; j <= n; j += i) {
            is_composite[j] = true;
        }
        return primes;
    }
}

因为 2 \times i 一定不是合数

i \times i 一定是质数

小于 i \times i 的 i 的倍数已被更小质因子筛过

这样可以把时间复杂度降为 O(n)

正确答案C

解析详情

【答案】C

【考点】埃拉托斯特尼筛法（埃氏筛）优化

【解析】对于质数 i，它的倍数 k \times i（k < i）在之前的循环中，一定会被 k 的某个质因子（该质因子一定小于 i）筛掉。因此，从 i \times i 开始标记可以避免重复计算，提高效率。但这并不能将复杂度降为 O(n)，埃氏筛复杂度约为 O(n \log \log n)。

【易错点】错误认为从 i \times i 开始就能达到线性时间复杂度。

第 7 题（单选题）

下面程序的运行结果为（）。

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

正确答案B

解析详情

【答案】B

【考点】二分答案法（最大化最小值问题）

【解析】排序后数组为 {1, 2, 4, 8, 9}。要求从中选 3 个数，使相邻数最小差值最大。若 dist=3，可选 {1, 4, 8} 或 {1, 4, 9}，满足条件；若 dist=4，选 1 后只能选 8、9，由于要求选 3 个，不满足。因此最大距离为 3。

【易错点】二分范围判断逻辑出错或模拟选数过程不细心。

第 8 题（单选题）

在升序数组中查找第一个大于等于 x 的位置，下面循环中横线应填（）。

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

r = mid;

r = mid - 1;

l = mid;

l = mid + 1;

正确答案A

解析详情

【答案】A

【考点】二分查找（lower_bound 原理）

【解析】当 `a[mid] >= x` 时，`mid` 可能是目标位置，也可能目标在 `mid` 左侧。因此需要保留 `mid` 作为一个可能的候选，即令 `r = mid`。此时查找范围变为 `[l, mid]`。若 `a[mid] < x`，则目标一定在 `mid` 右侧，令 `l = mid + 1`。最终 `l` 指向第一个大于等于 `x` 的位置。

【易错点】在 `a[mid] >= x` 时错误地使用 `r = mid - 1`，导致漏掉正确答案。

第 9 题（单选题）

关于递归函数调用，下列说法错误的是（）。

递归调用层次过深时，可能会耗尽栈空间导致栈溢出

尾递归函数可以通过编译器优化来避免栈溢出

所有递归函数都可以通过循环结构来改写，从而避免栈溢出

栈溢出发生时，程序会抛出异常并可以继续执行后续代码

正确答案D

解析详情

【答案】D

【考点】递归调用与系统栈

【解析】栈溢出（Stack Overflow）属于严重的系统错误。在 C++ 等语言中，它通常会导致程序异常终止或段错误（Segmentation Fault），而非抛出可捕获并继续执行的异常。选项 A、B、C 均为递归调用的基本属性或常见优化方式。

【易错点】误以为栈溢出可以像业务逻辑异常一样被捕获并让程序平稳恢复运行。

第 10 题（单选题）

给定 n 根木头，第 i 根长度为 a[i]。要切成不少于 m 段等长木段，求最大可能长度，则横线上应填写（）。

const int MAXN = 100005;
long long a[MAXN];
int n, m;

bool check(long long x){
    long long cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(x == 0) return true;
        cnt += a[i] / x;
        if(cnt >= m) return true;
    }
    return false;
}

int main(){
    cin >> n >> m;
    long long mx = 0;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    long long l = 1, r = mx;
    long long ans = 0;
    while(l <= r){
        long long mid = l + (r - l) / 2;
        if(check(mid)){
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

l = mid + 1;

l = mid - 1;

l = mid + 1;
r = mid;

l = mid;
r = mid + 1;

正确答案A

解析详情

【答案】A

【考点】二分答案法（最大化最小值）

【解析】当 `check(mid)` 为真时，表示长度为 `mid` 的方案可行。为了寻找“最大”长度，应保存当前结果并尝试更大的长度，即令 `l = mid + 1`。反之，若不可行，则尝试更短的长度 `r = mid - 1`。代码采用了标准的闭区间二分模板。

【易错点】二分范围缩小方向错误或死循环。

第 11 题（单选题）

下面代码用分治求“最大连续子段和”，其时间复杂度为（）。

int solve(vector<int>& a, int l, int r){
    if(l == r) return a[l];
    int mid = l + (r - l) / 2;
    int left = solve(a, l, mid);
    int right = solve(a, mid + 1, r);
    int sum = 0, lmax = INT_MIN;
    for(int i = mid; i >= l; i--){
        sum += a[i];
        lmax = max(lmax, sum);
    }
    sum = 0;
    int rmax = INT_MIN;
    for(int i = mid + 1; i <= r; i++) {
        sum += a[i];
        rmax = max(rmax, sum);
    }
    return max({left, right, lmax + rmax});
}

O(n^{2})

O(n \log n)

O(\log n)

O(n)

正确答案B

解析详情

【答案】B

【考点】分治算法的时间复杂度分析

【解析】该分治算法的递推式为 T(n) = 2T(n/2) + O(n)。其中 2T(n/2) 是两次递归调用的开销，O(n) 是合并（遍历中间部分求最大和）的开销。根据主定理，该递推式对应的复杂度为 O(n \log n)。

【易错点】误将合并过程视为常数时间导致错选 O(n)，或混淆递归深度与单层操作开销。

第 12 题（单选题）

游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。A组：A = {12, 35, 67, 89}，B组：B = {20, 45, 55, 78}，下面是归并合并函数的核心循环，横线处应填入（）。

int i = 0, j = 0;
vector<int> result;
while (i < A.size() && j < B.size()) {
    if ___ {
        result.push_back(A[i++]);
    } else {
        result.push_back(B[j++]);
    }
}
while (i < A.size()) {
    result.push_back(A[i++]);
}
while (j < B.size()) {
    result.push_back(B[j++]);
}

A[i] >= B[j]

A[i] <= B[j]

i >= j

i <= j

正确答案B

解析详情

【答案】B

【考点】归并操作的核心逻辑

【解析】归并排序的合并过程要求将两个已排序序列合并为一个新的有序序列。在比较 `A[i]` 和 `B[j]` 时，由于结果需要从小到大排列，如果 `A[i] <= B[j]`，则应先将较小的 `A[i]` 放入结果中并移动指针 `i`。这符合升序排列的要求。

【易错点】比较符号写反或比较了错误的变量（如比较下标）。

第 13 题（单选题）

有 n 位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为 pivot 的快速排序，请问此次排序的时间复杂度是（）。

void quicksort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int pivot = a[l];
    int i = l, j = r;
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        while (i < j && a[i] <= pivot) i++;
        if (i < j) swap(a[i], a[j]);
    }
    swap(a[l], a[i]);
    quicksort(a, l, i - 1);
    quicksort(a, i + 1, r);
}

O(n)

O(n \log n)

O(n^{2})

O(\log n)

正确答案C

解析详情

【答案】C

【考点】快速排序的最坏时间复杂度分析

【解析】快速排序的性能取决于基准值（pivot）的选择。如果数组已经有序，且始终选择第一个元素作为 pivot，则每次划分只能分出一个元素，递归树退化为一条链，深度为 n，每层开销为 O(n)，因此总复杂度为 O(n^2)。

【易错点】盲目记忆快排的平均复杂度 O(n \log n)，而忽视了有序数组这一特定最坏情况。

第 14 题（单选题）

下面关于排序算法的描述中，不正确的是()。

冒泡排序和插入排序都是稳定的排序算法

快速排序和归并排序都是不稳定的排序算法

冒泡排序和插入排序最好时间复杂度均为 O(n)

归并排序在最好、最坏和平均三种情况的时间复杂度均为 O(n \log n)

正确答案B

解析详情

【答案】B

【考点】排序算法的稳定性分析

【解析】快速排序通过不相邻元素的交换来实现划分，是不稳定的。而归并排序在合并过程中，如果两个元素相等，会优先取左侧序列的元素，从而保证了相对位置不变，是稳定的。因此 B 描述“归并排序是不稳定的”是错误的。

【易错点】混淆“稳定性”与“时间复杂度”两个概念。

第 15 题（单选题）

下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用 int 表示，则横线处应该填写（）。

int main(){
    string s;
    int b;
    cin >> s >> b;
    vector<int> a;
    for(char c : s) a.push_back(c - '0');
    vector<int> c;
    long long rem = 0;
    for(int i = 0; i < a.size(); i++) {
        rem = rem * 10 + a[i];
        int q = rem / b;
        c.push_back(q);
        _____
    }
    int pos = 0;
    while(pos < c.size() - 1 && c[pos] == 0) pos++;
    for(int i = pos; i < c.size(); i++) cout << c[i];
    cout << endl << rem << endl;
    return 0;
}

rem /= b;

rem %= b;

rem = b;

rem = q;

正确答案B

解析详情

【答案】B

【考点】高精度除法算法（大数除以小数）

【解析】在高精度除法中，我们模拟手算过程：从高位到底位逐位试除。每一位计算出的余数 `rem` 应该传递给下一位使用。在计算出当前位的商 `q` 后，剩余部分应更新为 `rem % b`，以便在下一轮循环中左移一位并加上下一位数字。因此选 B。

【易错点】混淆商（q）与余数（rem）的更新逻辑。

判断题（每题 2 分）

第 1 题（判断题）

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

正确答案正确

解析详情

【答案】正确

【考点】数组与链表的操作特性对比

【解析】数组由于内存连续且已知下标，可通过公式直接计算地址，访问复杂度为 O(1)。单链表在已知某结点指针的情况下，在其后插入结点只需修改指针指向，无需遍历，复杂度亦为 O(1)。

【易错点】注意链表是在“已知指针”的前提下插入 O(1)，若需先寻找插入位置则通常为 O(n)。

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

正确答案正确

解析详情

【答案】正确

【考点】二分查找的标准实现（lower_bound）

【解析】代码采用左闭右开区间 `[0, size)`。当 `a[mid] >= x` 时，收缩右边界 `r = mid`；否则增大左边界 `l = mid + 1`。循环结束时 `l == r` 且指向第一个满足条件的元素。逻辑完全正确。

【易错点】二分循环条件（l < r 或 l <= r）与边界更新（r = mid 或 r = mid - 1）需匹配。

第 3 题（判断题）

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

正确答案错误

解析详情

【答案】错误

【考点】快速排序的稳定性

【解析】快速排序的稳定性取决于它的交换操作。无论枢轴如何选取，快排在执行划分（Partition）过程中，经常会发生不相邻元素的交换，这极易破坏相同数值元素的相对顺序。因此快排本质上是不稳定的。

【易错点】混淆枢轴选择对性能的影响与对稳定性的影响。

第 4 题（判断题）

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

正确答案正确

解析详情

【答案】正确

【考点】主定理（Master Theorem）应用

【解析】根据主定理，对于 T(n) = aT(n/b) + f(n)，此处 a=2, b=2, f(n)=O(n^1)。因为 n^{\log_b a} = n^1，与 f(n) 同阶，故复杂度为 O(n \log n)。这是归并排序的典型复杂度。

【易错点】主定理三种情况记忆混淆。

第 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++;
        }
    }
}

正确答案错误

解析详情

【答案】错误

【考点】归并排序求逆序对

【解析】虽然代码中 `cnt += (m - i + 1)` 这一行是计算跨越左右两个有序子区间逆序对的正确逻辑，但该函数片段缺少了归并排序的核心步骤：递归划分过程以及实际的元素归并（Merge）排序操作。没有这两步，统计结果必然错误。

【易错点】误以为只要有一行核心计数逻辑就能正确统计全局逆序对，忽视了算法的完整性。

第 6 题（判断题）

唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。

正确答案正确

解析详情

【答案】正确

【考点】质数的判定原理

【解析】若一个合数 n 有大于 1 的因子，则它必定有一个小于或等于 \sqrt{n} 的质因子。如果检查了所有不超过 \sqrt{n} 的质数都没有发现其因子，说明该数不存在合数分解，必然为质数。

【易错点】边界条件 \sqrt{n} 是否包含在内的判断。

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

正确答案正确

解析详情

【答案】正确

【考点】综合时间复杂度分析

【解析】程序分为两部分：1. 对长度为 n 的数组排序开销为 O(n \log n)；2. 二分查找过程循环 \log D 次，每次调用 `check` 函数开销为 O(n)，故总开销为 O(n \log D)。两部分相加得所求复杂度。

【易错点】忽略排序部分的开销或错误估计二分查找的单次成本。

第 8 题（判断题）

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

正确答案错误

解析详情

【答案】错误

【考点】贪心算法与动态规划的区别

【解析】最优子结构是贪心算法和动态规划共同的必要条件。但贪心算法还要求满足“贪心选择性质”，即局部最优选择最终能导致全局最优。例如 0/1 背包问题具有最优子结构，但无法通过贪心算法得到最优解。

【易错点】误以为具备最优子结构就能直接使用贪心法，忽略了局部最优与全局最优的统一性要求。

第 9 题（判断题）

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

正确答案错误

解析详情

【答案】错误

【考点】线性筛（欧拉筛）核心原理

【解析】线性筛（欧拉筛）的核心策略是让每个合数只被其“最小质因子”筛去，而非最大质因子。代码中的 `if (i % primes[j] == 0) break;` 正是为了保证这一性质，从而确保了 O(n) 的线性效率。

【易错点】记反了线性筛是利用最小质因子还是最大质因子进行标记。

第 10 题（判断题）

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

正确答案错误

解析详情

【答案】错误

【考点】递归与非递归的相互转化

【解析】虽然任何递归都能转非递归，但并非都需要显式栈。例如简单的线性递归或尾递归，可以直接通过 `while` 或 `for` 循环来实现，利用循环变量更新代替压栈过程。只有复杂的树状递归通常才需要显式模拟栈。

【易错点】绝对化地认为非递归必须依赖栈结构。