首页 › 题库 › GESP编程能力等级认证 › 7 分治算法

GESP-C++五级 题库

共 36 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 7 分治算法 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

下面代码实现了归并排序。下述关于归并排序的说法中,不正确的是( )。

void merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) { 
    int i = l, j = mid + 1, k = l; 
    while (i <= mid && j <= r) { 
        if (arr[i] <= arr[j]) temp[k++] = arr[i++]; 
        else temp[k++] = arr[j++]; 
    } 
    while (i <= mid) temp[k++] = arr[i++]; 
    while (j <= r) temp[k++] = arr[j++]; 
    for (int p = l; p <= r; p++) arr[p] = temp[p]; 
} 
void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) { 
    if (l >= r) return; 
    int mid = l + (r - l) / 2; 
    mergeSort(arr, temp, l, mid); 
    mergeSort(arr, temp, mid + 1, r); 
    merge(arr, temp, l, mid, r); 
}


A
归并排序的平均复杂度是O(nlogn)。
B
归并排序需要O(n)的额外空间。
C
归并排序在最坏情况的时间复杂度是O(n^2)。
D
归并排序适合大规模数据。
答案与解析
正确答案:C
归并排序通过分治法将数组递归分割至单个元素,再逐层合并有序子序列。每次合并操作比较两个已排序子区间元素,按序放入临时数组,最终复制回原数组。递归深度为logn量级,每层合并总耗时O(n),整体时间复杂度由递归树结构决定。算法执行过程中需辅助数组存储中间结果,空间开销与输入规模成正比。无论数据初始分布如何,拆分与合并过程的行为保持一致,其时间复杂度在最坏、平均和最好情况下均相同。大规模数据处理中,该算法表现出稳定的性能特征。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

下述C++代码实现了快速排序算法,下面说法错误的是( )。

A

. 快速排序之所以叫“快速”,是因为它在平均情况下运行速度较快,常数小、就地排序,实践中通常比归并排序更高效。

B

在平均情况下,划分的递归层数为 log n,每层中的总循环数为 ,总时间为 O(nlog n)。

C

在最差情况下,每轮划分操作都将长度为 的数组划分为长度为 0 和 n-1的两个子数组,此时递归层数达到 n,每层中的循环数为 ,总时间为 。

D

划分函数 partition 中“从右往左查找”与“从左往右查找”的顺序可以交换

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

下述C++代码实现了归并排序算法,则横线上应填写( )

A

i < mid

B

j < right

C

i <= mid

D

j <= right

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

关于下述C++代码的快速排序算法,说法【错误】的是?( )

int randomPartition(std::vector<int>& arr, int low, int high) {
    int random = low + rand() % (high - low + 1);
    std::swap(arr[random], arr[high]);
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = randomPartition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
A
在 randomPartition 函数中,变量 i 的作用是记录大于基准值的元素的边界
B
randomPartition 函数随机选择基准值,可以避免输入数据特定模式导致的最坏情况下时间复杂度
C
快速排序平均时间复杂度是 O(n log n)
D
快速排序是稳定排序算法
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

考虑以下C++代码实现的快速排序算法,将数据从小到大排序,则横线上应填的最佳代码是?( )

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 基准值
    int i = low - 1;
    for (int j = low; j < high; j++) {
        ____________________ // 在此处填入代码
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}
// 快速排序
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
A
if (arr[j] > pivot) {
    i++;
    swap(arr[i], arr[j]);
}
B
if (arr[j] < pivot) {
    i++;
    swap(arr[i], arr[j]);
}
C
if (arr[j] < pivot) {
    swap(arr[i], arr[j]);
    i++;
}
D
if (arr[j] == pivot) {
    i++;
    swap(arr[i], arr[j]);
}
答案与解析
正确答案:B

快速排序是一种分治算法,其基本步骤如下:

选择基准:从数组中选择一个元素作为基准(通常选择最后一个元素)。

分区:重新排列数组,使得所有比基准小的元素放在基准前面,所有比基准大的元素放在基准后面。分区完成后,基准就位于其最终排序后的正确位置。

递归排序:递归地对基准前后的子数组进行快速排序。

在分区过程中:

i初始化为low - 1,表示小于基准的区域最初为空。

j从low到high - 1遍历数组。

如果arr[j]小于pivot,则i增加1,并将arr[i]和arr[j]交换。这样,arr[i]现在是一个小于pivot的元素。

本题答案为选项B。

题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

考虑以下C++代码实现的快速排序算法:

int partition(vector<int>& arr, int left, int right) {
	int pivot = arr[right]; // 基准值
	int i = left - 1;
	
	for (int j = left; j < right; j++) {
		if (arr[j] < pivot) {
			i++;
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[i + 1], arr[right]);
	return i + 1;
}

// 快速排序
void quickSort(vector<int>& arr, int left, int right) {
	if (left < right) {
		int pi = partition(arr, left, right);
		quickSort(arr, left, pi - 1);
		quickSort(arr, pi + 1, right);
	}
}

以下关于快速排序的说法,正确的是( )。

A
快速排序通过递归对子问题进行求解。
B
快速排序的最坏时间复杂度是 O(nlogn)。
C
快速排序是一个稳定的排序算法。
D
在最优情况下,快速排序的时间复杂度是 O(n)。
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

下面关于归并排序,描述正确的是( )。

A
归并排序是一个不稳定的排序算法。
B
归并排序的时间复杂度在最优、最差和平均情况下都是 (nlogn)。
C
归并排序需要额外的 O(1) 空间。
D
对于输入数组 {12, 11, 13, 5, 6, 7},代码输出结果为:7 6 5 13 12 11。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

关于分治算法,以下说法中不正确的是( )。

A
分治算法将问题分成子问题,然后分别解决子问题,最后合并结果。
B
归并排序采用了分治思想。
C
快速排序采用了分治思想。
D
冒泡排序采用了分治思想。
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

假设快速排序算法的输入是一个长度为 n 的已排序数组,且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项( )描述的是在这种情况下的快速排序行为。

A
快速排序对于此类输入的表现最好,因为数组已经排序。
B
快速排序对于此类输入的时间复杂度是 O(nlogn)。
C
快速排序对于此类输入的时间复杂度是O(n2)。
D
快速排序无法对此类数组进行排序,因为数组已经排序。
答案与解析
正确答案:C

快速排序的过程是,每次选择一个基准值,比基准值大的放到它的右边 ,比基准值小的放到它的左边,但是这个序列是一个有序序列,且每次都是选择最小的元素作为基准值,所以每次所有的值都会放到基准值的右边,也就是说,每次都只是把基准值这个位置排序好。

题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.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];
		i++;
		k++;
	}
	
	while (j < n2) {
		arr[k] = R[j];
		j++;
		k++;
	}
}

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 函数的递归调用次数大约是( )。

A
O(1)
B
O(n)
C
O(logn)
D
O(nlogn)
答案与解析
正确答案:B

merge_sort函数的作用是递归进行分治的过程,每次把序列分成两半,然后分别处理,merge函数的作用是把两个有序序列,通过双指针操作,合并为一个有序序列。merge函数的调用次数,先是两个数的合并,执行次数为n/2,然后是4个数合并,执行次数为n/4……大约为O(n)

题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

关于分治算法,以下哪个说法正确?

A
分治算法将问题分成子问题,然后分别解决子问题,最后合并结果。(2024.9-5)
B
归并排序不是分治算法的应用。
C
分治算法通常用于解决小规模问题。
D
分治算法的时间复杂度总是优于 O(nlog(n))。
答案与解析
正确答案:A

分治算法的思想就是把问题划分成子问题,然后继续划分,知道子问题可以直接解决,然后合并子问题得到的结果,推到原问题的答案。

B选项:归并排序的思想就是分治。

D选项:分治算法划分子问题的时间一般为logn,总的时间复杂度常为O(nlogn),如归并排序。

题目详情
12 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

为了正确实现快速排序,下面横线上的代码应为( )。

void qsort(vector<int>& 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) i++;
		while (arr[j] > pivot) j--;
		if (i <= j) {
			swap(arr[i], arr[j]); // 交换两个元素
			i++; j--;
		}
	} ________________________________; // 在此处填入代码
	if (left < j) qsort(arr, left, j); // 对左子数组进行快速排序
	if (i < right) qsort(arr, i, right); // 对右子数组进行快速排序
}
A
while (i <= mid)
B
while (i < mid)
C
while (i < j)
D
while (i <= j)
答案与解析
正确答案:D

快速排序的分区过程中,我们使用两个指针i和j分别从左到右和从右到左遍历数组,将小于基准值的元素放到基准值的左边,大于基准值的元素放到右边。

具体的分区过程如下:

首先选择一个基准值pivot,通常选择中间元素arr[mid]。

使用两个指针i和j,分别从数组的左右两端开始向中间移动。

i从左向右移动,直到找到一个大于或等于pivot的元素。

j从右向左移动,直到找到一个小于或等于pivot的元素。

如果i <= j,则交换arr[i]和arr[j],然后i向后移动一位,j向前移动一位。

重复步骤2和3,直到i大于j,此时所有小于等于pivot的元素都在pivot的左边,所有大于等于pivot的元素都在pivot的右边。

在填写横线上的代码时,应该使用while (i <= j),因为分区过程应该持续进行直到i超过j,这样保证了整个分区过程的完成。

题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

关于分治算法,以下哪个说法正确?

A
分治算法将问题分成子问题,然后分别解决子问题,最后合并结果。
B
归并排序不是分治算法的应用。
C
分治算法通常用于解决小规模问题。
D
分治算法的时间复杂度总是优于 O(nlog(n))。
答案与解析
正确答案:A

分治算法的基本思想是将原问题分解成若干个规模较小但结构与原问题相似的子问题,递归地求解这些子问题,然后再合并其结果,得到原问题的解。

题目详情
14 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

设A和B是两个长度为n的有序数组,现将A和B合并成一个有序数组,归并排序算法在最坏情况下至少要做( )次比较。

A
n2
B
nlogn
C
2n−1
D
n
答案与解析
正确答案:C

在最坏情况下,两个数组的元素需要逐个比较,直到其中一个数组的所有元素都放入新数组中。当一个数组的所有元素都被放入新数组后,剩下的数组中的元素不需要再与新数组中的元素比较,因此剩余的比较操作可以省略。因此,总的比较次数是n+(n−1),即2n−1

题目详情
15 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

归并排序的基本思想是(   )。

A
动态规划
B
分治
C
贪心算法
D
回溯算法
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
16 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

在快速排序中,选择的主元素(pivot)会影响算法的(   )。

A
不影响
B
时间复杂度
C
空间复杂度
D
时间复杂度和空间复杂度
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
17 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

下面C++代码以递归方式实现合并排序,并假设 merge (int T[], int R[], int s, int m, int t) 函数将有序(同样排序规则)的T[s..m]和T[m+1..t]归并到R[s..t]中。横线处应填上代码是(   )。

A

mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m,t,len)

B

mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m+1,t,len)

C

mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m+1,t,len)

D

mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m-1,t,len)

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
18 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

下面的C++代码实现对list的快速排序,有关说法,错误的是(   )。

A

qSort(less) + qSort(greater) + (vector<int>)pivot

B

(vector<int>)pivot + (qSort(less) + qSort(greater))

C

(qSort(less) + (vector<int>)pivot + qSort(greater))

D

qSort(less) + pivot + qSort(greater)

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
19 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

下面代码用于归并排序,其中 merge() 函数被调用次数为(     )。

A
0
B
1
C
6
D
7
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
20 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

在上题的归并排序算法中, mergeSort(listData, start, middle); 和 mergeSort(listData, middle+ 1, end); 涉及到的算法为(     )。

A
搜索算法
B
分治算法
C
贪心算法
D
递推算法
答案与解析
正确答案:B
这道题暂未补解析。
题目详情