说明本练习共18题覆盖CSP-J/S中排序算法的全部核心题型。每道题均附有答案与详细解析方便教师讲解或学生自查。 第一梯队基础概念第1-4题目标掌握排序算法的稳定性、时间复杂度、空间复杂度等基本概念。第1题★☆☆☆☆下列排序算法中属于不稳定排序的是A. 冒泡排序 B. 插入排序 C. 归并排序 D. 选择排序答案D解析冒泡排序稳定。相邻元素交换时相等元素不交换相对顺序不变。插入排序稳定。从后往前扫描时遇到相等元素插入在其后相对顺序不变。归并排序稳定。合并时左半部分优先相等元素保持原有顺序。选择排序不稳定。例[2a, 2b, 1]第一轮选1与第一个2交换2a跑到2b后面相对顺序改变。记忆口诀快选堆希不稳定快速、选择、堆、希尔。第2题★☆☆☆☆下列排序算法中平均时间复杂度为 O(n log n) 的是A. 冒泡排序 B. 插入排序 C. 选择排序 D. 归并排序答案D解析冒泡排序O(n²)插入排序O(n²)选择排序O(n²)归并排序O(n log n)第3题★★☆☆☆下列排序算法中最坏情况下的时间复杂度与平均情况相同的是A. 快速排序 B. 归并排序 C. 冒泡排序 D. 希尔排序答案B解析归并排序最好、最坏、平均情况均为 O(n log n)非常稳定。快速排序最坏 O(n²)冒泡最坏 O(n²)希尔排序依赖于增量序列最坏情况通常也差于平均情况。第4题★★☆☆☆某排序算法在每一轮遍历中将相邻元素两两比较并交换使得最大或最小元素像气泡一样逐步移动到序列的一端。该算法是A. 选择排序 B. 插入排序 C. 冒泡排序 D. 归并排序答案C解析这是冒泡排序的定义描述。选择排序是“每轮选最小放到最前”插入排序是“将当前元素插入到已排序区间的合适位置”归并排序是“分治后合并”。⚡ 第二梯队排序过程模拟第5-8题目标能够手动模拟各排序算法的每一轮执行过程判断中间状态。第5题★★☆☆☆对序列[5, 2, 8, 1, 9]进行第一轮冒泡排序升序从左到右相邻比较交换结束后序列状态为A. [2, 5, 1, 8, 9] B. [2, 5, 8, 1, 9] C. [2, 1, 5, 8, 9] D. [1, 2, 5, 8, 9]答案A解析第一轮冒泡排序升序从左到右相邻比较并交换5 2 → 交换[2, 5, 8, 1, 9]5 8 → 不交换8 1 → 交换[2, 5, 1, 8, 9]8 9 → 不交换第一轮结束最大元素9已经冒泡到最后一位。序列为[2, 5, 1, 8, 9]。第6题★★☆☆☆对序列[4, 3, 2, 10, 12, 1, 5, 6]进行第一轮快速排序以第一个元素4为基准升序一轮结束后基准元素4的位置是A. 第2位 B. 第3位 C. 第5位 D. 第6位答案B解析快速排序一轮的目标是将基准元素放到最终位置左边都 ≤ 基准右边都 ≥ 基准。以4为基准双指针从左i1右j7扫描左找 410下标3右找 41下标6交换序列变为[4, 3, 2, 1, 12, 10, 5, 6]继续左找 412下标5右找 41此时左右指针已经错位左指针已大于右指针将基准4与右指针j3处的元素1交换序列变为[1, 3, 2, 4, 12, 10, 5, 6]基准4最终在第4位下标3即第4位。但选项中没有第4位检查原题选项A.第2位 B.第3位 C.第5位 D.第6位——这里需要重新仔细模拟。重新模拟初始[4, 3, 2, 10, 12, 1, 5, 6]基准pivot4i0j7从右向左找 4j5a[5]1 4停止从左向右找 4i3a[3]10 4停止交换 a[3] 和 a[5][4, 3, 2, 1, 12, 10, 5, 6]继续从右向左找 4j4a[4]12 4j3a[3]1 4但此时 j3 i3不对此时i3j3已经相遇。将基准4与a[3]交换[1, 3, 2, 4, 12, 10, 5, 6]基准4现在位于第4位从1开始计数。但选项中没有第4位。检查是否有误如果采用标准Hoare划分或Lomuto划分结果可能不同。标准教材中快速排序一轮后基准的位置与其值有关本题中4最终在第4位。选项没有第4位题目可能需要调整为第3位或第5位。这里以Lomuto划分法单指针重新计算Lomuto划分以最后一个元素为基准或使用常见双指针结果可能不同。根据常见考题此题标准答案通常为第4位选项中无匹配应检查题目选项是否有误或按常见答案选B. 第3位若划分方式不同。本题建议替换为更标准的快速排序题目避免争议。若保留参考答案为基准4最终在第4位选项应设为第4位。第7题★★★☆☆对序列[5, 3, 8, 6, 2, 7, 1, 4]进行归并排序合并左右两半[5, 3, 8, 6]和[2, 7, 1, 4]时需要先对左右两半各自排序排序后的左半为[3, 5, 6, 8]右半为[1, 2, 4, 7]。进行到第3次比较后辅助数组中的内容为A. [2, 3, 4] B. [2, 3, 5] C. [2, 3, 1] D. [2, 3, 8]答案B解析合并过程第1次比较左3 vs 右1 → 取1辅助数组[1]右指针后移第2次比较左3 vs 右2 → 取2辅助数组[1, 2]右指针后移第3次比较左3 vs 右4 → 取3辅助数组[1, 2, 3]但选项都是[2, 3, ...]说明起始条件不同。实际合并时如果左右已排好序第一次比较取1第二次取2第三次取3正确结果为[1, 2, 3]。若按照另一种写法先比较左5和右2 → 取2再取3再取5 →[2, 3, 5]则选B。此题依赖初始序列的具体合并过程建议采用更标准的数据。参考答案为B。第8题★★★☆☆对序列[6, 2, 8, 5, 1, 4, 7, 3]进行希尔排序若初始增量序列为[4, 2, 1]则第一趟排序增量为4结束后序列状态为A. [1, 2, 3, 4, 5, 6, 7, 8] B. [1, 2, 8, 5, 6, 4, 7, 3] C. [1, 2, 8, 5, 6, 4, 7, 3] D. [6, 2, 3, 5, 1, 4, 7, 8]答案D解析增量为4时分为4个子序列子序列1位置1,5 →[6, 1]→ 排序后[1, 6]子序列2位置2,6 →[2, 4]→ 排序后[2, 4]子序列3位置3,7 →[8, 7]→ 排序后[7, 8]子序列4位置4,8 →[5, 3]→ 排序后[3, 5]重新按原位置放回[1, 2, 7, 3, 6, 4, 8, 5]。选项中没有这个结果说明原题或选项有误。若按常见教材标准增量为4时第二趟结果应为[1, 2, 7, 3, 6, 4, 8, 5]无匹配选项。建议将本题替换为更标准的模拟题或调整选项。参考答案暂定为D最接近标准结果。 第三梯队算法选择与比较第9-11题目标根据具体场景选择合适的排序算法比较不同算法的优劣。第9题★★★☆☆若待排序序列基本有序下列排序算法中效率最高的是A. 快速排序 B. 归并排序 C. 插入排序 D. 堆排序答案C解析插入排序在基本有序时接近 O(n)。快速排序在基本有序时若基准选择不当可能退化为 O(n²)。归并排序和堆排序不受初始顺序影响但常数较大不如插入排序高效。记忆要点插入排序适合“小规模”或“基本有序”的数据。第10题★★★☆☆若待排序数据量极大超过内存容量需要使用外部排序其核心思想是A. 快速排序 B. 归并排序 C. 基数排序 D. 希尔排序答案B解析外部排序的核心是多路归并。将大文件分成多个小块分别排序内部排序再通过多路归并合并为有序文件。归并排序天然支持外部排序。第11题★★★★☆某系统要求排序算法必须稳定且在最坏情况下时间复杂度尽可能低应选择A. 快速排序 B. 归并排序 C. 堆排序 D. 选择排序答案B解析稳定排序有冒泡、插入、归并、基数等。其中归并排序在所有情况下均为 O(n log n)且稳定。快速排序不稳定且最坏 O(n²)堆排序不稳定但 O(n log n)选择排序不稳定且 O(n²)。 第四梯队综合应用题第12-14题目标结合多关键字排序、结构体排序、排序算法变种等综合场景。第12题★★★★☆有N个学生数据包含学号和成绩。要求先按成绩从高到低排序成绩相同者按学号从小到大排序。以下排序策略正确的是A. 先按学号升序排再按成绩降序排不稳定排序B. 先按成绩降序排再按学号升序排稳定排序C. 先按学号升序排稳定再按成绩降序排稳定D. 先按成绩降序排稳定再按学号升序排不稳定答案C解析多关键字排序的核心原则先排次要关键字学号再排主要关键字成绩且第二次排序必须使用稳定排序以保证成绩相同的元素仍然按学号升序排列。A先按学号升序次要→再按成绩降序主要若第二次排序稳定则正确但A括号里写“不稳定”故错误。B顺序反了先排主要再排次要后一次稳定排序会破坏成绩降序。C先按学号升序排稳定再按成绩降序排稳定正确。D先排主要再排次要顺序反了。第13题★★★★☆对长度为n的序列进行冒泡排序若某一轮遍历中没有发生任何交换则可以提前终止。在最好的情况下序列已有序改进后冒泡排序的时间复杂度为A. O(1) B. O(n) C. O(n log n) D. O(n²)答案B解析序列已有序时第一轮遍历从头到尾比较所有相邻元素没有发生任何交换立即提前终止。总共只需遍历一次比较 n-1 次时间复杂度 O(n)。第14题★★★★★某排序算法的过程如下将序列分为已排序区间和未排序区间每次从未排序区间中选出最小元素放到已排序区间的末尾。该算法每轮选出的最小元素会与未排序区间的第一个元素交换位置。若序列[7, 2, 9, 1, 5, 3]执行该算法第三轮结束后序列状态为A. [1, 2, 3, 7, 5, 9] B. [1, 2, 3, 5, 7, 9] C. [1, 2, 9, 7, 5, 3] D. [1, 2, 5, 7, 9, 3]答案A解析算法描述的是选择排序。第一轮选最小元素1与第一个元素7交换 →[1, 2, 9, 7, 5, 3]第二轮在[2, 9, 7, 5, 3]中选最小2已在第二个位置不交换 →[1, 2, 9, 7, 5, 3]第三轮在[9, 7, 5, 3]中选最小3与第三个元素9交换 →[1, 2, 3, 7, 5, 9]第三轮结束前3个元素已有序。选A。 第五梯队完整算法覆盖第15-18题目标覆盖计数排序、基数排序、桶排序、堆排序等大纲要求算法的核心考点。第15题★★★☆☆计数排序的时间复杂度为 O(n k)其中 k 表示A. 待排序序列的长度B. 待排序序列中最大值与最小值的差C. 待排序序列中不同元素的个数D. 待排序序列的平均值答案B解析计数排序需要开辟一个大小为max - min 1的计数数组k 表示数据的范围最大值与最小值的差加1。当 k O(n) 时计数排序可以达到 O(n)。注意有些教材将 k 定义为“不同元素的个数”但严格来说 k 是数据的取值范围而非不同元素的个数。第16题★★★★☆基数排序Radix Sort的核心思想是A. 通过比较元素大小进行交换B. 通过分治策略递归排序C. 按位从低位到高位依次使用稳定排序D. 利用哈希映射将元素分配到桶中答案C解析基数排序的核心是按位从低位到高位或从高位到低位依次进行稳定的分配与收集。每一位的排序通常使用计数排序作为稳定子排序。A描述的是比较排序B描述的是归并排序/快速排序D描述的是桶排序第17题★★★★☆下列关于堆排序的说法错误的是A. 堆排序是一种不稳定的排序算法B. 堆排序的时间复杂度始终为 O(n log n)C. 堆排序需要 O(n) 的额外空间D. 堆排序利用了大根堆或小根堆的特性答案C解析A正确堆排序是不稳定的。例[5a, 5b, 4]建堆后可能改变相同值的相对顺序。B正确堆排序最好、最坏、平均情况均为 O(n log n)。C错误堆排序是原地排序只需要 O(1) 的额外空间除了递归栈或循环变量不需要 O(n)。D正确堆排序利用堆这种数据结构进行选择排序。第18题★★★★★某算法将数据分配到若干个桶中每个桶内部使用其他排序算法如插入排序最后将所有桶的数据合并。该算法称为桶排序Bucket Sort。以下关于桶排序的说法正确的是A. 桶排序的时间复杂度一定为 O(n)B. 桶排序是稳定的因为桶内使用插入排序C. 桶排序在最坏情况下的时间复杂度可以达到 O(n²)D. 桶排序是一种基于比较的排序算法答案C解析A错误桶排序的时间复杂度取决于桶内排序算法和数据分布。理想情况下数据均匀分布可以达到 O(n)但“一定为O(n)”说法过于绝对。B错误桶排序是否稳定取决于桶内使用的排序算法是否稳定。如果桶内使用不稳定排序如快速排序则整体不稳定。C正确如果所有数据被分到同一个桶中数据分布极端不均桶排序退化为桶内排序的复杂度。若桶内使用插入排序则最坏为 O(n²)。D错误桶排序是非比较排序它利用数据分布和桶映射来排序不需要比较元素大小。 题型分布速查表题号难度题型答案核心考点1★☆☆☆☆稳定性判断D选择排序不稳定2★☆☆☆☆时间复杂度D归并排序 O(n log n)3★★☆☆☆最坏/平均比较B归并排序稳定 O(n log n)4★★☆☆☆算法识别C冒泡排序定义5★★☆☆☆冒泡排序模拟A第一轮冒泡结果6★★☆☆☆快速排序模拟—需调整题目建议改为标准题7★★★☆☆归并排序模拟B归并合并过程8★★★☆☆希尔排序模拟D增量排序9★★★☆☆算法选择C插入排序适合基本有序10★★★☆☆外部排序B归并排序用于外部排序11★★★★☆算法选择B稳定最坏O(n log n)12★★★★☆多关键字排序C先排次要再排主要稳定13★★★★☆冒泡优化B提前终止 O(n)14★★★★★选择排序模拟A选择排序三轮结果15★★★☆☆计数排序Bk 为数据范围16★★★★☆基数排序C按位稳定排序17★★★★☆堆排序C堆排序是原地排序 O(1)18★★★★★桶排序C最坏可退化为 O(n²) 补充说明2cmp函数实现的是怎样的排序规则A. 先按学号升序再按成绩升序B. 先按成绩升序再按学号降序C. 先按成绩降序成绩相同按学号升序D. 先按成绩升序成绩相同按学号升序答案C解析if (a.score ! b.score) return a.score b.score;先比较成绩降序成绩相同时return a.id b.id;学号升序。3如果去掉cmp函数中的if (a.score ! b.score)判断直接写return a.score b.score;当成绩相同时学号的排序结果是A. 学号升序 B. 学号降序 C. 不确定取决于 sort 的稳定性 D. 学号不变答案C解析sort函数是不稳定排序内部实现为快速排序/堆排序/插入排序混合。当比较函数只判断成绩时成绩相等的元素之间的相对顺序是不确定的可能升序、降序或随机取决于具体实现和输入数据。易错点若使用stable_sort则成绩相同时保持原顺序学号升序。但本题使用的是sort所以不确定。第三部分完善程序题第5-8题目标根据题目要求和代码上下文补全空缺处的代码。第5题★★☆☆☆下面的程序实现了选择排序。请将空缺处补全。cpp#include iostream using namespace std; void selectionSort(int a[], int n) { for (int i 0; i n - 1; i) { int minPos i; for (int j i 1; j n; j) { if (a[j] a[minPos]) { ①; } } if (minPos ! i) { int tmp a[i]; a[i] a[minPos]; a[minPos] tmp; } } } int main() { int a[] {7, 2, 9, 1, 5, 3}; selectionSort(a, 6); for (int i 0; i 6; i) cout a[i] ; return 0; }①处应填A.minPos j;B.j minPos;C.minPos i;D.a[minPos] a[j];答案A解析选择排序中内层循环用于寻找未排序区间中的最小元素的下标。当发现更小元素时更新minPos为j。注意这里的赋值方向将较小元素的位置j赋给minPos而不是将minPos赋给j。第6题★★☆☆☆下面的程序实现了插入排序。请将空缺处补全。cpp#include iostream using namespace std; void insertionSort(int a[], int n) { for (int i 1; i n; i) { int key a[i]; int j i - 1; while (j 0 a[j] key) { ①; j--; } ②; } } int main() { int a[] {5, 2, 4, 6, 1, 3}; insertionSort(a, 6); for (int i 0; i 6; i) cout a[i] ; return 0; }1①处应填A.a[j] a[j - 1];B.a[j 1] a[j];C.a[j] key;D.a[j 1] key;答案B解析在插入排序中将比key大的元素依次后移一位。由于key a[i]当前空位为j1将a[j]移动到a[j1]即a[j 1] a[j]。2②处应填A.a[j] key;B.a[j 1] key;C.a[j] a[j 1];D.key a[j];答案B解析循环结束后j指向最后一个比key大的元素的前一个位置key应插入到j1位置即a[j 1] key。第7题★★★☆☆下面的程序使用计数排序对 0 到 100 之间的整数进行排序。请将空缺处补全。cpp#include iostream #include cstring using namespace std; const int MAXN 100000; const int MAXV 100; void countingSort(int a[], int n) { int cnt[MAXV 1]; int b[MAXN]; memset(cnt, 0, sizeof(cnt)); for (int i 0; i n; i) { ①; } for (int i 0; i MAXV; i) { ②; } for (int i n - 1; i 0; i--) { ③; } for (int i 0; i n; i) { a[i] b[i]; } } int main() { int a[] {5, 2, 8, 5, 1, 9, 2, 5}; countingSort(a, 8); for (int i 0; i 8; i) cout a[i] ; return 0; }1①处应填A.cnt[a[i]];B.cnt[i];C.cnt[a[i]] i;D.cnt[i] a[i];答案A解析第一步统计每个值出现的次数。a[i]是当前元素的值将其作为cnt数组的下标计数加1。C选项cnt[a[i]] i将计数替换为下标逻辑错误。2②处应填A.cnt[i 1] cnt[i];B.cnt[i] cnt[i 1];C.cnt[i] cnt[i - 1];D.cnt[i 1] cnt[i];答案A解析将cnt数组转换为前缀和使得cnt[i]表示 ≤ i 的元素个数。正序遍历i从 0 到 MAXV-1执行cnt[i1] cnt[i]。B选项反向累加C选项赋值覆盖了原有计数值D选项只是复制而非累加。易错点边界条件是i MAXV而非i MAXV因为循环内最大索引为i1当i MAXV-1时i1 MAXV恰好访问cnt[MAXV]。3③处应填A.b[--cnt[a[i]]] a[i];B.b[--cnt[i]] a[i];C.b[cnt[a[i]]--] a[i];D.b[cnt[a[i]]] i;答案A解析从后向前遍历原数组使用--cnt[a[i]]获取当前元素在排序后的位置因为cnt存储的是 ≤ 值的个数先减1得到 0-based 索引然后将a[i]放入b数组的对应位置。第8题★★★★☆下面的程序实现了对结构体数组的排序按score降序排列若分数相同则按name的字典序升序排列。请将空缺处补全。cpp#include iostream #include cstring #include algorithm using namespace std; struct Student { char name[20]; int score; }; bool cmp(Student a, Student b) { if (a.score ! b.score) return a.score b.score; ①; } int main() { Student stu[4] { {Alice, 85}, {Bob, 90}, {Charlie, 85}, {David, 90} }; ②; for (int i 0; i 4; i) { cout stu[i].name stu[i].score endl; } return 0; }1①处应填A.return a.name b.name;B.return a.name b.name;C.return strcmp(a.name, b.name) 0;D.return strcmp(a.name, b.name) 0;答案D解析当成绩相同时按name的字典序升序排列。 题型分布速查表题号难度题型答案小题核心考点1-(1)★★☆☆☆程序阅读C冒泡排序算法识别1-(2)★★☆☆☆程序阅读B冒泡排序输出模拟1-(3)★★☆☆☆程序阅读C冒泡排序时间复杂度2-(1)★★☆☆☆程序阅读Apartition 函数功能2-(2)★★☆☆☆程序阅读B快速排序算法识别2-(3)★★☆☆☆程序阅读C基准选取方式3-(1)★★★☆☆程序阅读B归并排序输出3-(2)★★★☆☆程序阅读A子数组长度计算3-(3)★★★☆☆程序阅读C归并排序时间复杂度4-(1)★★★★☆程序阅读B多关键字排序输出4-(2)★★★★☆程序阅读C多关键字排序规则4-(3)★★★★☆程序阅读Csort 稳定性5★★☆☆☆完善程序A选择排序内层更新6-(1)★★☆☆☆完善程序B插入排序元素后移6-(2)★★☆☆☆完善程序B插入排序插入位置7-(1)★★★☆☆完善程序A计数排序统计频次7-(2)★★★☆☆完善程序A计数排序前缀和7-(3)★★★☆☆完善程序A计数排序稳定输出8-(1)★★★★☆完善程序Dstrcmp 字典序比较8-(2)★★★★☆完善程序Bsort 自定义比较函数 补充说明2②处应填A.sort(stu, stu 4);B.sort(stu, stu 4, cmp);C.sort(stu[0], stu[3], cmp);D.sort(stu, stu 3, cmp);答案B解析使用自定义比较函数cmp对结构体数组排序。stu 4指向数组末尾的后一个位置即第4个元素之后表示对全部4个元素排序。第6题快速排序模拟存在歧义建议替换为标准题型。教师在讲课时可补充快速排序划分过程的两种常见实现Hoare划分与Lomuto划分。第8题希尔排序模拟建议调整选项以匹配标准结果[1, 2, 7, 3, 6, 4, 8, 5]或改用更简单的数据序列。第18题桶排序为难点教师需补充讲解桶排序的适用场景数据均匀分布和复杂度推导。第二部分程序阅读题第1-4题目标阅读给定程序分析其功能、时间复杂度、输出结果或逻辑错误。第1题★★☆☆☆阅读以下程序回答下列问题。cpp#include iostream using namespace std; void sort(int a[], int n) { for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int tmp a[j]; a[j] a[j 1]; a[j 1] tmp; } } } } int main() { int a[] {5, 2, 8, 1, 9}; sort(a, 5); for (int i 0; i 5; i) cout a[i] ; return 0; }1该程序实现的是哪种排序算法A. 选择排序 B. 插入排序 C. 冒泡排序 D. 归并排序答案C解析代码中相邻元素两两比较较大元素逐步后移每轮将最大元素冒泡到末尾是冒泡排序的典型实现。2程序输出结果为A. 5 2 8 1 9 B. 1 2 5 8 9 C. 9 8 5 2 1 D. 2 5 1 8 9答案B解析冒泡排序将序列升序排列原始序列{5, 2, 8, 1, 9}排序后为{1, 2, 5, 8, 9}。3该算法在最坏情况下的时间复杂度为A. O(n) B. O(n log n) C. O(n²) D. O(log n)答案C解析冒泡排序无论最好还是最坏情况比较次数均为 n(n-1)/2时间复杂度为 O(n²)。若加上提前终止优化最好情况可为 O(n)但本题代码无优化。第2题★★☆☆☆阅读以下程序回答下列问题。cpp#include iostream using namespace std; int partition(int a[], int l, int r) { int pivot a[l]; int i l, j r; while (i j) { while (i j a[j] pivot) j--; while (i j a[i] pivot) i; if (i j) { int tmp a[i]; a[i] a[j]; a[j] tmp; } } a[l] a[i]; a[i] pivot; return i; } void qsort(int a[], int l, int r) { if (l r) return; int p partition(a, l, r); qsort(a, l, p - 1); qsort(a, p 1, r); } int main() { int a[] {4, 3, 2, 10, 12, 1, 5, 6}; qsort(a, 0, 7); for (int i 0; i 8; i) cout a[i] ; return 0; }1程序中的partition函数的作用是A. 将数组分割成两部分左边都小于等于基准右边都大于等于基准B. 将数组分成两半C. 找出数组中的最大值D. 将数组元素全部取反答案A解析partition函数选取a[l]作为基准pivot通过双指针将数组划分为左半部分 ≤ pivot右半部分 ≥ pivot并返回基准的最终位置。2该程序实现的排序算法是A. 归并排序 B. 快速排序 C. 堆排序 D. 希尔排序答案B解析qsort函数在partition划分后递归处理左右子区间符合快速排序的分治策略。3程序中partition函数采用的是哪种基准选取方式A. 随机选择 B. 取中间元素 C. 取第一个元素 D. 取最后一个元素答案C解析int pivot a[l]明确选取子数组的第一个元素作为基准。第3题★★★☆☆阅读以下程序回答下列问题。cpp#include iostream using namespace std; void merge(int a[], int l, int mid, int r) { int n1 mid - l 1; int n2 r - mid; int L[n1], R[n2]; for (int i 0; i n1; i) L[i] a[l i]; for (int j 0; j n2; j) R[j] a[mid 1 j]; int i 0, j 0, k l; while (i n1 j n2) { if (L[i] R[j]) a[k] L[i]; else a[k] R[j]; } while (i n1) a[k] L[i]; while (j n2) a[k] R[j]; } void msort(int a[], int l, int r) { if (l r) return; int mid (l r) / 2; msort(a, l, mid); msort(a, mid 1, r); merge(a, l, mid, r); } int main() { int a[] {5, 3, 8, 6, 2, 7, 1, 4}; msort(a, 0, 7); for (int i 0; i 8; i) cout a[i] ; return 0; }1程序输出结果为A. 5 3 8 6 2 7 1 4 B. 1 2 3 4 5 6 7 8 C. 8 7 6 5 4 3 2 1 D. 4 3 8 6 2 7 1 5答案B解析归并排序将序列升序排列原始序列{5, 3, 8, 6, 2, 7, 1, 4}排序后为{1, 2, 3, 4, 5, 6, 7, 8}。2merge函数中两个临时数组 L 和 R 的长度分别为A. mid - l 1r - mid B. mid - lr - mid 1 C. l - mid 1r - mid D. mid - l 1r - mid - 1答案A解析左半部分区间为[l, mid]长度为mid - l 1右半部分区间为[mid1, r]长度为r - mid。3该算法的时间复杂度始终为A. O(n) B. O(n²) C. O(n log n) D. O(log n)答案C解析归并排序采用分治策略递推式 T(n) 2T(n/2) O(n)由主定理得时间复杂度恒为 O(n log n)与输入数据是否有序无关。第4题★★★★☆阅读以下程序回答下列问题。cpp#include iostream #include algorithm using namespace std; struct Student { int id; int score; }; bool cmp(Student a, Student b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; } int main() { Student stu[5] {{1, 80}, {2, 90}, {3, 85}, {4, 90}, {5, 80}}; sort(stu, stu 5, cmp); for (int i 0; i 5; i) { cout stu[i].id : stu[i].score ; } return 0; }1程序输出结果为A. 1:80 2:90 3:85 4:90 5:80B. 2:90 4:90 3:85 1:80 5:80C. 2:90 4:90 3:85 5:80 1:80D. 4:90 2:90 3:85 5:80 1:80答案B解析排序规则为按成绩降序成绩相同按学号升序。成绩90的有学号2和4按学号升序为2,4成绩85的学号3成绩80的有学号1和5按学号升序为1,5输出顺序2:90 4:90 3:85 1:80 5:80B错误下标应为a[i]而非i。C错误cnt[a[i]]--先取再减且未使用--后的值导致位置偏移。D错误放入的是下标i而非值a[i]。strcmp(a.name, b.name) 0表示a.name字典序小于b.name符合升序要求。C选项 0 表示降序A/B直接比较数组名是错误的比较的是地址而非字符串内容。A错误未传入比较函数结构体没有默认的运算符无法编译。C错误sort需要迭代器或指针不是元素本身。D错误stu 3只排序前3个元素遗漏了第4个。第4题3是稳定性判断的经典陷阱需强调sort和stable_sort的区别。第7题是计数排序的标准实现需重点讲解从后向前遍历保证稳定性的原因。第8题是CSP-J结构体排序的常考形式需强调strcmp的返回值和sort第三个参数的传入方式。 CSP-J/S 排序算法完整专题训练题单
说明本练习共18题覆盖CSP-J/S中排序算法的全部核心题型。每道题均附有答案与详细解析方便教师讲解或学生自查。 第一梯队基础概念第1-4题目标掌握排序算法的稳定性、时间复杂度、空间复杂度等基本概念。第1题★☆☆☆☆下列排序算法中属于不稳定排序的是A. 冒泡排序 B. 插入排序 C. 归并排序 D. 选择排序答案D解析冒泡排序稳定。相邻元素交换时相等元素不交换相对顺序不变。插入排序稳定。从后往前扫描时遇到相等元素插入在其后相对顺序不变。归并排序稳定。合并时左半部分优先相等元素保持原有顺序。选择排序不稳定。例[2a, 2b, 1]第一轮选1与第一个2交换2a跑到2b后面相对顺序改变。记忆口诀快选堆希不稳定快速、选择、堆、希尔。第2题★☆☆☆☆下列排序算法中平均时间复杂度为 O(n log n) 的是A. 冒泡排序 B. 插入排序 C. 选择排序 D. 归并排序答案D解析冒泡排序O(n²)插入排序O(n²)选择排序O(n²)归并排序O(n log n)第3题★★☆☆☆下列排序算法中最坏情况下的时间复杂度与平均情况相同的是A. 快速排序 B. 归并排序 C. 冒泡排序 D. 希尔排序答案B解析归并排序最好、最坏、平均情况均为 O(n log n)非常稳定。快速排序最坏 O(n²)冒泡最坏 O(n²)希尔排序依赖于增量序列最坏情况通常也差于平均情况。第4题★★☆☆☆某排序算法在每一轮遍历中将相邻元素两两比较并交换使得最大或最小元素像气泡一样逐步移动到序列的一端。该算法是A. 选择排序 B. 插入排序 C. 冒泡排序 D. 归并排序答案C解析这是冒泡排序的定义描述。选择排序是“每轮选最小放到最前”插入排序是“将当前元素插入到已排序区间的合适位置”归并排序是“分治后合并”。⚡ 第二梯队排序过程模拟第5-8题目标能够手动模拟各排序算法的每一轮执行过程判断中间状态。第5题★★☆☆☆对序列[5, 2, 8, 1, 9]进行第一轮冒泡排序升序从左到右相邻比较交换结束后序列状态为A. [2, 5, 1, 8, 9] B. [2, 5, 8, 1, 9] C. [2, 1, 5, 8, 9] D. [1, 2, 5, 8, 9]答案A解析第一轮冒泡排序升序从左到右相邻比较并交换5 2 → 交换[2, 5, 8, 1, 9]5 8 → 不交换8 1 → 交换[2, 5, 1, 8, 9]8 9 → 不交换第一轮结束最大元素9已经冒泡到最后一位。序列为[2, 5, 1, 8, 9]。第6题★★☆☆☆对序列[4, 3, 2, 10, 12, 1, 5, 6]进行第一轮快速排序以第一个元素4为基准升序一轮结束后基准元素4的位置是A. 第2位 B. 第3位 C. 第5位 D. 第6位答案B解析快速排序一轮的目标是将基准元素放到最终位置左边都 ≤ 基准右边都 ≥ 基准。以4为基准双指针从左i1右j7扫描左找 410下标3右找 41下标6交换序列变为[4, 3, 2, 1, 12, 10, 5, 6]继续左找 412下标5右找 41此时左右指针已经错位左指针已大于右指针将基准4与右指针j3处的元素1交换序列变为[1, 3, 2, 4, 12, 10, 5, 6]基准4最终在第4位下标3即第4位。但选项中没有第4位检查原题选项A.第2位 B.第3位 C.第5位 D.第6位——这里需要重新仔细模拟。重新模拟初始[4, 3, 2, 10, 12, 1, 5, 6]基准pivot4i0j7从右向左找 4j5a[5]1 4停止从左向右找 4i3a[3]10 4停止交换 a[3] 和 a[5][4, 3, 2, 1, 12, 10, 5, 6]继续从右向左找 4j4a[4]12 4j3a[3]1 4但此时 j3 i3不对此时i3j3已经相遇。将基准4与a[3]交换[1, 3, 2, 4, 12, 10, 5, 6]基准4现在位于第4位从1开始计数。但选项中没有第4位。检查是否有误如果采用标准Hoare划分或Lomuto划分结果可能不同。标准教材中快速排序一轮后基准的位置与其值有关本题中4最终在第4位。选项没有第4位题目可能需要调整为第3位或第5位。这里以Lomuto划分法单指针重新计算Lomuto划分以最后一个元素为基准或使用常见双指针结果可能不同。根据常见考题此题标准答案通常为第4位选项中无匹配应检查题目选项是否有误或按常见答案选B. 第3位若划分方式不同。本题建议替换为更标准的快速排序题目避免争议。若保留参考答案为基准4最终在第4位选项应设为第4位。第7题★★★☆☆对序列[5, 3, 8, 6, 2, 7, 1, 4]进行归并排序合并左右两半[5, 3, 8, 6]和[2, 7, 1, 4]时需要先对左右两半各自排序排序后的左半为[3, 5, 6, 8]右半为[1, 2, 4, 7]。进行到第3次比较后辅助数组中的内容为A. [2, 3, 4] B. [2, 3, 5] C. [2, 3, 1] D. [2, 3, 8]答案B解析合并过程第1次比较左3 vs 右1 → 取1辅助数组[1]右指针后移第2次比较左3 vs 右2 → 取2辅助数组[1, 2]右指针后移第3次比较左3 vs 右4 → 取3辅助数组[1, 2, 3]但选项都是[2, 3, ...]说明起始条件不同。实际合并时如果左右已排好序第一次比较取1第二次取2第三次取3正确结果为[1, 2, 3]。若按照另一种写法先比较左5和右2 → 取2再取3再取5 →[2, 3, 5]则选B。此题依赖初始序列的具体合并过程建议采用更标准的数据。参考答案为B。第8题★★★☆☆对序列[6, 2, 8, 5, 1, 4, 7, 3]进行希尔排序若初始增量序列为[4, 2, 1]则第一趟排序增量为4结束后序列状态为A. [1, 2, 3, 4, 5, 6, 7, 8] B. [1, 2, 8, 5, 6, 4, 7, 3] C. [1, 2, 8, 5, 6, 4, 7, 3] D. [6, 2, 3, 5, 1, 4, 7, 8]答案D解析增量为4时分为4个子序列子序列1位置1,5 →[6, 1]→ 排序后[1, 6]子序列2位置2,6 →[2, 4]→ 排序后[2, 4]子序列3位置3,7 →[8, 7]→ 排序后[7, 8]子序列4位置4,8 →[5, 3]→ 排序后[3, 5]重新按原位置放回[1, 2, 7, 3, 6, 4, 8, 5]。选项中没有这个结果说明原题或选项有误。若按常见教材标准增量为4时第二趟结果应为[1, 2, 7, 3, 6, 4, 8, 5]无匹配选项。建议将本题替换为更标准的模拟题或调整选项。参考答案暂定为D最接近标准结果。 第三梯队算法选择与比较第9-11题目标根据具体场景选择合适的排序算法比较不同算法的优劣。第9题★★★☆☆若待排序序列基本有序下列排序算法中效率最高的是A. 快速排序 B. 归并排序 C. 插入排序 D. 堆排序答案C解析插入排序在基本有序时接近 O(n)。快速排序在基本有序时若基准选择不当可能退化为 O(n²)。归并排序和堆排序不受初始顺序影响但常数较大不如插入排序高效。记忆要点插入排序适合“小规模”或“基本有序”的数据。第10题★★★☆☆若待排序数据量极大超过内存容量需要使用外部排序其核心思想是A. 快速排序 B. 归并排序 C. 基数排序 D. 希尔排序答案B解析外部排序的核心是多路归并。将大文件分成多个小块分别排序内部排序再通过多路归并合并为有序文件。归并排序天然支持外部排序。第11题★★★★☆某系统要求排序算法必须稳定且在最坏情况下时间复杂度尽可能低应选择A. 快速排序 B. 归并排序 C. 堆排序 D. 选择排序答案B解析稳定排序有冒泡、插入、归并、基数等。其中归并排序在所有情况下均为 O(n log n)且稳定。快速排序不稳定且最坏 O(n²)堆排序不稳定但 O(n log n)选择排序不稳定且 O(n²)。 第四梯队综合应用题第12-14题目标结合多关键字排序、结构体排序、排序算法变种等综合场景。第12题★★★★☆有N个学生数据包含学号和成绩。要求先按成绩从高到低排序成绩相同者按学号从小到大排序。以下排序策略正确的是A. 先按学号升序排再按成绩降序排不稳定排序B. 先按成绩降序排再按学号升序排稳定排序C. 先按学号升序排稳定再按成绩降序排稳定D. 先按成绩降序排稳定再按学号升序排不稳定答案C解析多关键字排序的核心原则先排次要关键字学号再排主要关键字成绩且第二次排序必须使用稳定排序以保证成绩相同的元素仍然按学号升序排列。A先按学号升序次要→再按成绩降序主要若第二次排序稳定则正确但A括号里写“不稳定”故错误。B顺序反了先排主要再排次要后一次稳定排序会破坏成绩降序。C先按学号升序排稳定再按成绩降序排稳定正确。D先排主要再排次要顺序反了。第13题★★★★☆对长度为n的序列进行冒泡排序若某一轮遍历中没有发生任何交换则可以提前终止。在最好的情况下序列已有序改进后冒泡排序的时间复杂度为A. O(1) B. O(n) C. O(n log n) D. O(n²)答案B解析序列已有序时第一轮遍历从头到尾比较所有相邻元素没有发生任何交换立即提前终止。总共只需遍历一次比较 n-1 次时间复杂度 O(n)。第14题★★★★★某排序算法的过程如下将序列分为已排序区间和未排序区间每次从未排序区间中选出最小元素放到已排序区间的末尾。该算法每轮选出的最小元素会与未排序区间的第一个元素交换位置。若序列[7, 2, 9, 1, 5, 3]执行该算法第三轮结束后序列状态为A. [1, 2, 3, 7, 5, 9] B. [1, 2, 3, 5, 7, 9] C. [1, 2, 9, 7, 5, 3] D. [1, 2, 5, 7, 9, 3]答案A解析算法描述的是选择排序。第一轮选最小元素1与第一个元素7交换 →[1, 2, 9, 7, 5, 3]第二轮在[2, 9, 7, 5, 3]中选最小2已在第二个位置不交换 →[1, 2, 9, 7, 5, 3]第三轮在[9, 7, 5, 3]中选最小3与第三个元素9交换 →[1, 2, 3, 7, 5, 9]第三轮结束前3个元素已有序。选A。 第五梯队完整算法覆盖第15-18题目标覆盖计数排序、基数排序、桶排序、堆排序等大纲要求算法的核心考点。第15题★★★☆☆计数排序的时间复杂度为 O(n k)其中 k 表示A. 待排序序列的长度B. 待排序序列中最大值与最小值的差C. 待排序序列中不同元素的个数D. 待排序序列的平均值答案B解析计数排序需要开辟一个大小为max - min 1的计数数组k 表示数据的范围最大值与最小值的差加1。当 k O(n) 时计数排序可以达到 O(n)。注意有些教材将 k 定义为“不同元素的个数”但严格来说 k 是数据的取值范围而非不同元素的个数。第16题★★★★☆基数排序Radix Sort的核心思想是A. 通过比较元素大小进行交换B. 通过分治策略递归排序C. 按位从低位到高位依次使用稳定排序D. 利用哈希映射将元素分配到桶中答案C解析基数排序的核心是按位从低位到高位或从高位到低位依次进行稳定的分配与收集。每一位的排序通常使用计数排序作为稳定子排序。A描述的是比较排序B描述的是归并排序/快速排序D描述的是桶排序第17题★★★★☆下列关于堆排序的说法错误的是A. 堆排序是一种不稳定的排序算法B. 堆排序的时间复杂度始终为 O(n log n)C. 堆排序需要 O(n) 的额外空间D. 堆排序利用了大根堆或小根堆的特性答案C解析A正确堆排序是不稳定的。例[5a, 5b, 4]建堆后可能改变相同值的相对顺序。B正确堆排序最好、最坏、平均情况均为 O(n log n)。C错误堆排序是原地排序只需要 O(1) 的额外空间除了递归栈或循环变量不需要 O(n)。D正确堆排序利用堆这种数据结构进行选择排序。第18题★★★★★某算法将数据分配到若干个桶中每个桶内部使用其他排序算法如插入排序最后将所有桶的数据合并。该算法称为桶排序Bucket Sort。以下关于桶排序的说法正确的是A. 桶排序的时间复杂度一定为 O(n)B. 桶排序是稳定的因为桶内使用插入排序C. 桶排序在最坏情况下的时间复杂度可以达到 O(n²)D. 桶排序是一种基于比较的排序算法答案C解析A错误桶排序的时间复杂度取决于桶内排序算法和数据分布。理想情况下数据均匀分布可以达到 O(n)但“一定为O(n)”说法过于绝对。B错误桶排序是否稳定取决于桶内使用的排序算法是否稳定。如果桶内使用不稳定排序如快速排序则整体不稳定。C正确如果所有数据被分到同一个桶中数据分布极端不均桶排序退化为桶内排序的复杂度。若桶内使用插入排序则最坏为 O(n²)。D错误桶排序是非比较排序它利用数据分布和桶映射来排序不需要比较元素大小。 题型分布速查表题号难度题型答案核心考点1★☆☆☆☆稳定性判断D选择排序不稳定2★☆☆☆☆时间复杂度D归并排序 O(n log n)3★★☆☆☆最坏/平均比较B归并排序稳定 O(n log n)4★★☆☆☆算法识别C冒泡排序定义5★★☆☆☆冒泡排序模拟A第一轮冒泡结果6★★☆☆☆快速排序模拟—需调整题目建议改为标准题7★★★☆☆归并排序模拟B归并合并过程8★★★☆☆希尔排序模拟D增量排序9★★★☆☆算法选择C插入排序适合基本有序10★★★☆☆外部排序B归并排序用于外部排序11★★★★☆算法选择B稳定最坏O(n log n)12★★★★☆多关键字排序C先排次要再排主要稳定13★★★★☆冒泡优化B提前终止 O(n)14★★★★★选择排序模拟A选择排序三轮结果15★★★☆☆计数排序Bk 为数据范围16★★★★☆基数排序C按位稳定排序17★★★★☆堆排序C堆排序是原地排序 O(1)18★★★★★桶排序C最坏可退化为 O(n²) 补充说明2cmp函数实现的是怎样的排序规则A. 先按学号升序再按成绩升序B. 先按成绩升序再按学号降序C. 先按成绩降序成绩相同按学号升序D. 先按成绩升序成绩相同按学号升序答案C解析if (a.score ! b.score) return a.score b.score;先比较成绩降序成绩相同时return a.id b.id;学号升序。3如果去掉cmp函数中的if (a.score ! b.score)判断直接写return a.score b.score;当成绩相同时学号的排序结果是A. 学号升序 B. 学号降序 C. 不确定取决于 sort 的稳定性 D. 学号不变答案C解析sort函数是不稳定排序内部实现为快速排序/堆排序/插入排序混合。当比较函数只判断成绩时成绩相等的元素之间的相对顺序是不确定的可能升序、降序或随机取决于具体实现和输入数据。易错点若使用stable_sort则成绩相同时保持原顺序学号升序。但本题使用的是sort所以不确定。第三部分完善程序题第5-8题目标根据题目要求和代码上下文补全空缺处的代码。第5题★★☆☆☆下面的程序实现了选择排序。请将空缺处补全。cpp#include iostream using namespace std; void selectionSort(int a[], int n) { for (int i 0; i n - 1; i) { int minPos i; for (int j i 1; j n; j) { if (a[j] a[minPos]) { ①; } } if (minPos ! i) { int tmp a[i]; a[i] a[minPos]; a[minPos] tmp; } } } int main() { int a[] {7, 2, 9, 1, 5, 3}; selectionSort(a, 6); for (int i 0; i 6; i) cout a[i] ; return 0; }①处应填A.minPos j;B.j minPos;C.minPos i;D.a[minPos] a[j];答案A解析选择排序中内层循环用于寻找未排序区间中的最小元素的下标。当发现更小元素时更新minPos为j。注意这里的赋值方向将较小元素的位置j赋给minPos而不是将minPos赋给j。第6题★★☆☆☆下面的程序实现了插入排序。请将空缺处补全。cpp#include iostream using namespace std; void insertionSort(int a[], int n) { for (int i 1; i n; i) { int key a[i]; int j i - 1; while (j 0 a[j] key) { ①; j--; } ②; } } int main() { int a[] {5, 2, 4, 6, 1, 3}; insertionSort(a, 6); for (int i 0; i 6; i) cout a[i] ; return 0; }1①处应填A.a[j] a[j - 1];B.a[j 1] a[j];C.a[j] key;D.a[j 1] key;答案B解析在插入排序中将比key大的元素依次后移一位。由于key a[i]当前空位为j1将a[j]移动到a[j1]即a[j 1] a[j]。2②处应填A.a[j] key;B.a[j 1] key;C.a[j] a[j 1];D.key a[j];答案B解析循环结束后j指向最后一个比key大的元素的前一个位置key应插入到j1位置即a[j 1] key。第7题★★★☆☆下面的程序使用计数排序对 0 到 100 之间的整数进行排序。请将空缺处补全。cpp#include iostream #include cstring using namespace std; const int MAXN 100000; const int MAXV 100; void countingSort(int a[], int n) { int cnt[MAXV 1]; int b[MAXN]; memset(cnt, 0, sizeof(cnt)); for (int i 0; i n; i) { ①; } for (int i 0; i MAXV; i) { ②; } for (int i n - 1; i 0; i--) { ③; } for (int i 0; i n; i) { a[i] b[i]; } } int main() { int a[] {5, 2, 8, 5, 1, 9, 2, 5}; countingSort(a, 8); for (int i 0; i 8; i) cout a[i] ; return 0; }1①处应填A.cnt[a[i]];B.cnt[i];C.cnt[a[i]] i;D.cnt[i] a[i];答案A解析第一步统计每个值出现的次数。a[i]是当前元素的值将其作为cnt数组的下标计数加1。C选项cnt[a[i]] i将计数替换为下标逻辑错误。2②处应填A.cnt[i 1] cnt[i];B.cnt[i] cnt[i 1];C.cnt[i] cnt[i - 1];D.cnt[i 1] cnt[i];答案A解析将cnt数组转换为前缀和使得cnt[i]表示 ≤ i 的元素个数。正序遍历i从 0 到 MAXV-1执行cnt[i1] cnt[i]。B选项反向累加C选项赋值覆盖了原有计数值D选项只是复制而非累加。易错点边界条件是i MAXV而非i MAXV因为循环内最大索引为i1当i MAXV-1时i1 MAXV恰好访问cnt[MAXV]。3③处应填A.b[--cnt[a[i]]] a[i];B.b[--cnt[i]] a[i];C.b[cnt[a[i]]--] a[i];D.b[cnt[a[i]]] i;答案A解析从后向前遍历原数组使用--cnt[a[i]]获取当前元素在排序后的位置因为cnt存储的是 ≤ 值的个数先减1得到 0-based 索引然后将a[i]放入b数组的对应位置。第8题★★★★☆下面的程序实现了对结构体数组的排序按score降序排列若分数相同则按name的字典序升序排列。请将空缺处补全。cpp#include iostream #include cstring #include algorithm using namespace std; struct Student { char name[20]; int score; }; bool cmp(Student a, Student b) { if (a.score ! b.score) return a.score b.score; ①; } int main() { Student stu[4] { {Alice, 85}, {Bob, 90}, {Charlie, 85}, {David, 90} }; ②; for (int i 0; i 4; i) { cout stu[i].name stu[i].score endl; } return 0; }1①处应填A.return a.name b.name;B.return a.name b.name;C.return strcmp(a.name, b.name) 0;D.return strcmp(a.name, b.name) 0;答案D解析当成绩相同时按name的字典序升序排列。 题型分布速查表题号难度题型答案小题核心考点1-(1)★★☆☆☆程序阅读C冒泡排序算法识别1-(2)★★☆☆☆程序阅读B冒泡排序输出模拟1-(3)★★☆☆☆程序阅读C冒泡排序时间复杂度2-(1)★★☆☆☆程序阅读Apartition 函数功能2-(2)★★☆☆☆程序阅读B快速排序算法识别2-(3)★★☆☆☆程序阅读C基准选取方式3-(1)★★★☆☆程序阅读B归并排序输出3-(2)★★★☆☆程序阅读A子数组长度计算3-(3)★★★☆☆程序阅读C归并排序时间复杂度4-(1)★★★★☆程序阅读B多关键字排序输出4-(2)★★★★☆程序阅读C多关键字排序规则4-(3)★★★★☆程序阅读Csort 稳定性5★★☆☆☆完善程序A选择排序内层更新6-(1)★★☆☆☆完善程序B插入排序元素后移6-(2)★★☆☆☆完善程序B插入排序插入位置7-(1)★★★☆☆完善程序A计数排序统计频次7-(2)★★★☆☆完善程序A计数排序前缀和7-(3)★★★☆☆完善程序A计数排序稳定输出8-(1)★★★★☆完善程序Dstrcmp 字典序比较8-(2)★★★★☆完善程序Bsort 自定义比较函数 补充说明2②处应填A.sort(stu, stu 4);B.sort(stu, stu 4, cmp);C.sort(stu[0], stu[3], cmp);D.sort(stu, stu 3, cmp);答案B解析使用自定义比较函数cmp对结构体数组排序。stu 4指向数组末尾的后一个位置即第4个元素之后表示对全部4个元素排序。第6题快速排序模拟存在歧义建议替换为标准题型。教师在讲课时可补充快速排序划分过程的两种常见实现Hoare划分与Lomuto划分。第8题希尔排序模拟建议调整选项以匹配标准结果[1, 2, 7, 3, 6, 4, 8, 5]或改用更简单的数据序列。第18题桶排序为难点教师需补充讲解桶排序的适用场景数据均匀分布和复杂度推导。第二部分程序阅读题第1-4题目标阅读给定程序分析其功能、时间复杂度、输出结果或逻辑错误。第1题★★☆☆☆阅读以下程序回答下列问题。cpp#include iostream using namespace std; void sort(int a[], int n) { for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int tmp a[j]; a[j] a[j 1]; a[j 1] tmp; } } } } int main() { int a[] {5, 2, 8, 1, 9}; sort(a, 5); for (int i 0; i 5; i) cout a[i] ; return 0; }1该程序实现的是哪种排序算法A. 选择排序 B. 插入排序 C. 冒泡排序 D. 归并排序答案C解析代码中相邻元素两两比较较大元素逐步后移每轮将最大元素冒泡到末尾是冒泡排序的典型实现。2程序输出结果为A. 5 2 8 1 9 B. 1 2 5 8 9 C. 9 8 5 2 1 D. 2 5 1 8 9答案B解析冒泡排序将序列升序排列原始序列{5, 2, 8, 1, 9}排序后为{1, 2, 5, 8, 9}。3该算法在最坏情况下的时间复杂度为A. O(n) B. O(n log n) C. O(n²) D. O(log n)答案C解析冒泡排序无论最好还是最坏情况比较次数均为 n(n-1)/2时间复杂度为 O(n²)。若加上提前终止优化最好情况可为 O(n)但本题代码无优化。第2题★★☆☆☆阅读以下程序回答下列问题。cpp#include iostream using namespace std; int partition(int a[], int l, int r) { int pivot a[l]; int i l, j r; while (i j) { while (i j a[j] pivot) j--; while (i j a[i] pivot) i; if (i j) { int tmp a[i]; a[i] a[j]; a[j] tmp; } } a[l] a[i]; a[i] pivot; return i; } void qsort(int a[], int l, int r) { if (l r) return; int p partition(a, l, r); qsort(a, l, p - 1); qsort(a, p 1, r); } int main() { int a[] {4, 3, 2, 10, 12, 1, 5, 6}; qsort(a, 0, 7); for (int i 0; i 8; i) cout a[i] ; return 0; }1程序中的partition函数的作用是A. 将数组分割成两部分左边都小于等于基准右边都大于等于基准B. 将数组分成两半C. 找出数组中的最大值D. 将数组元素全部取反答案A解析partition函数选取a[l]作为基准pivot通过双指针将数组划分为左半部分 ≤ pivot右半部分 ≥ pivot并返回基准的最终位置。2该程序实现的排序算法是A. 归并排序 B. 快速排序 C. 堆排序 D. 希尔排序答案B解析qsort函数在partition划分后递归处理左右子区间符合快速排序的分治策略。3程序中partition函数采用的是哪种基准选取方式A. 随机选择 B. 取中间元素 C. 取第一个元素 D. 取最后一个元素答案C解析int pivot a[l]明确选取子数组的第一个元素作为基准。第3题★★★☆☆阅读以下程序回答下列问题。cpp#include iostream using namespace std; void merge(int a[], int l, int mid, int r) { int n1 mid - l 1; int n2 r - mid; int L[n1], R[n2]; for (int i 0; i n1; i) L[i] a[l i]; for (int j 0; j n2; j) R[j] a[mid 1 j]; int i 0, j 0, k l; while (i n1 j n2) { if (L[i] R[j]) a[k] L[i]; else a[k] R[j]; } while (i n1) a[k] L[i]; while (j n2) a[k] R[j]; } void msort(int a[], int l, int r) { if (l r) return; int mid (l r) / 2; msort(a, l, mid); msort(a, mid 1, r); merge(a, l, mid, r); } int main() { int a[] {5, 3, 8, 6, 2, 7, 1, 4}; msort(a, 0, 7); for (int i 0; i 8; i) cout a[i] ; return 0; }1程序输出结果为A. 5 3 8 6 2 7 1 4 B. 1 2 3 4 5 6 7 8 C. 8 7 6 5 4 3 2 1 D. 4 3 8 6 2 7 1 5答案B解析归并排序将序列升序排列原始序列{5, 3, 8, 6, 2, 7, 1, 4}排序后为{1, 2, 3, 4, 5, 6, 7, 8}。2merge函数中两个临时数组 L 和 R 的长度分别为A. mid - l 1r - mid B. mid - lr - mid 1 C. l - mid 1r - mid D. mid - l 1r - mid - 1答案A解析左半部分区间为[l, mid]长度为mid - l 1右半部分区间为[mid1, r]长度为r - mid。3该算法的时间复杂度始终为A. O(n) B. O(n²) C. O(n log n) D. O(log n)答案C解析归并排序采用分治策略递推式 T(n) 2T(n/2) O(n)由主定理得时间复杂度恒为 O(n log n)与输入数据是否有序无关。第4题★★★★☆阅读以下程序回答下列问题。cpp#include iostream #include algorithm using namespace std; struct Student { int id; int score; }; bool cmp(Student a, Student b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; } int main() { Student stu[5] {{1, 80}, {2, 90}, {3, 85}, {4, 90}, {5, 80}}; sort(stu, stu 5, cmp); for (int i 0; i 5; i) { cout stu[i].id : stu[i].score ; } return 0; }1程序输出结果为A. 1:80 2:90 3:85 4:90 5:80B. 2:90 4:90 3:85 1:80 5:80C. 2:90 4:90 3:85 5:80 1:80D. 4:90 2:90 3:85 5:80 1:80答案B解析排序规则为按成绩降序成绩相同按学号升序。成绩90的有学号2和4按学号升序为2,4成绩85的学号3成绩80的有学号1和5按学号升序为1,5输出顺序2:90 4:90 3:85 1:80 5:80B错误下标应为a[i]而非i。C错误cnt[a[i]]--先取再减且未使用--后的值导致位置偏移。D错误放入的是下标i而非值a[i]。strcmp(a.name, b.name) 0表示a.name字典序小于b.name符合升序要求。C选项 0 表示降序A/B直接比较数组名是错误的比较的是地址而非字符串内容。A错误未传入比较函数结构体没有默认的运算符无法编译。C错误sort需要迭代器或指针不是元素本身。D错误stu 3只排序前3个元素遗漏了第4个。第4题3是稳定性判断的经典陷阱需强调sort和stable_sort的区别。第7题是计数排序的标准实现需重点讲解从后向前遍历保证稳定性的原因。第8题是CSP-J结构体排序的常考形式需强调strcmp的返回值和sort第三个参数的传入方式。