#gesp4p24. 2024GESP四级 排序

2024GESP四级 排序

2024GESP四级 排序

2403真题

1.(2403-9)插入排序在最好情况下的时间复杂度是( )?

{{ select(1) }}

  • O(1)O(1)
  • O(N/2)O(N/2)
  • O(N)O(N)
  • O(N2)O(N^2)

2406真题

2.(2406-7)关于直接插入排序,下列说法错误的是()?{{ select(2) }}

  • 插⼊排序的最好情况是数组已经有序,此时只需要进行n-1次比较,时间复杂度为O(n)O(n)
  • 最坏情况是数组逆序排序,此时需要进行n(n-1)/2次比较以及n-1次赋值操作(插入)
  • 平均来说插入排序算法的复杂度为O(n2)O(n^2)
  • 空间复杂度上,直接插⼊法是就地排序,空间复杂度为O(n)O(n)

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

  • O(n2)O(n^2)
  • O(2n)O(2^n)
  • O(1)O(1)
  • O(n)O(n)

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个单元操作。因此冒泡排序的计算开销通常比插入排序更高。
  • 选择排序在任何情况下的时间复杂度都为 O(n2)O(n^2)。
  • 冒泡排序在任何情况下的时间复杂度都为O(n2)O(n^2)。
  • 如果给定数据部分有序,插入排序通常比选择排序效率更高。

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;