判断题（每题 2 分，共 20 分）

第 1 题

数组和链表都是线性表。链表的优点是插入删除不需要移动元素，并且能随机查找。

{{ select(1) }}

• 正确
• 错误

---

第 2 题

假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm(a, b) 函数能正确找到两个正整数 $a$ 和 $b$ 的最小公倍数。

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

{{ select(2) }}

• 正确
• 错误

---

第 3 题

在单链表中，已知指针 $p$ 指向要删除的结点（非尾结点），想在 $O(1)$ 删除 $p$，可行做法是用 p->next 覆盖 $p$ 的值与 $next$，然后删除 p->next。

{{ select(3) }}

• 正确
• 错误

---

第 4 题

在求解所有不大于 $n$ 的素数时，线性筛法（欧拉筛）都应当优先于埃氏筛法使用，因为线性筛法的时间复杂度为 $O(n)$，低于埃氏筛法的 $O(n \log \log n)$。

{{ select(4) }}

• 正确
• 错误

---

第 5 题

二分查找仅适用于有序数据。若输入数据无序，当仅进行一次查找时，为了使用二分而排序通常不划算。

{{ select(5) }}

• 正确
• 错误

---

第 6 题

通过在数组的第一个、最中间和最后一个这 3 个数据中选择中间值作为枢轴（比较基准），快速排序算法可降低落入最坏情况的概率。

{{ select(6) }}

• 正确
• 错误

---

第 7 题

贪心算法在每一步都做出当前看来最优的局部选择，并且一旦做出选择就不再回溯；而分治算法将问题分解为若干子问题分别求解，再将子问题的解合并得到原问题的解。

{{ select(7) }}

• 正确
• 错误

---

第 8 题

以下 fib 函数计算第 $n$ 项斐波那契数（$fib(0)=0$，$fib(1)=1$），其时间复杂度为 $O(n)$。

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

{{ select(8) }}

• 正确
• 错误

---

第 9 题

递归函数一定要有终止条件，否则可能会造成栈溢出。

{{ select(9) }}

• 正确
• 错误

---

第 10 题

使用贪心算法解决问题时，通过对每一步求局部最优解，最终一定能找到全局最优解。

{{ select(10) }}

• 正确
• 错误