首页 › 试卷 › GESP编程能力等级认证 › GESP-Python六级 › 2024年9月CCF-GESP编程能力等级认证Python编程六级真题

2024年9月CCF-GESP编程能力等级认证Python编程六级真题 VIP

GESP-Python六级 共 27 题 2024 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

以下( )没有涉及Python语言的面向对象特性支持。

  • A Python中构造一个 class
  • B Python中调用 printf 函数
  • C Python中调用用户定义的类成员函数
  • D Python中构造来源于同一基类的多个派生类
查看答案与解析
答案:B
解析:

调用 printf 函数并没有涉及到类或者对象的概念,因此不属于面向对象特性的一部分。

2. 单选题

关于Python中面向对象的类的继承,下面说法错误的是( )

  • A 子类可以通过继承不能访问到父类的所有属性
  • B 多个子类可以继承同一个父类
  • C 子类和子类产生的对象都可以通过句点的方式拿到父类
  • D python中支持多继承
查看答案与解析
答案:A
解析:

A选项描述不正确,子类可以通过继承访问到父类的公有属性,但不能访问到私有属性。

B和D选项描述正确。

C选项描述正确,子类对象可以通过句点方式访问父类的公有属性。

3. 单选题

有6个元素,按照 6,5,4,3,2,1 的顺序进入栈S,下列( )的出栈序列是不能出现的( )。

  • A 5,4,3,6,1,2
  • B 4,5,3,1,2,6
  • C 3,4,6,5,2,1
  • D 2,3,4,1,5,6
查看答案与解析
答案:C
解析:

栈的操作是先进后出(FILO),出栈序列需要满足这个规则。

选项A、B和D都可以实现。

选项C无法实现,因为3出栈后不可能有4和6出栈。

4. 单选题

采用如下代码实现检查输入的字符串括号是否匹配,横线上应填入的代码为( )。

class Stack:
	def __init__(self):
		self.items = []
	def is_empty(self):
		return not self.items
	def push(self, item):
		self.items.append(item)
	def pop(self):
		if not self.is_empty():
			return self.items.pop()
	def peek(self):
		if not self.is_empty():
			return self.items[-1]
	def size(self):
		return len(self.items)
		
def paren_match(expr):
	s = Stack()
	balanced = True
	index = 0
	while index < len(expr) and balanced:
		symbol = expr[index]
		if symbol in '([{':
			________________
		else:
			if s.is_empty():
				balanced = False
			else:
				top = s.pop()
			if not matches(top, symbol):
				balanced = False
		index += 1
		
	if balanced and s.is_empty():
		return True
	else:
		return False
	
def matches(opening, closing):
	opens = '([{'
	closers = ')]}'
	return opening in opens and closers.index(closing) == opens.index(opening)
  • A s.push(symbol)
  • B s.pop(symbol)
  • C s.push(index)
  • D s.pop(index)
查看答案与解析
答案:A
解析:

当遇到开括号时,应该将开括号压入栈中,以便后续匹配闭括号。

正确的代码是 s.push(symbol)。

5. 单选题

下面代码判断队列的第一个元素是否等于 a,并删除该元素,横向上应填写( )。

import queue
q = queue.Queue()
a = 'a'
if ________________________________________
	q.get()
	print('元素 {} 是队列的第一个元素,并已被移除。'.format(a))
else:
	print('队列的第一个元素不是 {}.'.format(a))
  • A not q.empty() and q.queue[0] != a:
  • B not q.empty() and q.queue[0] == a:
  • C q.empty() and q.queue[0] == a:
  • D q.empty() and q.queue[0] != a:
查看答案与解析
答案:B
解析:

判断队列的第一个元素是否等于 a,并删除该元素,应填写 not q.empty() and q.queue[0] == a。

6. 单选题

假设字母表 {a,b,c,d,e} 在字符串出现的频率分别为 10%,15%,30%,16%,29%。若使用哈夫曼编码方式对字母进行二进制编码,则字符 abcdef 分别对应的一组哈夫曼编码的长度分别为( )。

  • A 4, 4, 1, 3, 2
  • B 3, 3, 2, 2, 2
  • C 3, 3, 1, 2, 1
  • D 4, 4, 1, 2, 2
查看答案与解析
答案:B
解析:

求哈夫曼编码需要先构建哈夫曼树,构建方法:① 从频率表中取出最小的两个元素,构建出新元素,② 将新元加入到频率表中,所以很明显abcdef分别对应的一组哈夫曼编码长度为3 3 2 2 2

7. 单选题

以下Python代码实现 n 位的格雷码,则横线上应填写( )。

def generate_gray_code(n):
	if n <= 0:
		return []
	if n == 1:
		return [0, 1]
		
	gray_code = generate_gray_code(n - 1)
	————————————————————————————————————————
	for x in gray_code]
	return gray_code + inverted_gray_code
  • A inverted_gray_code = [int((‘0’ * n + bin(x)[2:])[-n:], 2)
  • B inverted_gray_code = [int((‘1’ * n + bin(x)[2:])[-n:], 2)
  • C inverted_gray_code = [int((‘1’ * n + bin(x)[1:])[-n:], 2)
  • D inverted_gray_code = [int((‘1’ * n + bin(x)[2:])[n:], 2)
查看答案与解析
答案:B
解析:

题目要求实现一个函数generate_gray_code(n),该函数生成n位的格雷码。格雷码的特点是相邻两个数之间只有一个位不同。解析过程

1.基础情况

n <= 0:如果 n 小于等于0,返回空列表。

n == 1:如果 n 等于1,返回 [0, 1],这是1位格雷码。

2.递归调用

生成 n-1 位的格雷码:gray_code = generate_gray_code(n - 1)。

3.构造 n 位格雷码

我们需要构造n位的格雷码,方法是:

生成 n-1 位格雷码的前缀为 0 的部分。

生成 n-1 位格雷码的前缀为 1 的部分。

具体做法是:

对于 n-1 位格雷码的每个元素 x,构造前缀为 1 的 n 位格雷码。

横线处的代码

我们需要构造前缀为1的n位格雷码。对于n-1位格雷码的每个元素x,构造前缀为1的n位格雷码:

inverted_gray_code = [int((‘1’ * n + bin(x)[2:])[-n:], 2) for x in gray_code]

选项分析

inverted_gray_code = [int((‘0’ * n + bin(x)[2:])[-n:], 2) for x in gray_code]:

错误,前缀应该是 1,而不是 0。

inverted_gray_code = [int((‘1’ * n + bin(x)[2:])[-n:], 2) for x in gray_code]:

正确,构造前缀为 1 的 n 位格雷码。

inverted_gray_code = [int((‘1’ * n + bin(x)[1:])[-n:], 2) for x in gray_code]:

错误,bin(x)[1:] 应该是 bin(x)[2:]。

inverted_gray_code = [int((‘1’ * n + bin(x)[2:])[n:], 2) for x in gray_code]:

错误,切片 [n:] 导致截取错误的位置。

因此正确的答案是B

8. 单选题

给定一棵二叉树,其前序遍历结果为:ABDECFG,中序遍历结果为:DEBACFG,则这棵树的正确后序遍历结果是( )。

  • A EDBGFCA
  • B EDGBFCA
  • C DEBGFCA
  • D DBEGFCA
查看答案与解析
答案:A
解析:

在前序遍历中找根,在中序遍历中找根的左右子树,建好树后进行后序遍历。

结果为EDBGFCA

9. 单选题

一棵有 n 个结点的完全二叉树用数组进行存储与表示,已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点,则它的兄弟结点和右子结点的位置分别是( )。

  • A 8, 18
  • B 10, 18
  • C 8, 19
  • D 10, 19
查看答案与解析
答案:C
解析:

完全二叉树兄弟结点一般是左偶右奇,9号结点的兄弟结点只能是8号,而右子结点即9*2+1 = 19,选C

10. 单选题

二叉树的深度定义为从根结点到叶结点的最长路径上的结点数,则以下基于二叉树的深度优先搜索实现的深度计算函数中横线上应填写( )。

class Node:
	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None
		
def max_depth(root_node):
	if root_node is None:
		return 0
	else:
		left_depth = max_depth(root_node.left)
		right_depth = max_depth(root_node.right)
		_______________________________________
  • A return max(left_depth, right_depth)
  • B return min(left_depth, right_depth) + 1
  • C return max(left_depth, right_depth) + 1
  • D return max(left_depth, right_depth) - 1
查看答案与解析
答案:C
解析:

代码的思路是计算出当前根结点左子树的深度,右子树的深度,那么以根结点为子树的深度即max(左子树,右子树)+1,+1即将根结点的深度也计算在内,所以选C。

11. 单选题

以下基于二叉树的搜索实现的深度计算函数中横线上应填写( )。

class Node:
	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None
		
def height(root):
	if root is None:
		return 0
	else:
		left_height = height(root.left)
		right_height = height(root.right)
		_________________________________
  • A return max(left_height, right_height) + 1
  • B return min(left_height, right_height) - 1
  • C return min(left_height, right_height) + 1
  • D return max(left_height, right_height) - 1
查看答案与解析
答案:A
解析:

我们需要计算二叉树的深度。二叉树的深度是指从根节点到最远叶子节点的最长路径上的边数。这里的深度计算逻辑是递归的。基本情况:如果根节点 root 为空,返回 0,表示空树的深度为 0。

递归情况:

计算左子树的深度 left_height。

计算右子树的深度 right_height。

返回左右子树中深度较大的那个加上 1(根节点的高度)。

根据上述逻辑,横线处应该填写:

return max(left_height, right_height) + 1

这是因为我们要返回左右子树中深度较大的那个,并加上根节点的高度。

12. 单选题

二叉搜索树中的每个结点,其左子树的所有结点值都小于该结点值,右子树的所有结点值都大于该结点值。以下代码对给定的整数数组(假设数组中没有数值相等的元素),构造一个对应的二叉搜索树,横线上应填写():

class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None
		
class Solution:
	def isValidBST(self, root: TreeNode) -> bool:
		def helper(node, min_val, max_val):
			if not node:
				return True
			————————————————————————————————————————————————
				return False
			return helper(node.left, min_val, node.val) and helper(node.right,node.val, max_val)
			
		return helper(root, float('-inf'), float('inf'))
  • A if node.val <= min_val or node.val >= max_val:
  • B if node.val >= min_val or node.val >= max_val:
  • C if node.val <= min_val or node.val <= max_val:
  • D if node.val >= min_val or node.val <= max_val:
查看答案与解析
答案:A
解析:

题目描述了二叉搜索树(Binary Search Tree, BST)的性质,并给出了一个用于验证给定树是否为有效二叉搜索树的函数。我们需要填充横线上的代码,使其能够正确验证树的性质。

上述代码是一个用于验证二叉搜索树是否有效的函数isValidBST,并通过递归辅助函数helper来实现验证逻辑。

helper的作用是递归地验证当前节点node是否满足二叉搜索树的性质,即:

左子树的所有节点值小于当前节点值。

右子树的所有节点值大于当前节点值。

此外,函数还会传递当前节点值的有效范围min_val和max_val,确保节点值在指定范围内。

我们需要在横线上填充代码来检查当前节点的值是否在其有效范围内。具体来说:

如果当前节点值 node.val 小于等于 min_val 或者大于等于 max_val,则说明该节点不满足二叉搜索树的性质。

否则,继续递归检查左子树和右子树。

因此,正确的填充代码应该是:

if node.val <= min_val or node.val >= max_val: return False

因此选A

13. 单选题

对上题中的二叉搜素树,当输入数组为 [ 5 , 3 , 7 , 2 , 4 , 6 , 8 ] [5,3,7,2,4,6,8][5,3,7,2,4,6,8] 时,构建二叉搜索树,并采用如下代码实现的遍历方式,得到的输出是( )。

def traversal(tree_node* root) :
	if (root == nullptr) {
		return
	}
	
traversal(root->left)
print(root->val)
print(" ")
traversal(root->right)
  • A 5 3 7 2 4 6 8
  • B 2 3 4 5 6 7 8
  • C 2 4 3 6 8 7 5
  • D 2 4 3 5 6 7 8
查看答案与解析
答案:B
解析:

根据输入数组建BST为

然后根据 “左根右”的遍历规则输出为:

2 3 4 5 6 7 8,选B

14. 单选题

动态规划通常用于解决( )。

  • A 无法分解的问题
  • B 可以分解成相互依赖的子问题的问题
  • C 可以通过贪心算法解决的问题
  • D 只能通过递归解决的问题
查看答案与解析
答案:B
解析:

一个问题是否能用DP来解决我们的考虑一般有两点:① 最优子结构,②无后效性最优子结构即 选项B,可分解成相互依赖的子问题的问题,因此选B。

15. 单选题

阅读以下用动态规划解决的0-1背包问题的函数,假设背包的容量 W WW 是10kg,假设输入4个物品的重量 w e i g h t s weightsweights 分别为 1,3,4,6(单位为kg),每个物品对应的价值 v a l u e s valuesvalues 分别为 20,30,50,60,则函数的输出为( )。

def knapsack(capacity, weights, values):
	dp = [[0 for _ in range(capacity + 1)] for _ in range(len(weights) + 1)]
	for i in range(1, len(weights) + 1):
		for j in range(1, capacity + 1):
			if weights[i - 1] <= j:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
			else:
				dp[i][j] = dp[i - 1][j]
	return dp[-1][-1]
	
weights = [1, 3, 4,6]
values = [20,30,50,60]
capacity = 10
print(knapsack(capacity, weights, values))
  • A 90
  • B 100
  • C 110
  • D 140
查看答案与解析
答案:C
解析:

01背包问题,dp[n][w]表示将前n个物品放入容量为w的背包中得到的最大价值,4个物品的重量为1 3 4 6,价值为20 30 50 60,背包容量为10,最大价值是1 3 6 对应的110。

二、判断题

16. 判断题

C++、Python和JAVA等都是面向对象的编程语言。

  • A对
  • B错
查看答案与解析
答案:对
解析:

这些语言都支持面向对象编程的基本概念,如类、继承、封装和多态。

17. 判断题

在python中,类的静态成员变量只能被该类对象的成员函数访问。

  • A对
  • B错
查看答案与解析
答案:错
解析:

静态成员变量可以被类的所有实例共享,并且不仅限于成员函数访问,也可以在类外部访问。

18. 判断题

栈和队列均可通过数组或链表来实现,其中数组实现支持随机访问、占用内存较少,但插入和删除元素效率低;链表实现的元素插入与删除效率高,但元素访问效率低、占用内存较多。

  • A对
  • B错
查看答案与解析
答案:对
解析:

数组支持随机访问,插入和删除效率低;链表插入和删除效率高,但访问效率低,正确。

19. 判断题

运行以下python代码,屏幕将输出“derived class”。

class BaseClass:
	def my_method(self):
		print("base class")
		
class DerivedClass(BaseClass):
	def my_method(self):
		print("derived class")
		
derived_instance = DerivedClass()
derived_instance.my_method()
  • A对
  • B错
查看答案与解析
答案:对
解析:

定义基类BaseClass:

基类 BaseClass 定义了一个方法 my_method,该方法打印字符串 “base class”。

定义派生类DerivedClass:

派生类 DerivedClass 继承自 BaseClass。

派生类重写了基类中的 my_method 方法,该方法打印字符串 “derived class”。

创建派生类实例并调用方法:

创建 DerivedClass 的一个实例 derived_instance。

调用实例方法 my_method。

运行结果

当创建DerivedClass的实例并调用其my_method方法时,由于DerivedClass重写了基类BaseClass中的my_method方法,因此会执行派生类中的方法,并打印字符串"derived class"。

20. 判断题

如下列代码所示的基类(base)及其派生类(derived),则生成一个派生类的对象时,只调用派生类的构造函数。

class Base:
	def __init__(self):
		print("Base.__init__ called")
		
class Derived(Base):
	def __init__(self):
		print("Derived.__init__ called")
		super().__init__()
d = Derived()
  • A对
  • B错
查看答案与解析
答案:错
解析:

创建一个派生类的对象时,会先调用基类的构造函数,再调用派生类的构造函数。因此,题目中的描述是不正确的。

正确的构造顺序是:

调用基类 base 的构造函数,输出"base constructor"。

调用派生类 derived 的构造函数,输出"derived constructor"。

因此,题目描述 “生成一个派生类的对象时,只调用派生类的构造函数” 是错误的。

21. 判断题

哈夫曼编码本质上是一种贪心策略。

  • A对
  • B错
查看答案与解析
答案:对
解析:

哈夫曼编码通过每次选择局部最优解来达到全局最优解,符合贪心策略的定义。

22. 判断题

如果根结点的深度记为 1,则一棵恰有 2024 个叶结点的二叉树的深度最少是 12。

  • A对
  • B错
查看答案与解析
答案:对
解析:

考虑二叉树中第i层的叶结点数目最多为 2i-1, ,那 10 < i-1 < 11 , 11< i <12,因此 深度为 12是正确的。

23. 判断题

在非递归实现的树的广度优先搜索中,通常使用栈来辅助实现。

  • A对
  • B错
查看答案与解析
答案:错
解析:

广度优先搜索通常使用队列实现,而非栈。

24. 判断题

状态转移方程是动态规划的核心,可以通过递推方式表示问题状态的变化。

  • A对
  • B错
查看答案与解析
答案:对
解析:

状态转移方程是动态规划中表示状态变化的核心公式。

25. 判断题

应用动态规划算法时,识别并存储重叠子问题的解是必须的。

  • A对
  • B错
查看答案与解析
答案:对
解析:

动态规划算法通过存储重叠子问题的解来避免重复计算,提高效率。正确

三、简答题

26. 简答题

小杨和整数拆分

时间限制:20.0 s

内存限制:512.0 MB

题面描述

小杨有一个正整数n,小杨想将它拆分成若干完全平方数的和,同时小杨希望拆分的数量越少越好。

小杨请你编写程序计算出总和为n的完全平方数的最少数量。

输入格式

第一行包含一个正整数n,含义如题面所示。

输出格式

输出一个整数,代表总和为 n nn 的完全平方数的最少数量。


输入样例

18

输出样例

2

18=9+9=16+1+1,其中最少需要2个完全平方数。

对于全部数据,保证有1≤n≤105。

查看答案与解析
答案:<pre class="brush:python;toolbar:false">import math N = int(1e5) + 10 dp = [0] * N n = int(input()) for i in range(1, n + 1): dp[i] = i for j in range(1, int(math.sqrt(i)) + 1): dp[i] = min(dp[i - j * j] + 1, dp[i]) print(dp[n])</pre>
解析:

题目大意:给定一个正整数n,将其拆分成若干个完全平方数的和,要求拆分的数量越少越好。求最少需要多少个完全平方数才能构成n。

用DP进行求解

状态定义

设dp[i]表示构成整数i的最少完全平方数的数量。

状态转移方程

考虑如何通过已知的dp[j](其中j < i)来推导出dp[i]。

对于任意一个整数i,我们可以考虑将它拆分成一个完全平方数j2加上剩余部分i - j2 的和。因此, dp[i] 可以通过dp[i - j2] 来推导出来,即:

dp[i] =min 1≤ k ≤ i (dp[ i−j 2 ]+1)


解释:

dp[i - j2] 表示剩余部分 i - j2 的最少完全平方数数量。+ 1 表示当前添加了一个完全平方数 j2。

我们需要取所有可能的 j 的最小值,以确保 dp[i] 最小。

27. 简答题

算法学习

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨计划学习m种算法,为此他找了n道题目来帮助自己学习,每道题目至多学习一次。

小杨对于m种算法的初始掌握程度均为 0。第i道题目有对应的知识点ai即学习第i道题目可以令小杨对第ai种算法的掌握程度提高bi。小杨的学习目标是对m种算法的掌握程度均至少为k 。

小杨认为连续学习两道相同知识点的题目是不好的,小杨想请你编写程序帮他计算出他最少需要学习多少道题目才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。

输入格式

第一行三个正整数m,n,k,代表算法种类数,题目数和目标掌握程度。

第二行n个正整数a1,a2,a3,...,an,代表每道题目的知识点。

第二行n个正整数b1,b2,b3,...,bn,代表每道题目提升的掌握程度。

输出格式

输出一个整数,代表小杨最少需要学习题目的数量,如果不存在满足条件的方案,输出 -1。


输入样例1

3 5 10
1 1 2 3 3
9 1 10 10 1

输出样例1

4


输入样例2

2 4 10
1 1 1 2
1 2 7 10

输出样例2

-1

对于样例1,一种最优学习顺序为第一道题,第三道题,第四道题,第二道题。

对于全部数据,保证有1≤m,n≤105,1≤bi,k≤105,1≤ai≤m。

查看答案与解析
答案:<pre class="brush:python;toolbar:false">N = int(1e5) + 5 def cmp(i, j): return i &gt; j m,n, k = map(int, input().split()) score = [[] for _ in range(m + 2)] a = [0] * n b = [0] * n s = input().split() for i in range(n): a[i] = int(s[i]) s = input().split() for i in range(n): b[i] = int(s[i]) score[a[i]].append(b[i]) need = [0] * (m + 2) ans = 0 mx_meed = 0 mx_need_i = -1 for i in range(1, m + 1): score[i].sort(reverse=True) sum_vals = 0 for j in range(len(score[i])): sum_vals += score[i][j] if sum_vals &gt;= k: need[i] = j + 1 break if sum_vals &lt; k: print("-1") exit(0) ans += need[i] if need[i] &gt; mx_meed: mx_meed = need[i] mx_need_i = i if mx_meed - 1 &lt;= ans - mx_meed: print(ans) else: last = 0 for i in range(1, m + 1): if i != mx_need_i: last += len(score[i]) - need[i] print(2 * mx_meed - 1 if mx_meed - 1 &lt;= ans - mx_meed + last else -1)</pre><p><br/></p>
解析:

1.数据准备

读入数据,并将每道题目按知识点分类,记录每种算法通过题目提升掌握程度的列表score。

2.计算每种算法所需的题目数量

对于每种算法,我们需要计算达到目标掌握程度k所需的题目数量。为了最大化利用高分题目,我们需要按分数降序排序。

3.确定最少题目数量

我们需要找到一种安排,使得小杨学习的题目数量最少,并且避免连续学习相同知识点的题目。为此,我们找出需要题目最多的算法,并尝试调整学习顺序。

4.调整学习顺序

如果最多需要的题目数量mx_need减去1之后仍然不超过总需要的题目数量减去mx_need,那么可以通过调整顺序来满足要求;否则,输出-1。