#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) }}
- 最好情况和最坏情况的时间复杂度都是
- 最好情况是,最坏情况是
- 最好情况是,最坏情况是
- 最好情况是,最坏情况是
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