2023年12月GESP认证Python七级试卷解析

今天为大家带来的是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  种商品交换第y_j 种商品。每个商⼈都会按照商品价值进⾏交易，具体来说，如果v_xj>v_yj ，他将会付给你v_yj - v_xj  元钱；否则，那么你需要付给商⼈ v_xj - v_yj元钱。除此之外，每次交易商⼈还会收取 1 元作为⼿续费，不论交易商品的价值孰⾼孰低。

你现在拥有商品 a ，并希望通过⼀些交换来获得商品 b 。请问你⾄少要花费多少钱？（当然，这个最小花费也可能是负数，这表示你可以在完成目标的同时赚取一些钱。）

输入描述

第一行四个整数 N,M,a,b，分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证0 ≤ a, b < N、保证a ≠ b。

第二行 N个用单个空格隔开的正整数 v₀, v₁, ... , v_N-1，依次表示每种商品的价值。保证 1 ≤ v_i < 10⁹ 。

接下来 M行，每行两个整数x_j , y_j，表示第j个商人愿意使用第x_j种商品交换第yj种商品。保证0 ≤ x_j ，y_j < N保证x_j ≠ y_j  。

输出描述

输出一行一个整数，表示最少的花费。特别地，如果无法通过交换换取商品 ，请输出 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 ≤ 10³，M ≤ 10⁴。

对于100%的测试点，保证 N ≤10⁵，M ≤ 2 x 10⁵。

【解题思路】本题属于最短路问题且权值为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轮的胜者可以获得 2a_i 分，败者不得分，如果双方出牌相同，则算平局，二人都可获得a_i分 (i=1,2,...,N)。

玩了一会后，你们觉得这样太过于单调，于是双方给自己制定了不同的新规则。小杨会在整局游戏开始前确定自己全部 n轮的出牌，并将他的全部计划告诉你: 而你从第 2 轮开始，要么继续出上一轮出的牌，要么记一次“换牌”。游戏结束时，你换了t次牌，就要额外扣 b1 + ... + bt 分。

请计算出你最多能获得多少分。

输入描述

第一行一个整数 N，表示游戏轮数。

第二行 N 个用单个空格隔开的非负整数a₁,...,a_N，意义见题目描述。

第三行 N-1个用单个空格隔开的非负整数 b₁,...,b_N-1，表示换牌的罚分，具体含义见题目描述。由于游戏进行 N轮，所以你至多可以换 N-1次牌。

第四行 N 个用单个空格隔开的整数 c1,...,c_N，依次表示小杨从第 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 ≤ a_i，b_i ≤ 10⁶。

【解题思路】【解析】本题基于动态规划（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邮箱：[e-mail]

注：请在邮件中详细描述咨询的问题并留下考生的联系方式及姓名、身份证号，以便及时有效处理。

3. GESP电话：[phone]

咨询时间：周一至周五(法定节假日除外）: 上午 8:30-12:00；下午 13:00-17:30

GESP第五期认证报名已启动，扫描下方二维码，关注GESP公众号即可报名

点击“阅读原文”，进入官网。