2024.03中国计算机学会GESP等级考试python八级

题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 C D B A B C C B C D A A B D C Python　八级 2024 年 03 ⽉ 1 单选题（每题 2 分，共 30 分） 第 1 题 下列代码中，⽤到的算法是什么算法，去掉存储的空间，算法本⾝⽤到的空间复杂度是多少（ ） A. 二分法 ， O(log2N) B. 二分法 ， O(N) C. 折半查找 ， O(1) D. 折半查找 ， O(Nlog2N) 第 2 题 ⽆向图的临接矩阵存储⽅法中，下列描述正确的是（ ）。 A. 对角矩阵 B. 稀疏矩阵 C. 非对称矩阵 D. 对称矩阵 第 3 题 下列代码依次输⼊10,3,2后，结果是（ ）。 A. 23 B. 120 C. 16 D. 155 第 4 题 ⼀个等边五边形，每个顶点上有⼀个蚂蚁，蚂蚁沿着五边形的边严格匀速⾏⾛，⽅向随机，请问，开始⾛以 后，蚂蚁两两不相碰的概率是多少（ ）。 A. 1/16 B. 1/4 C. 1/32 D. 1/8 第 5 题 ⼀根长度为1的⼩⽊棒，随机的折成三段，请问这三段能够组成⼀个三角形的概率是多少？（ ）。 A. 1/3 B. 1/4 C. 1/8 D. 1/2 第 6 题 有北京，雄安，天津三个城市，同样两个城市之间来回票价⼀样。请问⽕车售票部门需要准备⼏种车票，⼏ 种票价（ ）。 A. 3,3 B. 6,6 C. 6,3 D. 3,6 第 7 题 对于如下图的⽆向图，在⽤Prim算法以节点F作为起点⽣成最⼩树的过程中，哪个选项不是产⽣最⼩树的中 间状态？（ ）。 A. B. C. D. 第 8 题 对于⼀棵是完全⼆叉树的排序⼆叉树，其平均搜索的时间复杂度为（ ）。 A. B. C. D. 第 9 题 关于快速幂，下列说法错误的是（ ）。 A. 使⽤了倍增思想 B. 每⼀步都把指数分成两半，⽽相应的底数做平⽅运算 C. 时间复杂度为 D. 可以⽤快速幂⽅法计算斐波那契数列的第 项 第 10 题 下⾯实现杨辉三角形的程序中，横线处填写正确的是（ ）。 A. z = triangles(x, y-1) + triangles(x, y) B. z = triangles(x-1, y+1) + triangles(x-1, y-1) C. z = triangles(x-1, y-1) + triangles(x, y) D. z = triangles(x-1, y-1) + triangles(x-1, y) 第 11 题 设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的盒⼦，现将这5个球投⼊5个盒⼦要求每个盒 ⼦放⼀个球，并且恰好有两个球的号码与盒⼦号码相同，问有多少种不同的⽅法（ ）。 A. 20 B. 10 C. 12 D. 24 第 12 题 1名⽼师和4名获奖同学排成⼀排照相留念，⽼师不站两端的排法下列所列式⼦正确的是（）。 A. B. C. D. 第 13 题 关于赋权图中，从某⼀个点出发，寻找最短路径的算法Dijkstra，下列说法中错误的是（ ）。 题号 1 2 3 4 5 6 7 8 9 10 答案 A. 算法解决了赋权有向图或者⽆向图的单源最短路径问题 B. 算法最终得到⼀个最短路径树 C. 常⽤于路由算法或者作为其他图算法的⼀个⼦模块 D. 算法采⽤的是⼀种贪⼼的策略 第 14 题 关于图的存储⽅法中，下列说法错误的是（ ）。 A. 图的存储结构主要分为：邻接矩阵和邻接表 B. 图的邻接矩阵存储⽅式是⽤两个数组来表⽰图：⼀个⼀维数组存储图中顶点信息，⼀个⼆维数组（邻接矩 阵）存储图中的边或弧的信息。 C. 对于边数相对顶点较少的图，邻接矩阵结构存在对存储空间的极⼤浪费 D. 如果图中边的数⽬远远⼤于n的平⽅称作稀疏图，这是⽤邻接表表⽰⽐⽤邻接矩阵表⽰节省空间 第 15 题 Dijkstra算法中，定义S集合是已求出最短路径的节点集合，对于下图中的图，Dijkstra算法的中间形成的S集 合，错误的是（ ）。 A. S={0(3)} B. S={0(3),2(6)} C. S={0(3),2(6),1(5)} D. S={0(3),2(6),1(8)} 2 判断题（每题 2 分，共 20 分） 第 1 题 线性表可以是空表，树可以是空树，图也可以是空。 第 2 题 在具有 个顶点、 条边的⽆向图中， ⽆向图的全部顶点的度的和等于边数的 2 倍。 第 3 题 图的任意⼏个点，⼏个边都可以组成这个图的⼦图。 第 4 题 在具有 个顶点、 条边的有向图中，⼊度+出度的和是 。 第 5 题 当⼀棵排序⼆叉树退化为单⽀⼆叉树后，其平均⽐较次数是 。 第 6 题 不算数据的存储，插⼊排序算法的空间复杂度为 。 第 7 题 图的存储⽅式主要有两种：邻接表和邻接矩阵。 第 8 题 对于边数相对顶点较少的图，使⽤邻接矩阵来存储更好。 第 9 题 排列问题与顺序有关，组合问题与顺序⽆关。 第 10 题 ⽤分治法可以优化等⽐数列的前 项求和的算法。 3 编程题（每题 25 分，共 50 分） 3.1 编程题 1 试题名称：公倍数问题 3.1.1 问题描述 ⼩ A 写了⼀个 的矩阵 ，我们看不到这个矩阵，但我们可以知道，其中第 ⾏第 列的元素 是 和 的 公倍数（ ， ）。现在有 个⼩朋友，其中第 个⼩朋友想知道，矩阵 中最多有多少个元 素可以是 （ ）。请你帮助这些⼩朋友求解。 注意：每位⼩朋友的答案互不相关，例如，有些位置既可能是 ，⼜可能是 ，则它同可以时满⾜ 两名⼩朋友的 要求。 ⽅便起见，你只需要输出 即可，其中 表⽰第 名⼩朋友感兴趣的答案。 3.1.2 输入描述 第⼀⾏三个正整数 。 3.1.3 输出描述 输出⼀⾏，即 。 请注意，这个数可能很⼤，使⽤ C++ 语⾔的选⼿请酌情使⽤ long long 等数据类型存储答案。 3.1.4 特别提醒 在常规程序中，输⼊、输出时提供提⽰是好习惯。但在本场考试中，由于系统限定，请不要在输⼊、输出中附带任 何提⽰信息。 3.1.5 样例输入 1 3.1.6 样例输出 1 3.1.7 样例解释 1 只有 可以是 ，其余都不⾏。 都可以是 ，⽽其余不⾏。 因此答案是 。 2 5 21 91 3.1.8 样例输入 2 3.1.9 样例输出 2 3.1.10 数据规模 对于 的测试点，保证 ； 对于 的测试点，保证 ； 对于 的测试点，保证 ， 。 3.1.11 参考程序 3.2 编程题 2 试题名称：接⽵竿 3.2.1 题面描述 ⼩杨同学想⽤卡牌玩⼀种叫做“接⽵竿”的游戏。 游戏规则是：每张牌上有⼀个点数 ，将给定的牌依次放⼊⼀列牌的末端。若放⼊之前这列牌中已有与这张牌点数相 同的牌，则⼩杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列（包括这两张牌本⾝）。 ⼩杨同学现在有⼀个长度为 的卡牌序列 ，其中每张牌的点数为 （ ）。⼩杨同学有 次询问。第 次 （ ）询问时，⼩杨同学会给出 ，⼩杨同学想知道如果⽤下标在 的所有卡牌按照下标顺序玩“接⽵ 竿”的游戏，最后队列中剩余的牌数。 100 100 1001 1852331 def count_divisors(limit, num): s = [0] * (num + 1) for i in range(1, limit + 1): for j in range(i, num + 1, i): s[j] += 1 return s def main(): N, M, K = map(int, input().split()) s_N = count_divisors(N, 10 ** 6) s_M = count_divisors(M, 10 ** 6) result = 0 for k in range(1, K + 1): result += k * s_N[k] * s_M[k] print(result) if __name__ == "__main__": main() 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 子任务编号 数据点占比 特殊条件 1 2 所有询问的右端点等于 3 3.2.2 输入格式 第⼀⾏包含⼀个正整数 ，表⽰测试数据组数。 对于每组测试数据，第⼀⾏包含⼀个正整数 ，表⽰卡牌序列 的长度。 第⼆⾏包含 个正整数 ，表⽰卡牌的点数 。 第三⾏包含⼀个正整数 ，表⽰询问次数。 接下来 ⾏，每⾏两个正整数 ，表⽰⼀组询问。 3.2.3 输出格式 对于每组数据，输出 ⾏。第 ⾏（ ）输出⼀个⾮负整数，表⽰第 次询问的答案。 3.2.4 样例1 3.2.5 样例解释 对于第⼀次询问，⼩杨同学会按照 的顺序放置卡牌，在放置最后⼀张卡牌时，两张点数为 的卡牌会被收 ⾛，因此最后队列中只剩余⼀张点数为 的卡牌。 对于第⼆次询问，队列变化情况为： 。因此最后队列中只剩余⼀张点数为 的卡 牌。 3.2.6 数据范围 对于全部数据，保证有 ， ， 。， 3.2.7 参考程序 1 6 1 2 2 3 1 3 4 1 3 1 6 1 5 5 6 1 2 3 4 5 6 7 8 1 1 0 2 1 2 3 4 import math T = int(input()) for cas in range(T): 1 2 3 4 n = int(input()) m = int(math.log(n, 2)) + 1 A = list(map(int, input().split())) pos = {} nxt = [[n for i in range(m + 1)] for j in range(n)] for i in range(n - 1, -1, -1): if not (A[i] in pos): nxt[i][0] = n else: nxt[i][0] = pos[A[i]] pos[A[i]] = i for i in range(n - 1, -1, -1): for j in range(1, m + 1): if nxt[i][j - 1] + 1 < n: nxt[i][j] = nxt[nxt[i][j - 1] + 1][j - 1] Q = int(input()) for q in range(Q): l, r = map(int, input().split()) l, r = l - 1, r - 1 x, ans = l, 0 while x <= r: while x <= r and nxt[x][0] > r: x, ans = x + 1, ans + 1 if x > r: break for i in range(m, -1, -1): if nxt[x][i] <= r: x = nxt[x][i] break x += 1 print(ans) 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 37 38 39