排序·多选训练2

第 1 题（多选）

关于二分查找的变体，正确的有（　）。

{{ multiselect(1) }}

• 可以查找第一个等于目标的位置
• 可以查找最后一个等于目标的位置
• 可以查找大于等于目标的第一个位置
• 可以用于数组和链表

第 2 题（多选）

关于二分查找的递归实现，正确的有（　）。

{{ multiselect(2) }}

• 每次递归调用问题规模减半
• 递归深度为O(log n)
• 递归实现可能导致栈溢出
• 循环实现比递归实现更节省空间

第 3 题（多选）

以下哪些排序算法在平均情况下的时间复杂度为O(n log n)？（　）

{{ multiselect(3) }}

• 冒泡排序
• 快速排序
• 归并排序
• 插入排序

第 4 题（多选）

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

{{ multiselect(4) }}

• 快速排序是一种不稳定的排序算法
• 快速排序的平均时间复杂度为O(n log n)
• 快速排序在最坏情况下的时间复杂度为O(n²)
• 快速排序是稳定的排序算法

第 5 题（多选）

关于归并排序，下列说法正确的有（　）。

{{ multiselect(5) }}

• 归并排序是稳定的排序算法
• 归并排序的时间复杂度在任何情况下均为O(n log n)
• 归并排序需要额外的O(n)辅助空间
• 归并排序通常采用迭代方式实现，而非递归