假设一个长度为 的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（ ）
A：O(n)。无序数组找最大需遍历 n-1 次比较。
以下排序方法中，（ ）是不稳定的。
C：堆排序。堆排序堆化下沉交换可能跨元素，相等元素相对顺序可能改变，不稳定；插入/冒泡/归并稳定。
考虑对 个数进行排序，以下最坏时间复杂度低于 的排序方法是（ ）。
C：归并排序。归并最坏 O(n log n)；插入/冒泡/快排最坏 O(n²)。
冒泡排序和插入排序都是稳定排序算法。
正确。冒泡和插入排序都只交换/移动相邻元素，相等元素相对顺序不变，都是稳定排序。
由于选择排序和插入排序的时间复杂度均为 ，在任何实际场景下两者的性能表现几乎相同，可以互相替代。
错。两者虽然平均 O(n²)，但选择排序交换次数少、插入排序对近有序数据接近 O(n)，实际场景不可简单互换。
选择排序算法在寻找每一轮最小值时，如果遇到相等的元素不进行交换，则选择排序是一种稳定的排序算法。
错。即使选择排序遇到相等元素不交换，因后续可能跳过该元素，相对顺序仍可能改变，本质上仍是不稳定排序。
如果使用带 flag 的冒泡排序，且待排序数组一开始就是有序的，那么算法只需一轮扫描即可结束，时间复杂度为 O(n)。
正确。带 flag 冒泡：已有序数组第一趟无任何交换，flag=false，break 提前结束；只一趟 n-1 次比较 O(n)。
下算法中，（ ）是不稳定的排序。
A：选择排序每趟将最小元素与未排序区首位交换，交换可能跨越相同值元素，使相等元素的相对顺序改变，故不稳定；冒泡、插入、归并均只相邻交换或按序合并，保持稳定。
归并排序的最好、最坏和平均时间复杂度均为 。
对。归并排序无论输入有序、逆序还是乱序，都按 mid 对半切分，每层合并总代价 O(n)、共 logn 层，最好、最坏、平均复杂度均为 O(nlogn)。
快速排序和归并排序都是稳定的排序算法。
错。归并排序合并时相等元素保持原相对顺序，是稳定的；快速排序的划分 swap 可能改变相等元素相对顺序，不稳定，两者稳定性不同。
下列关于排序的说法，正确的是（ ）。
B：归并合并时左半元素优先取出，相等元素相对顺序不变，稳定；快排划分时交换破坏稳定性，插入排序稳定，冒泡只交换相邻元素、无需额外数组属原地排序。
排序的算法很多，若按排序的稳定性和不稳定性分类，则（ ）是不稳定排序。
A：快速排序。快排每趟 partition 交换可能跨元素，相等元素相对顺序可能改变，不稳定；插入/归并/冒泡都是稳定排序。
设 和 是两个长度为 的有序数组，现在需要将 和 合并成一个排序好的数组。请问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（ ）
C：2n-1。两个有序数组合并最坏比较：每步各取一元素直到某一数组空，前 n-1 步各比一次，最后一次比较两个剩余数组的第一个元素确定全部顺序，共 2n-1 次。
以比较为基本运算，对于 个数，同时找到最大值和最小值，最坏情况下需要的最少比较次数为（ ）。
C：3n-2。2n 个数两两配对分大小（n 次比较），n 个较大者找最大 n-1 次、n 个较小者找最小 n-1 次，共 n+2(n-1)=3n-2 次（最优下界）。
假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排序算法结束后，可能出现的最坏情况是（ ）。
A：移除受影响数据后序列有序。基数排序按位分桶，异变只影响该位的桶位置，移除后剩余位仍保持有序。
对于给定的 ，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（ ）。
01int i, j, k = 0; 02for (i = 0; i < n; i++) { 03 for (j = 0; j < n; j *= 2) { 04 k = k + n / 2; 05 } 06}
B：O(n log n)。外层 n 次循环，内层 j*=2 循环 log n 次，总 O(n log n)。
假设快速排序算法的输入是一个长度为 的已排序数组，且该快速排序算法在分治过程中总是选择第一个元素作为基准元素。以下哪个选项描述的是这种情况下的快速排序行为？（ ）
C：O(n²)。有序数组选首为基准导致 partition 极度不平衡，每次只减少 1 个，递归 n 层共 O(n²)。
递归关系式 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？
C：O(n²)。T(n)=2T(n/2)+O(n²) 由主定理（a=2,b=2,f(n)=n², f(n)/n^(log_b a)=n²/n=n² 更大）→ T(n)=Θ(f(n))=O(n²)。
一般说来，冒泡排序算法优于归并排序。
错。冒泡排序平均与最坏均为 O(n²)，归并排序稳定且为 O(nlogn)，数据量大时归并远优于冒泡，不能说冒泡一般优于归并。
C++ 语言中的 qsort 库函数是不稳定排序。
对。C 标准库 qsort 通常用快速排序实现，划分时枢轴与元素交换会打乱相等元素的相对顺序，属于不稳定排序，与归并排序的稳定不同。
插入排序有时比快速排序时间复杂度更低。
对。当数据初始基本有序时，插入排序只需少量比较，可接近 O(N)；而快速排序最坏情况可达 O(N²)，因此插入排序有时确实更低。
在快速排序中，选择的主元素（pivot）会影响算法的（ ）。
B：pivot 的选择决定每趟划分是否均衡，直接影响时间复杂度——划分均衡时 O(n log n)，每次选到最大或最小值则退化为 O(n²)；空间复杂度主要由递归深度决定，与 pivot 关系不大。
归并排序和快速排序都采用递归实现，也都是不稳定排序。
错。归并排序两两合并有序子序列时，相等元素相对顺序保持不变，属于稳定排序；只有快速排序不稳定，故该句说两者皆不稳定是错误的。
假设快速排序算法的输入是一个长度为 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项（ ）描述的是在这种情况下的快速排序行为。
C：数组已升序且每次选第一个元素作基准，划分后一边为空、另一边剩 n−1 个元素，递归深度达 n，总时间复杂度 O(n²)，是快排最坏情形。
快速排序和归并排序的平均时间复杂度均为 ，且都是稳定排序。
错。快速排序与归并排序平均复杂度确实都是 O(nlogn)，但快排划分时交换会改变相等元素的相对顺序，是不稳定排序，故两算法都稳定的说法错误。
下面关于归并排序，描述正确的是（ ）。
B：归并排序最优、最差、平均均为 O(n log n)；A 错在归并稳定，C 错在需 O(n) 辅助数组，D 错在 {12,11,13,5,6,7} 应输出升序 5 6 7 11 12 13。
关于下述 C++ 代码的快速排序算法，说法错误的是（ ）。
01int randomPartition(std::vector<int>& arr, int low, int high) { 02 int random = low + rand() % (high - low + 1); 03 std::swap(arr[random], arr[high]); 04 05 int pivot = arr[high]; 06 int i = low - 1; 07 08 for (int j = low; j < high; j++) { 09 if (arr[j] <= pivot) { 10 i++; 11 std::swap(arr[i], arr[j]); 12 } 13 } 14 std::swap(arr[i + 1], arr[high]); 15 return i + 1; 16} 17 18void quickSort(std::vector<int>& arr, int low, int high) { 19 if (low < high) { 20 int pi = randomPartition(arr, low, high); 21 22 quickSort(arr, low, pi - 1); 23 quickSort(arr, pi + 1, high); 24 } 25}
D：快排靠 swap 交换元素，相等元素的相对顺序可能改变，是不稳定排序。A 中 i 标记小于等于 pivot 的边界，B 随机选 pivot 可避开有序输入的最坏 O(n²)，C 平均 O(nlogn)，均正确。
下述 C++ 代码实现了快速排序算法，下面说法错误的是（ ）。
01int partition(vector<int>& arr, int low, int high) { 02 int i = low, j = high; 03 int pivot = arr[low]; // 以首元素为基准 04 while (i < j) { 05 while (i < j && arr[j] >= pivot) j--; // 从右往左查找 06 while (i < j && arr[i] <= pivot) i++; // 从左往右查找 07 if (i < j) swap(arr[i], arr[j]); 08 } 09 swap(arr[i], arr[low]); 10 return i; 11} 12 13void quickSort(vector<int>& arr, int low, int high) { 14 if (low >= high) return; 15 int p = partition(arr, low, high); 16 quickSort(arr, low, p - 1); 17 quickSort(arr, p + 1, high); 18}
D：partition 以 arr[low] 为 pivot，必须先右后左找可交换元素；若先从左往右，i 自 pivot 处必前进，最后 swap(arr[i],arr[low]) 会把 pivot 放错位置。
下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是（ ）。
01void merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) { 02 int i = l, j = mid + 1, k = l; 03 while (i <= mid && j <= r) { 04 if (arr[i] <= arr[j]) temp[k++] = arr[i++]; 05 else temp[k++] = arr[j++]; 06 } 07 while (i <= mid) temp[k++] = arr[i++]; 08 while (j <= r) temp[k++] = arr[j++]; 09 for (int p = l; p <= r; p++) arr[p] = temp[p]; 10} 11 12void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) { 13 if (l >= r) return; 14 int mid = l + (r - l) / 2; 15 mergeSort(arr, temp, l, mid); 16 mergeSort(arr, temp, mid + 1, r); 17 merge(arr, temp, l, mid, r); 18}
C：归并排序最坏、平均时间都是 O(n log n)，不存在最坏 O(n²)；它合并时需 O(n) 的 temp 辅助数组，稳定且对大规模数据有最坏复杂度保证，故 A、B、D 正确，不正确的是 C。
归并排序和快速排序在平均情况下的时间复杂度均为 。但在稳定性方面，归并排序通常是不稳定的，而快速排序是稳定的。
错。平均 O(nlogn) 的说法正确，但稳定性说反了：归并排序合并时取 L[i]<=R[j] 能保持相等元素相对顺序，是稳定排序；快速排序划分时交换会打乱相等元素顺序，不稳定。
选择排序一般是不稳定的。（ ）
对。选择排序每趟把未排序区的最小值与当前位置交换，可能把相等的元素换到另一个相等元素之后（相对顺序被破坏），故一般不稳定。故对，故对。
快速排序一般是不稳定的。
对。快速排序以基准划分区间时会跨越式交换元素，可能把相等的两个元素换到彼此之后，改变它们排序前后的相对顺序，因此一般不稳定，故对。
下列关于排序稳定性的说法，正确的是（ ）。
A：冒泡排序只交换相邻逆序元素，相等元素相对顺序不变，是稳定排序；选择、快排一般不稳定，稳定排序不会改变相等元素顺序；稳定排序不改变相等元素相对顺序。
冒泡排序是稳定的排序算法。（ ）
对。冒泡排序每趟只交换相邻的逆序元素，相等的两个元素永远不会发生位置交换，排序前后的相对顺序保持不变，因此是稳定排序算法。故说法正确。
归并排序每次把长度为 的序列分成两个规模约为 的子序列，递归排序后再用线性时间合并。该算法的时间复杂度通常为（ ）。
D：O(n log n)。每次对半划分产生约 log n 层递归，每层合并总耗时 O(n)，总 O(n log n)，与输入顺序无关，最坏也是这个阶。