链表【不具备】的特点是?( )
2025年3月CCF-GESP编程能力等级认证C++编程五级真题 VIP
一、单选题
双向链表中每个结点有两个指针域 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 是当前位的值加上前一位的进位。
二、判断题
单链表中删除某个结点 p(非尾结点),但不知道头结点,可行的操作是将 p 的值设为 p->next 的值,然后删除 p->next 。( )
查看答案与解析
删除某个结点 p,但不知道头结点,无法直接找到 p 的前驱结点。
但是可以复制后继结点的值,然后删除后继节点。
假设单链表为:A -> B -> C -> D,要删除 B:
将 B 的值设为 C 的值:B->data = C->data(链表变为 A -> C -> C -> D)。
删除 B->next(即 C):B->next = C->next(链表变为 A -> C -> D)。
最终效果:B 被删除了。
链表存储线性表时要求内存中可用存储单元地址是连续的。( )
查看答案与解析
链表中的结点在内存中,是 动态分配 的。
每个结点可以分布在内存的任意位置,通过指针(next)连接。
存储单元的地址可以不连续,也可以是连续的。
线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因数筛去一次,因此效率更高。( )
查看答案与解析
线筛的时间复杂度是 O(n),每个合数只被其最小质因数筛去一次。
而埃筛的时间复杂度是 O(nlog log n),相对来说会更高,是在筛选过程中存在重复操作。
本题答案为正确。
贪心算法通过每一步选择当前最优解,从而一定能获得全局最优解。( )
查看答案与解析
贪心算法是一种在每一步选择中都采取当前状态下最优(局部最优)的决策,从而希望导致全局最优解的算法策略,但是贪心算法 不一定能得到全局最优解。
递归函数必须具有一个终止条件,以防止无限递归。( )
查看答案与解析
正确,如果没有终止条件,函数会无限调用自身;
终止条件是递归的出口,确保问题规模能逐步缩小至可直接求解的情况。
快速排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )
查看答案与解析
快速排序的 平均时间复杂度为 O(nlog?n),但最坏情况下退化为 O(n^2)。
其性能与输入数据是否有序及 pivot 选择策略密切相关。
归并排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )
查看答案与解析
归并排序无论输入数据是否有序,归并排序的时间复杂度 始终为 O(nlog?n)。这是因为:
分解阶段:将数组递归地分成两半,直到子数组长度为 1,共需 log?n 层递归。
合并阶段:每一层需要 O(n) 的时间合并两个有序子数组。
总时间复杂度:递归深度 log?n × 每层 O(n)) = O(nlog?n)。
二分查找适用于对无序数组和有序数组的查找。( )
查看答案与解析
二分查找(Binary Search)是一种高效的查找算法,其前提条件:输入数组 必须是有序的。
小杨有100元去超市买东西,每个商品有各自的价格,每种商品只能买1个,小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买,这体现了分治思想。( )
查看答案与解析
分治法的核心是:
分解:将问题划分为若干 相互独立且结构相同 的子问题。
解决:递归解决子问题。
合并:将子问题的解合并为原问题的解。
小杨的策略是 每次选当前最便宜的商品,这种策略的本质是贪心算法。
不是分治,因为无问题分解,无子问题合并。
归并排序算法体现了分治算法,每次将大的待排序数组分成大小大致相等的两个小数组,然后分别对两个小数组进行排序,最后对排好序的两个小数组合并成有序数组。( )
查看答案与解析
分治法的核心是:
分解:将问题划分为若干 相互独立且结构相同 的子问题。
解决:递归解决子问题。
合并:将子问题的解合并为原问题的解。
归并排序体现了分治算法。
三、简答题
平均分配
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 有 2n 件物品,小 B 和小 C 想从小 A 手上买走这些物品。对于第 i 件物品,小 B 会以 bi 的价格购买,而小 C 会以 ci 的价格购买。
为了平均分配这 2n 件物品,小 A 决定小 B 和小 C 各自只能买走恰好 n 件物品。你能帮小 A 求出他卖出这 2n 件物品所能获得的最大收入吗?
【输入描述】
第一行,一个正整数 n。
第二行, 2n 个整数 b1、b2、……、b(2n)。
第三行, 2n 个整数 c1、c2、……、c(2n)。
【输出描述】
一行,一个整数,表示答案。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于 20% 的测试点,保证 1<=n<=8。
对于另外 20% 的测试点,保证 0<=bi<=1,0<=ci<=1 。
对于所有测试点,保证 0<=n<=10^5,0<=bi<=10^9 ,0<=ci<=10^9 。
查看答案与解析
原根判断
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 知道,对于质数 p 而言,p 的原根 g 是满足以下条件的正整数:
其中 a mod p 表示 a 除以 p 的余数。
小 A 现在有一个整数 T,请你帮他判断 a 是不是 p 的原根。
【输入描述】
第一行,一个正整数 T,表示测试数据组数。
每组测试数据包含一行,两个正整数 a、p。
【输出描述】
对于每组测试数据,输出一行,如果 a 是 p 的原根则输出 Yes ,否则输出 No 。
【样例输入1】
【样例输出1】
【数据范围】
对于 40% 的测试点,保证 3<=p<=1000。
对于所有测试点,保证 1<=T<=20, 3<=p<=10^9,1<a<p , p为质数。
对于所有测试点,保证 ,-100<= A(i,j) <=100 。