GESP 客观题评测系统

2024-09-Level-5

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

单选题（每题 2 分）

第 1 题（单选题）

下面关于链表和数组的描述，错误的是（）。

数组大小固定，链表大小可动态调整。

数组支持随机访问，链表只能顺序访问。

存储相同数目的整数，数组比链表所需的内存多。

数组插入和删除元素效率低，链表插入和删除元素效率高。

正确答案C

解析详情

【答案】C

【考点】链表与数组的区别

【解析】数组和链表都是线性表。数组在物理存储上是连续的，支持随机访问（O(1)），但大小固定且插入删除需移动元素；链表通过指针连接，大小动态可调，插入删除效率高（O(1)），但不支持随机访问。由于链表每个节点需要额外存储指针域，存储相同数量的整数时，链表所需的内存通常比数组多。

【易错点】容易忽视链表节点的指针域（next 域）所带来的额外内存开销。

第 2 题（单选题）

通过（）操作，能完成在双向循环键表结点 p 之后插入结点 s 的功能（其中 next 域为结点的直接后继，prev 域为结点的直接前驱）。

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

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

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

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

正确答案D

解析详情

【答案】D

【考点】双向循环链表的操作

【解析】在 p 之后插入 s，需要修改四个指针指向：s 的前驱指向 p，s 的后继指向 p 的原后继，p 原后继的前驱指向 s，p 的后继指向 s。选项 D 的顺序是：①s->next=p->next（s 指向后继）；②p->next->prev=s（后继节点的前驱指向 s）；③s->prev=p（s 的前驱指向 p）；④p->next=s（p 指向 s）。这组顺序可以正确维护链表结构且不丢失节点引用。

【易错点】指针修改顺序非常关键，若先执行 p->next = s，则 p 原本的后继节点将无法通过 p->next 找到，导致断链。

第 3 题（单选题）

对下面两个函数，说法错误的是（）。

int sumA(int n) {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}

int sumB(int n) {
    if (n == 1)
        return 1;
    int res = n + sumB(n - 1);
    return res;
}

sumA体现了迭代的思想。

SumB采用的是递归方式。

SumB函数比SumA的时间效率更高。

两个函数的实现的功能相同。

正确答案C

解析详情

【答案】C

【考点】递归与迭代

【解析】 sumA 使用 for 循环进行累加，属于迭代思想；sumB 通过调用自身处理子问题，属于递归方式。两者功能相同，均计算 1 到 n 的和。但递归在执行时会产生额外的函数调用开销（如压栈、参数传递等），因此 sumB 的时间效率通常低于 sumA，且在大数据规模下可能导致栈溢出。

【易错点】误认为递归代码更简洁就代表效率更高，实际上递归通常具有更高的常数级时间开销和空间开销。

第 4 题（单选题）

有如下函数 fun，则 fun(20, 12) 的返回值为（）。

int fun(int a, int b) {
    if (a % b == 0)
        return b;
    else
        return fun(b, a % b);
}

正确答案C

解析详情

【答案】C

【考点】递归与最大公约数（辗转相除法）

【解析】该函数实现了辗转相除法求最大公约数。计算过程为：fun(20, 12) → 20%12=8，调用 fun(12, 8) → 12%8=4，调用 fun(8, 4) → 8%4=0，符合终止条件 a%b==0，返回 b，即 4。

【易错点】递归过程中 a 和 b 的位置变化，以及对取模运算结果的准确计算。

第 5 题（单选题）

下述代码实现素数表的埃拉托斯特尼筛法，筛选出所有小于等于 n 的素数，则横线上应填的最佳代码是()。

void sieve_Eratosthenes(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            // 在此处填入代码
        }
    }
    for (int i = sqrt(n) + 1; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

for (int j = i; j <= n; j++)

for (int j = i * i; j <= n; j++)

for (int j = i * i; j <= n; j += i)

for (int j = i; j <= n; j += i)

正确答案C

解析详情

【答案】C

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

【解析】埃氏筛的核心思想是：每发现一个素数 i，就将其所有倍数标记为合数。为了提高效率，标记应从 i*i 开始（因为更小的倍数如 2i, 3i 等已被更小的素数处理过），步长为 i。因此横线处应填 `for (int j = i * i; j <= n; j += i) is_prime[j] = false;`（选项 C 的循环头部分）。

【易错点】循环起点 j=i 或步长 j++ 是常见的低效写法，正确优化应从 i*i 开始且步长为 i。

第 6 题（单选题）

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

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

    for (int i = 2; i <= n / 2; i++) {
        if (is_prime[i])
            primes.push_back(i);
        // 在此处填入代码
        is_prime[i * primes[j]] = 0;
        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;
}

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

for (int j = 1; j < primes.size() && i * j <= n; j++)

for (int j = 2; j < primes.size() && i * primes[j] <= n; j++)

以上都不对

正确答案A

解析详情

【答案】A

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

【解析】线性筛保证每个合数只被其最小质因子筛选一次。内层循环需要遍历当前已找到的素数表 `primes`，并将 `i * primes[j]` 标记为合数。循环条件必须包含 `j < primes.size()` 防止越界，以及 `i * primes[j] <= n` 防止超出范围。选项 A 正确实现了这一逻辑。

【易错点】忽视 `i * primes[j] <= n` 的边界检查，或者混淆下标 j 的起始值。

第 7 题（单选题）

下面函数可以将 n 的所有质因数找出来，其时间复杂度是（）。

#include <iostream>
#include <vector>

vector<int> get_prime_factors(int n) {
    vector<int> factors;

    while (n % 2 == 0) {
        factors.push_back(2);
        n / = 2;
    }

    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            factors.push_back(i);
            n / = i;
        }
    }

    if (n > 2) {
        factors.push_back(n);
    }

    return factors;
}

O(n^{2})

O(n \log n)

O(\sqrt{n}\log n)

O(n)

正确答案C

解析详情

【答案】C

【考点】质因数分解的时间复杂度

【解析】代码中的 for 循环条件为 `i * i <= n`，这意味着 i 最高增加到 sqrt(n)。内层的 while 循环虽然会执行，但由于每次成功执行 `n /= i` 都会大幅减小 n 的规模，总的除法操作次数是 log n 级别的。因此，整体时间复杂度主要由外层循环决定，近似为 O(sqrt(n) log n)（log n 代表因子个数的影响）。

【易错点】误认为 for 循环和 while 循环是简单的嵌套关系导致估算复杂度过高，实际上 n 的动态缩小降低了总开销。

第 8 题（单选题）

现在用如下代码来计算 $x^{n}$ （n个x相乘），其时间复杂度为（）。

double quick_power(double x, unsigned n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    return quick_power(x, n / 2) * quick_power(x, n / 2) * ((n & 1) ? x : 1);
}

O(n)

O(n^{2})

O(\log n)

O(n \log n)

正确答案A

解析详情

【答案】A

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

【解析】该代码虽然采用了分治形式，但由于 `quick_power(x, n / 2)` 被调用了两次且没有存储中间结果，其递归式为 T(n) = 2T(n/2) + O(1)。根据主定理，该复杂度为 O(n)。若使用中间变量存储一次调用的结果，则复杂度可优化至 O(log n)。

【易错点】容易混淆标准快速幂（O(log n)）与此类重复计算的分治（O(n)）的区别。

第 9 题（单选题）

假设快速排序算法的输入是一个长度为n的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项（）描述的是在这种情况下快速排序行为。

快速排序对于此类输入的表现最好，因为数组已经排序。

快速排序对于此类输入的时间复杂度是

O(n \log n)

。

快速排序对于此类输入的时间复杂度是

O(n^2)

。

快速排序无法对此类数组进行排序，因为数组已经排序。

正确答案C

解析详情

【答案】C

【考点】快速排序的最坏情况

【解析】当输入数组已排序且每次选择第一个元素作为基准（pivot）时，快速排序会出现最极端的不平衡划分：每次划分只能减少一个元素，递归深度达到 n。此时时间复杂度退化为 O(n^2)。

【易错点】误认为“已排序”对所有排序算法都是最优情况，实际上对于未优化的快排，这是最差情况。

第 10 题（单选题）

考虑以下 C++ 代码实现的归并排序算法：

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

对长度为 n 的数组 arr，挑用函数 merge_sort(a, 0, n-1)，在排序过程中 merge 函数的递归调用次数大约是（）。

O(1)

O(n)

O(\log n)

O(n \log n)

正确答案B

解析详情

【答案】B

【考点】归并排序的递归结构

【解析】在归并排序的递归树中，`merge_sort` 被调用的次数是 2n-1 次（对应二叉树的所有节点），而 `merge` 函数是在每个非叶子节点处被调用一次。长度为 n 的数组在递归树中约有 n-1 个非叶子节点，因此 `merge` 的调用次数为 O(n) 级别。

【易错点】混淆递归深度（O(log n)）与总调用次数（O(n)）。

第 11 题（单选题）

现在有 n 个人要过河，每只船最多载 2 人，船的承重为 100kg。下列代码中，数组 weight 中保存有 n 个人的体重（单位为kg），已经按从小到大排好序，代码输出过河所需要的船的数目，采用的思想为（）。

int i, j;
int count = 0;
for (i = 0, j = n - 1; i < j; j--) {
    if (weight[i] + weight[j] <= 100) {
        i++;
    }
    count++;
}
printf("过河的船数: %d\\n", count);

枚举算法

贪心算法

迭代算法

递归算法

正确答案B

解析详情

【答案】B

【考点】贪心算法

【解析】代码采用了贪心策略：为了使船数最少，每次尝试让当前最重的人（j）和最轻的人（i）同船。如果他们的体重和不超过 100kg，则两人同船（i++）；否则最重的人只能单独坐一船。这保证了每一步都利用了当前状态下的最优组合，最终得到全局最优解。

【易错点】混淆枚举（尝试所有可能）与贪心（每步取当前局部最优）的区别。

第 12 题（单选题）

关于分治算法，以下哪个说法正确？

分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。

归并排序不是分治算法的应用。

分治算法通常用于解决小规模问题。

分治算法的时间复杂度总是优于

O(n \log(n))

。

正确答案A

解析详情

【答案】A

【考点】分治算法的基本概念

【解析】分治算法的核心思想是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，便以此类推，直至问题小到可以直接求解，最后将子问题的解合并得到原问题的解。归并排序和快速排序都是典型的分治应用。分治算法的时间复杂度并不总是优于 O(n log n)，取决于具体的分解和合并开销。

【易错点】误认为分治算法只适用于小规模问题，实际上它正是处理大规模问题的有力工具。

第 13 题（单选题）

根据下述二分查找法，在排好序的数组 1, 3, 6, 9, 17, 31, 39, 52, 61, 79 中查找数值 31，循环 while（left <= right）执行的次数为（）。

int binary_search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1; // 如果找不到目标元素，返回-1
}

正确答案C

解析详情

【答案】C

【考点】二分查找的过程模拟

【解析】数组为 [1, 3, 6, 9, 17, 31, 39, 52, 61, 79]，查找 31： 1. left=0, right=9, mid=4, nums[4]=17 < 31, left=5; 2. left=5, right=9, mid=7, nums[7]=52 > 31, right=6; 3. left=5, right=6, mid=5, nums[5]=31 == 31, 找到并返回。循环共执行了 3 次。

【易错点】二分查找中 mid 的计算（向下取整）以及 left/right 的更新边界。

第 14 题（单选题）

以下关于高精度运算的说法错误的是()。

高精度计算主要是用来处理大整数或需要保留多位小数的运算。

大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商。

高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。

高精度加法运算的关键在于逐位相加并处理进位。

正确答案C

解析详情

【答案】C

【考点】高精度算法基础

【解析】高精度乘法（模拟竖式法）的时间复杂度通常与参与运算的两个大整数的位数之积（N*M）有关。如果两个数位数分别是 N 和 M，总操作次数约为 N*M 级别，而不仅仅与较长者的位数有关。选项 C 的描述是不准确的。

【易错点】误认为所有高精度运算的复杂度都只与较长位数线性相关，实际上乘法和除法通常是平方级别的复杂度。

第 15 题（单选题）

当n=7时，下面函数的返回值为（）。

int fun(int n) {
    if (n == 1) return 1;
    else if (n >= 5) return n * fun(n - 2);
    else return n * fun(n - 1);
}

105

840

210

420

正确答案C

解析详情

【答案】C

【考点】递归函数的模拟执行

【解析】模拟过程如下： fun(7) = 7 * fun(5) fun(5) = 5 * fun(3) fun(3) = 3 * fun(2) (因为 3 < 5) fun(2) = 2 * fun(1) (因为 2 < 5) fun(1) = 1 最终结果为 7 * 5 * 3 * 2 * 1 = 210。

【易错点】在 n=3 和 n=2 时，由于不满足 n>=5，应执行 n * fun(n-1) 分支，容易在这里算错递减步长。

判断题（每题 2 分）

第 1 题（判断题）

在操作系统中，需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU将切换到下一个进程。这种循环操作可以通过环形链表来实现。

正确答案正确

解析详情

【答案】正确

【考点】链表的应用

【解析】环形链表是一种首尾相接的结构，非常适合模拟这种需要循环遍历的任务序列。在操作系统的进程调度中，这种结构能方便地实现时间片轮转调度。

【易错点】误认为只能用队列实现，实际上环形链表在处理循环逻辑时更具优势。

第 2 题（判断题）

找出自然数 n 以内的所有质数，常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中线性筛法效率更高。

正确答案正确

解析详情

【答案】正确

【考点】质数筛法

【解析】埃氏筛的时间复杂度为 O(n log log n)，而线性筛（欧拉筛）通过保证每个合数只被其最小质因子筛选一次，达到了 O(n) 的线性复杂度，因此效率更高。

【易错点】在小规模数据下两者差异不明显，但在 n 较大时线性筛优势显著。

第 3 题（判断题）

唯一分解定理表明任何一个大于1的整数都可以唯一地分解为素数之和。

正确答案错误

解析详情

【答案】错误

【考点】唯一分解定理

【解析】唯一分解定理是指任何一个大于 1 的正整数都可以唯一地分解为若干个素数的乘积（不计因子的顺序），而不是素数之和。

【易错点】混淆了“积”与“和”的概念。素数之和通常涉及哥德巴赫猜想等命题。

第 4 题（判断题）

贪心算法通过每一步选择局部最优解，从而一定能获得最优解。

正确答案错误

解析详情

【答案】错误

【考点】贪心算法的局限性

【解析】贪心算法只在每一步选择局部最优，虽然这种策略对某些问题（如霍夫曼编码、最小生成树）能得到全局最优解，但对许多问题（如 0/1 背包问题、最长路径问题）并不适用。

【易错点】误以为“局部最优”的累加必然导致“全局最优”，忽视了后续步骤可能受当前决策影响而失去最优机会。

第 5 题（判断题）

快速排序和归并排序的平均时间复杂度均为 $O(n \log n)$ ，且都是稳定排序。

正确答案错误

解析详情

【答案】错误

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

【解析】快速排序和归并排序的平均复杂度确实都是 O(n log n)，但稳定性不同：归并排序是稳定的，而快速排序是不稳定的（因为分区过程中元素的交换可能改变相同元素的相对顺序）。

【易错点】容易混淆不同 O(n log n) 排序算法（快排、归并、堆排）的稳定性。

第 6 题（判断题）

插入排序的时间复杂度总是比快速排序低。

正确答案错误

解析详情

【答案】错误

【考点】排序算法复杂度对比

【解析】插入排序的平均时间复杂度是 O(n^2)，快速排序的平均时间复杂度是 O(n log n)。在大多数情况下（n 较大时），快速排序的效率远高于插入排序。

【易错点】仅在数据规模极小或数据几乎已排序的情况下，插入排序的效率可能更高，但从总体趋势看其复杂度更高。

第 7 题（判断题）

引入分治策略往往可以提升算法效率。一方面，分治策略减少了操作数量；另一方面，分治后有利于系统的并行优化。

正确答案正确

解析详情

【答案】正确

【考点】分治策略的优势

【解析】分治策略能将 O(n^2) 的问题优化到 O(n log n) 级别（减少了操作总数），且由于子问题之间往往是独立的，天然适合在多核或分布式系统上并行处理。

【易错点】忽视了分治过程中递归调用本身带来的开销，但在复杂度量级提升面前，这些开销是值得的。

第 8 题（判断题）

二分查找要求被搜索的序列是有序的，否则无法保证正确性。

正确答案正确

解析详情

【答案】正确

【考点】二分查找的前提条件

【解析】二分查找依赖于序列的单调性来排除一半的搜索区间。如果序列无序，则无法通过比较中间值来确定目标在左半部分还是右半部分。

【易错点】在未排序的数组上使用二分查找会得到随机或错误的结果。

第 9 题（判断题）

在C++语言中，递归的实现方式通常会占用更多的栈空间，可能导致栈溢出。

正确答案正确

解析详情

【答案】正确

【考点】递归与系统栈

【解析】每一次函数递归调用都会在系统栈中开辟新的栈帧来存储局部变量和返回地址。如果递归层数过深，超出了操作系统分配的栈空间大小（通常为几 MB），就会触发栈溢出（Stack Overflow）错误。

【易错点】忽视了递归深度的控制，或者在大数据量下没有将递归改写为迭代。

第 10 题（判断题）

对于已经定义好的标准数学函数 $\sin(x)$ ，应用程序中的语句 $y=\sin(\sin(x))$ ；是一种递归调用。

正确答案错误

解析详情

【答案】错误

【考点】递归的概念

【解析】递归是指函数在定义中直接或间接地调用自身。`sin(sin(x))` 仅仅是将一个函数的返回值作为另一个函数（恰好是同一个函数）的参数，这属于嵌套调用，而非递归（因为 sin 函数的内部实现并不依赖于调用自身）。

【易错点】混淆了“函数嵌套”与“函数递归”的区别。