单选题(每题 2 分,共 30 分)

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;
    ListNode* next;
    // 构造函数
    explicit ListNode(const T& val = T())
        : data(val), prev(nullptr), next(nullptr) {}
};

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

void InitLinkedList(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\times6$
• $28=4\times7$
• $36=2\times3\times6$
• $30=2\times3\times5$

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. 对下面两个函数,说法错误的是( )。

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=2; i<=n; i++)
        res *= i;
}

{{ select(8) }}

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

9. 下列算法中,( )是不稳定的排序。 {{ select(9) }}

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

10. 考虑以下 C++ 代码实现的快速排序算法,将数据从小到大排序,则横线上应填的最佳代码是( )。

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);
        quickSort(arr, low, pi - 1);
        quickSort(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) 计算数组中最大元素,其中数组 $arr$ 从索引 $low$ 到 $high$,( )正确实现了分治逻辑。 {{ select(14) }}

• 选项如下:

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

• 选项如下:

  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;
  

• 选项如下:

  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;
  

• 选项如下:

  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 (leftMax > rightMax) ? leftMax : rightMax;
  

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 < c.size(); ++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;

判断题(每题 2 分,共 20 分)

16. 要删除单链表中某个结点 p(非尾结点),但不知道头结点,可行的操作是将 p->next 的数据拷贝到 p 的数据部分,将 p->next 设置为 p->next->next,然后删除 p->next。 {{ select(16) }}

• 正确
• 错误

17. 链表存储线性表时要求内存中可用存储单元地址是连续的。 {{ select(17) }}

• 正确
• 错误

18. 线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因数筛去一次,因此效率更高。 {{ select(18) }}

• 正确
• 错误

19. 贪心算法通过每一步选择当前最优解,从而一定能获得全局最优解。 {{ select(19) }}

• 正确
• 错误

20. 递归函数必须具有一个终止条件,以防止无限递归。 {{ select(20) }}

• 正确
• 错误

21. 快速排序算法的时间复杂度与输入是否有序无关,始终稳定为 $O(n\log n)$。 {{ select(21) }}

• 正确
• 错误

22. 归并排序算法的时间复杂度与输入是否有序无关,始终稳定为 $O(n\log n)$。 {{ select(22) }}

• 正确
• 错误

23. 二分查找适用于对无序数组和有序数组的查找。 {{ select(23) }}

• 正确
• 错误

24. 小杨有 $100$ 元去超市买东西,每个商品有各自的价格,每种商品只能买 $1$ 个,小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买,这体现了分治思想。 {{ select(24) }}

• 正确
• 错误

25. 归并排序算法体现了分治算法,每次将大的待排序数组分成大小大致相等的两个小数组,然后分别对两个小数组进行排序,最后对排好序的两个小数组合成有序数组。 {{ select(25) }}

• 正确
• 错误