#G095. GESP level4 排序算法

GESP level4 排序算法

GESP level4 - 排序算法

  1. 关于直接插入排序,下列说法错误的是() {{ select(1) }}
  • 插入排序的最好情况是数组已经有序,此时只需要进行n - 1次比较,时间复杂度为O(n)
  • 最坏情况是数组逆序排序,此时需要进行n(n - 1)/2次比较以及n - 1次赋值操作(插入)
  • 平均来说插入排序算法的复杂度为O(n²)
  • 空间复杂度上,直接插入法是就地排序,空间复杂度为O(n)
  1. 下列程序横线处,应该输入的是()
    1 #include
    2 using namespace std;
    3 int n,a[10001];
    4 void swap(int &a,int &b)
    5 {
    6     int t=a;
    7     a=b;
    8     b=t;
    9 }
    10 int main()
    11 {
    12     cin>>n;
    13     for(int i=1;i<=n;i++)
    14         cin>>a[i];
    15     for(int i=n;i>1;i--)
    16         for(int j=1;j<i;j++)
    17             if(a[j]>a[j + 1])
    18
    19 for(int i=1;i<=n;i++) 20 cout<<a[i]<<" "; 21 cout<<endl; 22 return 0; 23 }
    {{ select(2) }}
  • 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]);
  1. 关于几种排序算法的说法,下面说法错误的是( ) {{ select(3) }}
  • 选择排序不是一个稳定的排序算法
  • 冒泡排序算法不是一种稳定的排序算法
  • 插入排序是一种稳定的排序算法
  • 如果排序前2个相等的数在序列中的前后位置顺序和排序后它们2个的前后位置顺序相同,则称为一种稳定的排序算法
  1. 数组{45,66,23,1,10,97,52,88,5,33}进行从小到大冒泡排序过程中,第一遍冒泡过后的序列是( ) {{ select(4) }}
  • {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}
  1. 下面的排序算法程序中,横线处应该填入的是( )

    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)
    {</p>
    
     j -= 1;
    

    } a[j + 1]= key; }

    {{ select(5) }}

  • a[j]=a[j - 1];
  • a[j]=a[j + 1];
  • a[j + 1]=a[j - 1];
  • a[j + 1]=a[j];
  1. 对数组arr[]={5, 3, 8, 1}进行升序排序,执行第一轮冒泡排序后数组arr中的内容为( ) {{ select(6) }}
  • 3, 5, 1, 8
  • 3, 1, 5, 8
  • 3, 5, 8, 1
  • 5, 3, 8, 1
  1. 下面关于排序稳定性的描述,正确的是( ) {{ select(7) }}
  • 稳定性指算法的时间复杂度恒定
  • 稳定排序保证相同元素的相对顺序不变
  • 选择排序是稳定排序
  • 插入排序不是稳定排序
  1. 在排序算法中,稳定性指的是( ) {{ select(8) }}
  • 排序后数据不会丢失
  • 排序后相同元素的相对顺序保持不变
  • 排序后数据不会被修改
  • 排序后数据的时间复杂度不变
  1. 下面代码实现了冒泡排序函数,则横线上应填写( )
    1 //交换数组arr的第i个元素和第j个元素
    2 void swap(vector &arr, int i, int j)
    3 {
    4     arr[i] = arr[j];
    5     int tmp = arr[i];
    6     arr[j] = tmp;
    7 }
    8 int bubble_sort(vector &arr)
    9 {
    10     for (int i = arr.size() - 1; i > 0; i--)
    11     {
    12         bool flag = false; // 标志位
    13
    14 { 15 if (arr[j] > arr[j + 1]) 16 { 17 swap(arr, i, j); 18 flag = true; 19 } 20 } 21 if (!flag) break; // 此轮“冒泡”未交换任何元素 22 } 23 }
    {{ select(9) }}
  • 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--)
  1. 上一题算法的时间复杂度为( ) {{ select(10) }}
  • O(n)
  • O(n²)
  • O(n log n)
  • O(1)
  1. 下面代码实现了插入排序函数(升序),则横线上应填写( )
    1 void insertion_sort(vector &nums)
    2 {
    3     for (int i = 1; i < nums.size(); i++)
    4     {
    5         int base = nums[i], j = i - 1;
    6
    7 { 8 nums[j + 1] = nums[j]; 9 j--; 10 } 11 nums[j + 1] = base; 12 } 13 }
    {{ select(11) }}
  • while (j >= 0 && nums[j] > base)
  • while (j > 0 && nums[j] > base)
  • while (j >= 0 && nums[j] < base)
  • while (j > 0 && nums[j] < base)
  1. 冒泡排序在任何情况下的时间复杂度都为O(n²)。( ) {{ select(12) }}
  • 对
  • 错
  1. 冒泡排序和插入排序都是稳定的排序算法。( ) {{ select(13) }}
  • 对
  • 错
  1. 选择排序是稳定的排序算法。( ) {{ select(14) }}
  • 对
  • 错
  1. 对数组arr[]={4,3,1,5,2}进行升序排序,执行第一轮选择排序后数组arr中的内容是{1, 4, 3, 5, 2}。( ) {{ select(15) }}
  • 对
  • 错
  1. 插入排序在最好情况下的时间复杂度是O(n²)。( ) {{ select(16) }}
  • 对
  • 错
  1. 考虑最坏情况下冒泡排序算法的时间复杂度,T(n)为待排序数字的数目为n的复杂度,则其递推关系式为T(n)=T(n - 1)+n,T(0)=1。( ) {{ select(17) }}
  • 对
  • 错
  1. 对包含n个元素的数组进行冒泡排序,平均时间复杂度一般为( )。 {{ select(18) }}
  • O(n)
  • O(n log n)
  • O(n²)
  • 以上都不正确
  1. 冒泡排序的平均时间复杂度为O(n²),但最优情况下为O(n)。( ) {{ select(19) }}
  • 对
  • 错
  1. 插入排序在最好情况(已有序)下的时间复杂度是O(n²)。( ) {{ select(20) }}
  • 对
  • 错
  1. 如果待排序数据不能都装进内存,需要使用外排序算法。( ) {{ select(21) }}
  • 对
  • 错
  1. 对int a[]={2,0,2,4,3,1,6},执行第一趟选择排序处理后a中数据变为{0,2,2,4,3,1,6}。( ) {{ select(22) }}
  • 对
  • 错
  1. 下列排序算法中,不是稳定排序的是( )。 {{ select(23) }}
  • 冒泡排序
  • 插入排序
  • 选择排序
  • 以上都是稳定排序
  1. 在下列代码的横线处填写( ),完成对有n个int类型元素的数组array由小到大排序。
    void BubbleSort(int array[],int n){
    for(int i=n;i>=2;i--)
    for(__)//在此处填入代码
    if(array[j]>array[j+1]){
    int t=array[j];
    array[j]=array[j+1];
    array[j+1]=t;
    }
    }
    {{ select(24) }}
  • int j=1; j<n; j++
  • int j=0; j<n; j++
  • int j=0; j<i-1; j++
  • int j=0; j<i; j++
  1. 以下哪个排序算法在最坏情况下的时间复杂度最低?( ) {{ select(25) }}
  • 冒泡排序
  • 插入排序
  • 选择排序
  • 三者相同
  1. 排序算法的稳定性是指( )。 {{ select(26) }}
  • 相同元素在排序后的相对顺序保持不变
  • 排序算法的性能稳定,不随数据规模变化
  • 排序算法对任何输入都能正确工作
  • 排序算法的时间复杂度为常数
  1. 对数组arr[]={5,3,8,1}进行升序冒泡排序,第一轮排序后的结果是( )。 {{ select(27) }}
  • 3,5,1,8
  • 3,1,5,8
  • 5,3,1,8
  • 3,5,8,1