GESP-C++五级 题库
下面的代码用于判断整数 n 是否是质数,错误的说法是?( )
唯一分解定理描述了关于正整数的什么性质?( )
下面的C++代码,用于求一系列数据中的最大值。有关其算法说法【错误】的是?( )
下面的C++代码,用于求一系列数据中的最大值。有关其算法说法【错误】的是?( )
下面的 C++ 代码用于在升序数组 lst 中查找目标值 target 最后一次出现的位置。相关说法,正确的是?( )
硬币找零问题中要求找给客户最少的硬币。 coins 存储可用硬币规格,单位为角,假设规格都小于10角,且一定有1角规格。
amount 为要找零的金额,约定必须为1角的整数倍。输出为每种规格及其数量,按规格从大到小输出,如果某种规格不必要,则输出为0。
下面是其实现代码,相关说法正确的是?( )
用以下辗转相除法(欧几里得算法)求gcd(84, 60)的步骤中,第二步计算的数是?( )
调用gcd(84, 60)函数中:
big=84,small=60,big % small不为零,递归调用:
gcd(60, 24)。
根据唯一分解定理,下面整数的唯一分解是正确的?( )
唯一分解定理指出:任何一个大于 1 的整数,要么本身是一个质数,要么可以唯一地分解为一系列质数的乘积。
需要检查每个选项的分解是否 全部是质数,只有选项D符合。
下述代码实现素数表的线性筛法,筛选出所有小于等于 n 的素数,横线上应填的最佳代码是?( )
线性筛法的核心思想是 每个合数只被其最小质因数筛除一次,从而保证 O(n) 的时间复杂度。
内层循环的目的是 筛除 i×primes[j],因此需要满足:
j 不超过 primes 数组的大小(避免越界访问)。
i×primes[j]≤n(筛除的合数不能超过 n)。
本题答案为选项C。
对下面两个函数,说法【错误】的是?( )
两个计算阶乘的函数 factorialA 和 factorialB。
factorialA采用递归的方法,factorialB 采用循环方式实现,二者的时间复杂度均为O(n)。
下算法中,( )是不稳定的排序?
稳定排序 是指:如果两个相等的元素在排序前后的相对位置保持不变。
不稳定排序 是指:相等的元素在排序后可能交换位置。
对于选择排序,每次从未排序部分选择最小(或最大)元素,放到已排序部分的末尾。
例如:[5, 5, 2]进行排序,[5(1), 5(2), 2](用下标区分两个 5),找到最小值 2,交换 5(1)和 2,数组变为:[2, 5(2), 5(1)],两个5的相对顺序改变了。
若用二分法在[1, 100]内猜数,最多需要猜( )次?
二分查找每次将搜索区间对半分,最坏情况下需要猜测的次数:
2^6<100(6 次不够),2^7>=100(7 次足够)。
函数 int findMax(int arr[], int low, int high) 计算数组中最大元素,其中数组 arr 从索引low 到 high ,( )正确实现了分治逻辑?
分治法的核心思想是:分解,解决,合并。
对于 求数组最大值,分治法的具体实现是:
基准情况:如果 low == high,说明区间只有一个元素,直接返回 arr[low]。
分解:计算中间位置 mid。
递归求左半部分 [low, mid] 的最大值 leftMax。
递归求右半部分 [mid+1, high] 的最大值 rightMax。
合并:比较 leftMax 和 rightMax,返回较大者。
对下面两个函数,说法错误的是( )。
两块长方形土地的长宽分别为 24 和 36 米,要将它们分成正方形的小块,使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数 gcd(24, 36) 来求正方形分块的边长,则函数 gcd 调用顺序为( )。
唯一分解定理表明,每个大于1的自然数可以唯一地写成若干个质数的乘积。下面函数将自然数 n 的所有质因素找出来,横线上能填写的最佳代码是( )。
下述代码实现素数表的埃拉托色尼(埃氏)筛法,筛选出所有小于等于 n 的素数。
下面说法,正确的是( )。
下述代码实现素数表的线性筛法,筛选出所有小于等于 n 的素数。下面说法正确的是( )。
给定一个长度为 n 的有序数组 nums ,其中所有元素都是唯一的。下面的函数返回数组中元素 target 的索引。
关于上述函数,描述不正确的是( )。
给定一个长度为 的有序数组 nums ,其中可能包含重复元素。下面的函数返回数组中某个元素 target 的左边界,若数组中不包含该元素,则返回 −1 。例如在数组 nums = [5,7,7,8,8,10] 中查找 target=8 ,函数返回 8 88 在数组中的左边界的索引为 3 33。则横线上应填写的代码为( )。