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

GESP-C++七级 题库

共 270 道题 ,第 3 / 14 页 · 按题型筛选,点「查看答案」核对解析
41 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 1.1 三角函数

下面程序的输出为?( )

#include <iostream>
using namespace std;
int rec_fib[100];
int fib(int n) {
    if (n <= 1)
        return n;
    if (rec_fib[n] == 0)
        rec_fib[n] = fib(n - 1) + fib(n - 2);
    return rec_fib[n];
}
int main() {
    cout << fib(6) << endl;
    return 0;
}
A
8
B
13
C
64
D
结果是随机的。
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
42 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

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

int rec_fib[MAX_N];
int fib(int n) {
    if (n <= 1)
        return n;
    if (rec_fib[n] == 0)
        rec_fib[n] = fib(n - 1) + fib(n - 2);
    return rec_fib[n];
}
A
B
C
D
O(n)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
43 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下面 search 函数的平均时间复杂度为?( )

int search(int n, int * p, int target) {
    int low = 0, high = n;
    while (low < high) {
        int middle = (low + high) / 2;
        if (target == p[middle]) {
            return middle;
        } else if (target > p[middle]) {
            low = middle + 1;
        } else {
            high = middle;
        }
    }
    return -1;
}
A
O(n log(n))
B
O(n)
C
O(long(n))
D
O(1)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
44 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.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(n)
B
O(n×log n)
C
O(n×log log n)
D
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
45 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下列选项中,哪个【不可能】是下图的广度优先遍历序列?( )

A
1, 2, 4, 5, 3, 7, 6, 8, 9
B
1, 2, 5, 4, 3, 7, 8, 6, 9
C
1, 4, 5, 2, 7, 3, 8, 6, 9
D
1, 5, 4, 2, 7, 3, 8, 6, 9
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
46 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

下列哪个选项是C++中的关键字?( )

A
function
B
class
C
method
D
object
答案与解析
正确答案:B

本题考察 C++ 语法知识。 class 是类的关键字。(C++关键字)

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

下面代码输出的是?( )

int main() {
    int a = 5, b = 2;
    cout << (a >> b) << endl;
}
A
1
B
2
C
5
D
10
答案与解析
正确答案:A

输出  5>>2 ,应该是 1。(位运算)

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

以下代码的输出是什么?( )

int main() {
    int a = 10;
    int *p = &a;
    int *&q = p;
    *q = 20;
    cout << a << endl;
    return 0;
}
A
10
B
20
C
地址值
D
编译错误
答案与解析
正确答案:B

 *p 是—个指向 a 的指针, *&q 相当于对  *p 进行引用,所以修改  *q 就修改了 a 的值。(指针)

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

下面代码输出的是?( )

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    int *p = arr + 2;
    cout << *p << endl;
    return 0;
}
A
1
B
2
C
3
D
4
答案与解析
正确答案:C

应该输出 arr 的第三个元素。(指针)

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

下列关于排序的说法,正确的是?( )

A
选择排序是最快的排序算法之一。
B
归并排序通常是稳定的。
C
最差情况, N 个元素做快速排序的时间复杂度为 O(N)。
D
最好情况, N 个元素做插入排序的时间复杂度为 。
答案与解析
正确答案:B

归并排序可以不改变相同元素的相对位置。(排序算法)

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

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

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

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

题目详情
52 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

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

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

B 应该是—个有向无环图。(树和图结构)

题目详情
53 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.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
nl + nr == n
B
nl + nr == n2
C
(nl + nr) * (nl + nr) == n
D
(nl + nr) ^ 2 == n2
答案与解析
正确答案:A

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

题目详情
54 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 1.1 三角函数

给定一个无向图,图的节点编号从 0 到 n - 1,图的边以邻接表的形式给出。

下面的程序使用深度优先搜索(DFS)遍历该图,并输出遍历的节点顺序。横线处应该填入的是?( )

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void DFS(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    stack<int> s;
    s.push(start);
    visited[start] = true;
    while (!s.empty()) {
        int node = s.top();
        s.pop();
        cout << node << " "; // 输出当前节点
        // 遍历邻接节点
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                __________________
                __________________
            }
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<bool> visited(n, false);
// 从节点 0 开始 DFS遍历
    DFS(0, graph, visited);
    return 0;
}
A
visited[neighbor] = true;s.push(neighbor-1);
B
visited[neighbor] = true;s.push(neighbor+1);
C
visited[neighbor] = false;s.push(neighbor);
D
visited[neighbor] = true;s.push(neighbor);
答案与解析
正确答案:D

标记 neighbor 已经入栈并且将 neighbor 入栈,选择 D。(图结构、深度优先搜索)

题目详情
55 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 1.1 三角函数

给定一个整数数组 nums,找到其中最长的严格上升子序列的长度。

子序列是指从原数组中删除一些元素(或不删除)后,剩余元素保持原有顺序的序列。

下面的程序横线处应该填入的是?( )

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector<int> dp(n, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                _________________________
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int result = lengthOfLIS(nums);
    cout << result << endl;
    return 0;
}
A
dp[i] = max(dp[i], dp[j]);
B
dp[i] = max(dp[i+1], dp[j] + 1);
C
dp[i] = max(dp[i], dp[j] - 1);
D
dp[i] = max(dp[i], dp[j] + 1);
答案与解析
正确答案:D

考察 DP 解决最长上升子序列问题,如果  nums[i] > nums[j] ,则以 i 结尾的最长上升子序列可以从以 j 结尾 的最长上升子序列转移而来,所以选择 D 项。(动态规划)

题目详情
56 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 1.1 三角函数

给定一个整数数组 nums,找到其中最长的严格上升子序列的长度。

子序列是指从原数组中删除一些元素(或不删除)后,剩余元素保持原有顺序的序列。

该程序的时间复杂度为?( )

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector<int> dp(n, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                _________________________
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int result = lengthOfLIS(nums);
    cout << result << endl;
    return 0;
}
A
O(n2)
B
O(n)
C
O(log(n))
D
O(nlog(n))
答案与解析
正确答案:A

11, 12 两行执行了 O(n2) 次循环,所以复杂度为 O(n2)。(动态规划)

题目详情
57 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 1.1 三角函数

给定两个无向图 G1和 G2 ,判断它们是否同构。图的同构是指两个图的节点可以通过某种重新编号的方式完全匹配,且边的连接关系一致。

为了简化问题,假设图的节点编号从 0 到 n-1,并且图的边以邻接表的形式给出。下面程序中横线处应该给出的是?( )

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
string graphHash(vector<vector<int>>& graph) {
    vector<string> nodeHashes(graph.size());
    for (int i = 0; i < graph.size(); i++) {
        vector<int> neighbors = graph[i];
        sort(neighbors.begin(), neighbors.end());
        string hash;
        for (int neighbor : neighbors) {
            _______________________________
        }
        nodeHashes[i] = hash;
    }
    sort(nodeHashes.begin(), nodeHashes.end());
    string finalHash;
    for (string h : nodeHashes) {
        finalHash += h + ";";
    }
    return finalHash;
}
int main() {
    int n;
    cin >> n;
    vector<vector<int>> G1(n);
    for (int i = 0; i < n; i++) {
        int k;
        while (cin >> k) {
            G1[i].push_back(k);
            if (cin.get() == '\n') break;
        }
    }
    vector<vector<int>> G2(n);
    for (int i = 0; i < n; i++) {
        int k;
        while (cin >> k) {
            G2[i].push_back(k);
            if (cin.get() == '\n') break;
        }
    }
    string hash1 = graphHash(G1);
    string hash2 = graphHash(G2);
    if (hash1 == hash2) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}
A
hash += to_string(neighbor);
B
hash += to_string(neighbors);
C
hash += to_string(neighbor) + ",";
D
hash -= to_string(neighbors);
答案与解析
正确答案:C

应该将所有 neighbor ⽤  , 隔起来,因此选择 C。(图结构)

题目详情
58 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 1.1 三角函数

给定一个 m×n的二维网格 grid,每个格子中有一个非负整数。

请找出一条从左上角 (0, 0) 到右下角 (m-1, n-1) 的路径,使得路径上的数字总和最小。每次只能向右或向下移动。

横线处应该填入的是?( )

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = grid[0][0];
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            ________________________________
        }
    }
    return dp[m - 1][n - 1];
}
int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> grid(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    int result = minPathSum(grid);
    cout << result << endl;
    return 0;
}
A
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][1];
B
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
C
dp[i][j] = min(dp[i - 1][j], dp[i][j]) + grid[i][j];
D
dp[i][j] = min(dp[i][j], dp[i][j - 1]) + grid[i][j];
答案与解析
正确答案:B

B。(i, j) 可以从 (i    1 , j) 或者 (i, j    1) 走过来,因此  grid[i][j],选择 B。(动态规划)

题目详情
59 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 1.1 三角函数

给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

下面横线处应该填入的是?( )

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector<int> dp(n, 0);
    dp[0] = nums[0];
    int maxSum = dp[0];
    for (int i = 1; i < n; i++) {
        _______________________________
        maxSum = max(maxSum, dp[i]);
    }
    return maxSum;
}
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int result = maxSubArray(nums);
    cout << result << endl;
    return 0;
}
A
dp[i] = max(nums[i+1], dp[i - 1] + nums[i]);
B
dp[i] = max(nums[i], dp[i - 1] + nums[i]);
C
dp[i] = max(nums[i], dp[i + 1] + nums[i]);
D
dp[i] = max(nums[i], dp[i - 1] + nums[i+1]);
答案与解析
正确答案:B

dp[i] 表示以 i 结尾的最大子段和。如果 i-1 也在最大子段和中,对应 dp[i-1] + nums[i] ,否则只有 i 在最 大子段和,对应  nums[i] ,所以选择 B。(动态规划)

题目详情
60 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

在哈希表的实现中,冲突解决是一个重要的问题。以下哪种方法 不是 常见的哈希表冲突解决策略?( )

A
链地址法(Chaining)
B
开放地址法(Open Addressing)
C
二次哈希法(Double Hashing)
D
二分查找法(Binary Search)
答案与解析
正确答案:D

二分查找法用于有序数组中的查找,和哈希表冲突无关。(哈希表)

题目详情