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

GESP-C++五级 题库

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

区块链技术是比特币的基础。在区块链中,每个区块指向前一个区块,构成链式列表,新区块只能接在链尾,不允许在中间插入或删除。下面代码实现插入区块添加函数,则横线处填写( )。

//区块(节点) 
struct Block { 
    int index; // 区块编号(高度) 
    string data; // 区块里保存的数据 
    Block* prev; // 指向前一个区块 
    Block(int idx, const string& d, Block* p) : index(idx), data(d), prev(p) {} 
}; 
// 区块链 
struct Blockchain { 
    Block* tail; 
    // 初始化 
    void init() { 
        tail = new Block(0, "Genesis Block", nullptr); 
    } 
    // 插入新区块 
    void addBlock(const string& data) { 
        _______________________ //在此处填入代码 
    } 
    // 释放内存 
    void clear() { 
        Block* cur = tail; 
        while (cur != nullptr) { 
            Block* p = cur->prev; 
            delete cur; 
            cur = p; 
        } 
        tail = nullptr; 
    } 
};
A
Block* newBlock = new Block(tail->index + 1, data, tail);
tail = newBlock->prev;
B
Block* newBlock = new Block(tail->index + 1, data, tail);
tail = newBlock;
C
Block* newBlock = new Block(tail->index + 1, data, tail->prev);
tail = newBlock;
D
Block* newBlock = new Block(tail->index + 1, data, tail->prev);
tail = newBlock->prev;
答案与解析
正确答案:B
确定链尾当前区块,获取其编号与指针;创建新区块,编号为原尾部编号加一,数据为输入内容,前驱指针指向原尾部区块;更新区块链的尾指针,使其指向新创建的区块;确保链式结构连续,且新区块成为新的末端节点。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

假设我们有两个数 a=38和b=14,它们对模 同余,即 a=b(mod m)。以下哪个值不可能是 m?

A
3
B
4
C
6
D
9
答案与解析
正确答案:D
根据同余定义,若 a ≡ b (mod m),则 m 必须整除 |a - b|。计算 |a - b| 的值,得到一个正整数差。所有可能的 m 值必须是该差值的正因数。列出该差值的所有正因数,构成可能模数的集合。任何不属于该集合的正整数,均不可能作为满足同余关系的模。通过判断各候选值是否为该差值的因数,可确定其是否可能为 m。
题目详情

下面代码实现了欧几里得算法。下面有关说法,错误的是( )。

int gcd1(int a, int b) { 
    return b == 0 ? a : gcd1(b, a % b); 
} 
int gcd2(int a, int b) { 
    while (b != 0) { 
        int temp = b; 
        b = a % b; 
        a = temp; 
    } 
    return a; 
}
A
gcd1() 实现为递归方式。
B
gcd2() 实现为迭代方式。
C
当 a较大时, gcd1() 实现会多次调用自身,需要较多额外的辅助空间。
D
当 a较大时, gcd1() 的实现比 gcd2() 执行效率更高。
答案与解析
正确答案:D
分析两个函数的实现结构:gcd1使用函数调用自身的方式,每次传入参数b和a对b取模的结果,直到b为0时返回a;递归过程中每层调用均需保存执行上下文。gcd2通过循环更新变量a和b的值,其中b被赋为a % b,a被赋为原b的值,循环持续到b为0为止;整个过程仅使用固定数量的局部变量。比较两者在控制流机制上的差异,递归版本依赖调用栈传递状态,迭代版本通过变量重用维护状态。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.4 质因数分解

唯一分解定理描述的内容是( )。

A
任何正整数都可以表示为两个素数的和。
B
任何大于1的合数都可以唯一分解为有限个质数的乘积。
C
两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积。
D
所有素数都是奇数。
答案与解析
正确答案:B
分析一个正整数的因数分解结构,考虑其能否表示为质数的乘积,并关注该表示形式是否在不计顺序的情况下具有唯一性。考察分解过程中质因数的存在性和个数确定性,以及不同分解路径是否导向相同结果。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下述代码实现素数表的线性筛法,筛选出所有小于等于 的素数,则横线上应填的代码是( )。

vector<int> linear_sieve(int n) { 
    vector<bool> is_prime(n +1, true); 
    vector<int> primes; 
    is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理 
    for (int i = 2; i <= n; ++i) { 
        if (is_prime[i]) { 
            primes.push_back(i); 
    } 
    ________________________________ { // 在此处填入代码 
        is_prime[ i * primes[j] ] = 0; 
        if (i % primes[j] == 0) 
            break; 
        } 
    } 
    return primes; 
}


A
for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)

B
for(int j = sqrt(n); j <= n && i * primes[j] <= n; j++)

C
for (int j = 1; j <= sqrt(n); j++)

D
for(int j = 1; j < n && i * primes[j] <= n; j++)

答案与解析
正确答案:A
线性筛法通过标记合数的方式筛选素数,确保每个合数仅被其最小质因子筛除一次。外层循环遍历从2到n的整数i,若i未被标记,则将其加入素数表。内层循环需枚举已记录的素数j,用i与j的乘积标记合数,且当j能整除i时应终止以保证线性时间复杂度。内层循环的上限为当前已知素数个数,循环变量j作为素数列表的索引使用。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

下面代码尝试在有序数组中查找第一个大于等于 x 的元素位置。如果没有大于等于 x 的元素,返回arr.size() 。以下说法正确的是( )。

int lower_bound(vector<int>& arr, int x) { 
    int l = 0, r = arr.size(); 
    while(l < r) { 
        int mid = l + (r - l) / 2; 
        if(arr[mid] >= x) r = mid; 
        else l = mid + 1; 
    } 
    return l; 
}
A
上述代码逻辑正确
B
上述代码逻辑错误, while 循环条件应该用 l <= r
C
上述代码逻辑错误, mid 计算错误
D
上述代码逻辑错误,边界条件不对
答案与解析
正确答案:A
使用双指针维护搜索区间[l, r),循环条件为l < r。每次取中点mid = l + (r - l) / 2,避免整数溢出。若arr[mid] >= x,则第一个满足条件的位置在左半部分(含mid),更新r = mid;否则在右半部分,更新l = mid + 1。循环结束时l等于r,返回l。初始r设为数组长度可覆盖无解情况。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

下面给出了阶乘计算的两种方式。以下说法正确的是( )。

int factorial1(int n) { 
    if (n <= 1) return 1; 
    return n * factorial1(n - 1); 
} 
int factorial2(int n) { 
    int acc = 1; 
    while (n > 1) { 
        acc = n * acc; 
        n = n - 1; 
    } 
    return acc; 
}
A
上面两种实现方式的时间复杂度相同,都为O(n)
B
上面两种实现方式的空间复杂度相同,都为O(n)
C
上面两种实现方式的空间复杂度相同,都为O(1)
D
函数 factorial1() 的时间复杂度为O(2^n),函数 factorial2() 的时间复杂度为O(n)
答案与解析
正确答案:A
分析两个函数的执行机制。factorial1为递归实现,每次调用将当前n与factorial1(n-1)的结果相乘,递归深度随n线性增长,每层调用占用栈空间。factorial2为迭代实现,使用循环变量acc累积乘积,n递减至1时结束循环,仅使用固定数量的局部变量。时间复杂度由基本操作次数决定,两者均执行约n次乘法操作。空间复杂度由额外内存使用量决定,递归调用产生n层栈帧,迭代过程仅使用常数空间。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

下列关于排序的说法,正确的是( )。2025.12-5

A
快速排序是稳定排序
B
归并排序通常是稳定的
C
插入排序是不稳定排序
D
冒泡排序不是原地排序
答案与解析
正确答案:B
分析排序算法的稳定性时,需考察相等元素在排序前后相对位置是否保持不变。快速排序通过基准划分元素,交换过程可能导致相等元素顺序改变。归并排序在合并有序子序列时,若遵守左子序列优先原则,则相等元素的相对位置得以保留。插入排序将元素逐个插入已排序部分,若插入位置选择包含等于比较元素的情况,则可维持相对顺序。冒泡排序通过相邻元素交换实现,每轮将最小(或最大)元素移动到边界位置,仅使用常量级额外空间完成排序操作。原地排序指辅助空间复杂度为O(1)。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

函数 isPerfectNumber 判断一个正整数是否为完全数(该数是否即等于它的真因子之和),则横线上应填写( )。一个正整数 n 的真因子包括所有小于 n 的正因子,如28的真因子为1, 2, 4, 7, 14。

A

i <= n

B

i*i <= n

C

i <= n/2

D

i < n

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

以下代码计算两个正整数的最大公约数(GCD),横线上应填写( )

A

b

B

a

C

temp

D

a * b

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

函数 sieve 实现埃拉托斯特尼筛法(埃氏筛),横线处应填入( )。

A

i

B

i+1

C

i+2

D

i*i

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
12 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

函数 linearSieve 实现线性筛法(欧拉筛),横线处应填入( )

A

i % p == 0

B

p % i == 0

C

i == p

D

i * p == n

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

关于 埃氏筛 和 线性筛 的比较,下列说法错误的是( )

A

埃氏筛可能会对同一个合数进行多次标记

B

线性筛的理论时间复杂度更优,所以线性筛的速度往往优于埃氏筛

C

线性筛保证每个合数只被其最小质因子筛到一次

D

对于常见范围( n=<10^7),埃氏筛因实现简单,常数较小,其速度往往优于线性筛

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
14 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.4 质因数分解

唯一分解定理描述的是( )。

A

每个整数都能表示为任意素数的乘积

B

每个大于 1 的整数能唯一分解为素数幂乘积(忽略顺序)

C

合数不能分解为素数乘积

D

素数只有两个因子:1 和自身

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
15 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

给定一个 n x n 的矩阵 matrix ,矩阵的每一行和每一列都按升序排列。函数 countLE 返回矩阵中第k 小的元素,则两处横线上应分别填写( )。

A

hi = mid - 1;

lo = mid + 1;

B

hi = mid;

lo = mid;

C

hi = mid;

lo = mid + 1;

D

hi = mid + 1;

lo = mid;

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
16 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

假设你是一家电影院的排片经理,只有一个放映厅。你有一个电影列表 movies ,其中 movies[i] = [start_i, end_i] 表示第 i 部电影的开始和结束时间。请你找出最多能安排多少部不重叠的电影,则横线上应分别填写的代码为( )。

A

a[0] < b[0] 和 lastEnd

B

a[1] < b[1] 和 lastEnd

C

a[0] < b[0] 和 movies[i][0]

D

a[1] < b[1] 和 movies[i][0]

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
17 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

给定一个整数数组 nums ,下面代码找到一个具有最大和的连续子数组,并返回该最大和。则下面说法错误的是( )。

A

上述代码采用分治算法实现

B

上述代码采用贪心算法

C

上述代码时间复杂度为O(n log n)

D

上述代码采用递归方式实现

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
18 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

给定一个由非负整数组成的数组 digits ,表示一个非负整数的各位数字,其中最高位在数组首位,且digits 不含前导0(除非是0本身)。下面代码对该整数执行 +1 操作,并返回结果数组,则横线上应填写( )

A

digits[i] = 0;

B

digits[i] = 9;

C

digits[i] = 1;

D

digits[i] = 10;

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
19 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下列C++代码判断一个正整数是否是质数,说法正确的是?( )

bool is_prime(int n) {
    if (n <= 1)
        return false;
    if (n == 2 || n == 3 || n == 5)
        return true;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0)
        return false;
    int i = 7;
    int step = 4;
    int finish_number = sqrt(n) + 1;
    while (i <= finish_number) {
        if (n % i == 0)
            return false;
        i += step;
        step = 6 - step;
    }
    return true;
}
A
代码存在错误,比如5是质数,但因为 5 % 5 余数是0返回了 false
B
finish_number 的值应该是 n / 2 ,当前写法将导致错误
C
当前 while 循环正确的前提是:所有大于3的质数都符合 6k±1 形式
D
while 循环修改如下,其执行效果和执行时间相同。
for (int i = 2; i < finish_number; i++) {
    if (n % i == 0)
        return false;
}
return true;
答案与解析
正确答案:C
这道题暂未补解析。
题目详情

下列C++代码用两种方式求解两个正整数的最大公约数,说法【错误】的是?( )

int gcd0(int big, int small) {
    if (big < small) {
        swap(big, small);
    }
    if (big % small == 0) {
        return small;
    }
    return gcd0(small, big % small);
}
int gcd1(int big, int small) {
    if (big < small) {
        swap(big, small);
    }
    for (int i = small; i >= 1; --i) {
        if (big % i == 0 && small % i == 0)
            return i;
    }
    return 1;
}
A
gcd0() 函数的时间复杂度为 O(log n)
B
gcd1() 函数的时间复杂度为 O(n)
C
一般说来, gcd0() 的效率高于 gcd1()
D
gcd1() 中的代码 for (int i = small; i >= 1; --i) 应该修改为 for (int i = small; i > 1; --i)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情