2024年9月GESP编程能力认证C++等级考试六级真题(含答案和解析)

2024年9月GESP编程能力认证C++等级考试六级真题(含答案和解析)第一部分单项选择题（共15题，每题2分，满分30分）1.下列关于动态规划算法与分治算法的核心区别，描述正确的是（）A.动态规划要求子问题必须相互独立，分治算法不要求B.分治算法要求子问题必须存在重叠，动态规划不要求C.动态规划通过存储已求解子问题的答案避免重复计算，分治算法通常不做该存储D.动态规划只能求解最优化问题，分治算法只能求解计数问题【答案】C【解析】分治算法的核心是将原问题划分为若干互不重叠的独立子问题，递归求解后合并结果，典型应用如归并排序、快速排序，由于子问题无重叠，通常不需要额外存储子问题的解；动态规划适用于子问题存在重叠的场景，通过记忆化存储已计算的子问题结果避免重复计算，既可以求解最优化问题（如最长递增子序列、背包问题），也可以求解计数问题（如爬楼梯方案数、路径计数）。选项A颠倒了两类算法对子问题独立性的要求，选项B颠倒了子问题重叠的适用场景，选项D对两类算法的适用问题描述过于绝对，因此C表述正确。2.已知01背包问题中，共有n件物品，每件物品重量为w[i]，价值为v[i]，背包最大承重为W。若采用一维数组优化的动态规划解法，定义dp[j]表示背包容量为j时能装下的最大价值，则遍历背包容量j的正确顺序是（）A.从0到W正序遍历B.从W到w[i]逆序遍历C.从w[i]到W正序遍历D.遍历顺序不影响结果正确性【答案】B【解析】一维数组优化01背包时，为了保证每件物品只被选取一次，需要逆序遍历背包容量。如果正序遍历，当计算dp[j]时，dp[j-w[i]]已经是本轮（遍历当前物品i）更新过的值，相当于同一件物品可以被多次选取，会退化为完全背包的解法。逆序遍历时，计算dp[j]所依赖的dp[j-w[i]]仍然是上一轮（未放入物品i）的状态，能够保证每件物品最多被选一次，因此B正确。3.对长度为n的序列求解最长严格上升子序列长度，若采用基础的一维动态规划解法（无二分优化），其时间复杂度为（）A.O(logn)B.O(n)C.O(nlogn)D.O(n²)【答案】D【解析】基础一维DP求解最长上升子序列时，定义dp[i]表示以第i个元素结尾的最长上升子序列长度，对每个位置i需要遍历0到i-1的所有位置j，若a[j]<a[i]则更新dp[i]=max(dp[i],dp[j]+1)，总操作次数为n(n-1)/2，时间复杂度为O(n²)；O(nlogn)是基于二分查找优化后的解法时间复杂度，不属于基础一维DP的复杂度范畴，因此D正确。4.记忆化搜索相较于普通深度优先搜索（DFS）的核心优化点是（）A.减少了状态转移的方向B.避免了对重复状态的重复计算C.将递归转化为迭代降低栈溢出风险D.减少了每个状态可扩展的分支数量【答案】B【解析】记忆化搜索是在普通DFS的基础上，额外开辟存储空间记录每个已访问状态的计算结果，当再次进入同一状态时直接返回存储的结果，无需重复展开递归计算，核心是解决重叠子问题带来的重复计算开销。记忆化搜索不会改变状态转移方向、也不会减少分支数量，本质仍然是递归实现，因此A、C、D描述错误，B正确。5.给定一个共r行的数字三角形，第i行有i个数字，从顶部出发每次可以移动到当前位置正下方或者右下方的相邻节点，求从顶部到底部的路径最大数字和。若定义dp[i][j]表示从顶部出发走到第i行第j列时的最大路径和，下列状态转移方程正确的是（）A.dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+a[i][j]B.dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j]（边界位置单独处理）C.dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+a[i][j]D.dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]【答案】B【解析】数字三角形中，第i行第j列的位置只能从第i-1行的第j-1列（左上方相邻位置）和第i-1行第j列（正上方相邻位置）移动而来，因此当前位置的最大路径和为两个前驱位置的最大路径和加上当前位置的数值，需要注意每行首尾位置仅存在一个前驱，需要单独处理边界。选项A的前驱位置描述错误，访问j+1会造成数组越界；选项C是对路径数计数的转移方式，不是取最大值求最大和；选项D是自底向上递推时的转移方向，对应的dp定义应为从(i,j)位置走到三角形底部的最大和，与题干给出的dp定义不符，因此B正确。6.小明爬楼梯，每次可以走1阶、2阶或者3阶，若要爬到第n阶（n≥3），设dp[n]为爬到第n阶的合法方案数，下列递推关系正确的是（）A.dp[n]=dp[n-1]+dp[n-2]B.dp[n]=dp[n-1]*3C.dp[n]=dp[n-1]+dp[n-2]+dp[n-3]D.dp[n]=dp[n-1]*dp[n-2]*dp[n-3]【答案】C【解析】到达第n阶的最后一步有三种互斥且覆盖所有可能的情况：从n-1阶走1阶上来、从n-2阶走2阶上来、从n-3阶走3阶上来，因此总方案数为三种情况的方案数之和，递推式为dp[n]=dp[n-1]+dp[n-2]+dp[n-3]，边界条件为dp[0]=1（起点）、dp[1]=1、dp[2]=2，因此C正确。7.动态规划问题需要满足“无后效性”原则，下列对无后效性的描述正确的是（）A.某阶段的状态一旦确定，就不受这个状态之后的决策影响B.所有状态的取值必须是非负整数C.每个状态的转移只能向前不能回退D.问题必须能够划分为规模更小的子问题【答案】A【解析】无后效性是动态规划的核心前提之一，指的是当某个阶段的状态确定后，后续过程的演化仅与当前状态有关，与到达该状态的路径、以及该状态之前的决策无关，未来的决策不会影响已经确定的当前状态值。选项B是对状态取值的错误约束，状态值可以为任意符合问题定义的数值类型；选项C描述的是状态遍历的顺序性，不是无后效性的核心内涵；选项D是分治和动态规划共有的子问题特性，不是无后效性的定义，因此A正确。8.下列关于01背包和完全背包的描述，错误的是（）A.01背包中每件物品最多只能选取1次B.完全背包中每件物品可以选取无限次C.采用一维数组优化时，两者仅遍历背包容量的顺序不同D.两种背包问题都无法通过动态规划在多项式时间内求解【答案】D【解析】01背包和完全背包都是经典的动态规划可解问题，当背包容量为W、物品数为n时，一维优化解法的时间复杂度均为O(nW)，在常规算法题的数据范围内可以高效求解。选项A、B是两类背包问题的基本定义，描述正确；选项C描述正确：01背包逆序遍历容量避免重复选取物品，完全背包正序遍历容量支持物品多次选取，代码结构仅遍历顺序有差异；选项D描述错误，符合题干要求。9.求解两个长度分别为m和n的字符串的最长公共子序列长度，采用基础二维动态规划解法时，需要开辟的dp数组大小合理的是（）A.mB.nC.m*nD.m+n【答案】C【解析】最长公共子序列（LCS）的二维DP解法中，定义dp[i][j]表示第一个字符串前i个字符、第二个字符串前j个字符的最长公共子序列长度，i的取值范围为0~m，j的取值范围为0~n，因此数组大小为(m+1)*(n+1)，量级为m*n。一维滚动优化的LCS可以将空间复杂度降低到O(min(m,n))，但基础二维解法的数组大小为m*n量级，其余选项的数组大小无法存储全部状态，因此C正确。10.使用记忆化搜索求解斐波那契数列第n项时，时间复杂度和空间复杂度分别为（）A.时间O(2^n)，空间O(n)B.时间O(n)，空间O(n)C.时间O(n)，空间O(1)D.时间O(n²)，空间O(n)【答案】B【解析】普通递归求解斐波那契数列时，由于存在大量重复计算（如计算fib(5)需要多次重复计算fib(3)、fib(2)等值），时间复杂度为O(2^n)；记忆化搜索会将计算过的fib(k)结果存储在数组中，每个fib(k)仅需要计算1次，因此时间复杂度降低到O(n)，同时需要大小为n+1的数组存储已计算结果，加上递归栈的空间开销，空间复杂度为O(n)，因此B正确。11.求解整数拆分问题：将正整数n拆分为若干个正整数的和，求拆分后各数乘积的最大值。采用动态规划求解时，dp[0]的合理初始值是（）A.0B.1C.-1D.无穷大【答案】B【解析】整数拆分的状态转移中，当拆分出一个数k后，剩余部分为j-k，转移方程为dp[j]=max(dp[j],k*max(j-k,dp[j-k]))；当j-k=0时，意味着拆分结果就是k本身，此时乘以1可以保证数值计算正确，dp[0]=1作为边界值可以正确处理该情况。若初始化为0则会导致所有乘积结果为0，初始化-1或无穷大都会造成计算逻辑错误，因此B正确。12.经典打家劫舍问题：沿街有若干房屋，每个房屋内有一定数量的现金，相邻房屋装有连通的防盗系统，如果同时闯入相邻的两个房屋会触发报警。求不触发报警的情况下能偷窃到的最高金额。定义dp[i]为考虑前i个房屋时能偷窃到的最高金额，下列状态转移方程正确的是（）A.dp[i]=max(dp[i-1],dp[i-2]+a[i])B.dp[i]=dp[i-1]+a[i]C.dp[i]=dp[i-2]+a[i]D.dp[i]=max(dp[i-1],dp[i-2])+a[i]【答案】A【解析】对于第i个房屋，有两种互斥的合法选择：①不偷第i个房屋，此时最高金额等于前i-1个房屋的最高金额dp[i-1]；②偷第i个房屋，此时不能偷相邻的第i-1个房屋，最高金额等于前i-2个房屋的最高金额加上第i个房屋的现金dp[i-2]+a[i]。取两种选择的最大值即为dp[i]的正确取值，因此A正确。选项B会同时偷窃相邻房屋触发报警；选项C未考虑不偷第i个房屋的情况，无法得到全局最优解；选项D在两种选择下都加上了当前房屋的现金，相当于必须偷窃第i个房屋，逻辑错误。13.下列问题中，无法通过贪心算法得到全局最优解，必须使用动态规划求解的是（）A.部分背包问题（物品可分割为任意大小）B.01背包问题（物品不可分割）C.Huffman树构造D.正权图的单源最短路径（Dijkstra算法求解）【答案】B【解析】部分背包问题、Huffman树构造、Dijkstra求解正权图单源最短路径都是贪心算法的典型应用，每一步选择局部最优策略即可得到全局最优解；01背包问题中物品不可分割，局部选择单位重量价值最高物品的贪心策略无法保证全局最优，例如背包容量为4，物品A重量3价值3、物品B重量2价值2、物品C重量2价值2，贪心策略会优先选A，剩余容量1无法装下其他物品，总价值3，但实际最优是选择B和C总价值4，因此01背包必须通过动态规划枚举所有合法选择组合得到最优解，B正确。14.对r行的数字三角形最大路径和问题，采用动态规划求解时，若仅使用一维数组滚动更新状态，可达到的最优空间复杂度为（）A.O(r)B.O(r²)C.O(logr)D.O(1)【答案】A【解析】数字三角形的状态转移仅依赖上一行的状态值，因此可以用长度为r的一维数组，每次计算当前行的状态时从右往左更新数组值，不需要存储全部r行的二维数组，空间复杂度可以优化到O(r)；由于每行最多有r个元素，无法在O(1)或O(logr)空间下存储当前行的全部状态，因此A正确。15.下列关于子串和子序列的描述，正确的是（）A.子串要求字符在原字符串中连续出现，子序列不要求连续B.子序列要求字符在原字符串中连续出现，子串不要求连续C.长度为n的字符串，子串的个数为2^n个D.长度为n的字符串，子序列的个数为n(n+1)/2个【答案】A【解析】子串（连续子序列）要求选取的字符在原字符串中位置连续，长度为n的字符串（不含空串）的子串个数为n(n+1)/2；子序列选取的字符只需要保持原有的相对顺序，不需要位置连续，长度为n的字符串（不含空串）的子序列个数为2^n-1。选项A正确，其余选项颠倒了两者的定义，计数结果也存在错误。第二部分编程题（共2题，每题35分，满分70分）编程题1：受限台阶走法【题目描述】小明放学回家需要走一段共n阶的台阶，根据体力情况，小明走台阶时每次可以选择走1阶或者2阶，但是体能规则要求：不能连续两次走2阶，即如果某一步走了2阶，那么下一步必须走1阶调整体能，不能直接再走2阶。请计算小明从第0阶（地面起点）走到第n阶一共有多少种不同的合法走法。由于答案可能很大，请将结果对1000000007取模后输出。【输入格式】输入一行一个正整数n，表示台阶的总阶数，1≤n≤100000。【输出格式】输出一行一个整数，表示符合规则的走法总数对1000000007取模的结果。【样例输入】5【样例输出】6【样例解释】所有合法走法共6种，分别为：①1+1+1+1+1；②1+1+1+2；③1+1+2+1；④1+2+1+1；⑤2+1+1+1；⑥2+1+2。所有走法均不存在连续走2阶的情况，符合规则要求。【参考代码】usingnamespacestd;constintMOD=1000000007;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cin>>n;vector<vector<longlong>>dp(n+1,vector<longlong>(2,0));//dp[i][0]：到达第i阶，最后一步走1阶的方案数//dp[i][1]：到达第i阶，最后一步走2阶的方案数dp[0][0]=1;//起点状态，未走任何步数，默认符合不连续走2阶的要求dp[0][1]=0;for(inti=1;i<=n;++i){//最后一步走1阶，前i-1阶的所有合法状态都可以转移dp[i][0]=(dp[i-1][0]+dp[i-1][1])%MOD;//最后一步走2阶，需要i≥2，且前i-2阶的最后一步不能是2阶（避免连续走2阶）if(i>=2){dp[i][1]=dp[i-2][0]%MOD;}else{dp[i][1]=0;}}cout<<(dp[n][0]+dp[n][1])%MOD<<'\n';return0;}【题目解析】本题是带约束的线性动态规划问题，核心难点是规则中“不能连续走2阶”的限制，如果仅用一维数组记录到每个台阶的总方案数，无法区分到达该台阶时最后一步的走法，也就无法判断下一步走2阶是否会违反规则。因此通过增加状态维度，将每个位置的状态拆分为“最后一步走1阶”和“最后一步走2阶”两类，即可清晰实现状态转移：走1阶时不会造成连续2阶的违规，因此可以承接前一位置的所有合法状态；走2阶时必须保证上一步不是走2阶，因此只能从i-2位置“最后一步走1阶”的状态转移而来。算法时间复杂度为O(n)，空间复杂度可通过滚动变量优化至O(1)，对于n≤1e5的数据规模可以高效通过。编程题2：班会奖品采购【题目描述】班级准备为班会采购奖品，已知班费总金额为m元，共有n种不同的奖品可供选择，第i种奖品的单价为c[i]元，对应的学生满意度为w[i]。每种奖品最多只能买1件，要求总花费不能超过班费总金额，且采购的奖品带来的总满意度尽可能高。请计算能够达到的最大总满意度。【输入格式】第一行输入两个正整数n和m，分别表示奖品种类数和班费总金额，1≤n≤100，1≤m≤1000。接下来n行，每行输入两个正整数c[i]和w[i]，分别表示第i种奖品的单价和对应的满意度，1≤c[i]≤1000，1≤w[i]≤100。【输出格式】输出一行一个整数，表示不超过班费预算的前提下能获得的最大总满意度。【样例输入】41023344578【样例输出】12【样例解释】有两种最优采购方案：第一种是选择单价2元、3元、4元的三种奖品，总花费9元，总满意度3+4