gesp四级真题分类五：排序算法

ID: 6088

客观题

尝试: 1

已通过: 0

难度: 10

上传者:

root

五、排序算法（共31题）

1. 对 int a[] = {2,0,2,4,3,1,6}，执行第一趟选择排序处理后 a 中数据变为 {0,2,2,4,3,1,6}。（判断题）

正确
错误

2. 下面代码实现了冒泡排序函数，则横线上应填写（）。

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

for (int j = 0; j < arr.size() - 1; j++)
for (int j = arr.size() - 1; j > 0; j--)
for (int j = 0; j < i; j++)
for (int j = i - 1; j <= 0; j--)

3. 上一题算法的时间复杂度为（）。

O(n²)
O(2n)
O(1)
O(n)

4. 下面代码实现了插入排序函数（升序），则横线上应填写（）。

void insertion_sort(vector<int>& nums) {
    for (int i = 1; i < nums.size(); i++) {
        int base = nums[i], j = i - 1;
        // 在此处填入代码
        {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = base;
    }
}

while (j >= 0 && nums[j] > base)
while (j > 0 && nums[j] > base)
while (j >= 0 && nums[j] < base)
while (j > 0 && nums[j] < base)

5. 下面代码试图实现选择排序，使其能对数组 nums 排序为升序，则横线上应分别填写（）。

void selectionSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if ( ) { // 在此处填入代码
                minIndex = j;
            }
        }
        // 在此处填入代码
    }
}

nums[j] < nums[minIndex] 和 swap(nums[i], nums[minIndex])
nums[j] > nums[minIndex] 和 swap(nums[i], nums[minIndex])
nums[j] <= nums[minIndex] 和 swap(nums[j], nums[minIndex])
nums[j] <= nums[minIndex] 和 swap(nums[i], nums[j])

6. 下面程序实现插入排序（升序排序），则横线上应分别填写（）。

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && ) { // 此处
            arr[j + 1] = arr[j];
            j--;
        }
        // 此处
    }
}

arr[j] > key 和 arr[j + 1] = key
arr[j] < key 和 arr[j + 1] = key
arr[j] > key 和 arr[j] = key
arr[j] < key 和 arr[j] = key

7. 关于插入排序的时间复杂度，下列说法正确的是（）。

最好情况和最坏情况的时间复杂度都是 O(n²)
最好情况是 O(n)，最坏情况是 O(n²)
最好情况是 O(n)，最坏情况是 O(2ⁿ)
最好情况是 O(n²)，最坏情况是 O(2ⁿ)

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

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;
    }
}

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

9. 对数组 arr[]={5, 3, 8, 1} 进行升序排序，执行第一轮冒泡排序后数组 arr 中的内容为（）。

3, 5, 1, 8
3, 1, 5, 8
3, 5, 8, 1
5, 3, 8, 1

10. 对数组 arr[]={4,1,3,1,5,2} 进行冒泡排序（将最大元素放到最后），执行一轮之后是（）。

{1,4,3,1,5,2}
{1,3,1,4,2,5}
{1,4,3,1,2,5}
{4,1,3,1,5,2}

11. 给定数组 arr[] = {4,1,3,1,5,2}，执行第一轮冒泡排序后数组 arr 中的内容为（）。

1,4,3,1,5,2
1,3,1,4,2,5
1,4,3,1,2,5
4,1,3,1,5,2

12. 下面代码实现了插入排序函数，则横线上应填写（）。

void insertion_sort(vector<int>& nums) {
    for (int i = 1; i < nums.size(); i++) {
        // 此处
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = base;
    }
}

int base = nums[i], j = i - 1;
int base = nums[i], j = i;
int base = nums[0], j = i - 1;
int base = nums[0], j = i;

13. 关于排序算法的稳定性，以下说法错误的是（）。

稳定的排序算法不改变相等元素的相对位置
冒泡排序是稳定的排序算法
选择排序是稳定的排序算法
插入排序是稳定的排序算法

14. 某排序算法对如下数据排序（按score升序），则下面关于该排序算法稳定性的描述中，说法正确的是（）。

初始： (90,'A'), (90,'B'), (80,'C'), (90,'D') 排序后： (80,'C'), (90,'A'), (90,'B'), (90,'D')

不稳定，因为出现了相同分数
稳定，因为相同score的相对顺序保持为A在B前、B在D前
不稳定，因为C跑到前面了
无法判断

15. 下面代码试图把数组按升序进行“插入排序”，横线处应填写（）。

void ins(int a[], int n) {
    for(int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while(j >= 0 && ) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }
}

a[j] < key
a[j] > key
a[j+1] > key
a[j] == key

16. 对如下4个扑克牌进行排序，使用某排序算法按 value 排序后，结果为：{3,'D'}, {3,'B'}, {5,'A'}, {5,'C'}，则这个排序算法是稳定的吗？

struct Card { int value; char suit; };
Card cards[4] = {{5,'A'}, {3,'B'}, {5,'C'}, {3,'D'}};

稳定，因为相同 value 的元素相对顺序保持不变
不稳定，因为 {3,'D'} 出现在 {3,'B'} 之前
无法判断
稳定，因为结果是有序的

17. 下面的函数 selectTopK() 实现从 n 个学生中选出前 k 名成绩最好的学生，则横线上应填写（）。

void selectTopK(Student students[], int n, int k) {
    for (int i = 0; i < k; i++) {
        int maxIdx = i;
        for ( ) {
            if (students[j].score > students[maxIdx].score) {
                maxIdx = j;
            }
        }
        if (maxIdx != i) {
            swap(students[i], students[maxIdx]);
        }
    }
}

int j = 0; j < n; j++
int j = i + 1; j < n; j++
int j = i; j < n; j++
int j = 1; j <= n; j++

18. 某游戏的排行榜系统需要实时更新玩家分数。每次只有一个玩家的分数发生变化，排行榜已经是按分数降序排列的。下面函数 updateRanking() 要实现上述功能，则两处横线上应分别填写（）。

void updateRanking(Player players[], int size, int playerIdx) {
    Player updatedPlayer = players[playerIdx];
    if (playerIdx > 0 && updatedPlayer.score > players[playerIdx - 1].score) {
        int i = playerIdx;
        while (____________________) {
            players[i] = players[i - 1];
            i--;
        }
        players[i] = updatedPlayer;
    }
    else if (playerIdx < size - 1 && updatedPlayer.score < players[playerIdx + 1].score) {
        int i = playerIdx;
        while (____________________) {
            players[i] = players[i + 1];
            i++;
        }
        players[i] = updatedPlayer;
    }
}

i > 0 && updatedPlayer.score > players[i - 1].score 和 i < size - 1 && updatedPlayer.score < players[i + 1].score
i < size - 1 && updatedPlayer.score < players[i + 1].score 和 i > 0 && updatedPlayer.score > players[i - 1].score
i > 0 && updatedPlayer.score < players[i - 1].score 和 i < size - 1 && updatedPlayer.score < players[i + 1].score
i > 0 && updatedPlayer.score < players[i - 1].score 和 i < size - 1 && updatedPlayer.score > players[i + 1].score

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

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

20. 冒泡排序和插入排序都是稳定的排序算法。（判断题）

正确
错误

21. 插入排序在最好情况（已有序）下的时间复杂度是 O(n²)。（判断题）

正确
错误

22. 对数组 arr[5]={4,3,1,5,2} 进行升序排序，执行第一轮选择排序后数组 arr 中的内容是 {1,4,3,5,2}。（判断题）

正确
错误

23. 无论初始数组是否有序，选择排序都执行 O(n²) 次比较。（判断题）

正确
错误

24. 以下C++代码，尝试对有 n 个整数的数组 arr 进行排序。这个代码实现了选择排序算法。（判断题）

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]);
}

正确
错误

25. 下面这段代码实现了选择排序算法。（判断题）

void sort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int x = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > x) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = x;
    }
}

正确
错误

26. 冒泡排序和插入排序都是稳定排序算法。（判断题）

正确
错误

27. 对整数数组 {4,1,3,1,5,2} 进行冒泡排序（将最大元素放到最后），执行一轮之后是 {4,1,3,1,2,5}。（判断题）

正确
错误

28. 虽然插入排序的时间复杂度为 O(n²)，但由于单元操作相对较少，因此在小数据量的排序任务中非常受欢迎。（判断题）

正确
错误

29. 选择排序是稳定的排序算法。（判断题）

正确
错误

30. 冒泡排序在任何情况下的时间复杂度都为 O(n²)。（判断题）

正确
错误

31. 如果给定数据部分有序，插入排序通常比选择排序效率更高。（判断题）

正确
错误

#6088. gesp四级真题分类五：排序算法

五、排序算法（共31题）

登录