2024年3月GESP等级认证Python编程八级真题及答案

题号 1 2 3 4 5 6 7 8 9 10 11 1 2 13 14 15 答 案 C D B A B C C B C D A A B D C P yth on 　八级 2024 年 0 3 ⽉ 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. 可 以⽤快速幂⽅法计算斐波那契数列的第 项 第 1 0 题 下 ⾯实现杨辉三角形的程序中，横线处填写正确 的是（ ）。 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) 第 1 1 题 设 有编号为 1 ， 2 ， 3 ， 4 ， 5 的五个球和编号为 1 ， 2 ， 3 ， 4 ， 5 的盒⼦，现将这 5 个球投⼊ 5 个盒⼦要求每个盒 ⼦ 放⼀个球，并且恰好有两个球的号码与盒⼦号码相同，问有多少种不同的⽅法（ ）。 A. 20 B . 10 C . 12 D . 24 第 1 2 题 1 名 ⽼师和 4 名获奖同学排成⼀排照相留念，⽼师不站两端的排法下列所列式⼦正确的是（）。 A. B. C . D. 第 1 3 题 关 于赋权图中，从某⼀个点出发，寻找最短路径 的算法 Dijk str a ，下列说法中错误的是（ ）。 题号 1 2 3 4 5 6 7 8 9 10 答 案 A. 算 法解决了赋权有向图或者⽆向图的单源最短路径问题 B. 算 法最终得到⼀个最短路径树 C. 常 ⽤于路由算法或者作为其他图算法的⼀个⼦模块 D. 算 法采⽤的是⼀种贪⼼的策略 第 1 4 题 关 于图的存储⽅法中，下列说法错误的是（ ）。 A. 图 的存储结构主要分为：邻接矩阵和邻接表 B. 图 的邻接矩阵存储⽅式是⽤两个数组来表⽰图：⼀个⼀维数组存储图中顶点信息，⼀个⼆维数组（邻接矩 阵 ）存储图中的边或弧的信息。 C. 对 于边数相对顶点较少的图，邻接矩阵结构存在对存储空间的极⼤浪费 D. 如 果图中边的数⽬远远⼤于 n 的平⽅称作稀疏图 ，这是⽤邻接表表⽰⽐⽤邻接矩阵表⽰节省空间 第 1 5 题 D ijk str a 算法中，定义 S 集合是已求出最短路径 的节点集合，对于下图中的图， Dijk str a 算法的中间形成的 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 题 排 列问题与顺序有关，组合问题与顺序⽆关。 第 1 0 题 ⽤ 分治法可以优化等⽐数列的前 项 求和的算法。 3 编程题（每题 25 分，共 50 分） 3.1 编程题 1 试 题名称 ：公倍数问题 3.1.1 问 题描