首页 › 题库 › GESP编程能力等级认证 › 1 初等数论

GESP-C++五级 题库

共 130 道题 ,第 5 / 7 页 · 按题型筛选,点「查看答案」核对解析
章节 1 初等数论 清除
81 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

基于下面定义的函数,通过判断 isDivisibleBy9(n) == isDigitSumDivisibleBy9(n) 代码可验算如果 一个数能被9整除,则它的各位数字之和能被9整除。

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

假设函数 gcd() 能正确求两个正整数的最大公约数,则下面的 findMusicalPattern(4,6) 函数返回2。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
83 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

线性筛关键是“每个合数只会被最小质因子筛到一次”,因此为 。

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

下面C++代码是用欧几里得算法(辗转相除法)求两个正整数的最大公约数, a 大于 b 还是小于 b 都适用。( )

int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情

假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的 lcm() 函数能求相应两数的最小公倍数。( )

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
86 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

下面的C++代码用于输出每个数对应的质因数列表,输出形如: {5: [5], 6: [2, 3], 7: [7], 8: [2, 2, 2]} 。( )

int main() {
    int n, m;
    cin >> n >> m;
    if (n > m) swap(n, m);
    map<int, vector<int>> prime_factor;
    for (int i = n; i <= m; ++i) {
        int j = 2, k = i;
        while (k != 1) {
            if (k % j == 0) {
                prime_factor[i] = prime_factor[i] + j;
                k /= j;
            } else {
                ++j;
            }
        }
    }
    for (auto& p : prime_factor) {
        cout << p.first << ": ";
        for (int v : p.second)
            cout << v << " ";
        cout << endl;
    }
    return 0;
}
A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
87 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

如下为线性筛法,用于高效生成素数表,其核心思想是每个合数只被它的最小质因数筛掉一次,时间复杂度为 O(n)。( )

vector<int> linearSieve(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
    return primes;
}
A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
88 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因数筛去一次,因此效率更高。( )

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

线筛的时间复杂度是 O(n),每个合数只被其最小质因数筛去一次。

而埃筛的时间复杂度是 O(nlog log n),相对来说会更高,是在筛选过程中存在重复操作。

本题答案为正确。

题目详情
89 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

小杨有100元去超市买东西,每个商品有各自的价格,每种商品只能买1个,小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买,这体现了分治思想。( )

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

分治法的核心是:

分解:将问题划分为若干 相互独立且结构相同 的子问题。

解决:递归解决子问题。

合并:将子问题的解合并为原问题的解。

小杨的策略是 每次选当前最便宜的商品,这种策略的本质是贪心算法。

不是分治,因为无问题分解,无子问题合并。

题目详情
90 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因数筛去一次,因此效率更高。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
91 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

任何一个大于1的自然数都可以分解成若干个不同的质数的乘积,且分解方式是唯一的。(2024.12-5)

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
92 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

找出自然数 n 以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中线性筛法效率更高。

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

常见的质数筛有埃氏筛和欧拉筛(线性筛法),其中埃氏筛的时间复杂度为O(nlogn),经过一定的优化,可以到O(nloglogn),欧拉筛的时间复杂度为O(n),大部分情况下,欧拉筛的效率更高。

题目详情
93 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

唯一分解定理表明任何一个大于 1 的整数都可以唯一地分解为素数之和。

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

任何一个大于等于2的整数,都可以唯一的分解为若干个质数的幂次方的乘积的形式

题目详情
94 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

引入分治策略往往可以提升算法效率。一方面,分治策略减少了操作数量;另一方面,分治后有利于系统的并行优化。

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

分治算法的思想就是把问题划分成子问题,然后继续划分,知道子问题可以直接解决,然后合并子问题得到的结果,推得原问题的答案,分治提高了算法的效率,减少了操作数量。

题目详情
95 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

找出自然数n以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中埃氏筛法效率更高。

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

埃氏筛法是一种简单直观的质数筛选算法,适用于较小范围内的质数查找,随着 n 的增大,其效率会下降,因为需要标记的倍数越多。线性筛法是在埃氏筛法基础上的改进,效率更高。

题目详情
96 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

唯一分解定理表明任何一个大于1的整数都可以唯一地表示为一系列质数的乘积,即质因数分解是唯一的。

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

一个整数可以有多种因数分解的方式(比如顺序不同),但其包含的质数因子及其指数是唯一确定的。

题目详情
97 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

在进行全国人口普查时,将其分解为对每个省市县乡来进行普查和统计。这是典型的分治策略。

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

分治策略的基本思想是将一个大问题分解为若干个小问题,然后分别解决这些小问题,最后将它们的解合并起来得到整体的解。在人口普查中,各个地区的普查可以看作是对小问题的解决,最后将各地的数据统计合并,得到全国的人口统计数据

题目详情
98 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

在下面C++代码中,由于删除了变量 ptr ,因此 ptr 所对应的数据也随之删除,故执行下述代码时,将报错。

int* ptr = new int(10);
cout << *ptr << endl;
delete ptr;
cout << ptr << endl;
A
对
B
错
答案与解析
正确答案:错

删除指针ptr并不会删除数据本身,只是释放了指针指向的动态内存

题目详情

辗转相除法用于求两个整数的最大公约数。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
100 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

素数表的埃氏筛法和线性筛法的时间复杂度都是O(NloglogN)。(   )

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