单选题库 - E心E意

EXY-SC-1335

第 166 题

给定一个由非负整数组成的数组 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;
}

A

digits[i] = 0;

B

digits[i] = 9;

C

digits[i] = 1;

D

digits[i] = 10;

语言： C++

GESP真题五级

2025.9

单选题号： 15

EXY-SC-1334

第 167 题

给定一个整数数组 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);
}

A

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

B

上述代码采用贪心算法

C

上述代码时间复杂度为 $O(n \log n)$

D

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

语言： C++

GESP真题五级

2025.9

单选题号： 14

EXY-SC-1333

第 168 题

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

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

a[0] < b[0] 和 lastEnd

B

a[1] < b[1] 和 lastEnd

C

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

D

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

语言： C++

GESP真题五级

2025.9

单选题号： 13

EXY-SC-1332

第 169 题

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

A

i < mid

B

j < right

C

i <= mid

D

j <= right

语言： C++

GESP真题五级

2025.9

单选题号： 12

EXY-SC-1331

第 170 题

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

A

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

B

在平均情况下，划分的递归层数为 $\log n$，每层中的总循环数为 $n$，总时间为 $O(n \log n)$。

C

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

D

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

语言： C++

GESP真题五级

2025.9

单选题号： 11