题号 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 问 题描
GESP 3月认证 Python八级真题，2024年3月GESP等级认证Python编程八级真题及答案