练习题 -- 数据结构与算法 >> 排序
共 9 题
第 1/9 题
★★
下列排序算法中，辅助空间为O(1)的是：
正确答案: C
【算法-排序】
题目：辅助空间O(1)的排序：
✅ 正确答案：C.堆排序
错误选项：
❌ A.归并
❌ B.快排
❌ D.基数
📖 解析：堆O(1)，归并O(n)，快排O(logn)，基数O(n+r)。
题目：辅助空间O(1)的排序：
✅ 正确答案：C.堆排序
错误选项：
❌ A.归并
❌ B.快排
❌ D.基数
📖 解析：堆O(1)，归并O(n)，快排O(logn)，基数O(n+r)。
第 2/9 题
★★
时间复杂度不受初始状态影响的排序：
正确答案: C
【算法-排序】
题目：时间复杂度不受初始状态影响的排序：
✅ 正确答案：C.简单选择
错误选项：
❌ A.冒泡
❌ B.快排
❌ D.插入
📖 解析：简单选择始终O(n²)。冒泡/插入最好O(n)，快排最好O(nlogn)。
题目：时间复杂度不受初始状态影响的排序：
✅ 正确答案：C.简单选择
错误选项：
❌ A.冒泡
❌ B.快排
❌ D.插入
📖 解析：简单选择始终O(n²)。冒泡/插入最好O(n)，快排最好O(nlogn)。
第 3/9 题
★★★
{15,9,7,8,20,-1,4}以15为基准一趟快排结果：
正确答案: A
【算法-排序】
题目：{15,9,7,8,20,-1,4}以15为基准一趟快排：
✅ 正确答案：A.{4,9,7,8,-1,15,20}
错误选项：
❌ B.{-1,9,7,8,4,15,20}
❌ C.{-1,4,7,8,15,9,20}
❌ D.{4,-1,7,8,9,15,20}
📖 解析：右找<15的4，左找>15的20，交换→右找到-1，左到20，交错基准与-1换→A。
题目：{15,9,7,8,20,-1,4}以15为基准一趟快排：
✅ 正确答案：A.{4,9,7,8,-1,15,20}
错误选项：
❌ B.{-1,9,7,8,4,15,20}
❌ C.{-1,4,7,8,15,9,20}
❌ D.{4,-1,7,8,9,15,20}
📖 解析：右找<15的4，左找>15的20，交换→右找到-1，左到20，交错基准与-1换→A。
第 4/9 题
★
以下哪种排序算法在最好情况下时间复杂度为O(n)？
正确答案: B
【算法-排序】
题目：最好情况O(n)的排序：
✅ 正确答案：B.冒泡
错误选项：
❌ A.快排
❌ C.归并
❌ D.堆
📖 解析：冒泡最好O(n)（已有序），快排最好O(nlogn)。
题目：最好情况O(n)的排序：
✅ 正确答案：B.冒泡
错误选项：
❌ A.快排
❌ C.归并
❌ D.堆
📖 解析：冒泡最好O(n)（已有序），快排最好O(nlogn)。
第 5/9 题
★
对序列{2,1,4,5,3}使用简单选择排序，第一趟后的结果是：
正确答案: A
【算法-排序】
题目：{2,1,4,5,3}简单选择第一趟结果：
✅ 正确答案：A.{1,2,4,5,3}
错误选项：
❌ B.{1,2,3,5,4}
❌ C.{2,1,3,5,4}
❌ D.{1,2,4,3,5}
📖 解析：第一趟找最小(1)与第一个(2)交换→{1,2,4,5,3}。
题目：{2,1,4,5,3}简单选择第一趟结果：
✅ 正确答案：A.{1,2,4,5,3}
错误选项：
❌ B.{1,2,3,5,4}
❌ C.{2,1,3,5,4}
❌ D.{1,2,4,3,5}
📖 解析：第一趟找最小(1)与第一个(2)交换→{1,2,4,5,3}。
第 6/9 题
★
堆排序中，输出堆顶元素后，用什么元素替代堆顶？
正确答案: C
【算法-排序】
题目：堆排序输出堆顶后用什么替代？
✅ 正确答案：C.最后一个元素
错误选项：
❌ A.任意元素
❌ B.最小元素
❌ D.新插入元素
📖 解析：堆顶与末尾元素交换→堆大小减1→从堆顶向下调整。
📌 拓展：堆排序空间O(1)是其重要优点，适用于内存受限环境；但不稳定是其缺点。
题目：堆排序输出堆顶后用什么替代？
✅ 正确答案：C.最后一个元素
错误选项：
❌ A.任意元素
❌ B.最小元素
❌ D.新插入元素
📖 解析：堆顶与末尾元素交换→堆大小减1→从堆顶向下调整。
📌 拓展：堆排序空间O(1)是其重要优点，适用于内存受限环境；但不稳定是其缺点。
第 7/9 题
★★
对n个元素进行堆排序，将序列建成初始堆的时间复杂度是：
正确答案: A
【算法-排序】
题目：建堆的时间复杂度：
✅ 正确答案：A.O(n)
错误选项：
❌ B.O(nlogn)
❌ C.O(logn)
❌ D.O(n²)
📖 解析：从最后一个非叶节点向下调整，建堆累计O(n)。
📌 拓展：从最后一个非叶节点向下调整建堆，时间复杂度O(n)；每次取出堆顶后调整O(logn)，整体O(nlogn)。
题目：建堆的时间复杂度：
✅ 正确答案：A.O(n)
错误选项：
❌ B.O(nlogn)
❌ C.O(logn)
❌ D.O(n²)
📖 解析：从最后一个非叶节点向下调整，建堆累计O(n)。
📌 拓展：从最后一个非叶节点向下调整建堆，时间复杂度O(n)；每次取出堆顶后调整O(logn)，整体O(nlogn)。
第 8/9 题
★
下列排序算法中，属于稳定排序的是：
正确答案: C
【算法-排序】
题目：属于稳定排序的是：
✅ 正确答案：C.归并排序
错误选项：
❌ A.堆排
❌ B.快排
❌ D.希尔
📖 解析：归并稳定。快排/堆排/希尔不稳定。
题目：属于稳定排序的是：
✅ 正确答案：C.归并排序
错误选项：
❌ A.堆排
❌ B.快排
❌ D.希尔
📖 解析：归并稳定。快排/堆排/希尔不稳定。
第 9/9 题
★
以下排序算法中，每趟排序后都能确定一个元素的最终位置的是：
正确答案: C
【算法-排序】
题目：每趟确定一个元素最终位置的排序：
✅ 正确答案：C.冒泡
错误选项：
❌ A.插入
❌ B.希尔
❌ D.归并
📖 解析：冒泡每趟沉最大。快排每趟定基准位置。
题目：每趟确定一个元素最终位置的排序：
✅ 正确答案：C.冒泡
错误选项：
❌ A.插入
❌ B.希尔
❌ D.归并
📖 解析：冒泡每趟沉最大。快排每趟定基准位置。