#gesp4p24. 2024GESP四级 排序
2024GESP四级 排序
2024GESP四级 排序
2403真题
1.(2403-9)插入排序在最好情况下的时间复杂度是( )?
{{ select(1) }}
2406真题
2.(2406-7)关于直接插入排序,下列说法错误的是()?{{ select(2) }}
- 插⼊排序的最好情况是数组已经有序,此时只需要进行n-1次比较,时间复杂度为
- 最坏情况是数组逆序排序,此时需要进行n(n-1)/2次比较以及n-1次赋值操作(插入)
- 平均来说插入排序算法的复杂度为
- 空间复杂度上,直接插⼊法是就地排序,空间复杂度为
3.(2406-8)下列程序横线处,应该输入的是()?
#include<iostream>
using namespace std;
int n,a[10001];
void swap(int &a,int &b)
{
int t=a;
a=b;
b=t;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=n;i>1;i--)
for(int j=1;j<i;j++)
if(a[j]>a[j+1])
___________________;
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
{{ select(3) }}
- swap(a[j],a[j+1]);
- swap(a[j-1],a[j]);
- swap(a[j-1],a[j+1]);
- swap(&a[j-1],&a[j+1]);
4.(2406-10)关于几种排序算法的说法,下面说法错误的是()?{{ select(4) }}
- 选择排序不是⼀个稳定的排序算法
- 冒泡排序算法不是⼀种稳定的排序算法
- 插入排序是⼀种稳定的排序算法
- 如果排序前2个相等的数在序列中的前后位置顺序和排序后它们2个的前后位置顺序相同,则称为⼀种稳定的排序算法
5.(2406-11)数组{45,66,23,1,10,97,52,88,5,33}进⾏从⼩到⼤冒泡排序过程中,第⼀遍冒泡过后的序列是()?
{{ select(5) }}
- {45,23,1,10,66,52,88,5,33,97}
- {45,66,1,23,10,97,52,88,5,33}
- {45,66,23,1,10,52,88,5,33,97}
- {45,66,23,1,10,97,52,88,33,5}
6.(2406-12)下⾯的排序算法程序中,横线处应该填入的是()?
int a[8]={2,3,4,5,6,2,3,1};
for(int i=1;i<8;i++)
{
int key=a[i];
int j=i-1;
while(a[j]>key && j>=0)
{
________;
j-=1;
}
a[j+1]=key;
}
{{ select(6) }}
- a[j]=a[j-1]
- a[j]=a[j+1]
- a[j+1]=a[j-1]
- a[j+1]=a[j]
2409真题
7.(2409-10)在排序算法中,稳定性指的是( )?
{{ select(7) }}
- 排序后数据不会丢失
- 排序后相同元素的相对顺序保持不变
- 排序后数据不会被修改
- 排序后数据的时间复杂度不变
8.(2409-11)下面代码实现了冒泡排序函数,则横线上应填写( )?
//交换数组arr的第i个元素和第j个元素
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, i, j);
flag = true;
}
}
if (!flag)
break; // 此轮“冒泡”未交换任何元素
}
}
{{ select(8) }}
- 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--)
9.(2409-12)上一题算法的时间复杂度为( )? {{ select(9) }}
10.(2409-13)下面代码实现了插入排序函数(升序),则横线上应填写( )?
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;
}
}
{{ select(10) }}
- while (j >= 0 && nums[j] > base)
- while (j > 0 && nums[j] > base)
- while (j >= 0 && nums[j] < base)
- while (j > 0 && nums[j] < base)
2412真题
11.(2412-10)下面关于排序算法(冒泡排序、插入排序和选择排序)的描述中,不正确的是( )。?
{{ select(11) }}
- 冒泡排序基于元素交换实现,需借助临时变量,共涉及3个单元操作;而插入排序基于元素赋值实现,仅需1个单元操作。因此冒泡排序的计算开销通常比插入排序更高。
- 选择排序在任何情况下的时间复杂度都为 。
- 冒泡排序在任何情况下的时间复杂度都为。
- 如果给定数据部分有序,插入排序通常比选择排序效率更高。
12.(2412-11)冒泡排序的第一轮操作是从左到右遍历数组,通过两两比较相邻元素,将当前最大的元素移动到末尾。给定数组 arr[]={4, 1, 3, 1, 5, 2} ,执行第一轮冒泡排序后数组 arr 中的内容为( )。?
{{ select(12) }}
- 1, 4, 3, 1, 5, 2
- 1, 3, 1, 4, 2, 5
- 1, 4, 3, 1, 2, 5
- 4, 1, 3, 1, 5, 2
13.(2412-13)下面代码实现了插入排序函数,则横线上应填写( )?
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;
}
}
{{ select(13) }}
- 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;