查看原文
其他

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

中国计算机学会 中国计算机学会
2024-08-23



今天为大家带来的是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 种商品交换第y种商品。每个商⼈都会按照商品价值进⾏交易,具体来说,如果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 < 10

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

输出描述

输出一行一个整数,表示最少的花费。特别地,如果无法通过交换换取商品 ,请输出 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邮箱:gesp@ccf.org.cn

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

3. GESP电话:0512-67656856

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


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




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

继续滑动看下一个
中国计算机学会
向上滑动看下一个

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存