GESP-C++五级 题库
下述代码实现素数表的线性筛法,筛选出所有小于等于 n 的素数,则横线上应填的代码是( )。
这个地方是要枚举质数表,然后把质数的i倍数都筛掉,所以应该是选A。
现在用如下代码来计算xn(n个x相乘),其时间复杂度为( )。
假设快速排序算法的输入是一个长度为 n 的已排序数组,且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项( )描述的是在这种情况下的快速排序行为。
快速排序的过程是,每次选择一个基准值,比基准值大的放到它的右边 ,比基准值小的放到它的左边,但是这个序列是一个有序序列,且每次都是选择最小的元素作为基准值,所以每次所有的值都会放到基准值的右边,也就是说,每次都只是把基准值这个位置排序好。
考虑以下C++代码实现的归并排序算法:
对长度为 n 的数组 arr ,挑用函数 merge_sort(a, 0, n-1) ,在排序过程中 merge 函数的递归调用次数大约是( )。
merge_sort函数的作用是递归进行分治的过程,每次把序列分成两半,然后分别处理,merge函数的作用是把两个有序序列,通过双指针操作,合并为一个有序序列。merge函数的调用次数,先是两个数的合并,执行次数为n/2,然后是4个数合并,执行次数为n/4……大约为O(n)
现在有 n 个人要过河,每只船最多载2人,船的承重为100kg。下列代码中,数组 weight 中保存有 n 个人的体重(单位为kg),已经按从小到大排好序,代码输出过河所需要的船的数目,采用的思想为( )。
重量已经按照从小到大排序了,然后双指针处理,双指针的过程为最轻的人和最重的人尝试能否在同一个船上,如果可以,那么他们在同一个船上,否则,当前最重的人不能和其他人在一个船上,得单独一条船。采用的是贪心的思想。
关于分治算法,以下哪个说法正确?
分治算法的思想就是把问题划分成子问题,然后继续划分,知道子问题可以直接解决,然后合并子问题得到的结果,推到原问题的答案。
B选项:归并排序的思想就是分治。
D选项:分治算法划分子问题的时间一般为logn,总的时间复杂度常为O(nlogn),如归并排序。
根据下述二分查找法,在排好序的数组 1,3,6,9,17,31,39,52,61,79 中查找数值 31 ,循环while (left <= right) 执行的次数为( )。
模拟即可,
第一次:mid=5,nums[5]=17,此时小于要查找的31,所以left=6。
第二次:mid=8,nums[8]=52,此时大于要查找的31,所以right=7。
第三次:mid=6,nums[6]=31,找到要查找的值,结束。
以下关于高精度运算的说法错误的是( )。
C选项,高精度的乘法,运算时间和两个整数的长度之和有关,两个长度分别为len1和len2的整数相乘,结果的长度至少为len1+len2。
下面C++代码用于求斐波那契数列,该数列第1、2项为1,以后各项均是前两项之和。函数fibo()属于( )。
迭代算法:迭代算法是通过循环实现的,每次迭代利用前面计算的结果来推导出下一个结果。在给定的C++代码中,使用了一个循环for (int i = 3; i <= n; i++) 来计算斐波那契数列第n 项的值,通过迭代更新a 和b的值,直到计算出第n 项的值并返回。
下面C++代码用于将输入金额换成最少币种组合方案,其实现算法是( )。
贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优(最有利)的选择,以期望最终能够达到全局最优解。在这段代码中,每次循环都选择当前面值最大的硬币进行尽可能多的使用,从而达到最少硬币数量的组合方案。
算法实现分析:
数组coins 存储了面值从大到小的硬币面额{100, 50, 20, 10, 5, 2, 1}。
函数find_coins() 中使用了一个循环遍历所有硬币面额。在每次循环中,计算当前金额money 可以使用的当前面额硬币数量,并更新剩余金额money。
循环结束后,coins_used 数组存储了每种面额硬币的使用数量,以达到组合最少硬币数量的目的。
选择最优:由于每次都选择当前最大面额的硬币,贪心算法能够在保证每次选择最优的情况下,快速得到全局最优解,即使用最少数量的硬币来组合金额。
根据代码实现方式和贪心算法的特性,这段C++代码确实属于贪心算法。
小杨采用如下双链表结构保存他喜欢的歌曲列表:
小杨想在头指针为 head 的双链表中查找他喜欢的某首歌曲,采用如下查询函数,该操作的时间复杂度为( )。
该查询函数的时间复杂度为O(n),其中n是双链表中节点的数量。
函数使用一个指针temp从头指针head开始,沿着双链表向后遍历。
在每个节点处,它检查节点中的歌曲名称是否与目标歌曲my_song匹配。
最坏情况下,如果目标歌曲不在双链表中或者在最后一个节点才找到,那么需要遍历整个双链表,因此时间复杂度为O(n)
这是因为在最坏情况下,需要遍历所有n个节点才能确定目标歌曲是否存在。
小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲,他将其作为链表的第一首歌曲,则下面横线上应填入的代码为( )。
在将p 插入后,先前的头节点(head)必须更新其prev 指针,指向新的头节点p,以保持双向链表的结构:
p->next 指向先前的头节点head。head->prev 指向新的头节点p。
下面是根据欧几里得算法编写的函数,它计算的是 与 的( )。
欧几里得算法,也称为辗转相除法,用于计算两个非负整数的最大公约数。
在函数中,通过循环不断将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 的合数。
上题代码的时间复杂度是( )。
linear_sieve 函数的主要执行部分是主循环,(for (int i = 2; i <= n; ++i)):主循环从2到n进行遍历,因此有O(n)次迭代
为了正确实现快速排序,下面横线上的代码应为( )。
快速排序的分区过程中,我们使用两个指针i和j分别从左到右和从右到左遍历数组,将小于基准值的元素放到基准值的左边,大于基准值的元素放到右边。
具体的分区过程如下:
首先选择一个基准值pivot,通常选择中间元素arr[mid]。
使用两个指针i和j,分别从数组的左右两端开始向中间移动。
i从左向右移动,直到找到一个大于或等于pivot的元素。
j从右向左移动,直到找到一个小于或等于pivot的元素。
如果i <= j,则交换arr[i]和arr[j],然后i向后移动一位,j向前移动一位。
重复步骤2和3,直到i大于j,此时所有小于等于pivot的元素都在pivot的左边,所有大于等于pivot的元素都在pivot的右边。
在填写横线上的代码时,应该使用while (i <= j),因为分区过程应该持续进行直到i超过j,这样保证了整个分区过程的完成。
关于分治算法,以下哪个说法正确?
分治算法的基本思想是将原问题分解成若干个规模较小但结构与原问题相似的子问题,递归地求解这些子问题,然后再合并其结果,得到原问题的解。