GESP-C++五级 题库
根据下述二分查找法,在排好序的数组 1,3,6,9,17,31,39,52,61,79,81,90,96 中查找数值82,和82比较的数组元素分别是( )。
第一次迭代:
left = 0, right = 12,数组范围是整个数组。
mid = (0 + 12) / 2 = 6,即中间元素是39。
nums[mid] = 39,小于目标值82,所以更新 left = mid + 1 = 7。
第二次迭代:
left = 7, right = 12,数组范围缩小到[52, 61, 79, 81, 90, 96]。
mid = (7 + 12) / 2 = 9,即中间元素是79。
nums[mid] = 79,小于目标值82,所以更新 left = mid + 1 = 10。
第三次迭代:
left = 10, right = 12,数组范围缩小到[81, 90, 96]。
mid = (10 + 12) / 2 = 11,即中间元素是90。
nums[mid] = 90,大于目标值82,所以更新 right = mid - 1 = 10。
第四次迭代:
left = 10, right = 10,即只剩下一个元素81。
mid = (10 + 10) / 2 = 10,即中间元素是81。
nums[mid] = 81,小于目标值82,所以更新 left = mid + 1 = 11。
根据上述分析,与目标值82进行比较的数组元素依次是:39, 79, 90, 81
要实现一个高精度减法函数,则下面代码中加划线应该填写的代码为( )。
当a[i] < b[i] 时,表示当前位需要借位。a[i + 1]-- 将下一位a[i + 1] 的值减一,以便在当前位进行借位操作。
设A和B是两个长度为n的有序数组,现将A和B合并成一个有序数组,归并排序算法在最坏情况下至少要做( )次比较。
在最坏情况下,两个数组的元素需要逐个比较,直到其中一个数组的所有元素都放入新数组中。当一个数组的所有元素都被放入新数组后,剩下的数组中的元素不需要再与新数组中的元素比较,因此剩余的比较操作可以省略。因此,总的比较次数是n+(n−1),即2n−1
给定如下函数:
则当 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++ 代码片段用于计算阶乘。请在横线处填入( ),实现正确的阶乘计算。
下面的代码片段用于在双向链表中删除一个节点。请在横线处填入( ),使其能正确实现相应功能。
下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是( )?
下面的代码片段用于将两个高精度整数进行相加。请在横线处填入( ),使其能正确实现相应功能。
给定序列:1,3,6,9,17,31,39,52,61,79,81,90,96。使用以下代码进行二分查找查找元素 82时,需要循环多少次,即最后输出的 times 值为( )。
下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改,使其能正确实现相应功能。( )
在埃拉托斯特尼筛法中,要筛选出不大于 n 的所有素数,最外层循环应该遍历什么范围( )?
在快速排序中,选择的主元素(pivot)会影响算法的( )。
递归函数在调用自身时,必须满足( ),以避免无限递归?
假设给定链表为: ,若调用 searchValue(head, 5) ,函数返回值为( )。