#gesp4p25. 2025GESP四级 排序

2025GESP四级 排序

2025GESP四级 排序

2503真题

1.(2503-12)下面关于排序稳定性的描述,正确的是( )?

{{ select(1) }}

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

2.(2503-13)对数组 arr[]={5, 3, 8, 1} 进行升序排序,执行第一轮冒泡排序后数组 arr 中的内容为( )。?

{{ select(2) }}

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

2506真题

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

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

4.(2506-9)以下哪种情况是使用插入排序的合适场景? {{ select(4) }}

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

5.(2506-10)为了提高冒泡排序的效率,如果某轮“冒泡”中没有执行任何交换操作,说明数组已经完成排序,可直接返回结果,则两条横线上分别应该填写( )?

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(5) }}

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

2509真题

6.(2509-9)关于排序算法的稳定性,以下说法错误的是( )? {{ select(6) }}

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

7.(2509-10)下面代码试图实现选择排序,使其能对数组 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;
            }
        }
        ____________________; // 在此处填入代码
    }
}

{{ select(7) }}

  • 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])
    

8.(2509-11)下面程序实现插入排序(升序排序),则横线上应分别填写( )?

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--;
        }
        ____________________; // 在此处填入代码
    }
}

{{ select(8) }}

  • 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
    

9.(2509-12)关于插入排序的时间复杂度,下列说法正确的是( )? {{ select(9) }}

  • 最好情况和最坏情况的时间复杂度都是O(n2)O(n^2)
  • 最好情况是O(n)O(n),最坏情况是O(n2)O(n^2)
  • 最好情况是O(n)O(n),最坏情况是O(2n)O(2^n)
  • 最好情况是O(n2)O(n^2),最坏情况是O(2n)O(2^n)

2512真题

10.(2512-10)对如下4个扑克牌进行排序,

struct Card {
    int value;
    char suit; // 花色
};

Card cards[4] = {{5,'A'}, {3,'B'}, {5,'C'}, {3,'D'}};

使用某排序算法按value排序后,结果为: {3,'D'}, {3,'B'}, {5,'A'}, {5,'C'} ,则这个排序算法是稳定的吗?

{{ select(10) }}

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

11.(2512-11)下面的函数 selectTopK() 实现从 n 个学生中选出前 k 名成绩最好的学生颁发奖学金(不需要对所有学生完全排序,只需要找出前 k 名),则横线上应填写( )

struct Student {
    string name;
    int score;
};

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) {
            Student temp = students[i];
            students[i] = students[maxIdx];
            students[maxIdx] = temp;
        }
    }
}

{{ select(11) }}

  • 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++

12.(2512-12)某游戏的排行榜系统需要实时更新玩家分数。每次只有一个玩家的分数发生变化,排行榜已经是按分数降序排列的。现在需要将更新后的玩家调整到正确位置。下面的函数 updateRanking() 要实现上述功能,则两处横线上应分别填写( )

struct Player {
    string name;
    int score;
};
// 玩家索引playerIdx的分数刚刚更新,需要调整位置
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;
    }
}

{{ select(12) }}

  • 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