#G114. GESP level5 分治算法

GESP level5 分治算法

GESP level5 - 分治算法

  1. 归并排序的基本思想是( )? {{ select(1) }}
  • 将数组分成两个子数组,分别排序后再合并
  • 随机选择一个元素作为枢轴,将数组划分为两个部分
  • 从数组的最后一个元素开始,依次与前一个元素比较并交换位置
  • 比较相邻的两个元素,如果顺序错误就交换位置
  1. 分治算法的核心思想是将一个大问题分解成多个相同或相似的子问题进行解决,最后合并得到原问题的解。( ) {{ select(2) }}
  • 对
  • 错
  1. 下面C++代码以递归方式实现合并排序,并假设merge(int T[], int R[], int s, int m, int t)函数将有序的T[s..m]和T[m+1..t]归并到R[s..t]中。横线处应填上代码是( )?
void mergeSort(int SList[],int TList[],int s,int t,int len) {
    if(s==t) {
        TList[s] = SList[s];
        return;
    }
    int*T2 = new int[len];//保存中间结果
    int m = (s + t) / 2;
    // 在此处填入代码
    merge(T2, SList, s, m, t);
    delete T2;
    return ;
}

{{ select(3) }}

  • mergeSort(SList, T2, s, m, len), mergeSort(SList, T2, m, t, len)
  • mergeSort(SList, T2, s, m-1, len), mergeSort(SList, T2, m+1, t, len)
  • mergeSort(SList, T2, s, m, len), mergeSort(SList, T2, m+1, t, len)
  • mergeSort(SList, T2, s, m-1, len), mergeSort(SList, T2, m-1, t, len)
  1. 下面的C++代码实现对list的快速排序,有关说法,错误的是( )?
vector operator +(vector lA, vector lB) {
    vector lst;
    for (int i = 1; i < lA.size(); i++)
        lst.push_back(lA[i]);
    for (int i = 1; i < lB.size(); i++)
        lst.push_back(lB[i]);
    return lst;
}
vector qSort(vector lst) {
    if (lst.size() < 2)
        return lst;
    int pivot = lst[0];
    vector less, greater;
    for (int i = 1; i < lst.size(); i++)
        if (lst[i] <= pivot)
            less.push_back(lst[i]);
        else
            greater.push_back(lst[i]);
    for (int i = 1; i < lst.size(); i++)
        if (lst[i] <= pivot)
            less.push_back(lst[i]);
        else
            greater.push_back(lst[i]);
    return 
}

{{ select(4) }}

  • qSort(less) + qSort(greater) + (vector)pivot
  • (vector)pivot + (qSort(less) + qSort(greater))
  • (qSort(less) + (vector)pivot + qSort(greater))
  • qSort(less) + pivot + qSort(greater)
  1. 归并排序的时间复杂度是O(N logN)。( ) {{ select(5) }}
  • 对
  • 错
  1. 下面代码用于归并排序,其中merge()函数被调用次数为( )?
#include 
using namespace std;
void mergeSort(int*listData,int start,int end);
void merge(int*listData,int start,int middle,int end);
void mergeSort(int*listData, int start,int end) {
    if(start >= end)
        return;
    int middle = (start + end) / 2;
    mergeSort(listData, start, middle);
    mergeSort(listData, middle + 1, end);
    merge(listData, start, middle, end);
}
void merge(int*listData,int start,int middle,int end) {
    int leftSize = middle - start + 1;
    int rightSize = end - middle;
    int*left = new int[leftSize];
    int*right = new int[rightSize];
    for (int i = 0; i < leftSize; i++)
        left[i] = listData[start + i];
    for (int j = 0; j < rightSize; j++)
        right[j] = listData[middle + 1 + j];
    int i = 0, j = 0, k = start;
    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j]) {
            listData[k] = left[i];
            i++;
        } else {
            listData[k] = right[j];
            j++;
        }
        k++;
    }
    while (i < leftSize)
        listData[k++] = left[i++];
    while (j < rightSize)
        listData[k++] = right[j++];
    delete[] left;
    delete[] right;
}
int main() {
    int lstA[] = {1, 3, 2, 7, 11, 5, 3};
    int size = sizeof(lstA) / sizeof(lstA[0]);
    mergeSort(lstA, 0, size - 1);
    for (int i = 0; i < size; i++)
        cout << lstA[i] << " ";
    cout << endl;
    return 0;
}

{{ select(6) }}

  • 0
  • 1
  • 6
  • 7
  1. 在上题的归并排序算法中,mergeSort(listData, start, middle);和mergeSort(listData, middle + 1, end);涉及到的算法为( )? {{ select(7) }}
  • 搜索算法
  • 分治算法
  • 贪心算法
  • 递推算法
  1. 归并排序算法的基本思想是( )? {{ select(8) }}
  • 将数组分成两个子数组,分别排序后再合并
  • 随机选择一个元素作为枢轴,将数组划分为两个部分
  • 从数组的最后一个元素开始,依次与前一个元素比较并交换位置
  • 比较相邻的两个元素,如果顺序错误就交换位置
  1. 下面C++代码用于排序,下列说法中错误的是( )?
void sortA(int*arr, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j  arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}
void sortB(int*arr, int start, int end) {
    if (start >= end)
        return;
    int middle = (start + end) / 2;
    sortB(arr, start, middle);
    sortB(arr, middle + 1, end);
    int leftSize = middle - start + 1;
    int rightSize = end - middle;
    int*left = new int[leftSize];
    int*right = new int[rightSize];
    for (int i = 0; i < leftSize; i++)
        left[i] = arr[start + i];
    for (int j = 0; j < rightSize; j++)
        right[j] = arr[middle + 1 + j];
    int i = 0, j = 0, k = start;
    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j])
            arr[k++] = left[i++];
        else
            arr[k++] = right[j++];
    }
    while (i < leftSize)
        arr[k++] = left[i++];
    while (j < rightSize)
        arr[k++] = right[j++];
    delete[] left;
    delete[] right;
}

{{ select(9) }}

  • 两种排序算法的时间复杂度不同
  • 两种排序算法的空间复杂度一致
  • sortA的时间复杂度在最好和最坏情况下都是O(n²)
  • sortB的平均时间复杂度、最好情况的时间复杂度都是O(n log n),最坏情况的时间复杂度是O(n²)
  1. 上一题中的sortB函数,明显体现出的算法思想和编程方法包括( )? {{ select(10) }}
  • 递归
  • 分治
  • A、B都正确
  • A、B都不正确
  1. 假设快速排序算法的输入是一个长度为n的已排序数组,且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项( )描述的是在这种情况下的快速排序行为? {{ select(11) }}
  • 快速排序对于此类输入的表现最好,因为数组已经排序
  • 快速排序对于此类输入的时间复杂度是O(n log n)
  • 快速排序对于此类输入的时间复杂度是O(n²)
  • 快速排序无法对此类数组进行排序,因为数组已经排序
  1. 考虑以下C++代码实现的归并排序算法:
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1)
        arr[k++] = L[i++];
    while (j < n2)
        arr[k++] = R[j++];
}
void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

对长度为n的数组arr,调用函数merge_sort(a, 0, n-1),在排序过程中merge函数的递归调用次数大约是( )? {{ select(12) }}

  • O(n)
  • O(n log n)
  • O(log n)
  • O(n²)
  1. 关于分治算法,以下哪个说法正确? {{ select(13) }}
  • 分治算法将问题分成子问题,然后分别解决子问题,最后合并结果
  • 归并排序不是分治算法的应用
  • 分治算法通常用于解决小规模问题
  • 分治算法的时间复杂度总是优于O(n log (n))
  1. 在快速排序中,选择的主元素(pivot)会影响算法的( )? {{ select(14) }}
  • 不影响
  • 时间复杂度
  • 空间复杂度
  • 时间复杂度和空间复杂度
  1. 归并排序的基本思想是( )? {{ select(15) }}
  • 将数组分成两个子数组,分别排序后再合并
  • 随机选择一个元素作为枢轴,将数组划分为两个部分
  • 从后往前逐步将每个元素插入到已排序数组中的合适位置
  • 每次从待排序数组中选择最小的元素放到已排序数组末尾
  1. 下面关于归并排序,描述正确的是( )? {{ select(16) }}
  • 归并排序是一个不稳定的排序算法
  • 归并排序的时间复杂度在最优、最差和平均情况下都是O(n log n)
  • 归并排序需要额外的O(1)空间
  • 对于输入数组{12, 11, 13, 5, 6, 7},代码输出结果为:7 6 5 13 12 11
  1. 为了正确实现快速排序,下面横线上的代码应为( )?
void qsort(vector& arr, int left, int right) {
    int i, j, mid;
    int pivot;
    i = left;
    j = right;
    mid = (left + right) / 2;
    pivot = arr[mid];
    do {
        while (arr[i]  pivot) j--;
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    } while (i <= j);
    if (left < j)
        qsort(arr, left, j);
    if (i < right)
        qsort(arr, i, right);
    // 在此处填入代码
}

{{ select(17) }}

  • while (i <= mid)
  • while (i < j)
  • while (i < mid)
  • while (i <= j)
  1. 若用二分法在[1, 100]内猜数,最多需要猜( )次? {{ select(18) }}
  • 100
  • 10
  • 7
  • 5