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

1. 下面关于链表和数组的描述,错误的是( )。

{{ select(1) }}

• 数组大小固定,链表大小可动态调整。
• 数组支持随机访问,链表只能顺序访问。
• 存储相同数目的整数,数组比链表所需的内存多。
• 数组插入和删除元素效率低,链表插入和删除元素效率

2. 通过( )操作,能完成在双向循环链表结点 p 之后插入结点 s 的功能(其中 next 域为结点的直接后继,prev 域为结点的直接前驱)。

{{ select(2) }}

• 选项如下：

  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;
  

3. 对下面两个函数,说法错误的是( )。

{{ select(3) }}

• $sumA$体现了迭代的思想。
• $SumB$采用的是递归方式。
• $SumB$函数比$SumA$的时间效率更高。
• 两个函数的实现的功能相同。

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;
}

4. 有如下函数 fun,则 fun(20,12) 的返回值为( )。

{{ select(4) }}

• $20$
• $12$
• $4$
• $2$

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

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

{{ select(5) }}

• 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)

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

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

{{ select(6) }}

• 选项如下：

  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++)
  

• 以上都不对

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;
}

7. 下面函数可以将 $n$ 的所有质因数找出来,其时间复杂度是( )。

{{ select(7) }}

• $O(n^2)$
• $O(n \log n)$
• $O(\sqrt{n}\log n)$
• $O(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;
}

8. 现在用如下代码来计算 $x^n$($n$ 个 $x$ 相乘),其时间复杂度为( )。

{{ select(8) }}

• $O(n)$
• $O(n^2)$
• $O(\log n)$
• $O(n\log n)$

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

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

{{ select(9) }}

• 快速排序对于此类输入的表现最好,因为数组已经排序。
• 快速排序对于此类输入的时间复杂度是 $O(n\log 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 函数的递归调用次数大约是( )。

{{ select(10) }}

• $O(1)$
• $O(n)$
• $O(\log n)$
• $O(n \log n)$

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

{{ select(11) }}

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

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);

12. 关于分治算法,以下哪个说法正确?

{{ select(12) }}

• 分治算法将问题分成子问题,然后分别解决子问题,最后合并结果。
• 归并排序不是分治算法的应用。
• 分治算法通常用于解决小规模问题。
• 分治算法的时间复杂度总是优于 $O(n\log(n))$。

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

{{ select(13) }}

• $1$
• $2$
• $3$
• $4$

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;
}

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

{{ select(14) }}

• 高精度计算主要是用来处理大整数或需要保留多位小数的运算。
• 大整数除以小整数的处理的步骤可以是,将被除数和除数对齐,从左到右逐位尝试将除数乘以某个数,通过减法得到新的被除数,并累加商。
• 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。
• 高精度加法运算的关键在于逐位相加并处理进位。

15. 当 $n=7$ 时,下面函数的返回值为( )。

{{ select(15) }}

• $105$
• $840$
• $210$
• $420$

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

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

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

• 正确
• 错误

17. 找出自然数 $n$ 以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中线性筛法效率更高。 {{ select(17) }}

• 正确
• 错误

18. 唯一分解定理表明任何一个大于 $1$ 的整数都可以唯一地分解为素数之和。 {{ select(18) }}

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

21. 插入排序的时间复杂度总是比快速排序低。 {{ select(21) }}

• 正确
• 错误

22. 引入分治策略往往可以提升算法效率。一方面,分治策略减少了操作数量;另一方面,分治后有利于系统的并行优化。 {{ select(22) }}

• 正确
• 错误

23. 二分查找要求被搜索的序列是有序的,否则无法保证正确性。 {{ select(23) }}

• 正确
• 错误

24. 在 C++ 语言中,递归的实现方式通常会占用更多的栈空间,可能导致栈溢出。 {{ select(24) }}

• 正确
• 错误

25. 对于已经定义好的标准数学函数 $\sin(x)$,应用程序中的语句 y=sin(sin(x)); 是一种递归调用。 {{ select(25) }}

• 正确
• 错误