SCP 模拟 · SCP 2021 第一轮（初赛）模拟 第 6 题

下列算法中，没有运用分治思想的一项是

这题本质是考分治思想的识别，拿到题先想：分治的核心是‘把大问题拆成若干小问题，分别解决再合并’。遍历树时，前序/中序/后序都是递归拆子树再合并结果，层次遍历只是按层取节点，没有拆分合并过程，所以选 D。

容易把‘递归’和‘分治’混为一谈，以为只要是递归就是分治，其实递归只是实现方式，分治强调‘拆分→解决→合并’三步。命题人常挖坑在层次遍历，因为它用队列实现，看似也在处理子树，但并没有把问题拆成独立子问题再合并结果，只是按顺序取节点，所以很多学生会误选 B 或 C。

本题考查分治思想在算法中的体现。分治的核心是‘拆分→解决→合并’：把原问题拆成若干个规模更小的子问题，递归地求解这些子问题，最后将子问题的解合并成原问题的解。典型例子如归并排序和快速排序，都是先按某种规则把数组分成左右两半，分别排序，再合并或取中值。二叉树的前序、中序、后序遍历，本质上都是对根节点先处理，然后递归地对左子树和右子树分别遍历，最后合并结果（输出序列），也符合分治模式。层次遍历则不同：它用队列按层逐点取出节点，没有任何‘拆分子问题’的步骤，也不存在‘合并’操作，只是顺序输出，因此没有运用分治思想，正确答案是 D。命题人喜欢在层次遍历上挖坑，因为它看起来也在处理子树，但缺少分治的关键特征。解题时先判断是否出现‘拆分’和‘合并’，再结合递归结构确认。考频趋势上，分治思想在 CSP-J/S 中属于高频考点，近五年每年至少出现一次相关单选题或多选题，常与排序、树遍历结合。未来仍会高频考查分治与递归的区分，尤其是层次遍历这类‘看似递归实则非分治’的陷阱题。暂无足够依据预测具体年份或题型变化，但建议重点复习分治三要素及遍历算法的本质区别。