第 1 题 下面关于链表和数组的描述，错误的是（ ）。

{{ select(1) }}

• 当数据数量不确定时，为了应对各种可能的情况，需要申请一个较大的数组，可能浪费空间；此时用链表比较合适，大小可动态调整。
• 在链表中访问节点的效率较低，时间复杂度为$O(n)$。
• 链表插入和删除元素效率较低，时间复杂度为$O(n)$。
• 链表的节点在内存中是分散存储的，通过指针连在一起。

---

第 2 题 在循环单链表中，节点的 next 指针指向下一个节点，最后一个节点的 next 指针指向（ ）。

{{ select(2) }}

• 当前节点
• nullptr
• 第一个节点
• 上一个节点

---

第 3 题 为了方便链表的增删操作，一些算法生成一个虚拟头节点，方便统一删除头节点和其他节点。下面代码实现了删除链表中值为 val 的节点，横线上应填的最佳代码是（ ）。

{{ select(3) }}

• dummyHead->next = head; cur = dummyHead;
• dummyHead->next = head->next; cur = dummyHead;
• dummyHead->next = head; cur = dummyHead->next;
• dummyHead->next = head->next; cur = dummyHead->next;

---

第 4 题 对下面两个函数，说法错误的是（ ）。

{{ select(4) }}

• 两个函数的实现的功能相同。
• fibA采用递推方式。
• fibB采用的是递归方式。
• fibA时间复杂度为$O(n)$，fibB的时间复杂度为$O(n^{2})$。

---

第 5 题 两块长方形土地的长宽分别为24和36米，要将它们分成正方形的小块，使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数 gcd(24，36) 来求正方形分块的边长，则函数 gcd 调用顺序为（ ）。

{{ select(5) }}

• gcd(24, 36)、gcd(24, 12)、gcd(12, 0)
• gcd(24, 36)、gcd(12, 24)、 gcd(0, 12)
• gcd(24, 36)、gcd(24, 12)
• gcd(24, 36)、gcd(12, 24)

---

第 6 题 唯一分解定理表明，每个大于 $1$ 的自然数可以唯一地写成若干个质数的乘积。下面函数将自然数 $n$ 的所有质因素找出来，横线上能填写的最佳代码是（ ）。

{{ select(6) }}

• for (int i = 3; i <= n; i++)
• for (int i = 3; i * i <= n; i++)
• for (int i = 3; i <= n; i += 2)
• for (int i = 3; i * i <= n; i += 2)

---

第 7 题 下述代码实现素数表的埃拉托色尼(埃氏)筛法，筛选出所有小于等于$n$的素数。

下面说法，正确的是（ ）。

{{ select(7) }}

• 代码的时间复杂度是 $O(n\sqrt{n})$ 。
• 在标记非素数时，代码从 $i^{2}$ 开始，可以减少重复标记。
• 代码会输出所有小于等于 $n$ 的奇数。
• 调用函数 $sieve_Eratosthenes(10)$，函数返回值的数组中包含的元素有：$2,3,5,7,9$。

---

第 8 题 下述代码实现素数表的线性筛法，筛选出所有小于等于$n$的素数。下面说法正确的是（ ）。

{{ select(8) }}

• 线性筛的时间复杂度是 $O(n)$。
• 每个合数会被其所有的质因子标记一次。
• 线性筛和埃拉托色尼筛的实现思路完全相同。
• 以上都不对

---

第 9 题 考虑以下C++代码实现的快速排序算法:

以下关于快速排序的说法，正确的是（ ）。

{{ select(9) }}

• 快速排序通过递归对子问题进行求解。
• 快速排序的最坏时间复杂度是$O(n\ log\ n)$。
• 快速排序是一个稳定的排序算法。
• 在最优情况下，快速排序的时间复杂度是$O(n)$。

---

第 10 题 下面关于归并排序，描述正确的是（ ）。

{{ select(10) }}

• 归并排序是一个不稳定的排序算法。
• 归并排序的时间复杂度在最优、最差和平均情况下都是 $O(n\log n)$ 。
• 归并排序需要额外的 $O(1)$ 空间。
• 对于输入数组 {12,11,13,5,6,7}，代码输出结果为：7 6 5 13 12 11。

---

第 11 题 给定一个长度为 $n$ 的有序数组 nums，其中所有元素都是唯一的。下面的函数返回数组中元素 target 的索引。

关于上述函数，描述不正确的是（ ）。

{{ select(11) }}

• 函数采用二分查找，每次计算搜索当前搜索区间的中点，然后根据中点的元素值排除一半搜索区间。
• 函数采用递归求解，每次问题的规模减小一半。
• 递归的终止条件是中间元素的值等于 target，若数组中不包含该元素，递归不会终止。
• 算法的复杂度为 $O(logn)$。

---

第 12 题 给定一个长度为 $n$ 的有序数组 nums，其中可能包含重复元素。下面的函数返回数组中某个元素 target 的左边界，若数组中不包含该元素，则返回 -1。例如在数组 nums=[5,7,7,8,8,10] 中查找 target=8，函数返回8在数组中的左边界的索引为3。则横线上应填写的代码为（ ）。

{{ select(12) }}

• right= middle - 1;
• right = middle;
• right = middle + 1;
• 以上都不对

---

第 13 题 假设有多个孩子，数组 g 保存所有孩子的胃口值。有多块饼干，数组 s 保存所有饼干的尺寸。小杨给孩子们发饼干，每个孩子最多只能给一块饼干。饼干的尺寸大于等于孩子的胃口时，孩子才能得到满足。小杨的目标是尽可能满足越多数量的孩子，因此打算采用贪心算法来找出能满足的孩子的数目，则横线上应填写的代码为（ ）。

{{ select(13) }}

• result++; index--;
• result--; index--;
• result--; index++;
• result++; index++;

---

第 14 题 关于分治算法，以下说法中不正确的是（ ）。

{{ select(14) }}

• 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。
• 归并排序采用了分治思想。
• 快速排序采用了分治思想。
• 冒泡排序采用了分治思想。

---

第 15 题 小杨编写了一个如下的高精度减法函数：

下面说法，正确的是（ ）。

{{ select(15) }}

• 如果数组 $a$ 表示的整数小于b表示的整数，代码会正确返回二者的差为负数。
• 代码假设输入数字是以倒序存储的，例如 500 存储为 {0，0，5}。
• 代码的时间复杂度为 $O(- size( )+- size())$
• 当减法结果为 $0$ 时，结果数组仍然会存储很多个元素 $0$。

---