首页 › 题库 › GESP编程能力等级认证 › 2.1 多项式复杂度

GESP-C++五级 题库

共 17 道题 · 按题型筛选,点「查看答案」核对解析
章节 2.1 多项式复杂度 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

下述C++代码实现了快速排序算法,最坏情况的时间复杂度是( )。

int partition(vector<int>& arr, int low, int high) { 
    int i = low, j = high; 
    int pivot = arr[low]; // 以首元素为基准 
    while (i < j) { 
        while (i < j && arr[j] >= pivot) j--; 
        while (i < j && arr[i] <= pivot) i++; 
        if (i < j) swap(arr[i], arr[j]); 
    } 
    swap(arr[i], arr[low]); 
    return i; 
} 
void quickSort(vector<int>& arr, int low, int high) { 
    if (low >= high) return; 
    int p = partition(arr, low, high); 
    quickSort(arr, low, p - 1); 
    quickSort(arr, p + 1, high); 
}
A
O(n)
B
O(logn)
C
O(n^2)
D
O(nlogn)
答案与解析
正确答案:C
分析分区函数的划分逻辑,观察基准元素的选择方式及其在序列中的位置变化。考察每次划分时左右子区间的规模分布,特别是当输入序列已有序或逆序时,基准元素是否总位于子区间一端。根据递归调用的深度与每层处理的数据量,推导出总的比较和移动操作次数的增长趋势。结合划分过程的循环执行次数与递归树的层数,确定时间复杂度的上界表达式。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

下面函数可以将 n 的所有质因数找出来,其时间复杂度是( )。

#include <iostream>
#include <vector>

vector<int> get_prime_factors(int n) {
	vector<int> factors;
	
	while (n % 2 == 0) {
		factors.push_back(2);
		n /= 2;
	}
	
	for (int i = 3; i * i <= n; i += 2) {
		while (n % i == 0) {
			factors.push_back(i);
			n /= i;
		}
	}
	
	if (n > 2) {
		factors.push_back(n);
	}
	
	return factors;
}


A
O(n2)
B
O(nlogn)
C
D
O(n)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

现在用如下代码来计算xn(n个x相乘),其时间复杂度为( )。

double quick_power(double x, unsigned n) {
	if (n == 0) return 1;
	if (n == 1) return x;
	return quick_power(x, n / 2) * quick_power(x, n / 2) * ((n & 1) ? x : 1);
}


A
O(n)
B
O(n2)
C
O(logn)
D
O(nlogn)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

小杨采用如下双链表结构保存他喜欢的歌曲列表:

struct dl_node {
	string song;
	dl_node* next;
	dl_node* prev;
};

小杨想在头指针为 head 的双链表中查找他喜欢的某首歌曲,采用如下查询函数,该操作的时间复杂度为( )。

dl_node* search(dl_node* head, string my_song) {
	dl_node* temp = head;
	while (temp != nullptr) {
		if (temp->song == my_song)
			return temp;
		temp = temp->next;
	}
	return nullptr;
}
A
O(1)
B
O(n)
C
O(logn)
D
O(n2)
答案与解析
正确答案:B

该查询函数的时间复杂度为O(n),其中n是双链表中节点的数量。

函数使用一个指针temp从头指针head开始,沿着双链表向后遍历。

在每个节点处,它检查节点中的歌曲名称是否与目标歌曲my_song匹配。

最坏情况下,如果目标歌曲不在双链表中或者在最后一个节点才找到,那么需要遍历整个双链表,因此时间复杂度为O(n)

这是因为在最坏情况下,需要遍历所有n个节点才能确定目标歌曲是否存在。

题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

上题代码的时间复杂度是( )。

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

linear_sieve 函数的主要执行部分是主循环,(for (int i = 2; i <= n; ++i)):主循环从2到n进行遍历,因此有O(n)次迭代

题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是(   )?

int fibonacci(int n) {
	if (n <= 1) {
		return n;
	} else {
		return fibonacci(n - 1) + fibonacci(n - 2);
	}
}
A
O(1)
B
O(n)
C
O(2n)
D
O(logn)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

在上题的 _binarySearch 算法中,如果 lst 中有 N 个元素,其时间复杂度是(   )。

A

O(N)

B

O(logN)

C

O(NlogN)

D

O(N2)

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
8 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

以下 fib 函数计算第 n 项斐波那契数( fib(0)=0 , fib(1)=1 ),其时间复杂度为为O(n)。

int fib(int n) { 
    if (n <= 1) return n; 
    return fib(n-1) + fib(n-2); 
}
A
对
B
错
答案与解析
正确答案:错
分析函数的递归调用结构,识别是否存在重复计算。若函数使用循环或递归但未优化,需统计每层递归或每次迭代的执行次数。考察输入n与基本操作执行频次的关系,确定时间复杂度是否随n线性增长。检查是否有记忆化机制或动态规划思想减少冗余计算。对比标准O(n)实现方式,确认其状态转移是否仅依赖前两项且每个状态仅计算一次。
题目详情
9 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

下面递归实现的斐波那契数列的时间复杂度为 。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
10 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

下面代码采用分治算法求解标准 3 柱汉诺塔问题,时间复杂度为 。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
11 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

快速排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )

A
对
B
错
答案与解析
正确答案:错

快速排序的 平均时间复杂度为 O(nlog?n),但最坏情况下退化为 O(n^2)。

其性能与输入数据是否有序及 pivot 选择策略密切相关。

题目详情
12 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

快速排序的时间复杂度总比插入排序的时间复杂度低。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
13 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

插入排序的时间复杂度总是比快速排序低。

A
对
B
错
答案与解析
正确答案:错

插入排序的时间复杂度为O(n2),快速排序的均摊时间复杂度为O(nlogn),但是快速排序的最坏情况下,时间复杂度也是O(n2)

题目详情
14 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

插入排序有时比快速排序时间复杂度更低。

A
对
B
错
答案与解析
正确答案:对

插入排序在处理少量元素或部分有序数组时,由于其较低的时间复杂度可能比快速排序效率更高,而快速排序通常在处理大规模随机数据时表现更佳

题目详情
15 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

插入排序的时间复杂度是O(NlogN)。(   )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
16 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

插入排序有时比快速排序时间复杂度更低。(   )(2023年12月C++五级)

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
17 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

同样的整数序列分别保存在单链表和双向链中,这两种链表上的简单冒泡排序的复杂度相同。(   )(2023年12月C++五级)

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情