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

GESP-C++五级 题库

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

下面的代码用于判断整数 n 是否是质数,错误的说法是?( )

bool is_prime(int n) {
    if (n <= 1) return false;
    int finish_number = static_cast<int>(sqrt(n)) + 1;
    for (int i = 2; i < finish_number; ++i) {
        if (n % i == 0)
            return false;
    }
    return true;
}
A
埃氏筛算法相对于上面的代码效率更高
B
线性筛算法相对于上面的代码效率更高
C
上面的代码有很多重复计算,因为不是判断单个数是否为质数,故而导致筛选出连续数中质数的效率不高
D
相对而言,埃氏筛算法比上面代码以及线性筛算法效率都高
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
22 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.4 质因数分解

唯一分解定理描述了关于正整数的什么性质?( )

A
任何正整数都可以表示为两个素数的和。
B
任何大于1的合数都可以唯一分解为有限个质数的乘积。
C
两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积。
D
所有素数都是奇数。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
23 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

下面的C++代码,用于求一系列数据中的最大值。有关其算法说法【错误】的是?( )

int find_max_recursive(const vector<int>& nums, int left, int right) {
    if (left == right)
        return nums[left];
    int mid = left + (right - left) / 2;
    int left_max = find_max_recursive(nums, left, mid);
    int right_max = find_max_recursive(nums, mid + 1, right);
    return max(left_max, right_max);
}
int find_max(const vector<int>& nums) {
    if (nums.empty()) {
        throw invalid_argument("输入数组不能为空");
    }
    return find_max_recursive(nums, 0, nums.size() - 1);
}
A
该算法采用分治算法
B
该算法是递归实现
C
该算法采用贪心算法
D
该算法不是递推算法
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
24 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

下面的C++代码,用于求一系列数据中的最大值。有关其算法说法【错误】的是?( )

int find_max(const vector<int>& nums) {
    if (nums.empty()) {
        throw invalid_argument("输入数组不能为空");
    }
    int max_value = nums[0];
    for (int num : nums) {
        if (num > max_value) {
            max_value = num;
        }
    }
    return max_value;
}
A
本题 find_max() 函数采用的是迭代算法
B
本题 find_max() 函数的时间复杂度为 O(n)
C
和上一题的 find_max() 相比,因为没有递归,所以没有栈的创建和销毁开销
D
本题 find_max() 函数和上一题的 find_max() 时间复杂度相同
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
25 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

下面的 C++ 代码用于在升序数组 lst 中查找目标值 target 最后一次出现的位置。相关说法,正确的是?( )

int binary_search_last_occurrence(const vector<int>& lst, int target) {
    if (lst.empty()) return -1;
    int low = 0, high = lst.size() - 1;
    while (low < high) {
        int mid = (low + high + 1) / 2;
        if (lst[mid] <= target) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    if (lst[low] == target)
        return low;
    else
        return -1;
}
A
当 lst 中存在重复的 target 时,该函数总能返回最后一个 target 的位置,即便 lst 全由相同元素组成
B
当 target 小于 lst 中所有元素时,该函数会返回 0
C
循环条件改为 while (low <= high) 程序执行效果相同,且能提高准确性
D
将代码中 (low + high + 1) / 2 修改为 (low + high) / 2 效果相同
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
26 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

硬币找零问题中要求找给客户最少的硬币。 coins 存储可用硬币规格,单位为角,假设规格都小于10角,且一定有1角规格。 

amount 为要找零的金额,约定必须为1角的整数倍。输出为每种规格及其数量,按规格从大到小输出,如果某种规格不必要,则输出为0。

下面是其实现代码,相关说法正确的是?( )

const int MAX_COINS = 10;
int result[MAX_COINS] = {0}; // 假设最多10种面额
int find_coins(const vector<int>& coins, int amount) {
    sort(coins.begin(), coins.end(), greater<int>());
    int n = coins.size();
    for (int i = 0; i < n; ++i) {
        int coin = coins[i];
        int num = amount / coin;
        result[i] = num;
        amount -= num * coin;
        if (amount == 0) break;
    }
    cout << "找零方案如下:" << endl;
    for (int i = 0; i < n; ++i) {
        cout << sorted_coins[i] << "角需要" << result[i] << "枚" << endl;
    }
    return 0;
}
A
上述代码采用贪心算法实现
B
针对本题具体要求,上述代码总能找到最优解
C
上述代码采用枚举算法
D
上述代码采用分治算法
答案与解析
正确答案:A
这道题暂未补解析。
题目详情

用以下辗转相除法(欧几里得算法)求gcd(84, 60)的步骤中,第二步计算的数是?( )

int gcd(int a, int b) {
    int big = a > b ? a : b;
    int small = a < b ? a : b;
    if (big % small == 0) {
        return small;
    }
    return gcd(small, big % small);
}
A
84和60
B
60和24
C
24和12
D
12和0
答案与解析
正确答案:B

调用gcd(84, 60)函数中:

big=84,small=60,big % small不为零,递归调用:

gcd(60, 24)。

题目详情
28 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.4 质因数分解

根据唯一分解定理,下面整数的唯一分解是正确的?( )

A
18 = 3 × 6
B
28 = 4 × 7
C
36 = 2 × 3 × 6
D
30 = 2 × 3 × 5
答案与解析
正确答案:D

唯一分解定理指出:任何一个大于 1 的整数,要么本身是一个质数,要么可以唯一地分解为一系列质数的乘积。

需要检查每个选项的分解是否 全部是质数,只有选项D符合。

题目详情
29 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

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

vector<int> sieve_linear(int n) {
    vector<bool> is_prime(n +1, true);
    vector<int> primes;
    if (n < 2) return primes;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n/2; i++) {
        if (is_prime[i])
            primes.push_back(i);
        for (int j = 0; ___________________ ; j++) { // 在此处填入代码
            is_prime[ i * primes[j] ] = false;
            if (i % primes[j] == 0)
                break;
        }
    }
    for (int i = n/2 +1; i <= n; i++) {
        if (is_prime[i])
            primes.push_back(i);
    }
    return primes;
}
A
j < primes.size()
B
i * primes[j] <= n
C
j < primes.size() && i * primes[j] <= n
D
j <= n
答案与解析
正确答案:C

线性筛法的核心思想是 每个合数只被其最小质因数筛除一次,从而保证 O(n) 的时间复杂度。

内层循环的目的是 筛除 i×primes[j],因此需要满足:

j 不超过 primes 数组的大小(避免越界访问)。

i×primes[j]≤n(筛除的合数不能超过 n)。

本题答案为选项C。

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

对下面两个函数,说法【错误】的是?( )

int factorialA(int n) {
    if (n <= 1) return 1;
    return n * factorialA(n - 1);
}
int factorialB(int n) {
    if (n <= 1) return 1;
    int res = 1;
    for(int i=2; i<=n; i++)
        res *= i;
}
A
两个函数的实现的功能相同。
B
两个函数的时间复杂度均为 O(n)。
C
factorialA采用递归方式。
D
factorialB采用递归方式。
答案与解析
正确答案:D

两个计算阶乘的函数 factorialA 和 factorialB。

factorialA采用递归的方法,factorialB 采用循环方式实现,二者的时间复杂度均为O(n)。

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

下算法中,( )是不稳定的排序?

A
选择排序
B
插入排序
C
归并排序
D
冒泡排序
答案与解析
正确答案:A

稳定排序 是指:如果两个相等的元素在排序前后的相对位置保持不变。

不稳定排序 是指:相等的元素在排序后可能交换位置。

对于选择排序,每次从未排序部分选择最小(或最大)元素,放到已排序部分的末尾。

例如:[5, 5, 2]进行排序,[5(1), 5(2), 2](用下标区分两个 5),找到最小值 2,交换 5(1)和 2,数组变为:[2, 5(2), 5(1)],两个5的相对顺序改变了。

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

若用二分法在[1, 100]内猜数,最多需要猜( )次?

A
100
B
10
C
7
D
5
答案与解析
正确答案:C

二分查找每次将搜索区间对半分,最坏情况下需要猜测的次数:

2^6<100(6 次不够),2^7>=100(7 次足够)。

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

函数 int findMax(int arr[], int low, int high) 计算数组中最大元素,其中数组 arr 从索引low 到 high ,( )正确实现了分治逻辑?

A
if (low == high)
    return arr[low];
int mid = (low + high) / 2;
return arr[mid];
B
if (low >= high)
    return arr[low];
int mid = (low + high) / 2;
int leftMax = findMax(arr, low, mid - 1);
int rightMax = findMax(arr, mid, high);
return leftMax + rightMax;
C
if (low > high)
    return 0;
int mid = low + (high - low) / 2;
int leftMax = findMax(arr, low, mid);
int rightMax = findMax(arr, mid + 1, high);
return leftMax * rightMax;
D
if (low == high)
    return arr[low];
int mid = low + (high - low) / 2;
int leftMax = findMax(arr, low, mid);
int rightMax = findMax(arr, mid + 1, high);
return (leftMax > rightMax) ? leftMax : rightMax;
答案与解析
正确答案:D

分治法的核心思想是:分解,解决,合并。

对于 求数组最大值,分治法的具体实现是:

基准情况:如果 low == high,说明区间只有一个元素,直接返回 arr[low]。

分解:计算中间位置 mid。

递归求左半部分 [low, mid] 的最大值 leftMax。

递归求右半部分 [mid+1, high] 的最大值 rightMax。

合并:比较 leftMax 和 rightMax,返回较大者。

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

对下面两个函数,说法错误的是( )。

int fibA(int n) {
	if (n <= 1) return n;
	
	int f1 = 0, f2 = 1;
	for (int i = 2; i <= n; ++i) {
		int temp = f2;
		f2 = f1 + f2;
		f1 = temp;
	}
	return f2;
}
int fibB(int n) {
if (n <= 1) return n;
return fibB(n - 1) + fibB(n - 2);
}
A
两个函数的实现的功能相同。
B
fibA采用递推方式。
C
fibB采用的是递归方式。
D
fibA时间复杂度为 O(n),fibB的时间复杂度为 O(n)。
答案与解析
正确答案:D
这道题暂未补解析。
题目详情

两块长方形土地的长宽分别为 24 和 36 米,要将它们分成正方形的小块,使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数 gcd(24, 36) 来求正方形分块的边长,则函数 gcd 调用顺序为( )。

int gcd(int a, int b) {
	int big = a > b ? a : b;
	int small = a < b ? a : b;
	if (big % small == 0) {
		return small;
	}
	return gcd(small, big % small);
}
A
gcd(24, 36)、gcd(24, 12)、gcd(12, 0)
B
gcd(24, 36)、gcd(12, 24)、gcd(0, 12)
C
gcd(24, 36)、gcd(24, 12)
D
gcd(24, 36)、gcd(12, 24)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
36 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

唯一分解定理表明,每个大于1的自然数可以唯一地写成若干个质数的乘积。下面函数将自然数 n 的所有质因素找出来,横线上能填写的最佳代码是( )。

#include <vector>
vector<int> get_prime_factors(int n) {
	vector<int> factors;
	if (n <= 1) {
		cout << "输入的数必须是大于1的正整数" << endl;
		return;
	}
	while (n % 2 == 0) {
		factors.push_back(2);
		n /= 2;
	}
	
	________________________________ { // 在此处填入代码
		while (n % i == 0) {
			factors.push_back(i);
			n /= i;
		}
	}
	
	if (n > 2) {
		factors.push_back(n);
	}
	
	return factors;
}
A
for (int i = 3; i <= n; i ++)
B
for (int i = 3; i * i <= n; i ++)
C
for (int i = 3; i <= n; i += 2)
D
for (int i = 3; i * i <= n; i += 2)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
37 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下述代码实现素数表的埃拉托色尼(埃氏)筛法,筛选出所有小于等于 n 的素数。

vector<int> sieve_Eratosthenes(int n) {
	vector<bool> is_prime(n +1, true);
	vector<int> primes;
	
	for (int i = 2; i * i <= n; i++) {
		if (is_prime[i]) {
			primes.push_back(i);
			
			for (int j = i * i; j <= n; j += i) {
				is_prime[j] = false;
			}
		}
	}
	
	for (int i = sqrt(n) + 1; i <= n; i++) {
		if (is_prime[i]) {
			primes.push_back(i);
		}
	}
	
	return primes;
}

下面说法,正确的是( )。

A
代码的时间复杂度是 O(nn)。
B
在标记非素数时,代码从 i2开始,可以减少重复标记。
C
代码会输出所有小于等于 n 的奇数。
D
调用函数 sieve_Eratosthenes(10) ,函数返回值的数组中包含的元素有: 2, 3, 5, 7, 9 。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
38 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下述代码实现素数表的线性筛法,筛选出所有小于等于 n 的素数。下面说法正确的是( )。

vector<int> sieve_linear(int n) {
	vector<bool> is_prime(n +1, true);
	vector<int> primes;
	
	for (int i = 2; i <= n/2; 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] ] = 0;
			if (i % primes[j] == 0)
				break;
		}
	}
	
	for (int i = n/2 +1; i <= n; i++) {
		if (is_prime[i])
			primes.push_back(i);
	}
	
	return primes;
}
A
线性筛的时间复杂度是 O(n)。
B
每个合数会被其所有的质因子标记一次。
C
线性筛和埃拉托色尼筛的实现思路完全相同。
D
以上都不对
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
39 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

给定一个长度为 n 的有序数组 nums ,其中所有元素都是唯一的。下面的函数返回数组中元素 target 的索引。

int binarySearch(vector<int> &nums, int target, int left, int right) {
	if (left > right) {
		return -1;
	}
	
	int middle = left + ((right - left) / 2);
	if (nums[middle] == target) {
		return middle;
	}
	else if (nums[middle] < target) {
		return binarySearch(nums, target, middle + 1, right);
	}
	else
		return binarySearch(nums, target, left, middle - 1);
	}
}

int Find(vector<int> &nums, int target) {
	int n = nums.size();
	return binarySearch(nums, target, 0, n - 1);
}

关于上述函数,描述不正确的是( )。

A
函数采用二分查找,每次计算搜索当前搜索区间的中点,然后根据中点的元素值排除一半搜索区间。
B
函数采用递归求解,每次问题的规模减小一半。
C
递归的终止条件是中间元素的值等于 target ,若数组中不包含该元素,递归不会终止。
D
算法的复杂度为 O(logn).
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
40 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

给定一个长度为 的有序数组 nums ,其中可能包含重复元素。下面的函数返回数组中某个元素 target 的左边界,若数组中不包含该元素,则返回 −1 。例如在数组 nums = [5,7,7,8,8,10] 中查找 target=8 ,函数返回 8 88 在数组中的左边界的索引为 3 33。则横线上应填写的代码为( )。

int getLeftBoundary(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size() - 1;
	
	while (left < right) {
		int middle = left + ((right - left) / 2);
		if (target <= nums[middle])
			________________________________ // 在此处填入代码
		else
			left = middle+1;
	}
	
	return nums[left]==target?left:-1;
}
A
right = middle - 1;
B
right = middle;
C
right = middle + 1;
D
以上都不对
答案与解析
正确答案:B
这道题暂未补解析。
题目详情