今天为大家带来的是2023年12月认证C++ 七级真题解析回顾。
CCF编程能力等级认证，英文名Grade Examination of Software Programming（以下简称GESP），由中国计算机学会发起并主办，是为青少年计算机和编程学习者提供学业能力验证的平台。GESP覆盖中小学全学段，符合条件的青少年均可参加认证。GESP旨在提升青少年计算机和编程教育水平，推广和普及青少年计算机和编程教育。
GESP考察语言为图形化（Scratch）编程、Python编程及C++编程，主要考察学生掌握相关编程知识和操作能力，熟悉编程各项基础知识和理论框架，通过设定不同等级的考试目标，让学生具备编程从简单的程序到复杂程序设计的编程能力，为后期专业化编程学习打下良好基础。
本次为大家带来的是2023年12月份C++ 七级认证真题解析。
一、单选题（每题2分，共30分）
1、定义变量double x，如果下⾯代码输⼊为 100，输出最接近( )。
A. 0
B. -5
C. -8
D. 8
【答案】B
【解析】log10(x)表示10的多少次方是x，log2(x)表示2的多少次方是x，这里的x是输入的100，所以，log10(100)=2，又因为26=64，所以log2(100)是6.多，两者作差，约为-4.多，选B。
2、对于下⾯动态规划⽅法实现的函数， 以下选项中最适合表达其状态转移函数的为( )。
【答案】D
【解析】首先看代码，s数组是前缀和数组，f数组是dp数组，初始化f数组为正无穷，只有f[i][i]=0（1<=i<=n）的值为0，接着进行了区间dp，i和j分别是区间dp的两个端点，k是枚举的分界点，k的取值范围是[i,j)，所以选项C错误，根据第15行转移方程，发现后面的s[j]-s[i-1]是a[i]+a[i+1]+…+a[j]的和，且与k无关，可以单独拎出来，所以转移方程为f[i][j]=min(f[i][k]+f[k+1][j])+，选项D正确。选项A,B的错误点在于f(i,j)的初始值为正无穷，所以f(i,j)是不参与转移方程的。
3、下⾯代码可以⽤来求最长上升⼦序列（LIS）的长度，如果输⼊是：5 1 7 3 5 9，则输出是( )。
A. 9 7 5 1 1 9
B. 1 2 2 3 4 4
C. 1 3 5 7 9 9
D. 1 1 1 1 1 1
【答案】B
【解析】题目已经提示我们这是在求最长上升子序列，f数组的含义是以i结尾的最长上升子序列长度，ans是整个序列的最长上升子序列长度，代码中先依次输出了f[1],f[2],…,f[n],最后再输出ans，接着我们可以进行手算，1 7 3 5 9序列的f值分别为1,2,2,3,4,ans=4，所以正确答案为B。
4、C++语⾔中，下列关于关键字static的描述不正确的是( )。
A. 可以修饰类的成员函数。
B. 常量静态成员可以在类外进⾏初始化。
C. 若 a 是类 A 常量静态成员 ，则 a 的地址都可以访问且唯⼀。
D. 静态全局对象⼀定在 main 函数调⽤前完成初始化 ，执⾏完 main 函数后被析构。
【答案】C
【解析】static是静态意思，可以修饰成员变量和成员方法，static修饰成员变量表示该成员变量在内存中只存储一份，可以被共享访问，修改。选项C中a的地址都可以访问是不对的，所以本题选C。
5、G是⼀个⾮连通⽆向图，共有28条边，则该图⾄少有( )个顶点。
A. 6
B. 7
C. 8
D. 9
【答案】D
【解析】注意到题目里说的是非连通无向图，那么在同样的点数n下，为了有尽量多的边，可以分为两张连通图，一张n-1个点的完全图，另一张只有单独一个点，手算后可以发现，8个点的完全图有8*7/2=28个点，正好满足题目要求，所以总点数为9个，选D。
6、哈希表长31，按照下⾯的程序依次输⼊4 17 28 30 4，则最后的4存⼊哪个位置？ ( )
A. 3
B. 4
C. 5
D. 6
【答案】D
【解析】题目提示我们这是哈希表，根据代码，发现是按照%13进行哈希并且在发生冲突的情况下， 对应放到下一个位置，我们依次计算17 28 30 4会放置在什么位置，17放置在4,28放置在2,30本来放置在4，但是发生冲突，最终放置在5,4本来放置在4，但是4和5都被占用了，所以最终放置在6，选D。
7、某⼆叉树T的先序遍历序列为：{A B D F C E G H} ，中序遍历序列为：{B F D A G E H C} ，则下列说法中正确的是( )。
T的度为1
B. T的⾼为4
C. T有4个叶节点
D. 以上说法都不对
【答案】B
【解析】先序遍历是根左右，中序遍历是左根右，首先可以根据先序遍历和中序遍历画出完整的树，如下图：
所以正确答案为B。
8、下⾯代码段可以求两个字符串 s1 和 s2 的最长公共⼦串（LCS） ，下列相关描述不正确的是（ ）。
A. 代码的时间复杂度为0（n2）
B. 代码的空间复杂度为0（n2）
C. 空间复杂度已经最优
D. 采用了动态规划求解
【答案】C
【解析】题目告诉我们代码是在求解最长公共子串，代码中使用了双重for循环，且循环范围为[1~n1]以及[1~n2]，所以选项A正确，使用了二维数组dp，两维的长度也均为字符串长度，所以选项B正确，空间复杂度还可以使用滚动数组进一步优化为O(n)，所以选项C错误，本题选C，选项D正确，代码中使用的正是动态规划算法。
9、图的广度优先搜索中既要维护一个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历？( )
A. 双向栈
B. 队列
C. 哈希表
D. 堆
【答案】B
【解析】图的广度优先搜索是从若干点出发，依次向外进行逐层扩展的算法，使用队列存放待遍历节点，本题选B。
10、对关键字序列 {44， 36，23， 35， 52，73，90， 58} 建⽴哈希表 ，哈希函数为 h(k)=k%7 ，执⾏下⾯的 Insert 函数 ，则等概率情况下的平均成功查找长度（即查找成功时的关键字⽐较次数的均值）为( )。
A. 7/8
B. 1
C. 1.5
D. 2
【答案】C
【解析】代码采用链地址法来存储哈希，即将所有哈希地址相同的记录都链接在同一链表中，哈希方式为%7，我们依次对每个元素进行判断：44， 36，23， 35， 52，73，90， 58，每个数字的哈希地址分别是2,1,2,0,3,3,6,2，即哈希值为0~6的元素个数分别有1,1,3,2,0,0,1，对于之前的8个数字，它们查找成功的次数分别是1,1,2,1,1,2,1,3，总次数为12次，平均次数=12/8=1.5次，答案为C。
11、学⽣在读期间所上的某些课程中需要先上其他的课程 ，所有课程和课程间的先修关系构成⼀个有向图G，有向边<U, V>表⽰课程U是课程V的先修课，则要找到某门课程C的全部先修课下⾯哪种⽅法不可⾏？( )
A. BFS搜索
B. DFS搜索
C. DFS+BFS
D. 动态规划
【答案】D
【解析】查询有向图上有多少个点能够到达该点，可以在反图上进行搜索，所以选项A,B,C都可以，正确答案是D。
12、⼀棵完全⼆叉树有 2023 个结点 ，则叶结点有多少个？( )
A. 1024
B. 1013
C. 1012
D. 1011
【答案】C
【解析】设一棵完全二叉树有k层，则前k-1都是满二叉树，第k层的节点需要从左往右排列，那么第1层有1个节点，第2层有2个节点，第3层有4个节点。。。第9层有512个节点，此时总节点个数为1023，第10层放置剩余的1000个节点，那么叶节点个数为第10层的1000个节点，再加上第9层除去被第10层消耗的500个节点外剩余的12个节点，总共为1012个，选C 。也可以根据完全二叉树的节点编号性质来计算，即：第2023号结点的双亲是最后一个非叶结点，序号是2023/2=1011，所以叶节点个数为：2023-1011=1012。
13、⽤下⾯的邻接表结构保存⼀个有向图G，InfoType 和 VertexType 是定义好的类。设G有n个顶点、e条弧，则求图G中某个顶点u （其顶点序号为k）的度的算法复杂度是( )。
A. 0(n)
B. 0(e)
C. O(n ＋e)
D. O(n + 2＊8)
【答案】B
【解析】代码中使用了邻接表来存储边的信息，查找某个点的度时需要计算出度和入度。出度直接从该点出发，遍历该点出发的边即可。同时查询入度，可以在反图上进行类似操作，总复杂度为O(e),选B。也可以遍历整个邻接表，包含点顶点u的弧的数目就是该顶点的度。
14、给定⼀个简单有向图 G ，判断其中是否存在环路的下列说法哪个最准确？( )
A. BFS更快
B. DFS更快
C. BFS和DFS⼀样快
D. 不确定
【答案】D
【解析】对于不同的图，BFS和DFS的效率也不一样，有可能DFS更快，也有可能BFS更快，所以本题正确答案为D。
15、从顶点 v1 开始遍历下图 G 得到顶点访问序列 ，在下⾯所给的 4 个序列中符合⼴度优先的序列有⼏个？( )
A. 4
B. 3
C. 2
D. 1
【答案】B
【解析】广度优先遍历会首先搜索和s距离为k的所有顶点，然后再去搜索和s距离为k+1的其他顶点，所以第1个序列不是广度优先搜索的序列，因为v3和v1的距离超过了v4和v1的距离，但是序列中v3确排在v4前面，其余3个序列都是广度优先搜索的序列，本题选B。
二、判断题（每题2分，共20分）
1、 ⼩杨这学期准备参加GESP的7级考试 ，其中有关于三角函数的内容 ，他能够通过下⾯的代码找到结束循环的角度值。( )
【答案】正确
【解析】正确，代码将输入的角度转换成弧度，虽然对于任意的弧度，数学上均有，但int（）转换对某些x可能出现截断的情况，能够导致循环结束。
2、⼩杨在开发画笔刷⼩程序(applet)，操作之⼀是选中黄颜⾊，然后在下⾯的左图的中间区域双击后，就变成了右图。这个操作可以⽤图的泛洪算法来实现。( )
【答案】正确
【解析】泛洪算法是从某个点出发，向周边相邻的区域进行扩展，和操作的要求是一致的，正确。
3、假设⼀棵完全⼆叉树共有N个节点 ，则树的深度为log(N)+1。( )
【答案】错误
【解析】树的深度应该是[log2N+1]，直接写log会以e为底，错误。
4、给定⼀个数字序列 A1，A2，A3， ...，An，要求i和j（1<=i<=j<=n )，使A i+…+Aj 最⼤，可以使⽤动态规划⽅法来求解 。( )
【答案】正确
【解析】问题为最大子段和，动态规划的经典例题，设f[i]为以i结尾的子段最大值，则f[i]=max(a[i],f[i-1]+a[i]);正确。
5、若变量 x 为 double 类型正数 ，则 log(exp(x)) > log10(x) 。( )
【答案】正确
【解析】式子的左侧exp(x),是,所以log(exp(x))就等于x，等价于询问对于任意大于0的正实数x，是否有x>log10(x),当0<x<1时，log10(x)为负数，必然成立，当x==1时，log10(x)=0,成立，当x>1时，log10(x)的增长远远慢于x的增长，也成立，所以x>log10(x)成立，正确。
6、简单有向图有 n 个顶点和 e 条弧 ，可以⽤邻接矩阵或邻接表来存储 ，⼆者求节点 u 的度的时间复杂度⼀ 样 。( )
【答案】错误
【解析】错误，邻接矩阵求节点u的度时间复杂度为O(n),而邻接表为O(e)。
7、某个哈希表键值 x 为整数，为其定义哈希函数 H(x)=x%p，则 p 选择素数时不会产⽣冲突 。( )
【答案】错误
【解析】错误，设p为7，则键值14和21的hash值相同，产生了冲突。
8、动态规划只要推导出状态转移⽅程，就可以写出递归程序来求出最优解。( )
【答案】错误
【解析】错误，用递归法求解动态规划方程会造成重复计算，可能导致超时。另外，动态规划算法的核心是状态转移方程，但同时也需要定义状态、初始条件和边界条件等。
9、⼴度优先搜索（BFS）能够判断图是否连通 。( )
【答案】正确
【解析】正确，BFS是图论中遍历图的算法，可以从任意一个点出发进行BFS，记录遍历过程中经过的不同点的个数，若不等于总点数，则说明图不连通。
10、在C++中，如果定义了构造函数，则创建对象时先执⾏完缺省的构造函数，再执⾏这个定义的构造函数。( )
【答案】错误
【解析】错误，创建对象时最多只会执行一个构造函数。
三、编程题（每题25分，共50分）
1、商品交易
问题描述
市场上共有N种商品，编号从0⾄N-1，其中，第i种商品价值vi 元。
现在共有 M 个商⼈，编号从0⾄M - 1。在第j个商⼈这，你可以使⽤第x j 种商品交换第yj 种商品。每个商⼈都会按照商品价值进⾏交易，具体来说，如果vxj>vyj ，他将会付给你vyj - vxj 元钱；否则，那么你需要付给商⼈ vxj - vyj 元钱。除此之外，每次交易商⼈还会收取 1 元作为⼿续费，不论交易商品的价值孰⾼孰低。
你现在拥有商品 a ，并希望通过⼀些交换来获得商品 b 。请问你⾄少要花费多少钱？（当然，这个最小花费也可能是负数，这表示你可以在完成目标的同时赚取一些钱。）
输入描述
第一行四个整数 N,M,a,b，分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证0 ≤ a, b < N、保证a ≠ b。
第二行 N个用单个空格隔开的正整数 v0, v1, ... , vN-1，依次表示每种商品的价值。保证 1 ≤ vi < 109 。
接下来 M行，每行两个整数xj , yj，表示第j个商人愿意使用第xj种商品交换第yj种商品。保证0 ≤ xj ，yj < N保证xj ≠ yj 。
输出描述
输出一行一个整数，表示最少的花费。特别地，如果无法通过交换换取商品 ，请输出 No solution
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出1
样例解释1
可以先找 2号商人，花 2-1=1元的差价以及 1元手续费换得商品 1，再找 4号商人，花 4-2=2元的差价以及1元手续费换得商品 2。总计花费 1+1+2+1=5元。
样例输入 2
样例输出2
样例解释2
可以找 2号商人，直接换得商品 2 的同时，赚取 100 - 4 = 96 元差价，再支付 1元手续费，净赚 95 元。
也可以先找 0号商人换取商品 1，再找 1号商人换取商品 2，不过这样只能赚 94 元。
样例输入 3
样例输出3
数据规模
对于30%的测试点，保证 N ≤ 10，M ≤ 20。
对于70%的测试点，保证 N ≤ 103，M ≤ 104。
对于100%的测试点，保证 N ≤105，M ≤ 2 x 105。
【解题思路】发现不管通过什么方式换，最终因为价值不同而花费的金币数都是固定的，即v[b]-v[a],a为持有的商品，b为希望获得商品，唯一的区别是每次交易都要额外支付1块钱，所以需要最小化交易次数，我们把每件商品看作1个点，如果某件商品x能够换为某件商品y，则让x和y连一条边，我们的目标是从商品a出发尽快到达商品b，即经过的边的数量尽量少，可以通过bfs求经过的最少的边数，设这个值为min_dist[dst]，那么最终答案为min_dist[dst]+v[b]-v[a]。
【参考程序】
2、纸牌游戏
问题描述
你和小杨在玩一个纸牌游戏。
你和小杨各有3 张牌，分别是 0、1、2。你们要进行N轮游戏，每轮游戏双方都要出一张牌，并按 1战胜 0，2战胜1，0战胜2 的规则决出胜负。第i轮的胜者可以获得 2ai分，败者不得分，如果双方出牌相同，则算平局，二人都可获得ai分 (i=1,2,...,N)。
玩了一会后，你们觉得这样太过于单调，于是双方给自己制定了不同的新规则。小杨会在整局游戏开始前确定自己全部 n轮的出牌，并将他的全部计划告诉你: 而你从第 2 轮开始，要么继续出上一轮出的牌，要么记一次“换牌”。游戏结束时，你换了t次牌，就要额外扣 b1 + ... + bt 分。
请计算出你最多能获得多少分。
输入描述
第一行一个整数 N，表示游戏轮数。
第二行 N 个用单个空格隔开的非负整数 a1,...,aN，意义见题目描述。
第三行 N-1个用单个空格隔开的非负整数b1,...,bN-1，表示换牌的罚分，具体含义见题目描述。由于游戏进行 N轮，所以你至多可以换 N-1次牌。
第四行 N 个用单个空格隔开的整数 c1,...,cN，依次表示小杨从第 1轮至第 N 轮出的牌。保证
。
输出描述
一行一个整数，表示你最多获得的分数。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释
你可以第1轮出 0，并在第 2,3轮保持不变，如此输掉第 1,2轮，但在第 3轮中取胜，获得 2x 10 = 20 分;随后,你可以在第 4轮中以扣 1分为代价改出 1，并在第 4轮中取得胜利，获得 2 100 = 200分。如此，你可以获得最高的总分20 +200-1=219。
样例输入 2
样例输出 2
数据规模
对于30%的测试点，保证 N ≤ 15。
对于60%的测试点，保证 N ≤ 100。
对于所有测试点，保证 N ≤ 1,000; 保证 0 ≤ ai，bi ≤ 106。
【解题思路】考虑使用dp算法，设dp[i][j][k]表示前i轮中，第i轮出的牌为j(0<=j<=2),已经换过k次牌的最大得分，则
这里的a数组是奖励的得分，b数组是换牌的惩罚，c数组是小杨的出牌，result(x,y)表示出牌为x时和y的胜负情况(胜利返回2，平局返回1，失败返回0)
上面一行表示当前轮出牌和上一轮相同
下面一行表示不同，需要额外付出b[k]的代价
最终答案为
【参考程序】
【联系我们】
1. GESP微信：关注“CCF GESP”公众号，将问题以文字方式留言即可得到回复。
2. GESP邮箱：gesp@ccf.org.cn
注：请在邮件中详细描述咨询的问题并留下考生的联系方式及姓名、身份证号，以便及时有效处理。
3. GESP电话：0512-67656856
咨询时间：周一至周五(法定节假日除外）: 上午 8:30-12:00；下午 13:00-17:30
GESP第五期认证报名已启动，扫描下方二维码，关注GESP公众号即可报名
点击“阅读原文”，加入CCF。
原文始发于微信公众号（中国计算机学会）：2023年12月GESP认证C++七级试卷解析
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论