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

2024年12月GESP编程能力认证C++等级考试八级真题(含答案和解析)一、单选题（每题2分，共30分）。1.小杨家响应国家“以旧换新”政策，将自家的汽油车置换为新能源汽车，正在准备自编车牌。自编车牌包括5位数字或英文字母，要求第5位必须是数字，前4位中可以有最多1位英文字母。英文字母必须是大写，而且不能是O或I（因为容易与数字0或1混淆）。请问自编车牌共有多少种可能性？（）。答案：B。解析：（1）前4位中可以有最多1位英文字母，且英文字母不能是O或I。前4位的可能性分析：若前4位都是数字，每位有10种可能性（0-9），则有104=10000种可能性。若前4位中有1位是英文字母（24种可能性，除去O和I），则有4种位置可以放字母，其余3位是数字，有4*24*10*10*10=96000种可能性。（2）第5位必须是数字，有10种可能性（0-9）。总可能性为10*(10000+96000)=1060000种，答案为B。2.新年到，四家人在一起聚会。其中两家有三口人，另外两家有两口人。现在要安排大家在一张十人圆桌坐下，要求一家人必须相邻就座。由于有“主座”的习俗，每个座位都被认为是不同的。请问共有多少种就座方案？（）。答案：A。解析：（1）首先将每家看作一个整体，对这四家进行圆排列，圆排列的公式为(n−1)!，带入n=4，所以四家的圆排列有3!=6种。（2）然后考虑每家内部的排列：对于三口之家，内部排列有3!种。对于两口之家，内部排列有2!种。（3）本题有“主座”的习俗，每个座位都被认为是不同的。主座的可能性有10种。所以总的排列方式为6∗(3!)²*(2!)²*10=8640种。3.下面关于C++类继承的说法，错误的是（）。A.一个类可以继承多个类。B.一个类可以被多个类继承。C.一个类可以继承另一个类的子类。D.抽象类必须被至少一个类继承，否则会编译错误。答案：D。解析：在C++中，抽象类本身的定义是合法的，即使没有类继承它也不会产生编译错误，只是不能实例化。4.使用邻接表表达一个简单有向图，图中包含v个顶点、e条边，则该出边表中边节点的个数为（）。答案：D。解析：对于一个有向图，使用邻接表存储。邻接表中每个顶点对应一个链表，链表中的节点表示从该顶点出发的边所指向的顶点。边的数量为e条，每个边在邻接表中对应一个节点（因为是出边）。5.以下将二维数组作为参数的函数声明，哪个是符合语法的？（）。答案：C。解析：对于二维数组，必须指定除最左边一维之外的其他维的大小。选项A和B的第二维都没有指定大小。B：二维数组作为参数时，除最左边一维外，其他维必须指定大小，这里两维都未指定大小。选项C声明的是一个指向包含20个int的数组类型的指针，可以和二维数组参数对应，符合二维数组作为函数参数的正确声明方式。选项D声明的是一个包含20个int*类型的数组，并不是二维数组。6.已知两个点A、B在平面直角坐标系下的坐标分别为(xa,ya)和(xb,yb)，并分别定义变量doublexa,ya,xb,yb;存储坐标。假设直线AB的斜率存在，下列哪个表达式可以用来表达它？（）。答案：C。解析：对(xa,ya)和(xb,yb),斜率k=(ya-yb)/(xa-xb)。7.二项式的展开式中项的系数是（）。答案：C。解析：由二项式(a+b)n=∑C(n,k)*an-kbk,带入公式得到系数为C(6,3)=20,答案选C。8.以下关于动态规划的说法中，错误的是（）。A.动态规划方法有递推和递归两种实现形式。B.递归实现动态规划方法的时间复杂度总是不低于递推实现。C.动态规划方法将原问题分解为一个或多个相似的子问题。D.动态规划方法通常能够列出递推公式。答案：B。解析：对很多问题，动态规划的递推实现和递归实现的时间复杂度是一致的；对一些问题，递推实现的时间复杂度更低；对另一些问题，递归实现的时间复杂度更低。因此，既不能断言递推实现的时间复杂度总是不低于递归实现，也不能断言递归实现的时间复杂度总是不低于递推实现。这里的选项B错误。其他均正确。9.在下面的程序中，使用整数表示一种组合。整数二进制表示的某一位为1，表示该位对应的数被选中，反之为0表示未选中。例如，从0-5这6个数中选出3个，则0b111000代表选中3,4,5三个数，0b011001代表选中0,3,4三个数。zuhe_next函数按组合对应的整数由大到小的顺序，求出组合c的下一个组合。横线处可以填入的是（）。答案：D。解析：zuhe_next三个参数分别为(C当前组合对应的二进制状态,n个元素,选m个)。功能是按组合对应的整数由大到小的顺序，求出组合c的下一个组合。intlow2函数的目的是找到c中最低位的1所在的位置，D选项符合当前组合状态对应的二进制取位操作。10.下面程序的输出为（）。答案：A。解析：代码功能是求满足条件x+y+z<=15且x<=y<=z的整数三元组(x,y,z)的数量。11.下面最长公共子序列程序中，横线处应该填入的是（）。答案：C。解析：状态表示DP[i][j]由A序列的前i个字母，且由B序列的前j个字母中构成的LCS的长度。状态转移方程：①若Ai和Bj都位于公共子序列中，则必须满足Ai==Bj,也就是A的第i个元素与B的最第j元素相同。那么，只需要找LCS(A[i-1],B[j-1])，结果为LCS(A[i-1],B[j-1])的长度+1。②若Ai和Bj至少有一个不位于公共子序列中：1.LCS可以在(a1,a2,……a[i-1])和(b1,b2,b3……b[j])中找，记为LCS(A[i-1],B[j])；2.LCS可以在(a1,a2,……ai)和(b1,b2,b3……b[j-i])中找，记为LCS(A[i],B[j-1])；3.LCS可以在(a1,a2,……a[i-1])和(b1,b2,b3……b[j-1])中找，记为LCS(A[i-1],B[j-1])。第三个一定不优于前两个,当前情况记为:max(LCS(A[i-1],B[j]),LCS(A[i],B[j-1]))。目标状态:DP[n][m]。本题横线为上方的②情况，答案选C。12.下列Dijkstra算法中，横线处应该填入的是（）。A.B.C.D.答案：B。解析：朴素dijkstra算法，在非负权图中，用visited[]标记已经求得最短路的点(因为已经求得，所以后续不会再更新)，每次选择距离起点S的未求得最短路(visited[]==0)的,且最近的节点minv,由非负权图的原因，该节点minxj将加入已经求得最短路的点的集合，同时用minv尝试是否能更新S到其他待求节点的最短路。横线处就是用minv尝试是否能更新S到其他待求节点的最短路。13.假设图graph中顶点数v、边数e，上题程序的时间复杂度为（）。答案：B。解析：朴素Dijkstra+矩阵存储的复杂度为O(v²)。14.下面的快速排序程序中，两处横线处分别应填入的是（）。A.B.C.D.答案：A。解析：快速排序是一种基于分治策略的排序算法。它的基本思想是选择一个基准元素（pivot），通过一趟排序将待排记录分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。具体操作过程中，通常设置两个指针，一个从左向右（l），一个从右向左（r），通过比较指针所指元素与基准元素的大小关系来交换元素，最终将基准元素放到合适的位置，使得左边元素都小于等于它，右边元素都大于等于它。第一个横线处（while循环条件）：此处应该是循环进行划分操作的条件，即只要l小于r，就继续循环。所以应填入l<r。第二个横线处（quick_sort函数的参数）：第一次调用quick_sort是对基准元素左边的子数组进行排序，第二次调用是对基准元素右边的子数组进行排序。对于左边子数组，参数应该是quick_sort(a,pivot)，对于右边子数组，参数应该是quick_sort(a+pivot+1,n-pivot-1)。所以此处应填入a+pivot+1,n-pivot-1。15.上题程序的时间复杂度为（）。答案：D。解析：快速排序均摊复杂度为O(nlogn)。二、判断题（每题2分，共20分）。16.表达式'3'+'5'的结果为'8'，类型为char。（）。答案：错误。解析：字符'3'的ASCII码为51，字符'5'的ASCII码为53，因此运算结果的数值为104，与字符'8'的ASCII码56不同。17.在C++语言中，可以在函数内定义结构体，但该结构体类型只能在该函数内使用。（）。答案：正确。解析：C++中可以在函数内定义结构体。这种在函数内定义的结构体类型，其作用域仅限于该函数内部，外部函数无法使用这个结构体类型。18.对n个元素的数组进行排序，快速排序和归并排序的平均时间复杂度都为O(nlogn)。但快速排序存在退化情况，使得时间复杂度升高至O(n2)；归并排序需要额外的空间开销。（）。答案：正确。解析：排序复杂度表述正确。19.二维数组的最后一维在内存中一定是连续的，但第一维在内存中可能不连续。（）。答案：错误。解析：数组在内存中是连续存储的，二维数组也是，一行一行进行存储，第一行存完紧跟着存储第二行。例如定义二维数组inta[4][5]，存储元素a[0][4]之后紧跟着存储元素a[1][0]。不一定连续的一般是链表结构。20.使用math.h或cmath头文件中的函数，表达式log(1000)的结果类型为double、值约为3。（）。答案：错误。解析：log函数是以自然对数（底数为e≈2.71828）进行计算的，运算结果类型为double。log(1000)的值约等于6.907755。如果要得到3，可指定底数，即log10(1000)的结果约等于3。21.你有三种硬币，分别面值2元、5元和7元，每种硬币都有足够多。买一本书需要27元，则有8种硬币组合（组合与顺序无关，“1个2元+1个5元+1个2元”与“1个5元+2个2元”认为是同样的组合）可以正好付清，且不需要对方找钱。（）。答案：正确。解析：本题可以枚举出8种方案，也可以用DP。定义dp[i]:凑出金额i的组合数量。dp[0]=1，因为凑出0元有一种方法，就是什么都不选。状态转移方程：对于每个金额i（i>0），如果i大于等于硬币的面值coin，则dp[i]+=dp[i-coin]。可得凑27元的组合数为8。22.使用哈希函数f(x)=x%p建立键值为int类型的哈希表，只要p取小于等于哈希表大小的素数，可保证不发生碰撞。（）。答案：错误。解析：反例HASH大小为7，p=5（5是素数且小于等于7）时，对于键值5和10，哈希函数的计算结果都为0，会发生碰撞。23.杨辉三角中的第n行、第m项，即为将二项式(a+b)n展开后an-mbm项的系数。（）。答案：错误。解析：杨辉三角的n和m是从0开始的，第1行、第1列对应的系数为C(0,0)，第n行、第m项对应的系数为C(n-1,m-1)，因此错误。24.判断图是否连通，可以通过广度优先搜索实现。（）。答案：正确。解析：用广搜BFS搜索联通块的方式可判断图是否联通。25.要求解一元二次方程x2+ax+b=0，需要先判断表达式a^2-b*4>=0是否为真。（）。答案：错误。解析：判断Δ>=0,本题字母代入得到a²-4*b>=0，但在C/C++语言中，^是位异或运算符，不表示平方。三、编程题（每题25分，共50分）。26.试题名称：树上移动。题面描述：小杨有一棵包含n个节点的树，其中节点的编号从1到n，每个节点的颜色要么是白色要么是黑色。小杨可以任意选择节点s和节点t并从节点s出发移动到节点t，移动过程中小杨不能够经过重复节点。小杨希望自己在至多经过k个黑色节点的前提下，经过的总节点数尽可能多，请你帮小杨选择经过最多的节点数是多少。输入格式：第一行包含两个正整数n，k，代表节点数量和至多经过的黑色节点数。第二行包含n个正整数a1，a2，……，an，代表节点颜色，如果ai=0，代表节点颜色为白色，如果ai=1，代表节点颜色为黑色。之后n-1行，每行包含两个正整数ui，vi，代表存在一条连接节点ui和vi的边。输出格式：输出一个正整数，代表最多经过的节点数。对于全部数据，保证有1≤n≤1000，0≤k≤1000，0≤ai≤1。27.试题名称：排队。题目描述：小杨所在班级共有n位同学，依次以1，2，……，n标号。这n位同学想排成一行队伍，其中有些同学之间关系非常好，在队伍里需要排在相邻的位置。具体来说，有m对这样的关系(m