算法思想·多选训练7（2）

第 1 题（多选）

以下哪些算法应用了分治思想？（　）

{{ multiselect(1) }}

• 归并排序
• 快速排序
• 二分查找
• 埃拉托斯特尼筛法

第 2 题（多选）

关于素数判定，以下说法正确的有（　）。

{{ multiselect(2) }}

• 判断一个数n是否为素数，只需检查到√n即可
• 埃氏筛法的时间复杂度为O(n log log n)
• 线性筛法每个合数只会被其最小质因子筛一次
• 素数的判定没有更优方法，只能枚举到n-1

第 3 题（多选）

关于递归与迭代，正确的有（　）。

{{ multiselect(3) }}

• 递归通常比迭代更易于理解和编写
• 递归函数可能因栈空间不足而溢出
• 所有递归都可以改写为迭代
• 迭代的效率一定高于递归

第 4 题（多选）

关于循环链表，正确的有（　）。

{{ multiselect(4) }}

• 循环链表的尾节点指向头节点
• 循环链表可以从任意节点出发访问所有节点
• 循环链表比普通链表更节省内存
• 循环链表适合实现环形缓冲区

第 5 题（多选）

关于双向链表，正确的有（　）。

{{ multiselect(5) }}

• 每个节点有两个指针
• 可以方便地删除任意节点（已知位置）
• 比单向链表占用更多内存
• 在头部插入和删除时间复杂度为O(1)