今天为大家带来的是2023年12月认证Python 七级真题解析回顾。
CCF编程能力等级认证，英文名Grade Examination of Software Programming（以下简称GESP），由中国计算机学会发起并主办，是为青少年计算机和编程学习者提供学业能力验证的平台。GESP覆盖中小学全学段，符合条件的青少年均可参加认证。GESP旨在提升青少年计算机和编程教育水平，推广和普及青少年计算机和编程教育。
GESP考察语言为图形化（Scratch）编程、Python编程及C++编程，主要考察学生掌握相关编程知识和操作能力，熟悉编程各项基础知识和理论框架，通过设定不同等级的考试目标，让学生具备编程从简单的程序到复杂程序设计的编程能力，为后期专业化编程学习打下良好基础。
本次为大家带来的是2023年12月份Python 七级认证真题解析。
一、单选题（每题2分，共30分）
1、假设变量x为float类型，如果下面代码输入为100，输出最接近( )。
A.0
B.-5
C.-8
D.8
【答案】B
【解析】本题属于考察用python解决数学问题，使用了一个数学上对数方式来计算，计算10为底的对数5减以2为底的对数5,答案为：-5。
2、对于下面动态规划方法实现的函数，以下选项中最适合表达其状态转移函数的为( )。
【答案】D
【解析】本题属于考察区间动态规划状态转移表达式的题目，根据程序，我们可以抓住程序的终点，可以知道，在本区间中，i和j是两个端点值，k是分界点，所以k的范围是在[i,j),所以C中累加到j+1错误。通过16行状态转移方程得知，s列表和k无关，所以将其单独提出来，所以选择D。
3、下面代码可以用来求最长上升子序列（LIS）的长度，如果输入是整数序列是：5 1 7 3 5 9，则输出是( )。
A. 9 7 5 1 1 9
B. 1 2 2 2 3
C. 1 3 5 7 9 9
D. 1 1 1 1 1 1
【答案】B
【解析】本题属于考察最长上升子序列的问题，要寻找arr中最长上升子序列，要明白，子序列未必是连续的。其中cnt是用来记录连续上升元素的个数，如果中途被打断，则cnt从1开始重新计算。而ans则是用来记录列表的最长子序列的个数。将数字5,1,7,3,5,9分别带入，ans值分别为1 2 2 2 3，选择B。
4、Python中，下列关于类描述不正确的是( )。
A. 类属性可以通过类的名称访问其值。
B. 类属性也可以称之为类的静态属性。
C. 和实例属性相同，类属性前面也必须有self关键字，并以句点间隔。
D. 如果在类的某个实例（对象）中修改类属性的值，则其他该类实例访问该值时，其值也随之改变。
【答案】C
【解析】本题属于考察类的知识点，类属性是指在类中函数之外的属性，不需要前面有self关键字，所以选择C。
5、G是一个非连通无向图，共有28条边，则该图至少有( )个顶点。
A. 6
B. 7
C. 8
D. 9
【答案】D
【解析】本题属于考察非连通无向图，问至少有几个顶点，所以最多会有一个点是独立的点，我们可以看成有28条边的无向完全图有多少顶点再额外+1点，根据公式n(n-1)/2=28，得出n为8，所以该非连通无向图至少为9个顶点，选择D。
6、哈希表长31，按照下面的程序依次输入4 17 28 30 4，则4存入哪个位置？（ ）
A. 3
B. 4
C. 5
D. 6
【答案】D
【解析】本题属于考察哈希表，解决哈希冲突的问题，根据题意我们发现，是按照%13进行哈希，并且在发生冲突的时候，放到下一个位置，我们依次将4 17 28 30 4带入，得出17在4号，28在2号，30本应在4号但是被占用顺位到5号，4在4号，发生冲突后顺位到6号，选择D。
7、某二叉树T的先序遍历序列为：{A B D F C E G H}，中序遍历序列为：{B F D A G E H C}，则下列说法中正确的是( )。
A. T的度为1
B. T的高为4
C. T有4个叶节点
D. 以上说法都不对
【答案】B
【解析】本题属于考察二叉树的遍历问题，已知先序和中序，可得到如图二叉树：
选择B。
8、下面代码段可以求两个字符串s1和s2的最长公共子串（LCS），下列相关描述不正确的是（ ）。
A. 代码的时间复杂度为O(n^2)
B. 代码的空间复杂度为O(n^2)
C. 空间复杂度已经最优
D. 采用了动态规划求解
【答案】C
【解析】本题属于考察最长公共子串LCS，根据程序，我们发现，代码中使用了双重for循环，所以时间复杂度为O(n^2)，A为正确。代码中使用了二维列表res，所以空间复杂度为O(n^2)，B为正确。代码使用了动态规划的算法。其中C选项，我们可以将二维列表优化为一维列表，每次向下滚动后，原来的一维列表内容就不再使用，所以可以使用更新的方式，不断的更新一维列表，是空间复杂度降为O(n)，选择C。
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
【解析】本题属于考察有向图的搜索，即寻找有向图中有多少个点能到达指定点，所以BFS ,DFS,DFS+BFS都可以，选择D。
12、一棵完全二叉树有2023个结点，则叶结点有多少个？( )
A. 1024
B. 1013
C. 1012
D. 1011
【答案】C
【解析】本题属于考察二叉树叶结点的问题，通过公式，在总结点为奇数时,带入(n+1)/2可得1012，选择C。
13、用下面的邻接表结构保存一个有向图G，InfoType和VertexType是定义好的类。设G有n个顶点、e条弧，则求图G中某个顶点u（其顶点序号为k）的度的算法复杂度是( )。
A. O(n)
B. O(e)
C. O(n+e)
D. O(n+2*e)
【答案】B
【解析】本题中使用了领接表来存储有向图边的信息，在查找某点的度时，有两种方法：
需要考虑出度和入度，在考虑出度时候，直接遍历该点的出边即可，入度则在反图中进行遍历即可。
直接在领接表中找到所有关于此点的弧的数目，就是此点的度。
两种方法总复杂度均为O(e)，所以选择B。
14、给定一个简单有向图G，判断其中是否存在环路的下列说法哪个最准确？( )
A. BFS更快
B. DFS更快
C. BFS和DFS一样快
D. 不确定
【答案】D
【解析】本题属于考察搜索算法速率的题目，BFS和DFS搜索的效率在不同的图中是不一样的，所以没法确定，选择D。
15、从顶点v1开始遍历下图G得到顶点访问序列，在下面所给的4个序列中符合广度优先的序列有几个？( )
{v1 v2 v3 v4 v5} ， {v1 v2 v4 v3 v5} ， {v1 v4 v2 v3 v5} ， {v1 v2 v4 v5 v3}
A. 4
B. 3
C. 2
D. 1
【答案】B
【解析】本题属于考察广度优先搜索题目，广度优先是先将和该结点相连的点遍历一次，上面4个都是从V1开始搜索，和V1相连接的只有V2,V4，所以V1之后应该是V2,V4其顺序没有关系，将第一个排除，和V2相连接的有V3,V5,和V4相连接的只有V3。所以后三个完全符合广度优先搜索，选择B。
二、判断题（每题2分，共20分）
1、小杨这学期准备参加GESP的7级考试，其中有关于三角函数的内容，他能够通过下面的代码找到结束循环的角度值。( )
【答案】正确
【解析】本题是一道数学题，其中第5行是将角度转换为弧度，通过数学定理sin2x+cos2x=1，来找到合适的角度，所以正确。
2、小杨在开发画笔刷小程序（applet），操作之一是选中黄颜色，然后在下面的左图的中间区域双击后，就变成了右图。这个操作可以用图的泛洪算法来实现。( )
【答案】正确
【解析】泛洪算法的本质是通过一个点向周边相邻区域进行扩散，符合题目要求，所以正确。
3、假设一棵完全二叉树共有N个节点，则树的深度为log(N)+1。( )
【答案】错误
【解析】计算完全二叉树的公式为 floor(log2N)+1，和题意不符，错误。
4、给定一个数字序列A1，A2，A3，...，An，要求i和j（1<=i<=j<=n），使Ai+…+Aj最大，可以使用动态规划方法来求解。( )
【答案】正确
【解析】本题是考察求最大字段和，是动态规划的经典题目，正确。
5、若变量x为float类型正数，则log(math.exp(x))>math.log10(x)。( )
【答案】正确
【解析】题目中math.exp(x)为ex,所以logeex结果为x，根据log10x函数图像得知，只有在0<x<1时，log10x为负数，在x=1时，log10x为0，且函数log10x的斜率小于函数x的斜率，所以x>log10x，符合题意，正确。
6、简单有向图有n个顶点和e条弧，可以用邻接矩阵或邻接表来存储，二者求节点u的度的时间复杂度一样。( )
【答案】错误
【解析】根据题意，求结点u邻接矩阵的时间复杂度为O(n)，邻接表时间复杂度为O(e)，不符合题意，错误。
7、某个哈希表键值x为整数，为其定义哈希函数H(x)=x%p，则p选择素数时不会产生冲突。( )
【答案】错误
【解析】根据题意，如果两个整数x分别为p的倍数，则会产生哈希冲突，不符合题意，错误。
8、动态规划只要推导出状态转移方程，就可以写出递归程序来求出最优解。( )
【答案】错误
【解析】动态规划算法的核心是状态转移方程，但是也有状态，初始条件和边界条件等要求，所以不符合题意，错误。
9、广度优先搜索（BFS）能够判断图是否连通。( )
【答案】正确
【解析】在图论中遍历图的算法包含BFS，可以通过任意一点找到图中所有点，将不同点的个数相加和总数做对比，则能判断是否为连通图。正确。
10、在Python中，如果定义了构造函数，则创建对象时先执行完缺省的构造函数，再执行这个定义的构造函数。( )
【答案】错误
【解析】一个类中可以1个或多个构造函数，但是只会默认执行最后一个构造函数。不符合题意，错误。
三、编程题（每题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。
【解题思路】本题属于最短路问题且权值为1，则可以使用BFS来求解最短路。该算法从初始商品开始，探索所有可能的交易组合，计算到达目标商品的最低成本。在这个过程中，维护一个队列来追踪待探索的交易路径，并记录已探索商品的最低成本，避免重复计算。该问题的关键在于合理设置数据结构来存储商品、商人和交易的信息，并高效实现BFS算法来找到最优解。
其中最低成本的计算：在BFS的过程中，记录到达每种商品的当前最低成本。如果找到一条新的交易路径，其总成本比当前记录的成本低，则更新成本。如果能够通过交易到达目标商品，并且没有其他更低成本的路径，算法结束并输出最低成本。如果无法通过交易到达目标商品，则输出“无解”。
此题目的关键是最小化交易次数，因为不同商品间的价值差是固定的。通过将每件商品视为一个点，如果商品x可以换成商品y，那么在x和y之间连一条边。目标是从持有的商品a尽快到达希望获得的商品b，即最少经过的边数。这可以通过广度优先搜索（BFS）来实现。求出的最少边数记为min_dist[dst]。最终答案是min_dist[dst] + v[b] - v[a]，其中v[b]和v[a]分别是商品b和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 轮出的牌。保证ci∈｛0,1,2｝。
输出描述
一行一个整数，表示你最多获得的分数。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 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次牌的最大得分。状态转移方程如下：
dp[i][j][k] = max(dp[i-1][j][k] + result(j, c[i]) * a[i], dp[i-1][j'][k-1] + result(j, c[i]) * a[i] - b[k]) 其中j != j'
这里a数组表示每轮的奖励得分，b数组是换牌的惩罚，c数组记录小杨每轮的出牌。result(x, y)函数判断出牌为x时与y的胜负情况（胜利返回2，平局返回1，失败返回0）。
第一部分的状态转移表示当前轮出的牌与上一轮相同，不需要额外的换牌成本。
第二部分表示当前轮出的牌与上一轮不同，需要支付换牌的代价b[k]。
最终答案是max(dp[n][j][k])，其中j的范围是0到2，k的范围是0到n-1。
通过这种方式，我们可以有效地计算在不同出牌选择和换牌次数下的最大得分，并找出获得最高总得分的策略。
【参考程序】
【联系我们】
1. GESP微信：关注“CCF GESP”公众号，将问题以文字方式留言即可得到回复。
2. GESP邮箱：[email protected]
注：请在邮件中详细描述咨询的问题并留下考生的联系方式及姓名、身份证号，以便及时有效处理。
3. GESP电话：0512-67656856
咨询时间：周一至周五(法定节假日除外）: 上午 8:30-12:00；下午 13:00-17:30
GESP第五期认证报名已启动，扫描下方二维码，关注GESP公众号即可报名
点击“阅读原文”，进入官网。
原文始发于微信公众号（中国计算机学会）：2023年12月GESP认证Python七级试卷解析
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论