2024年12月CCF—GESP（Python六级）编程能力等级认证试卷
六级
2024
2025-05-30 16:34:45
104次
一、单选题
下面程序是一个二叉排序树的，横线处应该填入的是（ ）。
class BinarySortTree: def __init__(self): self.root = None def insert(self, key, value): node = TreeNode(key, value) if self.root is None: self.root = node return current = self.root while True: if key < current.key: ___________________________ current = current.left else: if current.right is None: current.right = node return current = current.right def search(self, key): current = self.root while current: if current.key == key: return current.value elif current.key > key: current = current.left else: current = current.right return None def inorder_traversal(self, node): if node: self.inorder_traversal(node.left) print(node.key, node.value) self.inorder_traversal(node.right)
A．if current.left is None: current.right = node return |
B．if current.right is None: current.right = node return |
C．if current.right is None: current.left = node return |
D．if current.left is None: current.left = node return |
【知识点】 CCF—GESP Python六级
二、判断题
三、编程题
运送物资
时间限制：2.0 s
内存限制：512.0 MB
题面描述
小杨管理着 m 辆货车，每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有 n 个运输站点，这些站点位于 A 市和 B 市之间。
每次运送物资时，货车从初始运输站点出发，前往 A 市或 B 市，之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点，其中 A 市的坐标为 ，B 市的坐标为 x ，运输站点的坐标为 p 且有 0<p<x，货车每次去 A 市运送物资的总行驶路程为 2p，去 B 市运送物资的总行驶路程为 2(x−p)。
对于第 i 个运输站点，其位置为 pi 且至多作为 ci 辆车的初始运输站点。小杨想知道，在最优分配每辆货车的初始运输站点的情况下，所有货车每天的最短总行驶路程是多少。
输入格式
第一行包含三个正整数 n,m,x，代表运输站点数量，货车数量和两市距离。
之后 n 行，每行包含两个正整数 pi,ci，代表第 i 个运输站点的位置和最多容纳车辆数。
之后 m 行，每行包含两个正整数 ai,bi，代表第 i 辆货车每天需要向 A 市运送 ai 次物资，向 B 市运送 bi 次物资。
输出格式
输出一个正整数，代表所有货车每天的最短总行驶路程。
输入样例
3 4 10 1 1 2 1 8 3 5 3 7 2 9 0 1 10000
输出样例
40186
样例解释
第1辆车的初始运输站点为站点 3，第 2 辆车的初始运输站点为站点 2。第 3 辆车的初始运输站点为站点 1，第 4 辆车的初始运输站点为站点 3。此时总行驶路程最短，为 40186。
对于全部数据，保证有1≤n,m≤105,2≤x≤108,0<pi<x,1≤ci≤105,0≤ai,bi≤105。数据保证 ∑ci≥m。
【知识点】 CCF—GESP Python六级
树上游走
时间限制：1.0 s
内存限制：512.0 MB
题面描述
小杨有一棵包含无穷节点的二叉树（即每个节点都有左儿子节点和右儿子节点；除根节点外，每个节点都有父节点），其中根节点的编号为 1 ，对于节点 i ，其左儿子的编号为 2×i，右儿子的编号为 2×i+1。
小杨会从节点 s 开始在二叉树上移动，每次移动为以下三种移动方式的任意一种：
第1种移动方式： 如果当前节点存在父亲节点，向上移动到当前节点的父亲节点，否则不移动；
第2种移动方式： 移动到当前节点的左儿子；
第3种移动方式： 移动到当前节点的右儿子。
小杨想知道移动 n 次后自己所处的节点编号。数据保证最后的所处的节点编号不超过1012。
输入格式
第一行包含一个正整数 n,s，代表移动次数和初始节点编号。
第二行包含一个长度为 n 且仅包含大写字母 U,L,R 的字符串，代表每次移动的方式，其中U 代表第1种移动方式，L 代表第2种移动方式，R 代表第3种移动方式。
输出格式
输出一个正整数，代表最后所处的节点编号。
输入样例
3 2 URR
输出样例
7
样例解释
小杨的移动路线为 2-1-3-7。
对于全部数据，保证有1≤n≤106,1≤s≤1012。
【知识点】 CCF—GESP Python六级
