首页 › 题库 › GESP编程能力等级认证 › GESP-C++八级

GESP-C++八级 题库

共 270 道题 ,第 3 / 14 页 · 按题型筛选,点「查看答案」核对解析
41 单选题 适中 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
这道题暂未补解析。
题目详情
42 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

下面 quick_sort 函数试图实现快速排序算法,两处横线处分别应该填入的是?( )

void swap(int & a, int & b) {
    int temp = a;
    a = b;
    b = temp;
}
int partition(int a[], int l, int r) {
    int pivot = a[l], i = l + 1, j = r;
    while (i <= j) {
        while (i <= j && a[j] >= pivot)
            j--;
        while (i <= j && a[i] <= pivot)
            i++;
        if (i < j)
            swap(a[i], a[j]);
    }
    ________; // 在此处填入选项
    return ________; // 在此处填入选项
}
void quick_sort(int a[], int l, int r) {
    if (l < r) {
        int pivot = partition(a, l, r);
        quick_sort(a, l, pivot - 1);
        quick_sort(a, pivot + 1, r);
    }
}
A
swap(a[l], a[i])i
B
swap(a[l], a[j])i
C
swap(a[l], a[i])j
D
swap(a[l], a[j])j
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
43 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

下面 LIS 函数试图求出最长上升子序列的长度,横线处应该填入的是?( )

int max(int a, int b) {
    return (a > b) ? a : b;
}
int LIS(vector<int> & nums) {
    int n = nums.size();
    if (n == 0)
        return 0;
    vector<int> dp(n, 1);
    int maxLen = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i])
                ________; // 在此处填入选项
        maxLen = max(maxLen, dp[i]);
    }
    return maxLen;
}
A
dp[j] = max(dp[j] + 1, dp[i])
B
dp[j] = max(dp[j], dp[i] + 1)
C
dp[i] = max(dp[i] + 1, dp[j])
D
dp[i] = max(dp[i], dp[j] + 1)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
44 单选题 适中 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
这道题暂未补解析。
题目详情
45 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

下面的程序使用邻接矩阵表达的带权无向图,则从顶点0到顶点3的最短距离为?( )

int weight[4][4] = {
    { 0, 5, 8, 10},
    { 5, 0, 1, 7},
    { 8, 1, 0, 3},
    {10, 7, 3, 0}
};
A
9
B
10
C
11
D
12
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
46 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

国家“以旧换新”政策仍在继续,小杨家决定在家里旧的冰箱、电视、洗衣机、微波炉中选两种换新。

其中,冰箱有4种型号可选,电视有6种型号可选,洗衣机有3种型号可选,微波炉有5种型号可选。

请问小杨家共有多少种换新的方案?( )

A
18
B
119
C
238
D
360
答案与解析
正确答案:B

根据乘法原理和加法原理,答案为 4x6 4x3+4x5+6x3+6x5+3x5 = 119。(计数原理、排列组合)

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

小杨和3位朋友约好一起去看电影“哪吒2”。打开购票软件,他们发现,已经没有同一排连续的四个座位了(图中每个方框代表一个座位,红色方框代表已经售出)。

朋友们商量了一下,决定分为两组,每组两人在同一排的相邻两个座位,且两组之间至少有一对座位是前后相邻的。请问共有多少种购票方案?( )

A
495
B
96
C
7
D
4
答案与解析
正确答案:C

根据题面可以数出—共 7 种购票方案。(计数原理、排列组合

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

下面关于C++类构造和析构函数的说法,错误的是?( )

A
构造函数不能声明为虚函数。
B
析构函数必须声明为虚函数。
C
类的默认构造函数可以被声明为private。
D
类的析构函数可以被声明为private。
答案与解析
正确答案:B

析构函数不—定必须是虚函数,当类有虚函数并且可能被继承时才必须声明为虚函数。(面向对象:类的相 关概念)

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

下列关于树和图的说法,【错误】的是?( )

A
树是一种有向无环图,有向无环图都是一棵树。
B
如果把树看做有向图,每个节点指向其子节点,则该图是弱连通图。
C
N个顶点且连通的无向图,其最小生成树一定包含N-1个条边。
D
N+1个顶点、 N条边的有向图,一定不是强连通的。
答案与解析
正确答案:A

有向的树才可以看作有向无环图,有向无环图不—定是树。(树图结构)

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

从1到2025这2025个数中,包含数字5的个数?( )

A
600
B
601
C
602
D
603
答案与解析
正确答案:D

个位为 5 的数有 203 个,十位为 5 的数有 20  x  10 = 200 个,百位为 5 的数有 2  x  100 = 200 个,—共 有 603 个。(计数原理、排列组合)

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

已定义 double 类型的变量 r 和 theta ,分别表示图中圆半径和圆心角。下列表达式中可以求出弦长 s 的是?( )

A
r * cos(theta)
B
r * cos(theta / 2) * 2
C
r * sin(theta)
D
r * sin(theta / 2) * 2
答案与解析
正确答案:D

从圆心向弦做垂线,由垂线定理可以得到答案为D

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

个节点的平衡二叉树的高为?( )

A
B
C
D
无法确定。
答案与解析
正确答案:D

平衡二叉树的形态不固定,不能确定高度。(平衡二叉树)

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

下列关于算法的说法,【错误】的是?( )

A
如果有足够的时间和空间,枚举法能解决一切有限的问题。
B
分治算法将原问题分为多个子问题进行求解,且分解出的子问题必须相互独立。
C
如果能找到合理的贪心原则,贪心算法往往能够比其他方法更快求解。
D
倍增法在搜索未知长度的有序数组时,通过动态倍增或减半步长,快速定位目标范围。
答案与解析
正确答案:B

子问题可以不独立,在解决完子问题后再合并。(算法的时空效率分析)

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

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
nl + nr == n
B
nl + nr == n2
C
(nl + nr) * (nl + nr) == n
D
(nl + nr) ^ 2 == n2
答案与解析
正确答案:A

此时应该判断两半的和的平方是否等于原数,而原数是 n2 ,n 是其平方根,所以选择 A。(阅读模拟程序、 字符串函数)

题目详情
55 单选题 适中 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
这道题暂未补解析。
题目详情
56 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下面的欧氏筛法程序中,两个横线处应填入的分别是?( )

int primes[MAXP], num = 0;
bool isPrime[MAXN + 1] = {false};
void sieve() {
    for (int n = 2; n <= MAXN; n++) {
        if (!isPrime[n])
            primes[num++] = n;
        for (int i = 0; i < num && ________; i++) { // 在此处填入选项
            isPrime[n * primes[i]] = true;
            if (________) // 在此处填入选项
                break;
        }
    }
}
A
n * primes[i] < MAXNn % primes[i] == 0
B
n * primes[i] < MAXNprimes[i] > n
C
n * primes[i] <= MAXNn % primes[i] == 0
D
n * primes[i] <= MAXNprimes[i] > n
答案与解析
正确答案:C

第—空应该保证  n * primes[i] 不超过筛法的范围,第二空应该是如果当前  primes[i] 是 n 的最小素因子 则停止循环。(数论:质数筛法)

题目详情
57 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.2 最短路径

下面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
map[i][j] = map[i][k] + map[k][j]
B
map[i][k] = map[i][j] - map[k][j]
C
map[i][j] = map[i][k] - map[k][j]
D
map[k][j] = map[i][j] - map[i][k]
答案与解析
正确答案:A

根据 Floyd 算法,如果 i 到 k 加上 k 到 j 的最短路长度小于当前 i 到 j 的最短路长度,则用前者更新后者。 (图论算法: Floyd 算法)

题目详情
58 单选题 适中 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 算法)

题目详情
59 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 3.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
a[j] += a[j + 1]
B
a[j] += a[j - 1]
C
a[j - 1] += a[j]
D
a[j + 1] += a[j]
答案与解析
正确答案:B

根据组合数的递推式 ci,j = ci - 1,j + ci - 1,j - 1 可以知道应该选择 B (这里使用了滚动数组)。(杨辉三角)

题目详情
60 单选题 适中 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
这道题暂未补解析。
题目详情