Skip to content

2023年 408 数据结构 第 11 题

数据结构2023年选择题2分

题目

使用快速排序算法对数据进行升序排序,若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的枢轴是( )。

错因

A

把"序列里最小的元素"当成枢轴。11 确实是序列最小值,但快排的枢轴不是"最小值"——它是划分后落在最终位置上的那个元素,要满足"左边都比它小,右边都比它大"。看 11 的左边是 68(>11),不满足"左边全 ≤ 11",11 不可能是枢轴。

B

只看到 70 两侧元素分布有点像"小、大",没逐个核对。70 左边是 68, 11(都 < 70)✓,但右边是 23, 80, 77, 48, 81, 93, 88——23 < 70,违反"右边全 > 枢轴"的性质,70 不是枢轴。

C

跟 B 类似的偷懒。80 左边 68, 11, 70, 23 都 < 80 ✓,但右边 77 < 80(也 48 < 80),违反性质。80 也不是。

总解析

枢轴的判定准则:一次划分后,枢轴必须落在最终位置——即"左边所有元素 ≤ 枢轴,右边所有元素 ≥ 枢轴"(升序时)。逐个候选验证最快。

序列:68, 11, 70, 23, 80, 77, 48, 81, 93, 88(下标 0..9)

逐项验证

候选左边右边检验
11 (idx 1)左 68 > 11 ✗
70 (idx 2)右 23 < 70 ✗
80 (idx 4)右 77, 48 < 80 ✗
81 (idx 7){68, 11, 70, 23, 80, 77, 48}(max=80 ≤ 81){93, 88}(min=88 ≥ 81)

81 的左边最大是 80,右边最小是 88,恰好夹住 81——这就是它划分完成的最终位置。

最终答案是 D(81)

实战技巧:碰到"找枢轴"题,先扫一眼两侧分界的元素——枢轴左边的最大值和右边的最小值都必须把枢轴夹在中间。从中间往两端扫往往比逐个候选快。

最后更新:

🎬 可视化演示
加载中...

提示:可在可视化区直接操作播放、步进、修改参数