01｜2025-03-L5-SC-09

学生训练答案：A

原卷事实

题目比较四种排序的稳定性。

必要假设

按教材中的标准实现。

C++11 / 算法语义

选择排序交换最小元素时可能改变相等元素的相对次序。

命题预期

选择A。

推导结论

训练答案A。

02｜2025-03-L5-TF-10

学生训练答案：T

原卷事实

题面描述分割、递归排序和合并三个阶段。

必要假设

按标准归并排序。

C++11 / 算法语义

该过程正是分治：分解为两个近等规模子问题，递归解决后线性合并。

命题预期

判断为真。

推导结论

训练答案T。

03｜2025-06-L5-TF-05

学生训练答案：T

原卷事实

题目比较归并排序三类输入的时间复杂度。

必要假设

按标准归并排序实现。

C++11 / 算法语义

递归层数O(log n)，每层合并总工作O(n)，三者均为O(n log n)。

命题预期

判断为真。

推导结论

学生训练答案T。

04｜2025-06-L5-TF-08

学生训练答案：F

原卷事实

题面从分解和合并开销推出分治通常更慢。

必要假设

未限定具体问题和直接算法。

C++11 / 算法语义

分治常用于降低复杂度，如归并排序和二分查找；不能仅凭有拆分合并步骤推断通常更低效。

命题预期

判断为假。

推导结论

学生训练答案F。

05｜2025-12-L5-SC-08

学生训练答案：B

原卷事实

题目比较常见排序性质。

必要假设

采用标准实现。

C++11 / 算法语义

快速排序通常不稳定；归并可稳定；插入稳定；冒泡原地。

命题预期

选择B。

推导结论

训练答案B。

06｜2026-03-L5-TF-03

学生训练答案：F

原卷事实

题面把枢轴位置与稳定性直接关联。

必要假设

采用普通交换式快速排序。

C++11 / 算法语义

稳定性取决于分区时是否保持相等键相对次序，选中间元素不能保证。

命题预期

判断为假。

推导结论

训练答案F。

07｜2026-03-L5-SC-14

学生训练答案：B

原卷事实

题目比较标准排序性质。

必要假设

冒泡含提前终止优化；归并时相等元素优先取左侧。

C++11 / 算法语义

归并排序通常稳定，因此B错误。

命题预期

选择B。

推导结论

训练答案B。

08｜2025-03-L5-TF-06

学生训练答案：F

原卷事实

题面断言快速排序不受输入影响且始终O(n log n)。

必要假设

未限定随机化或三数取中等枢轴策略。

C++11 / 算法语义

普通快速排序平均O(n log n)，最坏可退化为O(n²)，输入和枢轴选择会影响。

命题预期

判断为假。

推导结论

训练答案F。

09｜2025-03-L5-TF-07

学生训练答案：T

原卷事实

题面讨论标准归并排序的运行时间。

必要假设

按每层线性合并的标准实现。

C++11 / 算法语义

递归深度为O(log n)，每层总合并工作O(n)，输入初始有序性不改变该界。

命题预期

判断为真。

推导结论

训练答案T。

10｜2025-06-L5-TF-04

学生训练答案：F

原卷事实

每个非基例mergeSort调用在两次递归后输出HERE并调用merge。

必要假设

调用入口覆盖至少两个元素。

C++11 / 算法语义

merge会在递归树的每个内部结点调用，不止一次，HERE也输出多次。

命题预期

判断为假。

推导结论

学生训练答案F。

11｜2025-09-L5-TF-07

学生训练答案：F

原卷事实

题目对两种排序都断言稳定。

必要假设

按教材标准实现。

C++11 / 算法语义

归并排序可稳定，普通快速排序不稳定。

命题预期

判断为F。

推导结论

训练答案F。

12｜2025-12-L5-TF-06

学生训练答案：T

原卷事实

题面描述三数取中枢轴。

必要假设

相对固定取首元素的普通输入分布讨论概率。

C++11 / 算法语义

三数取中可减少极端枢轴出现机会，但不消除最坏情况。

命题预期

“可降低概率”成立。

推导结论

训练答案T。

13｜2025-12-L5-SC-09

学生训练答案：C

原卷事实

代码为标准数组归并排序。

必要假设

temp数组长度足够。

C++11 / 算法语义

平均和最坏时间均O(n log n)，额外空间O(n)。

命题预期

C错误。

推导结论

训练答案C。

14｜2025-12-L5-SC-10

学生训练答案：C

原卷事实

代码以首元素为枢轴。

必要假设

输入可使每次划分极不平衡。

C++11 / 算法语义

递推可退化为T(n)=T(n-1)+O(n)，故O(n²)。

命题预期

选择C。

推导结论

训练答案C。

15｜2026-03-L5-SC-12

学生训练答案：B

原卷事实

两个输入数组均升序。

必要假设

索引有效且result初始为空。

C++11 / 算法语义

应先放两当前元素中较小者；相等时取A也保持有序与稳定。

命题预期

选择B。

推导结论

训练答案B。

16｜2026-03-L5-SC-13

学生训练答案：C

原卷事实

数组已升序且每次取首元素为枢轴。

必要假设

比较与交换按给定实现。

C++11 / 算法语义

每次划分极不平衡，递推为T(n)=T(n-1)+O(n)。

命题预期

选择C。

推导结论

训练答案C。

17｜2026-06-L5-TF-04

学生训练答案：T

原卷事实

代码复制两段并以双指针写回。

必要假设

L、R分别已排序且边界合法。

C++11 / 算法语义

主循环选较小元素，随后复制剩余元素。

命题预期

判断为T。

推导结论

训练答案T。

18｜2026-06-L5-TF-05

学生训练答案：T

原卷事实

题目描述分治法的一般步骤。

必要假设

子问题可递归求解。

C++11 / 算法语义

分解、解决、合并是分治的基本结构。

命题预期

判断为T。

推导结论

训练答案T。

19｜2026-06-L5-SC-07

学生训练答案：C

原卷事实

代码把指数规模减半。

必要假设

n为非负整数且乘法结果可表示。

C++11 / 算法语义

xⁿ由x^(n/2)平方并按奇偶补乘x。

命题预期

选项C。

推导结论

训练答案C。

20｜2026-06-L5-TF-10

学生训练答案：F

原卷事实

前半句给出平均复杂度，后半句交换了典型稳定性。

必要假设

按常见实现。

C++11 / 算法语义

归并排序通常稳定，快速排序通常不稳定，因此整句错误。

命题预期

判断为F。

推导结论

训练答案F。

21｜2026-06-L5-SC-11

学生训练答案：B

原卷事实

双指针相遇于基准最终位置i。

必要假设

区间与下标有效。

C++11 / 算法语义

将首元素基准与arr[i]交换。

命题预期

选项B。

推导结论

训练答案B。

22｜2026-06-L5-SC-12

学生训练答案：B

原卷事实

题目询问归并排序核心过程。

必要假设

按标准归并排序。

C++11 / 算法语义

递归排序两半并合并有序部分。

命题预期

选项B。

推导结论

训练答案B。

23｜2025-03-L5-SC-10

学生训练答案：B

原卷事实

pivot取arr[high]，i维护小于pivot区间的末端。

必要假设

采用Lomuto划分并按从小到大排序。

C++11 / 算法语义

遇到arr[j] < pivot时先递增i，再交换arr[i]与arr[j]。

命题预期

选择B。

推导结论

训练答案B。

24｜2025-03-L5-SC-14

学生训练答案：D

原卷事实

目标是在闭区间[low,high]求最大值。

必要假设

输入区间非空。

C++11 / 算法语义

正确分治需以low==high为基例，把区间拆为[low,mid]和[mid+1,high]，再取两侧最大值。

命题预期

只有D同时满足基例、完整分割和max合并。

推导结论

训练答案D。

25｜2025-06-L5-SC-14

学生训练答案：D

原卷事实

官方A把i说成大于基准值边界，官方B使用绝对化“避免”，官方答案D。

必要假设

学生版只收窄A、B措辞，不改代码、C、D或答案。

C++11 / 算法语义

源码中i是<=pivot区间右边界；随机枢轴只降低而非消除最坏O(n²)概率；快速排序平均O(n log n)且通常不稳定。

命题预期

命题预期D，原卷A也错误造成多解。

推导结论

用户批准学生版把A改为正确边界描述、B改为概率表述，使D成为唯一错误；学生答案D。

26｜2025-09-L5-SC-12

学生训练答案：D

原卷事实

左右子数组均是闭区间。

必要假设

下标范围合法。

C++11 / 算法语义

主循环后需复制右区间剩余元素，条件为j<=right。

命题预期

选择D。

推导结论

训练答案D。

27｜2025-09-L5-SC-14

学生训练答案：B

原卷事实

代码递归求左、右和跨中点三类最大和。

必要假设

数组非空，区间合法。

C++11 / 算法语义

递推式T(n)=2T(n/2)+O(n)，复杂度O(n log n)，属分治递归而非贪心。

命题预期

错误项B。

推导结论

训练答案B。

28｜2026-03-L5-TF-05

学生训练答案：F

原卷事实

代码只比较两个区间并累加cnt。

必要假设

即使左右半段预先有序，该函数也未实际归并；更未递归统计左右内部逆序对。

C++11 / 算法语义

它不能单独正确统计整个[l,r]逆序对总数。

命题预期

判断为假。

推导结论

训练答案F。

29｜2026-03-L5-SC-11

学生训练答案：B

原卷事实

每层递归求左右子问题并线性扫描跨中点和。

必要假设

数组区间非空且求和不溢出int。

C++11 / 算法语义

T(n)=2T(n/2)+O(n)=O(n log n)。

命题预期

选择B。

推导结论

训练答案B。

30｜2026-06-L5-SC-13

学生训练答案：A

原卷事实

每个非叶递归结点调用一次mergeArray。

必要假设

n>=1。

C++11 / 算法语义

二叉递归树有n个叶结点、n-1个内部结点。

命题预期

选项A。

推导结论

训练答案A。

31｜2025-09-L5-SC-11

学生训练答案：D

原卷事实

代码用首元素作pivot并先从右扫描。

必要假设

按给定划分逻辑判断。

C++11 / 算法语义

若先从左扫，如[0,1]可将pivot错换到右侧并导致排序错误，因此顺序不可直接交换。

命题预期

错误项D。

推导结论

训练答案D。