GESP 2024年 9月认证 Python 六级真题

题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 B A C A B B B A C C A A B B C Python　六级 2024 年 09 ⽉ 1 单选题（每题 2 分，共 30 分） 第 1 题 以下（ ）没有涉及Python语⾔的⾯向对象特性⽀持。 A. Python中构造⼀个 class B. Python中调⽤ printf 函数 C. Python中调⽤⽤户定义的类成员函数 D. Python中构造来源于同⼀基类的多个派⽣类 第 2 题 关于Python中⾯向对象的类的继承，下⾯说法错误的是（ ） A. ⼦类可以通过继承不能访问到⽗类的所有属性 B. 多个⼦类可以继承同⼀个⽗类 C. ⼦类和⼦类产⽣的对象都可以通过句点的⽅式拿到⽗类 D. python中⽀持多继承 第 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 第 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() 1 2 3 4 5 6 7 8 9 10 A. s.push(symbol) B. s.pop(symbol) C. s.push(index) D. s.pop(index) 第 5 题 下⾯代码判断队列的第⼀个元素是否等于 ，并删除该元素，横向上应填写（ ）。 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: 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) 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 import queue q = queue.Queue() a = 'a' if ________________________________________ q.get() print('元素 {} 是队列的第一个元素，并已被移除。'.format(a)) else: print('队列的第一个元素不是 {}.'.format(a)) 1 2 3 4 5 6 7 8 D. 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 第 7 题 以下Python代码实现 位的格雷码，则横线上应填写（ ）。 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) 第 8 题 给定⼀棵⼆叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG，则这棵树的正确后序遍历 结果是（ ）。 A. EDBGFCA B. EDGBFCA C. DEBGFCA D. DBEGFCA 第 9 题 ⼀棵有 个结点的完全⼆叉树⽤数组进⾏存储与表⽰，已知根结点存储在数组的第 个位置。若存储在数组第 个位置的结点存在兄弟结点和两个⼦结点，则它的兄弟结点和右⼦结点的位置分别是（ ）。 A. 8, 18 B. 10, 18 C. 8, 19 D. 10, 19 第 10 题 ⼆叉树的深度定义为从根结点到叶结点的最长路径上的结点数，则以下基于⼆叉树的深度优先搜索实现的 深度计算函数中横线上应填写（ ）。 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 1 2 3 4 5 6 7 8 9 10 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 第 11 题 上⼀题的⼆叉树深度计算还可以采⽤⼆叉树的⼴度优先搜索来实现。以下基于⼆叉树的⼴度优先搜索实现 的深度计算函数中横线上应填写（ ）。 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 第 12 题 ⼆叉搜索树中的每个结点，其左⼦树的所有结点值都⼩于该结点值，右⼦树的所有结点值都⼤于该结点 值。以下代码对给定的整数数组(假设数组中没有数值相等的元素)，构造⼀个对应的⼆叉搜索树，横线上应填写（ ）: 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) _______________________________________ 1 2 3 4 5 6 7 8 9 10 11 12 13 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) _________________________________ 1 2 3 4 5 6 7 8 9 10 11 12 13 class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None 1 2 3 4 5 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: 第 13 题 对上题中的⼆叉搜素树，当输⼊数组为 时，构建⼆叉搜索树，并采⽤如下代码实现的遍历⽅ 式，得到的输出是（ ）。 A. B. C. D. 第 14 题 动态规划通常⽤于解决（ ）。 A. ⽆法分解的问题 B. 可以分解成相互依赖的⼦问题的问题 C. 可以通过贪⼼算法解决的问题 D. 只能通过递归解决的问题 第 15 题 阅读以下⽤动态规划解决的0-1背包问题的函数，假设背包的容量 是10kg，假设输⼊4个物品的重量 分别为 （单位为kg），每个物品对应的价值 分别为 ，则函数的输出为（ ）。 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')) 6 7 8 9 10 11 12 13 14 15 16 def traversal(tree_node* root) : if (root == nullptr) { return } traversal(root->left) print(root->val) print(" ") traversal(root->right) 1 2 3 4 5 6 7 8 9 def knapsack(capacity, weights, values): dp = [[0 for _ in range(capacity + 1)] for _ in range(len(weights) + 1)] 1 2 题号 1 2 3 4 5 6 7 8 9 10 答案 A. 90 B. 100 C. 110 D. 140 2 判断题（每题 2 分，共 20 分） 第 1 题 C++、Python和JAVA等都是⾯向对象的编程语⾔。 第 2 题 在python中，类的静态成员变量只能被该类对象的成员函数访问。 第 3 题 栈和队列均可通过数组或链表来实现，其中数组实现⽀持随机访问、占⽤内存较少，但插⼊和删除元素效率 低；链表实现的元素插⼊与删除效率⾼，但元素访问效率低、占⽤内存较多。 第 4 题 运⾏以下python代码，屏幕将输出“derived class”。 第 5 题 如下列代码所⽰的基类（base）及其派⽣类（derived），则⽣成⼀个派⽣类的对象时，只调⽤派⽣类的构造 函数。 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)) 3 4 5 6 7 8 9 10 11 12 13 14 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() 1 2 3 4 5 6 7 8 9 10 子任务编号 数据点占比 1 20% 2 40% 3 40% 第 6 题 哈夫曼编码本质上是⼀种贪⼼策略。 第 7 题 如果根结点的深度记为 ，则⼀棵恰有 个叶结点的⼆叉树的深度最少是 。 第 8 题 在⾮递归实现的树的⼴度优先搜索中，通常使⽤栈来辅助实现。 第 9 题 状态转移⽅程是动态规划的核⼼，可以通过递推⽅式表⽰问题状态的变化。 第 10 题 应⽤动态规划算法时，识别并存储重叠⼦问题的解是必须的。 3 编程题（每题 25 分，共 50 分） 3.1 编程题 1 试题名称：⼩杨和整数拆分 时间限制：20.0 s 内存限制：512.0 MB 3.1.1 题面描述 ⼩杨有⼀个正整数 ，⼩杨想将它拆分成若⼲完全平⽅数的和，同时⼩杨希望拆分的数量越少越好。 ⼩杨请你编写程序计算出总和为 的完全平⽅数的最少数量。 3.1.2 输入格式 第⼀⾏包含⼀个正整数 ，含义如题⾯所⽰。 3.1.3 输出格式 输出⼀个整数，代表总和为 的完全平⽅数的最少数量。 3.1.4 样例1 ，其中最少需要 个完全平⽅数。 class Base: def __init__(self): print("Base.__init__ called") class Derived(Base): def __init__(self): print("Derived.__init__ called") super().__init__() d = Derived() 1 2 3 4 5 6 7 8 9 181 21 对于全部数据，保证有 。 3.1.5 参考程序 3.2 编程题 2 试题名称：算法学习 时间限制：1.0 s 内存限制：512.0 MB 3.2.1 题面描述 ⼩杨计划学习 种算法，为此他找了 道题⽬来帮助⾃⼰学习，每道题⽬⾄多学习⼀次。 ⼩杨对于 种算法的初始掌握程度均为 。第 道题⽬有对应的知识点 ，即学习第 道题⽬可以令⼩杨对第 种 算法的掌握程度提⾼ 。⼩杨的学习⽬标是对 种算法的掌握程度均⾄少为 。 ⼩杨认为连续学习两道相同知识点的题⽬是不好的，⼩杨想请你编写程序帮他计算出他最少需要学习多少道题⽬才 能使得他在完成学习⽬标的同时避免连续学习两道相同知识点的题⽬。 3.2.2 输入格式 第⼀⾏三个正整数 ，代表算法种类数，题⽬数和⽬标掌握程度。 第⼆⾏ 个正整数 ，代表每道题⽬的知识点。 第⼆⾏ 个正整数 ，代表每道题⽬提升的掌握程度。 3.2.3 输出格式 输出⼀个整数，代表⼩杨最少需要学习题⽬的数量，如果不存在满⾜条件的⽅案，输出 -1。 3.2.4 样例1 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]) 1 2 3 4 5 6 7 8 9 10 11 12 13 3 5 10 1 1 2 3 3 9 1 10 10 1 1 2 3 41 子任务编号 数据点占比 1 30% 2 30% 3 40% 3.2.5 样例2 对于样例1，⼀种最优学习顺序为第⼀道题，第三道题，第四道题，第⼆道题。 对于全部数据，保证有 。 3.2.6 参考程序 2 4 10 1 1 1 2 1 2 7 10 1 2 3 -11 N = int(1e5) + 5 def cmp(i, j): return i > 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 >= k: need[i] = j + 1 break if sum_vals < k: print("-1") exit(0) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 ans += need[i] if need[i] > mx_meed: mx_meed = need[i] mx_need_i = i if mx_meed - 1 <= 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 <= ans - mx_meed + last else -1) 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51