GESP第五次认证真题解析|Python八级真题回顾

一、单选题（每题2分，共30分）

1、下列代码中，用到的算法是什么算法，去掉存储的空间，算法本⾝⽤到的空间复杂度是多少（ ）

A.二分法 ， O(log2N)

B.二分法 ， O(N)

C.折半查找 ， O(1)

D.折半查找 ， O(Nlog2N)

【答案】C

【考纲知识点】空间复杂度

【解析】去掉存储需要的空间，用到的变量是left、right和mid，空间复杂度是O(3)，常数级别通常用O（1）表示。折半查找通常也是只二分法。

2、无向图的临接矩阵存储方法中，下列描述正确的是（ ）。

A.对角矩阵

B.稀疏矩阵

C.非对称矩阵

D.对称矩阵

【答案】D

【考纲知识点】图的知识

【解析】题目要求是无向图，例如，点a到点b的距离等于点b到点a的距离，所以是一个对称矩阵。

3、下列代码依次输⼊10,3,2后，结果是（ ）。

A. 23

B. 120

C. 16

D. 155

【答案】B

【考纲知识点】函数知识

【解析】先输入了10，然后根据输入，first_term是3，根据第4行语句，last_term得21，计算后sum后的结果是120。本题考察的是等差数列的求和公式。

4、一个等边五边形，每个顶点上有一个蚂蚁，蚂蚁沿着五边形的边严格匀速行走，方向随机，请问，开始走以

后，蚂蚁两两不相碰的概率是多少（ ）。

A. 1/16

B. 1/4

C. 1/32

D. 1/8

【答案】A

【考纲知识点】数学知识

【解析】先分析蚂蚁两两不相碰的情况，只有都按照同一方向走，才能不碰到。每只蚂蚁都可以顺指针走或者逆时针走2种选择，也就是1/2.5只同一方向就是(1/2)5,2种情况，2*(1/2)5=1/16。

5、一根长度为1的小木棒，随机的折成三段，请问这三段能够组成一个三角形的概率是多少？（ ）。

A. 1/3

B. 1/4

C. 1/8

D. 1/2

【答案】C

【考纲知识点】数学知识

【解析】构成三角形，假设x，y分别表示其中两段的长度，则第3段的长度为1－x－y，则试验的全部结果可构成集合Ω＝{(x，y)|0<x<1, 0<y<1,0<x＋y<1}，要使3段构成三角形，当且仅当任意两段之和大于第3段，即x＋y>1－x－y⇒x＋y>1/2，x＋1－x－y>y⇒y<1/2，y＋1－x－y>x⇒x<1/2.故所求结果构成集合A＝{(x，y)|x＋y>1/2，y<1/2，x<1/2}。

三角形周长最长值是1，所以x和y的取值范围是[0,1]，构成最大三角形。看函数构成的直线包括：x+y>1/2,x<1/2,y<1/2，构成阴影部分，面积占1/4.

6、有北京，雄安，天津三个城市，同样两个城市之间来回票价一样。请问火车售票部门需要准备几种车票，几种票价（ ）。

A. 3,3

B. 6,6

C. 6,3

D. 3,6

【答案】C

【考纲知识点】数学知识

【解析】票价是一样的，例如北京-天津的票价==天津到北京的票价。城市之间的交通可以枚举：北京-天津，北京到-雄安，雄安-天津。不考虑起点和终点的差异，一共有3种票价。所以选择A或C。在考虑起点和终点的情况，每种票价乘2，就是车票种类。

7、对于如下图的无向图，在用Prim算法以节点F作为起点生成最小树的过程中，哪个选项不是产生最小树的中间状态？（ ）。

A.

B.

C.

D.

【答案】C

【考纲知识点】最小生成树知识

【解析】prim算法可以从任意一点开始生成最小生成树，每次取的都是加入最小生成树节点中最小的边权值。C中当B点加入时，会优先选择G点加入，B-G边权值更小。

8、对于⼀棵是完全⼆叉树的排序⼆叉树，其平均搜索的时间复杂度为（ ）。

A.O(1)

B. O(log n)

C. O(n)

D. O(n²)

【答案】C

【考纲知识点】树的知识

【解析】该树是完全二叉树，又是排序树。二叉排序树的特点：（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；（3）左、右子树也分别为二叉排序树。总是在二分，因此时间复杂度是B选项。

9、关于快速幂，下列说法错误的是（ ）。

A.使用了倍增思想

B.每⼀步都把指数分成两半，⽽相应的底数做平方运算

C.时间复杂度为O(NlogN)

D.可以用快速幂⽅法计算斐波那契数列的第N项

【答案】C

【考纲知识点】数学知识

【解析】快速幂的时间复杂度是O(logn)。

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)

【答案】D

【考纲知识点】数学知识

【解析】杨辉三角形除了第1列和对角线上的数字是1，其他都是左上角和正上方的数字之和，因此选D。

11、设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的盒⼦，现将这5个球投入5个盒⼦要求每个盒⼦放⼀个球，并且恰好有两个球的号码与盒⼦号码相同，问有多少种不同的⽅法（ ）。

A. 20

B. 10

C. 12

D. 24

【答案】A

【考纲知识点】数学知识

【解析】排列组合知识。选取2个球放在号码相同的盒子，并且盒子不为空，其他的3个球，放第1个球，因为不能再放在编号相同的盒子，只有2种选择，第2个和第3个只有1种，C(5,2)*2*1*1=20.

12、1名⽼师和4名获奖同学排成⼀排照相留念，⽼师不站两端的排法下列所列式子正确的是（）。

A.

B.

C.

D.

【答案】A

【考纲知识点】数学知识

【解析】老师不站2端，只有3个位置可选，C(3,1)，剩下的位置排列是A(4,4)。

13、关于赋权图中，从某一个点出发，寻找最短路径的算法Dijkstra，下列说法中错误的是（ ）。

A.算法解决了赋权有向图或者无向图的单源最短路径问题

B.算法最终得到一个最短路径树

C.常用于路由算法或者作为其他图算法的一个子模块

D.算法采用的是一种贪心的策略

【答案】B

【考纲知识点】最短路径

【解析】如果存在负边权，最终结果不一定是最短路径树。

14、关于图的存储方法中，下列说法错误的是（ ）。

A.图的存储结构主要分为：邻接矩阵和邻接表

B.图的邻接矩阵存储方式是用两个数组来表示图：一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。

C.对于边数相对顶点较少的图，邻接矩阵结构存在对存储空间的极大浪费

D.如果图中边的数目远远大于n的平方称作稀疏图，这是用邻接表表示比用邻接矩阵表示节省空间

【答案】D

【考纲知识点】图的知识

【解析】图中边最多数量是n*(n-1)/2。

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)}

【答案】A

【考纲知识点】最短路径知识

【解析】从0出发，最小边是0-2，边权值是3；0和1的最小边是8，点1加入。BCD都是错误的

二、判断题（每题2分，共20分）

1、 线性表可以是空表，树可以是空树，图也可以是空。

【答案】错误

【考纲知识点】图的知识

【解析】图不能是空的。

2、在具有n个顶点、e条边的无向图中， 无向图的全部顶点的度的和等于边数的 2倍。

【答案】正确

【考纲知识点】图的知识

【解析】一条边有2个顶点，度是点连边的统计，因此是2倍。

3、图的任意几个点，几个边都可以组成这个图的⼦图。

【答案】错误

【考纲知识点】图的知识

【解析】图的子图定义：边的子集（包含这些边依附的顶点）组成的图。

4、在具有n个顶点、e条边的有向图中，入度+出度的和是2e。

【答案】正确

【考纲知识点】图的知识

【解析】有向图的全部顶点入度之和等于出度之和且等于边数。顶点的度等于入度与出度之和。

5、当⼀棵排序⼆叉树退化为单⽀⼆叉树后，其平均⽐较次数是O(N)。

【答案】正确

【考纲知识点】树的知识

【解析】单支二叉树意味着一棵树退化成线性。平均比较次数是O(N)。

6、不算数据的存储，插⼊排序算法的空间复杂度为O(1)。

【答案】错误

【考纲知识点】排序知识

【解析】插入排序需要的辅助空间是常数个。

7、图的存储方式主要有两种：邻接表和邻接矩阵。

【答案】正确

【考纲知识点】图的知识

【解析】图的2种常见存储方式。

8、对于边数相对顶点较少的图，使用邻接矩阵来存储更好。

【答案】错误

【考纲知识点】图的知识

【解析】边少用邻接表存储更省空间。

9、排列问题与顺序有关，组合问题与顺序无关。

【答案】正确

【考纲知识点】数学知识

【解析】排列和组合的定义。排列要考虑顺序，组合只考虑情况。

10、用分治法可以优化等比数列的前n项求和的算法。

【答案】正确

【考纲知识点】算法知识

【解析】前n项求和公式可以用快速幂的方法来求。

三、编程题（每题25分，共50分）

1、公倍数问题

题面描述

小A写了一个N×M的矩阵A,我们看不到这个矩阵，但我们可以知道，其中第i行第j列的元素A_i，j是i和j的公倍数(i=1,...,N，j=1,...,M)。现在有K个小朋友，其中第k个小朋友想知道，矩阵A中最多有多少个元素可以是k(k =1,2,...,K)。请你帮助这些小朋友求解。

注意：每位小朋友的答案互不相关，例如，有些位置既可能是x，又可能是y，则它同可以时满足x , y两名小朋友的要求。

方便起见，你只需要输出即可，其中ans_k表示第k名小朋友感兴趣的答案。

输入描述

第一行三个正整数N,M,K。

输出描述

输出一行，即。

请注意，这个数可能很大，使用C++语言的选手请酌情使用long long 等数据类型存储答案。

特别提醒

在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。

样例输入1

样例输出1

样例解释1

只有A_1,1可以是1，其余都不行。

A_1,1,A_1,2,A_2,1,A_2,2都可以是2，而其余不行。

因此答案是1×1+2×4=9。

样例输入2

样例输出2

数据范围

对于30的测试点，保证N,M,K≤10;

对于60的测试点，保证N,M,K≤500;

对于100的测试点，保证N,M≤10⁵，K≤10⁶。

【题目解析】

Aij的元素是i和j的公倍数，意味着该数字能够整除i和j。

根据样例分析：K=2时，求的是k=1，2的和。k=1时，i=j=1，A11是1的公倍数，符合条件，有1个方案。k=2时，A11-A22的公倍数可以是2，其他的不行，有4种方案。按照题目输出：1*1+2*4=9.

枚举，如果k=4，公倍数方案是A11,A12,A14,A21,A22,A24,A41,A42,A44,有9种方案。4提供的贡献值是：4*9=36。9种方案分析，是{1,2,4}和{1,2,4}的两两组合，3*3=9种。

结论：

1、i和j，有一个是k的倍数，即可满足。

2、4的约数有1,2,4.4也是1,2,4的倍数。4有多少个因子，统计出来。

3、因为是矩阵，两两相乘，就是每个数字提供的方案数。

【参考程序】

2、接竹竿

问题描述

小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。

游戏规则是：每张牌上有一个点数v，将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相同的牌，则小杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列（包括这两张牌本身）。

小杨同学现在有一个长度为n的卡牌序列A,其中每张牌的点数为A_i(1≤i ≤n)。小杨同学有q次询问。第i次(1≤i ≤q)询问时，小杨同学会给出l_i, r_i，小杨同学想知道如果用下标在山[l_i, r_i]的所有卡牌按照下标顺序玩“接竹竿”的游戏，最后队列中剩余的牌数。

输入描述

第一行包含一个正整数T，表示测试数据组数。

对于每组测试数据，第一行包含一个正整数n，表示卡牌序列A的长度。

第二行包含n个正整数A₁,A₂,...,A_n，表示卡牌的点数A。

第三行包含一个正整数q，表示询问次数。

接下来q行，每行两个正整数l_i, r_i，表示一组询问。

输出格式

对于每组数据，输出q行。第i行(1≤i ≤q)输出一个非负整数，表示第i次询问的答案。

样例1

样例解释

对于第一次询问，小杨同学会按照1,2,2的顺序放置卡牌，在放置最后一张卡牌时，两张点数为2的卡牌会被收走，因此最后队列中只剩余一张点数为1的卡牌。

对于第二次询问，队列变化情况为:{}→ {1} → {1,2} → {1,2,2} → {1}→ {1,3} → {1,3,1}→ {}→ {3}。因此最后队列中只剩余一张点数为3的卡牌。

数据范围

对于全部数据，保证有1≤T ≤5，1≤n ≤1.5x10⁴，1≤q ≤1.5x10⁴，1≤ A_i≤13。

【题目解析】

根据题意，每张牌最大的数字是13，然后根据提供的区间【L,R】，看长度最远的2个数字，去掉后剩下的卡牌数量。注意：按照队列方式入队，遇到相同的数字，之间的卡牌数字就全部消失。例如，1,2,3,1,4,2,3。消失的是1231，而不是23142这个区间。另一种情况，如果是3个1，例如1,2,1,3,1,4,2,会消除121这3张卡牌。

结论：

1、记录下一个出现的数字；求该区间内，第一个和它相同的数字。用区间最值来求。

2、从左到右去查找，如果第1个数字，队列后面没有相同的，继续判断第2个。

求解：区间是[L,R]，和第1个数字相同的最近数字的位置，该位置不能超过R。依次类推求第2个，第3个……。

可以用区间最值RMQ来统计。注意要倒序处理，从n到1.

【参考程序】