附上汇总帖GESP认证C编程真题解析 | 汇总单选题第1题下面关于链表和数组的描述错误的是 。A. 数组大小固定链表大小可动态调整。B. 数组支持随机访问链表只能顺序访问。C. 存储相同数目的整数数组比链表所需的内存多。D. 数组插入和删除元素效率低链表插入和删除元素效率高。【答案】C【解析】错误的是C。链表由于需要额外存储指针通常比数组占用更多内存。第2题通过 操作能完成在双向循环链表结点p之后插入结点s 的功能其中next 域为结点的直接后继prev 域为结点的直接前驱。A. p-next-prev s; s-prev p; p-next s; s-next p-next;B. p-next-prev s; p-next s; s-prev p; s-next p-next;C. s-prev p; s-next p-next; p-next s; p-next-prev s;D. s-next p-next; p-next-prev s; s-prev p; p-next s;【答案】D【解析】选项D正确地更新了双向循环链表的指针。具体步骤如下1s-next p-next;将新结点s的后继设为p的后继。2p-next-prev s; 将原本p的后继的前驱设为s。3s-prev p;将新结点s的前驱设为p。4p-nexts;将p的后继设为s。这样所有相关指针都被正确更新实现插入操作。第3题对下面两个函数说法错误的是 。intsumA(intn){intres0;for(inti1;in;i){resi;}returnrs;}intsumB(intn){if(n1)return1;intresnsumB(n-1);returnres;}A. sumA体现了迭代的思想。B. SumB采用的是递归方式。C. SumB函数比SumA的时间效率更高。D. 两个函数的实现的功能相同。【答案】C【解析】sumA函数使用迭代方式通过一个for循环计算1到n的和。sumB函数采用递归方式逐步将问题分解为求1到n-1的和再加上n。由于递归调用会增加函数调用栈的开销因此sumB的时间效率低于sumA。两个函数实现了相同的功能艮即计算从1到n的整数和。第4题有如下函数fun则fun(20, 12的返回值为 。intfun(inta,intb){if(a%b0)returnb;elsereturnfun(b,a%b);}【答案】C【解析】fun(20, 12) fun(12, 8) fun(8, 4) 4第5题下述代码实现素数表的埃拉托斯特尼筛法筛选出所有小于等于n 的素数则横线上应填的最佳代码是 。voidsieve_Eratosthenes(intn){vectorboolis_prime(n1,true);vectorintprimes;for(inti2;i*in;i){if(is_prime[i]){primes.push_back(i);__________________________{// 在此处填入代码is_prime[j]false;}}}for(intisqrt(n)1;in;i){if(is_prime[i]){primes.push_back(i);}}returnprimes;}A. for (int ji; jn; j)B. for (int ji * i; jn; j)C. for (int ji * i; jn; ji)D. for (int ji; jn; ji)【答案】C【解析】埃拉托斯特尼筛法用于找出所有小于等于n的素数。代码中需要填入的是将i的倍数标记为非素数的循环。根据第9行代码可知j代表i的倍数。选项A和B中的j代表的不是i的倍数。选项D错误的将i素数本身标记为非素数。选项C更符合逻辑确保j从i * i开始将每个i的倍数标记为非素数。因此最佳选择是C。第6题下述代码实现素数表的线性筛法筛选出所有小于等于 n 的素数则横线上应填的代码是 。vectorintsieve_linear(intn){vectorboolis_prime(n1,true);vectorintprimes;for(inti2;in/2;i){if(is_prime[i])primes.push_back(i);___________________________{// 在此处填入代码is_prime[i*primes[j]]0;if(i%primes[j]0)break;}}for(intin/21;in;i){if(is_prime[i])primes.push_back(i);}returnprimes;}A. for (int j0; jprimes.size() i * primes[j]n; j)B. for (int j1; jprimes.size() i * jn; j)C. for (int j2; jprimes.size() i * primes[j]n; j)D. 以上都不对【答案】A【解析】该代码实现了线性筛法用于找出所有小于等于n的素数。关键在于内层循环确保将i的倍数标记为非素数。选项A中的for (int j0; jprimes.size() i * primes[j]n; j)正确地初始化j并且条件判断合理确保不会越界。内部逻辑is_prime[i * primes[j]]0;将i与当前质数的乘积标记为非素数如果i能被当前质数整除则跳出循环。因此最佳选择是A。第7题下面函数可以将n 的所有质因数找出来其时间复杂度是 。#includeiostream#includevectorvectorintget_prime_factors(intn){vectorintfactors;while(n%20){factors.push_back(2);n/2;}for(inti3;i*in;i2){while(n%i0){factors.push_back(i);n/i;}}if(n2){factors.push_back(n);}returnfactors;}A.O ( n 2 ) O(n^2)O(n2)B.O ( n l o g n ) O(nlogn)O(nlogn)C.O ( n l o g n ) O(\sqrt nlogn)O(nlogn)D.O ( n ) O(n)O(n)【答案】C【解析】该函数用于找出整数n的所有质因数。时间复杂度分析如下首先处理2的倍数通过while(n % 2 0)循环将所有2的因子加入结果中。这部分操作最多执行O ( l o g n ) O(logn)O(logn)次因为每次都将n除以2。接下来通过一个for循环从3开始检查奇数因子。内层while(n % i 0)循环在找到一个因子i时将其不断地除去。这部分操作的总次数与n的素因子的个数有关。由于质因数分解的过程涉及到对每个可能的因子进行试探最坏情况下需要检查到sqrt(n)因此外层for循环的复杂度为O ( s q r t ( n ) ) O(sqrt(n))O(sqrt(n))。结合内层while循环每次除法操作的复杂度为O ( l o g n ) O(logn)O(logn)。综合起来总体时间复杂度为O ( s q r t ( n ) ∗ l o g n ) O(sqrt(n)*logn)O(sqrt(n)∗logn)。因此正确答案是C。第8题现在用如下代码来计算x n x^nxnn个x相乘其时间复杂度为 。doublequick_power(doublex,unsignedn){if(n0)return1;if(n1)returnx;returnquick_power(x,n/2)*quick_power(x,n/2)*((n1)?x:1);}A.O ( n ) O(n)O(n)B.O ( n 2 ) O(n^2)O(n2)C.O ( l o g n ) O(logn)O(logn)D.O ( n l o g n ) O(nlogn)O(nlogn)【答案】A【解析】这段代码采用快速幂算法用于计算x n x^nxn。正确的快速幂算法的时间复杂度为O ( l o g n ) O(logn)O(logn)但是本题中的实现每每次递归调用会进行两次 quick_power 调用因此时间复杂度为O ( 2 l o g n ) O(2^{logn})O(2logn)即O ( n ) O(n)O(n)。第9题假设快速排序算法的输入是一个长度为n的已排序数组且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项 描述的是在这种情况下的快速排序行为。A.快速排序对于此类输入的表现最好因为数组已经排序。B.快速排序对于此类输入的时间复杂度是O ( n l o g n ) O(n log n)O(nlogn)。C.快速排序对于此类输入的时间复杂度是O ( n 2 ) O(n^2)O(n2)。D.快速排序无法对此类数组进行排序因为数组已经排序。【答案】C【解析】快速排序在已排序数组上选择第一个元素作为基准时每次划分都会导致一侧为空另一侧包含剩余的所有元素。这种情况下递归深度为n且每层需要O ( n ) O(n)O(n)时间因此总时间复杂度为O ( n 2 ) O(n^2)O(n2)。选项C正确。第10题考虑以下C代码实现的归并排序算法voidmerge(intarr[],intleft,intmid,intright){intn1mid-left1;intn2right-mid;intL[n1],R[n2];for(inti0;in1;i)L[i]arr[lefti];for(intj0;jn2;j)R[j]arr[mid1j];inti0,j0,kleft;while(in1jn2){if(L[i]R[j]){arr[k]L[i];i;}else{arr[k]R[j];j;}k;}while(in1){arr[k]L[i];i;k;}while(jn2){arr[k]R[j];j;k;}}voidmerger_sort(intarr[],intleft,intright){if(leftright){intmidleft(right-left)/2;merge_sort(arr,left,mid);merge_sort(arr,mid1,right);merge_sort(arr,left,mid,right);}}对长度为n的数组arr调用函数merge_sort(a, 0, n-1) 在排序过程中merge 函数的递归调用次数大约是 。A.O ( 1 ) O(1)O(1)B.O ( n ) O(n)O(n)C.O ( l o g n ) O(log n)O(logn)D.O ( n l o g n ) O(n log n)O(nlogn)【答案】B【解析】本题中询问的是merge函数递归调用的次数归并排序是一个分治算法它将数组不断二分直到每个子数组只有一个元素即有n个子数组合并过程中将这些数组两两合并直到合并成一个数组排序完成因此合并了n-1次大约是O ( n ) O(n)O(n)。第11题现在有n个人要过河每只船最多载2人船的承重为100kg。下列代码中数组weight 中保存有n个人的体重单位为kg已经按从小到大排好序代码输出过河所需要的船的数目采用的思想为 。inti,j;intcount0;for(i0,jn-1;ij;j--){if(weight[i]weight[j]100){i;}count;}printf(过河的船数: %d\n,count);A. 枚举算法B. 贪心算法C. 迭代算法D. 递归算法【答案】B【解析】代码实现的方法每次都尽量让最轻和最重的人一起过河以减少船的数量。这种策略是典型的贪心算法因为它在每一步选择中都做出局部最优解从而达到全局最优。因此答案为B。第12题关于分治算法以下哪个说法正确A. 分治算法将问题分成子问题然后分别解决子问题最后合并结果。B. 归并排序不是分治算法的应用。C. 分治算法通常用于解决小规模问题。D.分治算法的时间复杂度总是优于O ( n l o g ( n ) ) O(n log(n))O(nlog(n))。【答案】A【解析】A选项正确。分治算法的核心思想是将一个复杂的问题分解为相对简单的子问题分别求解后再合并其结果。B选项错误。归并排序正是分治算法的经典应用之一。C选项错误。分治算法通常用于大规模问题通过递归地分解问题来简化计算。D选项错误。分治算法的时间复杂度具体取决于问题和实现方式。第13题根据下述二分查找法在排好序的数组1369173139526179 中查找数值31循环while (left right执行的次数为 。intbinary_search(vectorintnums,inttarget){intleft0;intrightnums.size()-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){returnmid;}elseif(nums[mid]target){leftmid1;}else{rightmid-1;}}return-1;// 如果找不到目标元素返回-1}A. 1B. 2C. 3D. 4【答案】C【解析】具体步骤如下1初始left 0right 9mid 4元素为172更新left 5right 9mid 7元素为523更新left 5right 6mid 5元素为31共执行了3次循环因此答案是C。第14题以下关于高精度运算的说法错误的是 。A. 高精度计算主要是用来处理大整数或需要保留多位小数的运算。B. 大整数除以小整数的处理的步骤可以是将被除数和除数对齐从左到右逐位尝试将除数乘以某个数通过减法得到新的被除数并累加商。C. 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。D. 高精度加法运算的关键在于逐位相加并处理进位。【答案】C【解析】A选项正确。B选项正确。C选项错误。高精度乘法的运算时间与两个整数的长度都有关而不仅仅是较长者的位数。D选项正确。第15题当n7时下面函数的返回值为 。intfun(intn){if(n1)return1;elseif(n5)returnn*fun(n-2);elsereturnn*fun(n-1);A. 105B. 840C. 210D. 420【答案】C【解析】fun(1) 1fun(2) 2 * fun(1) 2 * 1 2fun(3) 3 * fun(2) 3 * 2 6fun(5) 5 * fun(3) 5 * 6 30fun(7) 7 * fun(5) 7 * 30 210判断题第1题在操作系统中需要对一组进程进行循环。每个进程被赋予一个时间片当时间片用完时CPU将切换到下一个进程。这种循环操作可以通过环形链表来实现。A. 正确B. 错误【答案】A【解析】在操作系统中时间片轮转调度算法Round Robin常用于实现多任务处理。环形链表是一种适合的结构因为它可以自然地循环遍历所有进程当一个进程的时间片用完时CPU可以迅速切换到下一个进程。因此这种循环操作确实可以通过环形链表来实现。第2题找出自然数n以内的所有质数常用算法有埃拉托斯特尼埃氏筛法和线性筛法其中线性筛法效率更高。A. 正确B. 错误【答案】A【解析】埃拉托斯特尼筛法和线性筛法都是用于找出自然数n以内所有质数的有效算法。埃氏筛法通过标记合数来找到质数而线性筛法在此基础上进行了优化避免了重复标记从而提高了效率。因此线性筛法确实比埃氏筛法更高效。第3题唯一分解定理表明任何一个大于1的整数都可以唯一地分解为素数之和。A. 正确B. 错误【答案】B唯一分解定理也称为算术基本定理表明任何一个大于1的整数都可以唯一地表示为若干个素数的乘积而不是和。例如30可以唯一分解为2×3×5)。题目中提到“素数之和”是错误的。第4题贪心算法通过每一步选择局部最优解从而一定能获得最优解。A. 正确B. 错误【答案】B【解析】贪心算法通过每一步选择局部最优解但并不总能保证得到全局最优解。只有在某些特定问题中贪心算法才能确保获得最优解。因此题目中的说法是不正确的。第5题快速排序和归并排序的平均时间复杂度均为O ( n l o g n ) O(nlogn)O(nlogn)且都是稳定排序。A.正确B.错误【答案】B【解析】快速排序和归并排序的平均时间复杂度均为(O ( n l o g n ) O(n log n)O(nlogn))但它们在稳定性上有所不同。归并排序是稳定排序而快速排序不是稳定排序因为元素相同的两个记录可能会因为交换而改变顺序。第6题插入排序的时间复杂度总是比快速排序低。A.正确B.错误【答案】B【解析】插入排序的时间复杂度在最坏情况下为O ( n 2 ) O(n^2)O(n2)而快速排序的平均时间复杂度为O ( n l o g n ) O(n log n)O(nlogn)。虽然插入排序在小规模数据或接近有序的数据上表现较好但总体来说快速排序在大多数情况下更高效。因此题目中的说法是不正确的。第7题第7题引入分治策略往往可以提升算法效率。一方面分治策略减少了操作数量另一方面分治后有利于系统的并行优化。A. 正确B. 错误【答案】A【解析】分治策略通过将问题分解为更小的子问题逐步解决并合并结果从而提升算法效率。它不仅减少了操作数量还能进行并行计算提高系统性能。因此引入分治策略确实可以提升算法效率。第8题二分查找要求被搜索的序列是有序的否则无法保证正确性。A. 正确B. 错误【答案】A【解析】二分查找算法要求被搜索的序列必须是有序的因为它通过不断折半缩小搜索范围来定位目标值。如果序列无序二分查找无法正确判断目标值的位置从而不能保证正确性。第9题在C语言中递归的实现方式通常会占用更多的栈空间可能导致栈溢出。A. 正确B. 错误【答案】A【解析】在C语言中递归函数调用会占用栈空间每次递归调用都会在栈上分配新的帧。如果递归深度过大可能导致栈溢出。因此递归实现方式确实通常会占用更多的栈空间有潜在的栈溢出风险。第10题对于已经定义好的标准数学函数sin(x)应用程序中的语句ysin(sin(x))是一种递归调用。A. 正确B. 错误【答案】B【解析】递归调用是指函数在其定义中直接或间接地调用自身。语句 y sin(sin(x))是对标准数学函数 sin 的嵌套调用而不是递归调用因为 sin 函数并没有在其内部再次调用自己。编程题题解洛谷 B4050 [GESP202409 五级] 挑战怪物题解洛谷 B4051 [GESP202409 五级] 小杨的武器
GESP认证C++编程真题解析 | 202409 五级
附上汇总帖GESP认证C编程真题解析 | 汇总单选题第1题下面关于链表和数组的描述错误的是 。A. 数组大小固定链表大小可动态调整。B. 数组支持随机访问链表只能顺序访问。C. 存储相同数目的整数数组比链表所需的内存多。D. 数组插入和删除元素效率低链表插入和删除元素效率高。【答案】C【解析】错误的是C。链表由于需要额外存储指针通常比数组占用更多内存。第2题通过 操作能完成在双向循环链表结点p之后插入结点s 的功能其中next 域为结点的直接后继prev 域为结点的直接前驱。A. p-next-prev s; s-prev p; p-next s; s-next p-next;B. p-next-prev s; p-next s; s-prev p; s-next p-next;C. s-prev p; s-next p-next; p-next s; p-next-prev s;D. s-next p-next; p-next-prev s; s-prev p; p-next s;【答案】D【解析】选项D正确地更新了双向循环链表的指针。具体步骤如下1s-next p-next;将新结点s的后继设为p的后继。2p-next-prev s; 将原本p的后继的前驱设为s。3s-prev p;将新结点s的前驱设为p。4p-nexts;将p的后继设为s。这样所有相关指针都被正确更新实现插入操作。第3题对下面两个函数说法错误的是 。intsumA(intn){intres0;for(inti1;in;i){resi;}returnrs;}intsumB(intn){if(n1)return1;intresnsumB(n-1);returnres;}A. sumA体现了迭代的思想。B. SumB采用的是递归方式。C. SumB函数比SumA的时间效率更高。D. 两个函数的实现的功能相同。【答案】C【解析】sumA函数使用迭代方式通过一个for循环计算1到n的和。sumB函数采用递归方式逐步将问题分解为求1到n-1的和再加上n。由于递归调用会增加函数调用栈的开销因此sumB的时间效率低于sumA。两个函数实现了相同的功能艮即计算从1到n的整数和。第4题有如下函数fun则fun(20, 12的返回值为 。intfun(inta,intb){if(a%b0)returnb;elsereturnfun(b,a%b);}【答案】C【解析】fun(20, 12) fun(12, 8) fun(8, 4) 4第5题下述代码实现素数表的埃拉托斯特尼筛法筛选出所有小于等于n 的素数则横线上应填的最佳代码是 。voidsieve_Eratosthenes(intn){vectorboolis_prime(n1,true);vectorintprimes;for(inti2;i*in;i){if(is_prime[i]){primes.push_back(i);__________________________{// 在此处填入代码is_prime[j]false;}}}for(intisqrt(n)1;in;i){if(is_prime[i]){primes.push_back(i);}}returnprimes;}A. for (int ji; jn; j)B. for (int ji * i; jn; j)C. for (int ji * i; jn; ji)D. for (int ji; jn; ji)【答案】C【解析】埃拉托斯特尼筛法用于找出所有小于等于n的素数。代码中需要填入的是将i的倍数标记为非素数的循环。根据第9行代码可知j代表i的倍数。选项A和B中的j代表的不是i的倍数。选项D错误的将i素数本身标记为非素数。选项C更符合逻辑确保j从i * i开始将每个i的倍数标记为非素数。因此最佳选择是C。第6题下述代码实现素数表的线性筛法筛选出所有小于等于 n 的素数则横线上应填的代码是 。vectorintsieve_linear(intn){vectorboolis_prime(n1,true);vectorintprimes;for(inti2;in/2;i){if(is_prime[i])primes.push_back(i);___________________________{// 在此处填入代码is_prime[i*primes[j]]0;if(i%primes[j]0)break;}}for(intin/21;in;i){if(is_prime[i])primes.push_back(i);}returnprimes;}A. for (int j0; jprimes.size() i * primes[j]n; j)B. for (int j1; jprimes.size() i * jn; j)C. for (int j2; jprimes.size() i * primes[j]n; j)D. 以上都不对【答案】A【解析】该代码实现了线性筛法用于找出所有小于等于n的素数。关键在于内层循环确保将i的倍数标记为非素数。选项A中的for (int j0; jprimes.size() i * primes[j]n; j)正确地初始化j并且条件判断合理确保不会越界。内部逻辑is_prime[i * primes[j]]0;将i与当前质数的乘积标记为非素数如果i能被当前质数整除则跳出循环。因此最佳选择是A。第7题下面函数可以将n 的所有质因数找出来其时间复杂度是 。#includeiostream#includevectorvectorintget_prime_factors(intn){vectorintfactors;while(n%20){factors.push_back(2);n/2;}for(inti3;i*in;i2){while(n%i0){factors.push_back(i);n/i;}}if(n2){factors.push_back(n);}returnfactors;}A.O ( n 2 ) O(n^2)O(n2)B.O ( n l o g n ) O(nlogn)O(nlogn)C.O ( n l o g n ) O(\sqrt nlogn)O(nlogn)D.O ( n ) O(n)O(n)【答案】C【解析】该函数用于找出整数n的所有质因数。时间复杂度分析如下首先处理2的倍数通过while(n % 2 0)循环将所有2的因子加入结果中。这部分操作最多执行O ( l o g n ) O(logn)O(logn)次因为每次都将n除以2。接下来通过一个for循环从3开始检查奇数因子。内层while(n % i 0)循环在找到一个因子i时将其不断地除去。这部分操作的总次数与n的素因子的个数有关。由于质因数分解的过程涉及到对每个可能的因子进行试探最坏情况下需要检查到sqrt(n)因此外层for循环的复杂度为O ( s q r t ( n ) ) O(sqrt(n))O(sqrt(n))。结合内层while循环每次除法操作的复杂度为O ( l o g n ) O(logn)O(logn)。综合起来总体时间复杂度为O ( s q r t ( n ) ∗ l o g n ) O(sqrt(n)*logn)O(sqrt(n)∗logn)。因此正确答案是C。第8题现在用如下代码来计算x n x^nxnn个x相乘其时间复杂度为 。doublequick_power(doublex,unsignedn){if(n0)return1;if(n1)returnx;returnquick_power(x,n/2)*quick_power(x,n/2)*((n1)?x:1);}A.O ( n ) O(n)O(n)B.O ( n 2 ) O(n^2)O(n2)C.O ( l o g n ) O(logn)O(logn)D.O ( n l o g n ) O(nlogn)O(nlogn)【答案】A【解析】这段代码采用快速幂算法用于计算x n x^nxn。正确的快速幂算法的时间复杂度为O ( l o g n ) O(logn)O(logn)但是本题中的实现每每次递归调用会进行两次 quick_power 调用因此时间复杂度为O ( 2 l o g n ) O(2^{logn})O(2logn)即O ( n ) O(n)O(n)。第9题假设快速排序算法的输入是一个长度为n的已排序数组且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项 描述的是在这种情况下的快速排序行为。A.快速排序对于此类输入的表现最好因为数组已经排序。B.快速排序对于此类输入的时间复杂度是O ( n l o g n ) O(n log n)O(nlogn)。C.快速排序对于此类输入的时间复杂度是O ( n 2 ) O(n^2)O(n2)。D.快速排序无法对此类数组进行排序因为数组已经排序。【答案】C【解析】快速排序在已排序数组上选择第一个元素作为基准时每次划分都会导致一侧为空另一侧包含剩余的所有元素。这种情况下递归深度为n且每层需要O ( n ) O(n)O(n)时间因此总时间复杂度为O ( n 2 ) O(n^2)O(n2)。选项C正确。第10题考虑以下C代码实现的归并排序算法voidmerge(intarr[],intleft,intmid,intright){intn1mid-left1;intn2right-mid;intL[n1],R[n2];for(inti0;in1;i)L[i]arr[lefti];for(intj0;jn2;j)R[j]arr[mid1j];inti0,j0,kleft;while(in1jn2){if(L[i]R[j]){arr[k]L[i];i;}else{arr[k]R[j];j;}k;}while(in1){arr[k]L[i];i;k;}while(jn2){arr[k]R[j];j;k;}}voidmerger_sort(intarr[],intleft,intright){if(leftright){intmidleft(right-left)/2;merge_sort(arr,left,mid);merge_sort(arr,mid1,right);merge_sort(arr,left,mid,right);}}对长度为n的数组arr调用函数merge_sort(a, 0, n-1) 在排序过程中merge 函数的递归调用次数大约是 。A.O ( 1 ) O(1)O(1)B.O ( n ) O(n)O(n)C.O ( l o g n ) O(log n)O(logn)D.O ( n l o g n ) O(n log n)O(nlogn)【答案】B【解析】本题中询问的是merge函数递归调用的次数归并排序是一个分治算法它将数组不断二分直到每个子数组只有一个元素即有n个子数组合并过程中将这些数组两两合并直到合并成一个数组排序完成因此合并了n-1次大约是O ( n ) O(n)O(n)。第11题现在有n个人要过河每只船最多载2人船的承重为100kg。下列代码中数组weight 中保存有n个人的体重单位为kg已经按从小到大排好序代码输出过河所需要的船的数目采用的思想为 。inti,j;intcount0;for(i0,jn-1;ij;j--){if(weight[i]weight[j]100){i;}count;}printf(过河的船数: %d\n,count);A. 枚举算法B. 贪心算法C. 迭代算法D. 递归算法【答案】B【解析】代码实现的方法每次都尽量让最轻和最重的人一起过河以减少船的数量。这种策略是典型的贪心算法因为它在每一步选择中都做出局部最优解从而达到全局最优。因此答案为B。第12题关于分治算法以下哪个说法正确A. 分治算法将问题分成子问题然后分别解决子问题最后合并结果。B. 归并排序不是分治算法的应用。C. 分治算法通常用于解决小规模问题。D.分治算法的时间复杂度总是优于O ( n l o g ( n ) ) O(n log(n))O(nlog(n))。【答案】A【解析】A选项正确。分治算法的核心思想是将一个复杂的问题分解为相对简单的子问题分别求解后再合并其结果。B选项错误。归并排序正是分治算法的经典应用之一。C选项错误。分治算法通常用于大规模问题通过递归地分解问题来简化计算。D选项错误。分治算法的时间复杂度具体取决于问题和实现方式。第13题根据下述二分查找法在排好序的数组1369173139526179 中查找数值31循环while (left right执行的次数为 。intbinary_search(vectorintnums,inttarget){intleft0;intrightnums.size()-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){returnmid;}elseif(nums[mid]target){leftmid1;}else{rightmid-1;}}return-1;// 如果找不到目标元素返回-1}A. 1B. 2C. 3D. 4【答案】C【解析】具体步骤如下1初始left 0right 9mid 4元素为172更新left 5right 9mid 7元素为523更新left 5right 6mid 5元素为31共执行了3次循环因此答案是C。第14题以下关于高精度运算的说法错误的是 。A. 高精度计算主要是用来处理大整数或需要保留多位小数的运算。B. 大整数除以小整数的处理的步骤可以是将被除数和除数对齐从左到右逐位尝试将除数乘以某个数通过减法得到新的被除数并累加商。C. 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。D. 高精度加法运算的关键在于逐位相加并处理进位。【答案】C【解析】A选项正确。B选项正确。C选项错误。高精度乘法的运算时间与两个整数的长度都有关而不仅仅是较长者的位数。D选项正确。第15题当n7时下面函数的返回值为 。intfun(intn){if(n1)return1;elseif(n5)returnn*fun(n-2);elsereturnn*fun(n-1);A. 105B. 840C. 210D. 420【答案】C【解析】fun(1) 1fun(2) 2 * fun(1) 2 * 1 2fun(3) 3 * fun(2) 3 * 2 6fun(5) 5 * fun(3) 5 * 6 30fun(7) 7 * fun(5) 7 * 30 210判断题第1题在操作系统中需要对一组进程进行循环。每个进程被赋予一个时间片当时间片用完时CPU将切换到下一个进程。这种循环操作可以通过环形链表来实现。A. 正确B. 错误【答案】A【解析】在操作系统中时间片轮转调度算法Round Robin常用于实现多任务处理。环形链表是一种适合的结构因为它可以自然地循环遍历所有进程当一个进程的时间片用完时CPU可以迅速切换到下一个进程。因此这种循环操作确实可以通过环形链表来实现。第2题找出自然数n以内的所有质数常用算法有埃拉托斯特尼埃氏筛法和线性筛法其中线性筛法效率更高。A. 正确B. 错误【答案】A【解析】埃拉托斯特尼筛法和线性筛法都是用于找出自然数n以内所有质数的有效算法。埃氏筛法通过标记合数来找到质数而线性筛法在此基础上进行了优化避免了重复标记从而提高了效率。因此线性筛法确实比埃氏筛法更高效。第3题唯一分解定理表明任何一个大于1的整数都可以唯一地分解为素数之和。A. 正确B. 错误【答案】B唯一分解定理也称为算术基本定理表明任何一个大于1的整数都可以唯一地表示为若干个素数的乘积而不是和。例如30可以唯一分解为2×3×5)。题目中提到“素数之和”是错误的。第4题贪心算法通过每一步选择局部最优解从而一定能获得最优解。A. 正确B. 错误【答案】B【解析】贪心算法通过每一步选择局部最优解但并不总能保证得到全局最优解。只有在某些特定问题中贪心算法才能确保获得最优解。因此题目中的说法是不正确的。第5题快速排序和归并排序的平均时间复杂度均为O ( n l o g n ) O(nlogn)O(nlogn)且都是稳定排序。A.正确B.错误【答案】B【解析】快速排序和归并排序的平均时间复杂度均为(O ( n l o g n ) O(n log n)O(nlogn))但它们在稳定性上有所不同。归并排序是稳定排序而快速排序不是稳定排序因为元素相同的两个记录可能会因为交换而改变顺序。第6题插入排序的时间复杂度总是比快速排序低。A.正确B.错误【答案】B【解析】插入排序的时间复杂度在最坏情况下为O ( n 2 ) O(n^2)O(n2)而快速排序的平均时间复杂度为O ( n l o g n ) O(n log n)O(nlogn)。虽然插入排序在小规模数据或接近有序的数据上表现较好但总体来说快速排序在大多数情况下更高效。因此题目中的说法是不正确的。第7题第7题引入分治策略往往可以提升算法效率。一方面分治策略减少了操作数量另一方面分治后有利于系统的并行优化。A. 正确B. 错误【答案】A【解析】分治策略通过将问题分解为更小的子问题逐步解决并合并结果从而提升算法效率。它不仅减少了操作数量还能进行并行计算提高系统性能。因此引入分治策略确实可以提升算法效率。第8题二分查找要求被搜索的序列是有序的否则无法保证正确性。A. 正确B. 错误【答案】A【解析】二分查找算法要求被搜索的序列必须是有序的因为它通过不断折半缩小搜索范围来定位目标值。如果序列无序二分查找无法正确判断目标值的位置从而不能保证正确性。第9题在C语言中递归的实现方式通常会占用更多的栈空间可能导致栈溢出。A. 正确B. 错误【答案】A【解析】在C语言中递归函数调用会占用栈空间每次递归调用都会在栈上分配新的帧。如果递归深度过大可能导致栈溢出。因此递归实现方式确实通常会占用更多的栈空间有潜在的栈溢出风险。第10题对于已经定义好的标准数学函数sin(x)应用程序中的语句ysin(sin(x))是一种递归调用。A. 正确B. 错误【答案】B【解析】递归调用是指函数在其定义中直接或间接地调用自身。语句 y sin(sin(x))是对标准数学函数 sin 的嵌套调用而不是递归调用因为 sin 函数并没有在其内部再次调用自己。编程题题解洛谷 B4050 [GESP202409 五级] 挑战怪物题解洛谷 B4051 [GESP202409 五级] 小杨的武器
