GESP-C++五级 题库
对下面两个函数,说法错误的是( )。
sumA函数是递推,sumB函数是递归,两个函数都是求的1~n的和,两个函数的时间复杂度基本一致,都是O(n)。
有如下函数 fun ,则 fun(20, 12) 的返回值为( )。
函数为辗转相除求两数的最大公约数,结果为4,如果没有看出函数作用,也可以手动模拟递归过程。
下述代码实现素数表的埃拉托斯特尼筛法,筛选出所有小于等于 n 的素数,则横线上应填的最佳代码是( )。
下述代码实现素数表的线性筛法,筛选出所有小于等于 n 的素数,则横线上应填的代码是( )。
这个地方是要枚举质数表,然后把质数的i倍数都筛掉,所以应该是选A。
现在有 n 个人要过河,每只船最多载2人,船的承重为100kg。下列代码中,数组 weight 中保存有 n 个人的体重(单位为kg),已经按从小到大排好序,代码输出过河所需要的船的数目,采用的思想为( )。
重量已经按照从小到大排序了,然后双指针处理,双指针的过程为最轻的人和最重的人尝试能否在同一个船上,如果可以,那么他们在同一个船上,否则,当前最重的人不能和其他人在一个船上,得单独一条船。采用的是贪心的思想。
下面C++代码用于将输入金额换成最少币种组合方案,其实现算法是( )。
贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优(最有利)的选择,以期望最终能够达到全局最优解。在这段代码中,每次循环都选择当前面值最大的硬币进行尽可能多的使用,从而达到最少硬币数量的组合方案。
算法实现分析:
数组coins 存储了面值从大到小的硬币面额{100, 50, 20, 10, 5, 2, 1}。
函数find_coins() 中使用了一个循环遍历所有硬币面额。在每次循环中,计算当前金额money 可以使用的当前面额硬币数量,并更新剩余金额money。
循环结束后,coins_used 数组存储了每种面额硬币的使用数量,以达到组合最少硬币数量的目的。
选择最优:由于每次都选择当前最大面额的硬币,贪心算法能够在保证每次选择最优的情况下,快速得到全局最优解,即使用最少数量的硬币来组合金额。
根据代码实现方式和贪心算法的特性,这段C++代码确实属于贪心算法。
下面是根据欧几里得算法编写的函数,它计算的是 与 的( )。
欧几里得算法,也称为辗转相除法,用于计算两个非负整数的最大公约数。
在函数中,通过循环不断将b 更新为a 除以b 的余数,直到b 变为0。此时a 的值就是最大公约数。
函数最终返回的是变量a 的值,即为输入的两个整数a 和b 的最大公约数。
因此,根据给出的函数实现和算法特性,函数gcd(int a, int b) 计算的是两个整数的最大公约数。
所以,答案是C.最大公约数。
欧几里得算法还可以写成如下形式:
下面有关说法,错误的是( )。
递归实现的gcd()函数并不比非递归实现的效率更高。两者的时间复杂度是相同的,选择使用哪种实现通常更依赖于个人或特定环境下的偏好或要求。
下述代码实现素数表的线性筛法,筛选出所有小于等于 的素数,则横线上应填的代码是( )。
使用for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) 这个循环来遍历当前已知的素数列表primes,确保了我们使用当前素数i 来乘以已知素数primes[j],并且正确地筛选掉不超过n 的合数。
给定如下函数:
则当 n = 7 n=7n=7 时,函数返回值为( )。
函数的计算过程:
fun(1) 的返回值是 1。
fun(2) 的返回值是 2。
对于其他 n >= 3 的情况,函数递归地计算 fun(n):
fun(3) = fun(1) - fun(2) = 1 - 2 = -1
fun(4) = fun(2) - fun(3) = 2 - (-1) = 3
fun(5) = fun(3) - fun(4) = (-1) - 3 = -4
fun(6) = fun(4) - fun(5) = 3 - (-4) = 7
fun(7) = fun(5) - fun(6) = -4 - 7 = -11
根据递归定义,我们可以看出 fun(n) 的计算是基于前两个值的递归差值。
现在来解决问题,当 n = 7 时,函数 fun(7) 返回的值是 -11。
因此,正确答案是 -11。
给定如下函数(函数功能同上题,增加输出打印):
则当 n = 4 n=4n=4 时,屏幕上输出序列为( )。
分析函数调用过程:
当n = 4 时,函数调用fun(4):
fun(4) 输出4,然后计算fun(2) - fun(3)。输出顺序为4。
fun(2) 输出2,然后返回2。输出顺序为4 2。
fun(3) 输出3,然后计算fun(1) - fun(2)。输出顺序为4 2 3.
fun(1) 输出1,然后返回1。输出顺序为4 2 3 1.
fun(2) 返回2,因为已经计算过,不再输出。输出顺序为4 2 3 1 2.
计算fun(3) = 1 - 2 = -1,返回-1。输出顺序为4 2 3 1 2.
计算fun(4) = 2 - (-1) = 3,返回3。输出顺序为4 2 3 1 2 4.
结论:
因此,当n = 4 时,屏幕上输出的序列是 4 2 3 1 2。
唯一分解定理描述的内容是( )?
下面的 C++ 代码片段用于计算阶乘。请在横线处填入( ),实现正确的阶乘计算。
下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改,使其能正确实现相应功能。( )
在埃拉托斯特尼筛法中,要筛选出不大于 n 的所有素数,最外层循环应该遍历什么范围( )?
下面C++代码用于求斐波那契数列,该数列第1、2项为1,以后各项均是前两项之和。下面有关说法错误的是( )。

fiboA( ) 用递归方式, fiboB() 循环方式
fiboA( ) 更加符合斐波那契数列的数学定义,直观易于理解,而 fiboB() 需要将数学定义转换为计算机程序实现
fiboA( ) 不仅仅更加符合数学定义,直观易于理解,且因代码量较少执行效率更高
fiboB( ) 虽然代码量有所增加,但其执行效率更高
阅读下面的C++代码,执行后其输出是( )。

1->120<===>2->120
1->120<===>1->120
1->120<===>1->2->3->4->5->120
1->120<===>2->3->4->5->6->120