二、判断题

第 1 题 数组和链表都是线性表｡链表的优点是插入删除不需要移动元素,并且能随机查找｡（ ） {{ select(1) }}

• 对
• 错

第 2 题 假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的 lcm(a,b) 函数能正确找到两个正整数 a 和 b 的最小公倍数｡（ ） {{ select(2) }}

• 对
• 错

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

第 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)$ 。（ ） {{ select(8) }}

• 对
• 错

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

第 9 题 递归函数一定要有终止条件,否则可能会造成栈溢出｡（ ） {{ select(9) }}

• 对
• 错

第 10 题 使用贪心算法解决问题时,通过对每一步求局部最优解,最终一定能找到全局最优解｡（ ） {{ select(10) }}

• 对
• 错