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

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

下面C++代码是用欧几里得算法(辗转相除法)求两个正整数的最大公约数, a 大于 b 还是小于 b 都适用。( )
假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的 lcm() 函数能求相应两数的最小公倍数。( )
下面的C++代码用于输出每个数对应的质因数列表,输出形如: {5: [5], 6: [2, 3], 7: [7], 8: [2, 2, 2]} 。( )
如下为线性筛法,用于高效生成素数表,其核心思想是每个合数只被它的最小质因数筛掉一次,时间复杂度为 O(n)。( )
线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因数筛去一次,因此效率更高。( )
线筛的时间复杂度是 O(n),每个合数只被其最小质因数筛去一次。
而埃筛的时间复杂度是 O(nlog log n),相对来说会更高,是在筛选过程中存在重复操作。
本题答案为正确。
小杨有100元去超市买东西,每个商品有各自的价格,每种商品只能买1个,小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买,这体现了分治思想。( )
分治法的核心是:
分解:将问题划分为若干 相互独立且结构相同 的子问题。
解决:递归解决子问题。
合并:将子问题的解合并为原问题的解。
小杨的策略是 每次选当前最便宜的商品,这种策略的本质是贪心算法。
不是分治,因为无问题分解,无子问题合并。
找出自然数 n 以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中线性筛法效率更高。
常见的质数筛有埃氏筛和欧拉筛(线性筛法),其中埃氏筛的时间复杂度为O(nlogn),经过一定的优化,可以到O(nloglogn),欧拉筛的时间复杂度为O(n),大部分情况下,欧拉筛的效率更高。
唯一分解定理表明任何一个大于 1 的整数都可以唯一地分解为素数之和。
任何一个大于等于2的整数,都可以唯一的分解为若干个质数的幂次方的乘积的形式
引入分治策略往往可以提升算法效率。一方面,分治策略减少了操作数量;另一方面,分治后有利于系统的并行优化。
分治算法的思想就是把问题划分成子问题,然后继续划分,知道子问题可以直接解决,然后合并子问题得到的结果,推得原问题的答案,分治提高了算法的效率,减少了操作数量。
找出自然数n以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中埃氏筛法效率更高。
埃氏筛法是一种简单直观的质数筛选算法,适用于较小范围内的质数查找,随着 n 的增大,其效率会下降,因为需要标记的倍数越多。线性筛法是在埃氏筛法基础上的改进,效率更高。
唯一分解定理表明任何一个大于1的整数都可以唯一地表示为一系列质数的乘积,即质因数分解是唯一的。
一个整数可以有多种因数分解的方式(比如顺序不同),但其包含的质数因子及其指数是唯一确定的。
在进行全国人口普查时,将其分解为对每个省市县乡来进行普查和统计。这是典型的分治策略。
分治策略的基本思想是将一个大问题分解为若干个小问题,然后分别解决这些小问题,最后将它们的解合并起来得到整体的解。在人口普查中,各个地区的普查可以看作是对小问题的解决,最后将各地的数据统计合并,得到全国的人口统计数据
在下面C++代码中,由于删除了变量 ptr ,因此 ptr 所对应的数据也随之删除,故执行下述代码时,将报错。
删除指针ptr并不会删除数据本身,只是释放了指针指向的动态内存
