GESP-C++五级 题库
下面的 C++ 代码用于在升序数组 lst 中查找目标值 target 最后一次出现的位置。相关说法,正确的是?( )
有关下面C++代码的说法,【错误】的是?( )
硬币找零问题中要求找给客户最少的硬币。 coins 存储可用硬币规格,单位为角,假设规格都小于10角,且一定有1角规格。
amount 为要找零的金额,约定必须为1角的整数倍。输出为每种规格及其数量,按规格从大到小输出,如果某种规格不必要,则输出为0。
下面是其实现代码,相关说法正确的是?( )
关于下述C++代码的快速排序算法,说法【错误】的是?( )
小杨编写了一个如下的高精度除法函数,则横线上应填写的代码为?( )
链表【不具备】的特点是?( )
双向链表中每个结点有两个指针域 prev 和 next ,分别指向该结点的前驱及后继结点。
设 p 指向链表中的一个结点,它的前驱结点和后继结点均非空。要删除结点 p ,则下述语句中【错误】的是?( )
要删除双向链表中的结点 p,需要正确调整其前驱(prev)和后继(next)结点的指针:
让 p->prev->next 指向 p->next(前驱的后继指向 p 的后继)。
让 p->next->prev 指向 p->prev(后继的前驱指向 p 的前驱)。
选项A错误:
p->next->prev = p->next; // 错误:让后继的前驱指向自己(p->next),破坏了链表结构
p->prev->next = p->prev; // 错误:让前驱的后继指向自己(p->prev),链表断裂
假设双向循环链表包含头尾哨兵结点(不存储实际内容),分别为 head 和 tail ,链表中每个结点有两个指针域 prev 和 next ,分别指向该结点的前驱及后继结点。
下面代码实现了一个空的双向循环链表,横线上应填的最佳代码是?( )
双向循环链表的结构:
头哨兵 head:
head->prev 应该指向链表的最后一个结点(即 tail)。
head->next 应该指向链表的第一个实际结点(如果链表为空,则指向 tail)。
尾哨兵 tail:
tail->prev 应该指向链表的最后一个实际结点(如果链表为空,则指向 head)。
tail->next 应该指向链表的第一个结点(即 head)。
由于链表为空,head 和 tail 应该互相指向对方:
head->next = tail
tail->prev = head
用以下辗转相除法(欧几里得算法)求gcd(84, 60)的步骤中,第二步计算的数是?( )
调用gcd(84, 60)函数中:
big=84,small=60,big % small不为零,递归调用:
gcd(60, 24)。
根据唯一分解定理,下面整数的唯一分解是正确的?( )
唯一分解定理指出:任何一个大于 1 的整数,要么本身是一个质数,要么可以唯一地分解为一系列质数的乘积。
需要检查每个选项的分解是否 全部是质数,只有选项D符合。
下述代码实现素数表的线性筛法,筛选出所有小于等于 n 的素数,横线上应填的最佳代码是?( )
线性筛法的核心思想是 每个合数只被其最小质因数筛除一次,从而保证 O(n) 的时间复杂度。
内层循环的目的是 筛除 i×primes[j],因此需要满足:
j 不超过 primes 数组的大小(避免越界访问)。
i×primes[j]≤n(筛除的合数不能超过 n)。
本题答案为选项C。
在程序运行过程中,如果递归调用的层数过多,会因为( )引发错误?
如果递归层数过深,栈空间会被耗尽,导致 栈溢出错误。
对下面两个函数,说法【错误】的是?( )
两个计算阶乘的函数 factorialA 和 factorialB。
factorialA采用递归的方法,factorialB 采用循环方式实现,二者的时间复杂度均为O(n)。
下算法中,( )是不稳定的排序?
稳定排序 是指:如果两个相等的元素在排序前后的相对位置保持不变。
不稳定排序 是指:相等的元素在排序后可能交换位置。
对于选择排序,每次从未排序部分选择最小(或最大)元素,放到已排序部分的末尾。
例如:[5, 5, 2]进行排序,[5(1), 5(2), 2](用下标区分两个 5),找到最小值 2,交换 5(1)和 2,数组变为:[2, 5(2), 5(1)],两个5的相对顺序改变了。
考虑以下C++代码实现的快速排序算法,将数据从小到大排序,则横线上应填的最佳代码是?( )
快速排序是一种分治算法,其基本步骤如下:
选择基准:从数组中选择一个元素作为基准(通常选择最后一个元素)。
分区:重新排列数组,使得所有比基准小的元素放在基准前面,所有比基准大的元素放在基准后面。分区完成后,基准就位于其最终排序后的正确位置。
递归排序:递归地对基准前后的子数组进行快速排序。
在分区过程中:
i初始化为low - 1,表示小于基准的区域最初为空。
j从low到high - 1遍历数组。
如果arr[j]小于pivot,则i增加1,并将arr[i]和arr[j]交换。这样,arr[i]现在是一个小于pivot的元素。
本题答案为选项B。
若用二分法在[1, 100]内猜数,最多需要猜( )次?
二分查找每次将搜索区间对半分,最坏情况下需要猜测的次数:
2^6<100(6 次不够),2^7>=100(7 次足够)。
下面代码实现了二分查找算法,在数组 arr 找到目标元素 target 的位置,则横线上能填写的最佳代码是?( )
计算 mid 需要满足:
正确性:必须保证 mid 是当前区间的中间位置。
安全性:避免整数溢出(当 left 和 right 很大时,left + right 可能溢出)。
选项A:int mid = left + (right - left) / 2,数学等价于选项C,但是通过 right - left 避免直接计算 left + right,防止溢出。
贪心算法的核心特征是?( )
贪心算法是一种在每一步选择中都采取当前状态下最优(局部最优)的决策,从而希望导致全局最优解的算法策略,但是贪心算法 不一定能得到全局最优解。
函数 int findMax(int arr[], int low, int high) 计算数组中最大元素,其中数组 arr 从索引low 到 high ,( )正确实现了分治逻辑?
分治法的核心思想是:分解,解决,合并。
对于 求数组最大值,分治法的具体实现是:
基准情况:如果 low == high,说明区间只有一个元素,直接返回 arr[low]。
分解:计算中间位置 mid。
递归求左半部分 [low, mid] 的最大值 leftMax。
递归求右半部分 [mid+1, high] 的最大值 rightMax。
合并:比较 leftMax 和 rightMax,返回较大者。
小杨编写了一个如下的高精度乘法函数,则横线上应填写的代码为?( )
高精度乘法(大数乘法)通过 逐位相乘并处理进位 来实现。
选项B正确,temp 是当前位的值加上前一位的进位。