试卷解析 · 理解每一步

2025-09-Level-5

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

单选题

第 1 题（单选题，2 分）

以下哪种情况使用链表比数组更合适？

数据量固定且读多写少

需要频繁在中间或开头插入、删除元素

需要高效随机访问元素

存储空间必须连续

正确答案B

解析详情

答案 B链表与数组的区别

思路与推导

链表通过改变指针即可实现元素的插入和删除，在中间或开头操作的时间复杂度为 O(1)（前提是已找到位置）；数组则需要移动大量后续元素，复杂度为 O(n)。数组适合随机访问和数据量固定的场景。

第 2 题（单选题，2 分）

函数 removeElements 删除单链表中所有结点值等于 val 的结点，并返回新的头结点，其中链表头结点为 head，则横线处填写（）。

// 结点结构体

struct Node {
    int val;
    Node* next;

    Node() : val(0), next(nullptr) {}
    Node(int x) : val(x), next(nullptr) {}
    Node(int x, Node *next) : val(x), next(next) {}
};

Node* removeElements(Node* head, int val) {
    Node dummy(0, head); // 哑结点，统一处理头结点
    Node* cur = &dummy;
    while (cur->next) {
        if (cur->next->val == val) {
            // 在此填入代码
        }
        else {
            cur = cur->next;
        }
    }
    return dummy.next;
}

Node* del = cur;
cur = del->next;
delete del;

Node* del = cur->next;
cur->next = del;
delete del;

Node* del = cur->next;
cur->next = del->next;
delete del;

Node* del = cur->next;
delete del;
cur->next = del->next;

正确答案C

解析详情

答案 C单链表的结点删除

思路与推导

当发现 `cur->next->val == val` 时，需要删除 `cur->next` 指向的结点。操作方法是：先用临时指针 `del` 指向待删结点，再将 `cur->next` 跳过该结点指向 `del->next`，最后 `delete del` 释放内存。

第 3 题（单选题，2 分）

函数 hasCycle 采用Floyd快慢指针法判断一个单链表中是否存在环，链表的头节点为 head，即用两个指针在链表上前进：slow 每次走1步，fast 每次走2步，若存在环，fast 终会追上 slow（相遇）；若无环，fast 会先到达 nullptr，则横线上应填写（）。

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

bool hasCycle(Node *head) {
    if (!head || !head->next)
        return false;
    Node* slow = head;
    Node* fast = head->next;
    while (fast && fast->next) {
        if (slow == fast) return true;
            // 在此填入代码
    }
    return false;
}

slow = slow->next;
fast = fast->next->next;

slow = fast->next;
fast = slow->next->next;

slow = slow->next;
fast = slow->next->next;

slow = fast->next;
fast = fast->next->next;

正确答案A

解析详情

答案 A快慢指针（Floyd 判环算法）

思路与推导

Floyd 判环算法的核心是两个指针以不同速度移动。通常 slow 每次走 1 步（`slow = slow->next`），fast 每次走 2 步（`fast = fast->next->next`）。如果链表有环，fast 最终会从后方追上 slow。

第 4 题（单选题，2 分）

函数 isPerfectNumber 判断一个正整数是否为完全数（该数是否即等于它的真因子之和），则横线上应填写（）。一个正整数 n 的真因子包括所有小于 n 的正因子，如28的真因子为1, 2, 4, 7, 14。

bool isPerfectNumber(int n) {
    if(n <= 1) return false;
    int sum = 1;
    for(int i = 2; _____; i++) {
        if(n % i == 0) {
            sum += i;
            if(i != n/i) sum += n/i;
        }
    }
    return sum == n;
}

i <= n

i*i <= n

i <= n/2

i < n

正确答案B

解析详情

答案 B完全数判断与约数枚举优化

思路与推导

在寻找因子时，若 $i$ 是 $n$ 的因子，则 $n/i$ 也是因子。因此只需枚举到 $\sqrt{n}$ 即可找到所有因子对。循环中 `sum += i` 和 `sum += n/i` 已经处理了成对的因子，故循环条件应为 `i * i <= n`。

第 5 题（单选题，2 分）

以下代码计算两个正整数的最大公约数(GCD)，横线上应填写（）。

int gcd0(int a, int b) {
    if (a < b) {
        swap(a, b);
    }
    while(b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return ___;
}

temp

a * b

正确答案B

解析详情

答案 B欧几里得算法（辗转相除法）

思路与推导

辗转相除法的逻辑是： $gcd(a, b) = gcd(b, a \% b)$ 。代码中 `while(b != 0)` 循环不断更新 `a` 为当前的除数，`b` 为余数。当余数 `b` 为 0 时，当前的 `a` 即为最大公约数。

第 6 题（单选题，2 分）

函数 sieve 实现埃拉托斯特尼筛法(埃氏筛)，横线处应填入（）。

vector<bool> sieve(int n) {
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i <= n; i++) {
        if(is_prime[i]) {
            for(int j = ___; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

i+1

i*2

i*i

正确答案D

解析详情

答案 D埃拉托斯特尼筛法（埃氏筛）优化

思路与推导

在埃氏筛中，当处理质数 $i$ 时，小于 $i \times i$ 的倍数（如 $i \times 2, i \times 3 \dots$ ）一定已经被更小的质数处理过了。因此，为了减少重复标记，内层循环可以从 $i \times i$ 开始。

第 7 题（单选题，2 分）

函数 linearSieve 实现线性筛法(欧拉筛)，横线处应填入（）。

vector<int> linearSieve(int n) {
    vector<bool> is_prime(n+1, true);
    vector<int> primes;
    for(int i = 2; i <= n; i++) {
        if(is_prime[i]) primes.push_back(i);
        for(int p : primes) {
            if(p * i > n) break;
            is_prime[p * i] = false;
            if(_____) break;
        }
    }
    return primes;
}

i % p == 0

p % i == 0

i == p

i * p == n

正确答案A

解析详情

答案 A线性筛法（欧拉筛）的核心逻辑

思路与推导

线性筛的核心在于确保每个合数只被其“最小质因子”筛掉。当 `i % p == 0` 时，说明 $p$ 是 $i$ 的最小质因子，那么对于后续的质数 $p'$ ， $p' \times i$ 的最小质因子依然是 $p$ 而不是 $p'$ ，如果不 break 就会造成重复筛选。

第 8 题（单选题，2 分）

关于埃氏筛和线性筛的比较，下列说法错误的是（）。

埃氏筛可能会对同一个合数进行多次标记

线性筛的理论时间复杂度更优，所以线性筛的速度往往优于埃氏筛

线性筛保证每个合数只被其最小质因子筛到一次

对于常见范围（

n \leq 10^7

），埃氏筛因实现简单，常数较小，其速度往往优于线性筛

正确答案B

解析详情

答案 B筛法复杂度与实际运行性能对比

思路与推导

虽然线性筛理论复杂度为 O(n) 优于埃氏筛的 O(n log log n)，但线性筛涉及更多的内存访问和判断逻辑，常数较大。在 $n \leq 10^7$ 等常见范围内，高度优化的埃氏筛由于缓存友好性好、实现简单，实际运行速度往往比线性筛更快。

第 9 题（单选题，2 分）

唯一分解定理描述的是（）。

每个整数都能表示为任意素数的乘积

每个大于1的整数能唯一分解为素数幂乘积（忽略顺序）

合数不能分解为素数乘积

素数只有两个因子：1和自身

正确答案B

解析详情

答案 B算术基本定理（唯一分解定理）

思路与推导

算术基本定理规定：每一个大于 1 的自然数，要么本身就是质数，要么可以写为一系列质数的乘积；且如果不考虑因子的顺序，这种分解方式是唯一的。格式通常表示为 $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$ 。

第 10 题（单选题，2 分）

给定一个 n x n 的矩阵 matrix，矩阵的每一行和每一列都按升序排列。函数 countLE 返回矩阵中第 k 小的元素，则两处横线上应分别填写（）。

// 统计矩阵中 <= x 的元素个数：从左下角开始

int countLE(const vector<vector<int>>& matrix, int x) {
    int n = (int)matrix.size();
    int i = n - 1, j = 0, cnt = 0;
    while (i >= 0 && j < n) {
        if (matrix[i][j] <= x) {
            cnt += i + 1;
            ++j;
        }
        else {
            --i;
        }
    }
    return cnt;
}

int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = (int)matrix.size();
    int lo = matrix[0][0];
    int hi = matrix[n - 1][n - 1];
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (countLE(matrix, mid) >= k) {
            // 在此处填入代码
            hi = mid;
        } else {
            // 在此处填入代码
            lo = mid + 1;
        }
    }
    return lo;
}

hi = mid - 1;
lo = mid + 1;

hi = mid;
lo = mid;

hi = mid;
lo = mid + 1;

hi = mid + 1;
lo = mid;

正确答案C

解析详情

答案 C二分查找（值域二分）

思路与推导

该题是在有序矩阵中找第 k 小。通过二分枚举“数值” mid，并统计矩阵中 $\leq mid$ 的个数。如果个数 $\geq k$ ，说明目标值在左侧或就是 mid，故 `hi = mid`；如果个数 $< k$ ，说明目标值必在右侧且不包含 mid，故 `lo = mid + 1`。

第 11 题（单选题，2 分）

下述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);
}

快速排序之所以叫“快速”，是因为它在平均情况下运行速度较快，常数小、就地排序，实践中通常比归并排序更高效。

在平均情况下，划分的递归层数为 logn，每层中的总循环数为 n，总时间为

O(n \log n)

。

在最差情况下，每轮划分操作都将长度为 n 的数组划分为长度为 0 和 n-1 的两个子数组，此时递归层数达到 n，每层中的循环数为 n，总时间为

O(n^2)

。

划分函数 partition 中“从右往左查找”与“从左往右查找”的顺序可以交换。

正确答案D

解析详情

答案 D快速排序的双指针划分逻辑 0.

思路与推导

当选择首元素 `arr[low]` 为 pivot 时，必须先从右向左查找。这是因为我们要保证指针相遇的位置 `i` 对应的值一定 $\leq pivot$ ，这样最后 `swap(arr[i], arr[low])` 才能正确将 pivot 换到中间。如果交换查找顺序，`i` 可能会停留在大于 pivot 的元素处。

第 12 题（单选题，2 分）

下述 C++ 代码实现了归并排序算法，则横线上应填写（）。

void merge(vector<int> &nums, int left, int mid, int right) {
    // 左子数组区间为 [left, mid]，右子数组区间为 [mid+1, right]
    vector<int> tmp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (_____) {
        tmp[k++] = nums[j++];
    }
    for (k = 0; k < tmp.size(); k++) {
        nums[left + k] = tmp[k];
    }
}

void mergeSort(vector<int> &nums, int left, int right) {
    if (left >= right)
        return;
    int mid = (left + right) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}

i < mid

j < right

i <= mid

j <= right

正确答案D

解析详情

答案 D归并排序的合并操作逻辑

思路与推导

归并排序的 `merge` 过程将两个有序子数组合并。第一个 while 循环合并了两侧直到一侧结束，后续两个单独的 while 循环负责将剩余部分考入临时数组。由于右侧数组范围是 $[mid+1, right]$ ，且指针为 $j$ ，故条件应为 `j <= right`。

第 13 题（单选题，2 分）

假设你是一家电影院的排片经理，只有一个放映厅。你有一个电影列表 movies，其中 movies[i] = [start_i, end_i] 表示第 i 部电影的开始 and 结束时间。请你找出最多能安排多少部不重叠的电影，则横线上应分别填写的代码为（）。

int maxMovies(vector<vector<int>>& movies) {
    if (movies.empty()) return 0;

    sort(movies.begin(), movies.end(), [](const vector<int>& a, const vector<int>& b) {
        return ___; // 在此处填入代码
    });

    int count = 1;
    int lastEnd = movies[0][1];
    for (int i = 1; i < movies.size(); i++) {
        if (movies[i][0] >= lastEnd) {
            count++;
            ___ = movies[i][1]; // 在此处填入代码
        }
    }

    return count;
}

a[0] < b[0] 和 lastEnd

a[1] < b[1] 和 lastEnd

a[0] < b[0] 和 movies[i][0]

a[1] < b[1] 和 movies[i][0]

正确答案B

解析详情

答案 B贪心算法（区间调度问题）

思路与推导

区间不重叠问题的经典贪心策略是：按“结束时间”升序排序，每次选择结束最早且与当前已选电影不重叠的电影。因此第一空填 `a[1] < b[1]`。当选中新电影后，需要更新上一次电影的结束时间，故第二空更新 `lastEnd`。

第 14 题（单选题，2 分）

给定一个整数数组 nums，下面代码找到一个具有最大和的连续子数组，并返回该最大和。则下面说法错误的是（）。

int crossSum(vector<int>& nums, int left, int mid, int right) {
    int leftSum = INT_MIN, rightSum = INT_MIN;
    int sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = max(leftSum, sum);
    }
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = max(rightSum, sum);
    }
    return leftSum + rightSum;
}

int helper(vector<int>& nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }
    int mid = left + (right - left) / 2;
    int leftMax = helper(nums, left, mid);
    int rightMax = helper(nums, mid + 1, right);
    int crossMax = crossSum(nums, left, mid, right);
    return max({leftMax, rightMax, crossMax});
}

int maxSubArray(vector<int>& nums) {
    return helper(nums, 0, nums.size() - 1);
}

上述代码采用分治算法实现

上述代码采用贪心算法

上述代码时间复杂度为O(nlogn)

上述代码采用递归方式实现

正确答案B

解析详情

答案 B最大子数组和问题的分治解法

思路与推导

代码中的 `helper` 函数不断将区间对半平分并递归调用自身，分别计算左半区最大和、右半区最大和以及跨越中间的最大和 `crossSum`。这属于典型的分治算法。贪心算法实现该问题通常使用 Kadane 算法，而不是递归分治。

第 15 题（单选题，2 分）

给定一个由非负整数组成的数组 digits，表示一个非负整数的各位数字，其中最高位在数组首位，且 digits 不含前导 0（除非是 0 本身）。下面代码对该整数执行 +1 操作，并返回结果数组，则横线上应填写（）。

vector<int> plusOne(vector<int>& digits) {
    for (int i = (int)digits.size() - 1; i >= 0; --i) {
        if (digits[i] < 9) {
            digits[i] += 1;
            return digits;
        }
        // 在此处填入代码
    }
    digits.insert(digits.begin(), 1);
    return digits;
}

digits[i] = 0;

digits[i] = 9;

digits[i] = 1;

digits[i] = 10;

正确答案A

解析详情

答案 A大数加法模拟（进位处理）

思路与推导

从最低位开始遍历。如果当前位小于 9，直接加 1 并返回。如果当前位是 9，加 1 后会产生进位，该位变为 0，循环继续处理更高位。如果循环结束仍未返回，说明最高位也产生了进位（如 99+1=100），则在数组开头插入 1。

判断题

第 1 题（判断题，2 分）

基于下面定义的函数，通过判断 isDivisibleBy9(n) == isDigitSumDivisibleBy9(n) 代码可验算如果一个数能被 9 整除，则它的各位数字之和能被 9 整除。

bool isDivisibleBy9(int n) {
    return n % 9 == 0;
}

bool isDigitSumDivisibleBy9(int n) {
    int sum = 0;
    string numStr = to_string(n);
    for (char c : numStr) {
        sum += (c - '0');
    }
    return sum % 9 == 0;
}

正确答案正确

解析详情

答案正确整除性判定规则

思路与推导

根据数学性质，一个整数能被 9 整除的充要条件是其各位数字之和能被 9 整除。代码中 `isDivisibleBy9` 直接判定整除，`isDigitSumDivisibleBy9` 计算位和后判定整除，二者逻辑等价。

第 2 题（判断题，2 分）

假设函数 gcd() 能正确求两个正整数的最大公约数，则下面的 findMusicalPattern(4, 6) 函数返回 2。

void findMusicalPattern(int rhythm1, int rhythm2) {
    int commonDivisor = gcd(rhythm1, rhythm2);
    int patternLength = (rhythm1 * rhythm2) / commonDivisor;
    return patternLength;
}

正确答案错误

解析详情

答案错误C++ 函数返回值与最小公倍数计算

思路与推导

首先，该函数定义为 `void` 类型，不能使用 `return` 返回数值，编译会报错。其次，代码逻辑计算的是最小公倍数 $(4 imes 6) / gcd(4, 6) = 24 / 2 = 12$ ，而不是 2。

第 3 题（判断题，2 分）

下面递归实现的斐波那契数列的时间复杂度为 $O(2^{n})$ 。

long long fib_memo(int n, long long memo[]) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    return memo[n];
}

int main() {
    int n = 40;
    long long memo[100];
    fill_n(memo, 100, -1);
    long long result2 = fib_memo(n, memo);
    return 0;
}

正确答案错误

解析详情

答案错误记忆化递归的时间复杂度分析

思路与推导

代码使用了记忆化搜索（`memo` 数组）。每个 `n` 对应的值只会被计算一次并存入数组，后续直接调用。因此时间复杂度降为 O(n)，不再是普通递归的指数级 O(2^n)。

第 4 题（判断题，2 分）

链表通过更改指针实现高效的结点插入与删除，但结点访问效率低、占用内存较多，且对缓存利用不友好。

正确答案正确

解析详情

答案正确链表的优缺点分析

思路与推导

链表不支持随机访问，访问第 n 个结点需 O(n)；每个结点多了一个指针域，内存开销大；物理存储不连续，无法利用 CPU 缓存预取，导致缓存命中率低。但其插入删除确实只需修改指针。

第 5 题（判断题，2 分）

二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找，且仅适用于数组或基于数组实现的数据结构。

正确答案正确

解析详情

答案正确二分查找的适用范围

思路与推导

二分查找的核心是能够通过 $O(1)$ 的时间定位中间元素（随机访问）。数组支持此操作，但普通链表定位中间结点需 $O(n)$ ，会使二分查找退化为 $O(n)$ ，失去优势。故主要适用于数组。

第 6 题（判断题，2 分）

线性筛关键是“每个合数只会被最小质因子筛到一次”，因此为 $O(n)$ 。

正确答案正确

解析详情

答案正确线性筛（欧拉筛）的时间复杂度

思路与推导

线性筛（欧拉筛）通过 `i % p == 0` 的判断，确保了每个合数被其最小质因子标记。因为每个数（共 n 个）被访问的次数是常数级，所以总复杂度为 O(n)。

第 7 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误排序算法的稳定性

思路与推导

归并排序是稳定的（取决于合并逻辑中对相等元素的处理），但标准快速排序在分区（partition）过程中，元素的交换可能会改变相等元素的相对顺序，因此是不稳定的。

第 8 题（判断题，2 分）

下面代码采用分治算法求解标准 3 柱汉诺塔问题，时间复杂度为 $O(n\log n)$ 。

void move(vector<int> &src, vector<int> &tar) {
    int pan = src.back();
    src.pop_back();
    tar.push_back(pan);
}

void dfs(int n, vector<int> &src, vector<int> &buf, vector<int> &tar) {
    if (n == 1) {
        move(src, tar);
        return;
    }

    dfs(n - 1, src, tar, buf);
    move(src, tar);
    dfs(n - 1, buf, src, tar);
}

void solveHanota(vector<int> &A, vector<int> &B, vector<int> &C) {
    int n = A.size();
    dfs(n, A, B, C);
}

正确答案错误

解析详情

答案错误递归算法的时间复杂度分析（汉诺塔问题）

思路与推导

汉诺塔问题的递归方程为 $T(n) = 2T(n-1) + 1$ 。求解可得 $T(n) = 2^n - 1$ ，因此其时间复杂度为指数级 O(2^n)，并非 O(n log n)。

第 9 题（判断题，2 分）

所有递归算法都可以转换为迭代算法。

正确答案正确

解析详情

答案正确递归与迭代的等价性

思路与推导

在计算机科学中，任何递归程序都可以通过引入显式栈结构转换为等效的非递归（迭代）形式。这是计算理论的基本结论。

第 10 题（判断题，2 分）

贪心算法总能得到全局最优解。

正确答案错误

解析详情

答案错误贪心算法的适用性与局限性

思路与推导

贪心算法在每一步都做出当前看来最优的选择，但并非所有问题都具备“贪心选择性质”和“最优子结构”。对于如 0/1 背包等问题，贪心算法只能得到近似解而非全局最优解。