ID: 9972

传统题

1000ms

256MiB

尝试: 0

已通过: 0

难度: 1

上传者:

bitworld

标签>

模拟

CSPJ

初赛

普及组排序算法专题训练（10题）

题目1：冒泡排序及其优化

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

判断题

内层循环的条件j < n - i - 1确保每趟比较次数递减。 ( )
swapped变量用于检测是否发生交换，可以提前结束排序。 ( )
如果将第7行的swapped = false移到循环外，算法仍能正确工作。 ( )

选择题 4. 如果将第8行的j < n - i - 1改为j < n - 1，会有什么影响？ ( )
A. 算法效率提高
B. 算法效率降低，但仍正确
C. 算法可能出错
D. 没有影响

第10行的swap(arr[j], arr[j + 1])可以用以下哪段代码替换而不影响功能？ ( )
A. arr[j] = arr[j + 1]; arr[j + 1] = arr[j];
B. int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp;
C. arr[j + 1] = arr[j]; arr[j] = arr[j + 1];
D. 以上都可以

题目2：选择排序及其变形

#include <iostream>
#include <vector>
using namespace std;

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
}

void bidirectionalSelectionSort(vector<int>& arr) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        int minIndex = left, maxIndex = right;
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[minIndex]) minIndex = i;
            if (arr[i] > arr[maxIndex]) maxIndex = i;
        }
        swap(arr[left], arr[minIndex]);
        if (maxIndex == left) maxIndex = minIndex;
        swap(arr[right], arr[maxIndex]);
        left++;
        right--;
    }
}

判断题

选择排序每趟找到最小元素并与当前位置交换。 ( )
双向选择排序中，如果最大元素在left位置，需要特殊处理。 ( )
第15行的if (maxIndex == left) maxIndex = minIndex;可以省略。 ( )

选择题 4. 如果将第6行的j = i + 1改为j = 0，算法会： ( )
A. 仍然正确但效率降低
B. 产生错误结果
C. 变成插入排序
D. 死循环

双向选择排序中，第18行的left++和right--的作用是： ( )
A. 缩小待排序区间
B. 避免重复比较
C. 提高算法稳定性
D. A和B都正确

题目3：插入排序及二分插入排序

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void binaryInsertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int left = 0, right = i - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
    }
}

判断题

插入排序中，第8行的j >= 0检查防止数组越界。 ( )
二分插入排序减少了比较次数，但移动次数不变。 ( )
第25行的left = mid + 1确保找到正确的插入位置。 ( )

选择题 4. 如果将第8行的arr[j] > key改为arr[j] >= key，会： ( )
A. 使算法不稳定
B. 提高算法效率
C. 使算法变成稳定排序
D. 没有影响

二分插入排序中，第30行的j >= left条件确保： ( )
A. 正确移动元素
B. 避免数组越界
C. 提高算法效率
D. A和B都正确

题目4：快速排序及其变体

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void quickSort3Way(vector<int>& arr, int low, int high) {
    if (low >= high) return;
    
    int lt = low, gt = high;
    int pivot = arr[low];
    int i = low;
    
    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr[lt], arr[i]);
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            swap(arr[i], arr[gt]);
            gt--;
        } else {
            i++;
        }
    }
    
    quickSort3Way(arr, low, lt - 1);
    quickSort3Way(arr, gt + 1, high);
}

判断题

partition函数中，pivot选择最后一个元素。 ( )
三路快排中，lt指针指向小于pivot的区域的末尾。 ( )
第33行的i++只在元素等于pivot时执行。 ( )

选择题 4. 如果将第9行的arr[j] <= pivot改为arr[j] < pivot，会： ( )
A. 使算法不稳定
B. 改变分区行为
C. 提高算法效率
D. 没有影响

三路快排中，第35行的if (maxIndex == left) maxIndex = minIndex;的作用是： ( )
A. 处理最大元素在left位置的特殊情况
B. 提高算法稳定性
C. 避免重复交换
D. 以上都正确

题目5：归并排序及其应用

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int mergeAndCount(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
    
    int i = 0, j = 0, k = left;
    int count = 0;
    
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
            count += (n1 - i);
        }
        k++;
    }
    
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
    
    return count;
}

判断题

merge函数中，使用临时数组L和R存储左右子数组。 ( )
第15行的L[i] <= R[j]保证归并排序是稳定的。 ( )
mergeAndCount函数用于计算逆序对数量。 ( )

选择题 4. 如果将第15行的L[i] <= R[j]改为L[i] < R[j]，会： ( )
A. 使算法不稳定
B. 提高算法效率
C. 减少比较次数
D. 没有影响

mergeAndCount函数中，第45行的count += (n1 - i)的作用是： ( )
A. 计算当前逆序对数量
B. 统计剩余元素数量
C. 记录比较次数
D. 以上都不正确

题目6：堆排序及应用

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
    
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

vector<int> topK(vector<int>& arr, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    for (int num : arr) {
        if (minHeap.size() < k) {
            minHeap.push(num);
        } else if (num > minHeap.top()) {
            minHeap.pop();
            minHeap.push(num);
        }
    }
    
    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    return result;
}

判断题

heapify函数维护最大堆性质。 ( )
第24行的i = n / 2 - 1从最后一个非叶子节点开始建堆。 ( )
topK函数使用最小堆来找最大的k个元素。 ( )

选择题 4. 如果将第7行的arr[left] > arr[largest]改为arr[left] >= arr[largest]，会： ( )
A. 使堆排序不稳定
B. 提高算法效率
C. 改变堆的性质
D. 没有影响

topK函数中，第38行的num > minHeap.top()判断确保： ( )
A. 只保留最大的k个元素
B. 堆的大小不超过k
C. 算法时间复杂度为O(n log k)
D. 以上都正确

题目7：计数排序及基数排序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;
    
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;
    
    vector<int> count(range), output(arr.size());
    
    for (int i = 0; i < arr.size(); i++) {
        count[arr[i] - minVal]++;
    }
    
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - minVal] - 1] = arr[i];
        count[arr[i] - minVal]--;
    }
    
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = output[i];
    }
}

void countingSortForRadix(vector<int>& arr, int exp) {
    vector<int> output(arr.size());
    vector<int> count(10, 0);
    
    for (int i = 0; i < arr.size(); i++) {
        count[(arr[i] / exp) % 10]++;
    }
    
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = output[i];
    }
}

判断题

计数排序中，count数组存储每个元素的出现次数。 ( )
第15行的循环计算前缀和，用于确定元素位置。 ( )
基数排序按位排序，从高位到低位。 ( )

选择题 4. 如果将第20行的逆序遍历改为正序遍历，会： ( )
A. 使计数排序不稳定
B. 提高算法效率
C. 改变排序结果
D. 没有影响

countingSortForRadix函数中，第32行的(arr[i] / exp) % 10用于获取： ( )
A. 当前位的数字
B. 数字的总位数
C. 数字的大小
D. 以上都不正确

题目8：排序算法应用 - 区间合并

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    
    sort(intervals.begin(), intervals.end(), const vector<int>& a, const vector<int>& b {
        return a[0] < b[0];
    });
    
    vector<vector<int>> merged;
    merged.push_back(intervals[0]);
    
    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] <= merged.back()[1]) {
            merged.back()[1] = max(merged.back()[1], intervals[i][1]);
        } else {
            merged.push_back(intervals[i]);
        }
    }
    
    return merged;
}

判断题

第5行的lambda表达式用于按区间起始位置排序。 ( )
第12行的判断检查区间是否重叠。 ( )
算法可以处理包含负数的区间。 ( )

选择题 4. 如果将第12行的<=改为<，会： ( )
A. 改变区间合并的规则
B. 使算法不能合并相邻区间
C. 提高算法效率
D. 没有影响

第13行的max(merged.back()[1], intervals[i][1])确保： ( )
A. 合并后的区间包含所有原始区间
B. 选择较大的结束位置
C. 避免区间遗漏
D. 以上都正确

题目9：排序算法应用 - 荷兰国旗问题

#include <iostream>
#include <vector>
using namespace std;

void dutchFlag(vector<int>& arr) {
    int low = 0, mid = 0, high = arr.size() - 1;
    
    while (mid <= high) {
        if (arr[mid] == 0) {
            swap(arr[low], arr[mid]);
            low++;
            mid++;
        } else if (arr[mid] == 1) {
            mid++;
        } else {
            swap(arr[mid], arr[high]);
            high--;
        }
    }
}

判断题

三个指针low、mid、high将数组分为四个区域。 ( )
当arr[mid]为2时，只移动high指针。 ( )
算法可以处理包含负数的数组。 ( )

选择题 4. 如果将第8行的mid++删除，会： ( )
A. 使算法陷入死循环
B. 改变排序结果
C. 提高算法效率
D. 没有影响

荷兰国旗问题的时间复杂度是： ( )
A. O(n)
B. O(n log n)
C. O(n²)
D. O(1)

题目10：排序算法比较与应用选择

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void smartSort(vector<int>& arr) {
    int n = arr.size();
    
    if (n <= 10) {
        // 使用插入排序
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
        return;
    }
    
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    int range = maxVal - minVal;
    
    if (range > 0 && range < 1000) {
        // 使用计数排序
        vector<int> count(range + 1, 0);
        for (int num : arr) count[num - minVal]++;
        int index = 0;
        for (int i = 0; i <= range; i++) {
            while (count[i]-- > 0) {
                arr[index++] = i + minVal;
            }
        }
        return;
    }
    
    // 使用快速排序
    quickSort(arr, 0, n - 1);
}

判断题

智能排序根据数据规模选择排序算法。 ( )
当数据范围较小时，选择计数排序。 ( )
快速排序是默认的排序算法。 ( )

选择题 4. 如果将第7行的n <= 10改为n <= 5，会： ( )
A. 增加插入排序的使用频率
B. 减少插入排序的使用频率
C. 提高算法效率
D. 没有影响

第23行的range < 1000条件基于什么考虑？ ( )
A. 计数排序的空间复杂度
B. 计数排序的时间复杂度
C. 数据分布的均匀性
D. 以上都正确

#CSPJCSMN11. 普及组程序专项-排序

普及组程序专项-排序

普及组排序算法专题训练（10题）

题目1：冒泡排序及其优化

题目2：选择排序及其变形

题目3：插入排序及二分插入排序

题目4：快速排序及其变体

题目5：归并排序及其应用

题目6：堆排序及应用

题目7：计数排序及基数排序

题目8：排序算法应用 - 区间合并

题目9：排序算法应用 - 荷兰国旗问题

题目10：排序算法比较与应用选择

#CSPJCSMN11. 普及组程序专项-排序

普及组程序专项-排序

普及组排序算法专题训练（10题）

题目1：冒泡排序及其优化

题目2：选择排序及其变形

题目3：插入排序及二分插入排序

题目4：快速排序及其变体

题目5：归并排序及其应用

题目6：堆排序及应用

题目7：计数排序及基数排序

题目8：排序算法应用 - 区间合并

题目9：排序算法应用 - 荷兰国旗问题

题目10：排序算法比较与应用选择

还没有账户？

登录