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

GESP-C++八级 题库

共 46 道题 ,第 1 / 3 页 · 按题型筛选,点「查看答案」核对解析
章节 7 算法效率分析 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下列代码的时间复杂度(以 为自变量,忽略常数与低阶项)是( )。

long long s = 0; 
for (int i = 1; i <= n; i++) { 
    for (int j = 1; j * j <= i; j++) { 
      s += j; 
     } 
}
A
O(n)
B
O(n log n)
C
O(n√n)
D
O(n^2)
答案与解析
正确答案:C
分析外层循环的执行次数,确定其控制变量的变化规律。观察内层循环的条件表达式,推导每次外层循环迭代时内层循环的执行次数。将内外层循环的执行次数相乘,得到总操作次数的数量级。忽略常数因子与低阶项,提取最高次项以表示时间复杂度。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

对一个包含V个顶点、E条边的图,执行广度优先搜索,其最优时间复杂度是( )。

A

O(V)

B

O(V+E)

C

O(V^2)

D

O(E)

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面程序的时间复杂度为( )。

int primes[MAXP], num = 0; 
bool isPrime[MAXN] = {false}; 
void sieve() { 
        for (int n = 2; n <= MAXN; n++) { 
                if (!isPrime[n]) 
                        primes[num++] = n; 
                for (int i = 0; i < num && n * primes[i] <= MAXN; i++) { 
                        isPrime[n * primes[i]] = true; 
                        if (n % primes[i] == 0) 
                                break; 
                } 
        } 
}


A

O(nlogn)

B

O(nloglogn)

C

O(n)

D

O(logn)

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下列Dijkstra算法,假设图graph中顶点数v、边数e,则程序的时间复杂度为( )。

A

O(v^2)

B

O(vlogv+e)

C

O(v+e)logv

D

O(v+e)

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面 count_triple 函数的时间复杂度为( )。

A

O(n^2)

B

O(n^2logn)

C

O(n)

D

O(nlogn)

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

n 个结点的二叉树,执行广度优先搜索的平均时间复杂度是?( )

A
O(log n)
B
O(n log n)
C
O(n)
D
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面的 sum_digit 函数试图求出从 1 到 n (包含 1 和 n )的数中,包含数字 d 的个数。该函数的时间复杂度为?( )

#include <string>
int count_digit(int n, char d) {
    int cnt = 0;
    std::string s = std::to_string(n);
    for (int i = 0; i < s.length(); i++)
        if (s[i] == d)
            cnt++;
    return cnt;
}
int sum_digit(int n, char d) {
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += count_digit(i, d);
    return sum;
}
A
O(n log n)
B
O(n)
C
O(log n)
D
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面 count_triple 函数的时间复杂度为?( )

nt gcd(int a, int b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
int count_triple(int n) {
    int cnt = 0;
    for (int v = 1; v * v * 4 <= n; v++)
        for (int u = v + 1; u * (u + v) * 2 <= n; u += 2)
            if (gcd(u, v) == 1) {
                int a = u * u - v * v;
                int b = u * v * 2;
                int c = u * u + v * v;
                cnt += n / (a + b + c);
            }
    return cnt;
}
A
O(n)
B
C
O(n log n)
D
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面 LIS 函数试图求出最长上升子序列的长度,其时间复杂度为?( )

#define INT_MIN (-1000)
int LIS(vector<int> & nums) {
    int n = nums.size();
    vector<int> tail;
    tail.push_back(INT_MIN);
    for (int i = 0; i < n; i++) {
        int x = nums[i], l = 0, r = tail.size();
        while (l < r) {
            int mid = (l + r) / 2;
            if (tail[mid] < x)
                l = mid + 1;
            else
                r = mid;
        }
        if (r == tail.size())
            tail.push_back(x);
        else
            tail[r] = x;
    }
    return tail.size() - 1;
}
A
O(log n)
B
O(n)
C
O(n log n)
D
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

2025 是个神奇的数字,因为它是由两个数 20 和 25 拼接而成,而且 2025 =(20+25)2 。小杨决定写个程序找找小于 N 的正整数中共有多少这样神奇的数字。

该函数的时间复杂度为?( )

#include <string>
int count_miracle(int N) {
    int cnt = 0;
    for (int n = 1; n * n < N; n++) {
        int n2 = n * n;
        std::string s = std::to_string(n2);
        for (int i = 1; i < s.length(); i++)
            if (s[i] != '0') {
                std::string sl = s.substr(0, i);
                std::string sr = s.substr(i);
                int nl = std::stoi(sl);
                int nr = std::stoi(sr);
                if (_________) // 在此处填入选项
                    cnt++;
            }
    }
    return cnt;
}
A
O(N log N)
B
C
D
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面Floyd算法程序的时间复杂度为?( )

#include <iostream>
using namespace std;
#define N 21
#define INF 99999999
int map[N][N];
int main() {
    int n, m, t1, t2, t3;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)
                map[i][j] = 0;
            else
                map[i][j] = INF;
        }
    }
    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2 >> t3;
        map[t1][t2] = t3;
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (map[i][j] > map[i][k] + map[k][j])
                    ________; // 在此处填入选项
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout.width(4);
            cout << map[i][j];
        }
        cout << endl;
    }
}
A
O(N)
B
C
D
答案与解析
正确答案:C

22, 23 ,24 行,循环共执行 o(n3) 次。(图论算法:  Floyd 算法)

题目详情
12 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下列程序实现了输出杨辉三角形,其时间复杂度为?( )

#include <iostream>
using namespace std;
#define N 35
int a[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        a[i] = 1;
        for (int j = i - 1; j > 0; j--)
            ________; // 在此处填入选项
        for (int j = 0; j <= i; j++)
            cout << a[j] << " ";
        cout << endl;
    }
    return 0;
}
A
O(n)
B
O(n log n)
C
D
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

假设图graph中顶点数v、边数e,上题程序的时间复杂度为( )。

A

O(e)

B

O(v2)

C

O(vlogv+e)

D

O((v+e)logv)

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
14 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

上题程序的时间复杂度为( )。

A
O(n)
B
O(n2)
C
O(2n)
D
O(nlogn)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
15 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

n个结点的二叉树,执行释放全部结点操作的时间复杂度是( )。

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

对二叉树执行DFS,在回溯阶段依次释放每个节点,复杂度O(n)。

题目详情
16 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面程序的 Merge_Sort 函数时间复杂度为( )。

void Merge(int a[], int left, int mid, int right) {
	int temp[right - left + 1];
	int i = left;
	int j = mid + 1;
	int k = 0;
	while (i <= mid && j <= right) {
		if (a[i] < a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}
	while (i <= mid)
		temp[k++] = a[i++];
	while (j <= right)
		temp[k++] = a[j++];
	for (int m = left, n = 0; m <= right; m++, n++)
		a[m] = temp[n];
}
void Merge_Sort(int a[], int left, int right) {
	if (left == right)
		return;
	int mid = (left + right) / 2;
	Merge_Sort(a, left, mid);
	Merge_Sort(a, mid + 1, right);
	Merge(a, left, mid, right);
}
A
O(nlogn)
B
O(n2)
C
O(2n)
D
O(logn)
答案与解析
正确答案:A

归并排序基于分治

时间复杂度为O(nlogn)。空间复杂度O(n);

题目详情
17 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面 fibonacci 函数的时间复杂度为( )。

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

有V个顶点、E条边的图的深度优先搜索遍历时间复杂度为( )。

A
O(V)
B
O(E)
C
O(V+E)
D
O(log(V+E))
答案与解析
正确答案:C

每个顶点每条边都会被访问一次,所有时间复杂度是C。

题目详情
19 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面程序的时间复杂度为( )。

bool notPrime[N] = {false};
void sieve() {
	for (int n = 2; n * n < N; n++)
		if (!notPrime[n])
			for (int i = n * n; i < N; i += n)
				notPrime[i] = true;
}
A
O(N)
B
O(N×logN)
C
O(N×loglogN)
D
O(N2)
答案与解析
正确答案:C

代码是求欧拉筛,参数有些优化,时间复杂度是C。

题目详情
20 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

下面程序的最差时间复杂度为( )。

int gcd(int m, int n) {
	if (m == 0)
		return n;
	return gcd(n % m, m);
}
A
B
O(log(n))
C
O(n)
D
O(1)
答案与解析
正确答案:B

欧几里得算法的最坏时间复杂度。在最坏的情况,m和n为菲波那切数列中相邻的两项,所以时间复杂度是O(logn)。

题目详情