GESP 4级客观题｜冒泡、插入、选择排序｜课后作业

考试频率：高频。本卷共 6 题。

1. 小杨在整理一副扑克牌的所有红心扑克牌，使其从小到大排列。他的做法是：最开始抓到第1张扑克牌被认为已经排好序；然后抓第2张扑克牌，将其插入至有序部分的正确位置；不断循环步骤，每次将新抓到扑克牌插入至有序部分，直至抓完所有扑克牌，这样抓牌结束时就完成了扑克牌的排序。小杨这种整理扑克牌的方式与（ ）排序的方式最接近。

   {{ select(1) }}

• 冒泡排序
• 插入排序
• 选择排序
• 直接排序

2. 下面关于排序稳定性的描述，正确的是（ ）。

   {{ select(2) }}

• 稳定性指算法的时间复杂度恒定
• 稳定排序保证相同元素的相对顺序不变
• 选择排序是稳定排序
• 插入排序不是稳定排序

3. 下⾯关于排序算法（冒泡排序、插⼊排序和选择排序）的描述中，不正确的是（ ）。

   {{ select(3) }}

• 冒泡排序基于元素交换实现，需借助临时变量，共涉及3个单元操作；⽽插⼊排序基于元素赋值实现，仅需1个单元操作。因此冒泡排序的计算开销通常⽐插⼊排序更⾼。
• 选择排序在任何情况下的时间复杂度都为$O(n^2)$。
• 冒泡排序在任何情况下的时间复杂度都为$O(n^2)$。
• 如果给定数据部分有序，插⼊排序通常⽐选择排序效率更⾼。

4. 关于⼏种排序算法的说法，下⾯说法错误的是（ ）。

   {{ select(4) }}

• 选择排序不是⼀个稳定的排序算法
• 冒泡排序算法不是⼀种稳定的排序算法
• `插⼊排序是⼀种稳定的排序算法
• 如果排序前2个相等的数在序列中的前后位置顺序和排序后它们2个的前后位置顺序相同，则称为⼀种稳定的排序算法

5. 以下哪种情况是使用插入排序的合适场景？

   {{ select(5) }}

• 数据量非常大，且乱序严重
• 希望获得稳定排序，但不要求实时性
• 数据几乎有序，只需少量调整
• 想在交换次数最少的前提下排好大数组

6. 为了提高冒泡排序的效率，如果某轮"冒泡"中没有执行任何交换操作，说明数组已经完成排序，可直接返回结果，则两条横线上分别应该填写（ ）。

void bubbleSortWithFlag(vector<int> &nums) {
    for (int i = nums.size() - 1; i > 0; i--) {
        bool flag;
        ________________ // 在此处填入代码
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                ___________________________ // 在此处填入代码
            }
        }
        if (!flag)
            break;
    }
}

{{ select(6) }}

• flag = false; 和 flag = false;
• flag = false; 和 flag = true;
• flag = true; 和 flag = false;
• flag = true; 和 flag = true;