题目描述

1. 链表不具备的特点是（）

   {{ select(1) }}

• 可以随机访问任何一个元素。
• 插入、删除操作不需要移动元素
• 无需事先估计存储空间大小
• 所需存储空间与存储元素个数成正比

2. 双向链表中那个每个节点有两个指针域 prev 和 next，分别指向该结点的前驱及后继结点。设 $p$ 指向链表中的一个结点，它的前驱结点和后继结点均非空。要删除 $p$，则以下描述错误的是？

   {{ select(2) }}

• p->next->prev = p->next; p->prev->next = p->prev; delete p;
• p->prev->next = p->next; p->next->prev = p->prev; delete p;
• p->next->prev = p->prev; p->next->prev->next = p->next; delete p;
• p->prev->next = p->next; p->prev->next->prev = p->prev; delete p;

3. 假设双向循环链表包含头尾哨兵结点（不存储实际内容），分别为 head 和 tail，链表中每个结点有两个指针域 prev 和 next，下面代码实现一个空的双向循环链表，横线上应填的最佳代码是（ ）。

template <typename T>
struct ListNode {
    T data;
    ListNode *prev, *next;

    // 构造函数
    explicit ListNode(const T &val = T()) : data(val), prev(nullptr), next(nullptr) {}
};

struct LinkedList {
    ListNode<T> *head, *tail;
};

void IninLinkedList(LinkedList *list) {
    list->head = new ListNode<T>();
    list->tail = new ListNode<T>();
    ___________ // 此处填入代码
}

{{ select(3) }}

• list->head->prev = list->head; list->tail->prev = list->head;
• list->head->next = list->tail; list->tail->prev = list->head;
• list->head->next = list->tail; list->tail->next = list->head;
• list->head->next = list->tail; list->tail->next = nullptr;

4. 用辗转相除法（欧几里得算法）求 gcd(84, 60) 的步骤中，第二步计算的数是（ ）。

int gcd(int a, int b) {
    int big = a > b ? a : b;
    int small = a < b ? a : b;
    if (big % small == 0) {
        return small;
    }
    return gcd(small, big % small);
}

{{ select(4) }}

• 84 和 60
• 60 和 24
• 24 和 12
• 12 和 0

5. 根据唯一分解定理，下面整数的唯一分解是正确的（ ）。 {{ select(5) }}

• 18 = 3 × 6
• 28 = 4 × 7
• 36 = 2 × 3 × 6
• 30 = 2 × 3 × 5

6. 下述代码实现素数表的线性筛法，筛选出所有小于等于 n 的素数，横线上应填的最佳代码是（ ）。

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

    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= n / 2; i++) {
        if (is_prime[i]) 
            primes.push_back(i);
        
        for (int j = 0; ________________; j++) {
            is_prime[i * primes[j]] = false;
            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;
}

{{ select(6) }}

• j < primes.size()
• i * primes[j] <= n
• j < primes.size() && i * primes[j] <= n
• j <= n

7. 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

   {{ select(7) }}

• 系统分配的栈空间溢出
• 系统分配的堆空间溢出
• 系统分配的队列空间溢出
• 系统分配的链表空间溢出

8. 对下面两个函数，说法错误的是（ ）。
   （提供 factorialA 和 factorialB 的递归与迭代代码）

int factorialA(int n) {
    if (n <= 1) return 1;
    return n * factorialA(n - 1);
}

int factorialB(int n) {
    if (n <= 1) return 1;
    int res = 1;
    for (int i = 1; i <= n; i++) {
        res *= i;
    }
    return res;
}

{{ select(8) }}

• 两个函数实现的功能相同
• 两个函数的时间复杂度均为 O(n)
• factorialA 采用递归方式
• factorialB 采用递归方式

9. 下列排序算法中，不稳定的是（ ）。

   {{ select(9) }}

• 选择排序
• 插入排序
• 归并排序
• 冒泡排序

10. 考虑以下 C++ 快速排序算法，将数据从小到大排序，横线上应填的最佳代码是（ ）。
    （提供 partition 函数部分代码）

int partition(vector<int>& arr, int low, int high) { 
    int pivot = arr[high]; // 基准值
    int i = low - 1;

    for (int j = low; j < high; j++) { 

        ___________ // 此处填入代码
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quicksort(vector<int>& arr, int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    qucik(arr, low, pi - 1);
    quick(arr, pi + 1, high);
  }
}

{{ select(10) }}

• if (arr[j] > pivot) { i++; swap(arr[i], arr[j]); }
• if (arr[j] < pivot) { i++; swap(arr[i], arr[j]); }
• if (arr[j] < pivot) { swap(arr[i], arr[j]); i++; }
• if (arr[j] == pivot) { i++; swap(arr[i], arr[j]); }

11. 若用二分法在 [1, 100] 内猜数，最多需要猜（ ）次。
    {{ select(11) }}

• 100
• 10
• 7
• 5

12. 下面代码实现了二分查找算法，在数组 arr 找到目标元素 target 的位置，横线上能填写的最佳代码是（ ）。

int binarySearch(int arr[], int left, int right, int target) { 
    while (left <= right) { 
        __________ // 此处填入代码
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

{{ select(12) }}

• int mid = left + (right - left) / 2;
• int mid = left;
• int mid = (left + right) / 2;
• int mid = right;

13. 贪心算法的核心特征是（ ）。

    {{ select(13) }}

• 总是选择当前最优解
• 回溯尝试所有可能
• 分阶段解决子问题
• 总能找到最优解

14. 函数 int findMax(int arr[], int low, int high) 计算数组中最大元素，下列选项中正确实现了分治逻辑的是（ ）。

A 选项代码

if (low == high) return arr[low];
int mid = (low + high) / 2;
return arr[mid];

B 选项代码

if (low >= high) return arr[low];
int mid = (low + high) / 2;
int leftMax = findMax(arr, low, mid - 1);
int rightMax = findMax(arr, mid, high);
return leftMax + rightMax;

C 选项代码

if (low > high) return 0;
int mid = low +  (high - low) / 2;
int leftMax = findMax(arr, low, mid);
int rightMax = findMax(arr, mid + 1, high);
return leftMax * rightMax;

D 选项代码

if (low == high) return arr[low];
int mid = low +  (high - low) / 2;
int leftMax = findMax(arr, low, mid);
int rightMax = findMax(arr, mid + 1, high);
return max(leftMax, rightMax);

{{ select(14) }}

• 选 A
• 选 B
• 选 C
• 选 D

15. 小杨编写了如下的高精度乘法函数，横线上应填写的代码是（ ）。

vector<int> multiply(vector<int> &a, vector<int> &b) { 
    int m = a.size(), n = b.size();
    vector<int> c(m + n, 0);

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            c[i + j] += a[i] * b[j];
        }
    }

    int carry = 0;
    for (int k = 0; k < m + n; k++) {

        ____________ // 此处填入代码
        c[k] = temp % 10;
        carry = temp / 10;
    }

    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;
}

{{ select(15) }}

• int temp = c[k];
• int temp = c[k] + carry;
• int temp = c[k] - carry;
• int temp = c[k] * carry;