单选题（每题 $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. 下述代码实现素数表的埃拉托斯特尼筛法，筛选出所有小于等于 $n$ 的素数，则横线上应填的最佳代码是( )。

{{ select(3) }}

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

4. 下面是根据欧几里得算法编写的函数，它计算的是 $a$ 与 $b$ 的（ ）。

{{ select(4) }}

• 最小公倍数
• 最大公共质因子
• 最大公约数
• 最小公共质因子

5. 欧几里得算法还可以写成如下形式:

下面有关说法，错误的是（ ）。

{{ select(5) }}

• 本题的 gcd() 实现为递归方式。
• 本题的 gcd() 代码量少，更容易理解其辗转相除的思想。
• 当 $a$ 较大时，本题的 gcd() 实现会多次调用自身，需要较多额外的辅助空间。
• 当 $a$ 较大时，相比上题中的 gcd() 的实现，本题的 gcd() 执行效率更高。

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

{{ select(6) }}

• for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
• for (int j = 0; j <= sqrt(n) && i * primes[j] <= n; j++)
• for (int j = 0; j <= n; j++)
• for (int j = 1; j <= sqrt(n); j++)

7. 上题代码的时间复杂度是（ ）

{{ select(7) }}

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

8. 为了正确实现快速排序，下面横线上的代码应为（ ）。

{{ select(8) }}

• while (i <= mid)
• while (i < mid)
• while (i < j)
• while (i <= j)

9. 关于分治算法，以下哪个说法正确？

{{ select(10) }}

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

10. 根据下述二分查找法，在排好序的数组 1，3，6，9，17，31，39，52，61，79，81，90，96 中查找数值 $82$，和 $82$ 比较的数组元素分别是（ ）

{{ select(10) }}

• 52, 61, 81, 90
• 52, 79, 90, 81
• 39, 79, 90, 81
• 39, 79, 90

11. 要实现一个高精度减法函数，则下面代码中加划线应该填写的代码为( )。

{{ select(11) }}

• a[i + 1]--;
• a[i]--;
• b[i + 1]--;
• b[i]--;

12. 设 $A$ 和 $B$ 是两个长度为 $m$ 的有序数组，现将 $A$ 和 $B$ 合并成一个有序数组，归并排序算法在最坏情况下至少要做（ ）次比较。

    {{ select(12) }}

• $n^2$
• $n\logn$
• $2n-1$
• $n$

13. 给定如下函数：

则当 $n==7$ 时，函数返回值为（ ）。

{{ select(13) }}

• $0$
• $1$
• $21$
• $-11$

14. 给定如下函数（函数功能同上题，增加输出打印）：

则当 $n==4$ 时，屏幕上输出序列为（ ）。 {{ select(14) }}

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

15. 贪心算法的核心思想是（ ）？ {{ select(15) }}

• 在每⼀步选择中都做当前状态下的最优选择
• 在每⼀步选择中都选择局部最优解
• 在每⼀步选择中都选择全局最优解
• 以上都对