1. 辗转相除法用于求两个整数的最大公约数。

【答案】正确

【考纲知识点】辗转相除法

【解析】辗转相除法，又称欧几里得算法，是一种用于计算两个非负整数a和b的最大公约数的方法

2. 插入排序的时间复杂度是𝑂(N 𝑙𝑜𝑔 ​N​) 。

【答案】错误

【考纲知识点】排序算法(插入排序)

【解析】插入排序的时间复杂度在平均情况下为O(n²)，最好情况下的时间复杂度为O(n)，最坏情况下的时间复杂度为O(n²)。这是因为：

平均情况：当待排序数组中的元素分布较为均匀时，插入排序需要进行的比较次数大约是输入规模的一半，即O(n²)。

最好情况：如果待排序数组已经是有序的，那么插入排序只需进行n-1次比较即可完成排序，此时的时间复杂度为O(n)。

最坏情况：当待排序数组是完全逆序的，即所有元素都比前一个元素大（或小），此时需要进行的比较次数达到最大，即1+2+3+…+N-1，总次数为N(N-1)/2，因此时间复杂度为O(n²)。

3. 二分查找要求被搜索的序列是有序的，否则无法保证正确性。

【答案】正确

【考纲知识点】二分查找

【解析】二分查找，它的前提条件是被搜索的序列是有序的（升序或降序），如果序列无序则无法通过大小来进行折半

4. 使用贪心算法解决问题时，每一步的局部最优解一定会导致全局最优解。

【答案】错误

【考纲知识点】贪心算法

【解析】贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解，并不能得到全局最优解

5. 分治算法的核心思想是将一个大问题分解成多个相同或相似的子问题进行解决，最后合并得到原问题的解。

【答案】正确

【考纲知识点】分治算法

【解析】

【答案】正确

【考纲知识点】分治算法(归并排序和快速排序)

【解析】分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法的精髓：

分--将问题分解为规模更小的子问题；

治--将这些规模更小的子问题逐个击破；

合--将已解决的子问题合并，最终得出“母”问题的解

6. 分治算法的典型应用之⼀是归并排序，其时间复杂度为𝑂(N 𝑙𝑜𝑔 ​N​) 。

【答案】正确

【考纲知识点】分治算法

【解析】归并排序 是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用，其时间复杂度为𝑂(N 𝑙𝑜𝑔 ​N​)

7. 素数表的埃氏筛法和线性筛法的时间复杂度都是𝑂(N 𝑙𝑜𝑔 𝑙𝑜𝑔 ​N​) 。

【答案】错误

【考纲知识点】素数 埃氏筛法 线性筛法

【解析】素数线性筛每次只要筛选小于等于i的第一个素因子的素数与i的乘积，既不会造成重复筛选，又不会遗漏， 时间复杂度O(N)。埃氏筛法的时间复杂度为𝑂(N 𝑙𝑜𝑔 𝑙𝑜𝑔 ​N​)

8. 贪心算法是一种可以应用于所有问题的通用解决方案。

【答案】错误

【考纲知识点】贪心算法

【解析】贪心算法核心思想是选择当前状态下的最佳选择，动态规划的核心思想是最优子结构和重叠子问题。贪心不能解决动态规划类问题。

9. 单链表和双链表都可以在常数时间内实现在链表头部插入或删除节点的操作。

【答案】正确

【考纲知识点】链表

【解析】单链表的创建分为头插法和尾插法，单链表的删除分为按位序删除和指定结点的删除。双链表的插入分为头插法，尾插法，和中间位置插入，双链表的删除，一种的将单个节点进行删除，一种是将所有与目标值相同的节点进行删除，所以不管是单链表还是双链表都可以实现

10. 在C语言中，递归的实现方式式通常会占用更多的栈空间，可能导致栈溢出。

【答案】正确

【考纲知识点】递归

【解析】递归的优缺点：优点：代码简洁、便于理解；缺点：时间和空间消耗大、可能存在栈溢出、可能存在重复计算；计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以递归调用的次数过多，会导致栈溢出。