2023年12月GESP认证Python八级试卷解析

【答案】C

【解析】本题本质是一道数学题目，将问题分为2部分，第一部分为A->C->B,有2种方案，第二部分为A->D->B，有3种方案，加起来是5种，选择C。

【答案】A

【解析】本题考察的是“+”号的运算，其中A,B选择是关于列表的加法，是将两个列表的拼接成一个列表，不会报错。C选项是关于元组的加法，元组是不可修改的，但是两个元组相加是生成了另一个元组，并不会修改原始元组，不会报错。D选项是关于字典的加法，字典相加也是将两个字典合并成一个新的字典，不会报错。选择A。

【答案】D

【解析】本题中，对象的生命周期开始和结束分别会执行构造函数和析构函数，所以A,B,正确。对于虚函数，在python中是虚函数的装饰器有@abstractmethod和@virtual，并且是通过继承和方法重写来实现的，其中构造函数不能当成虚函数使用，因为创建一个对象时我们总是要明确指定对象的类型，尽管我们可能通过基类的指针或引用去访问它但析构却不一定，我们往往通过基类的指针来销毁对象。这时候如果析构函数不是虚函数，就不能正确识别对象类型从而不能正确调用析构函数。选择D。

【答案】B

【解析】邻接矩阵的行列分别为n个，大小则为n*n。选择B。

【答案】C

【解析】本题是排序题目，5位同学排序方法有A55,减去指定同学排在第一位的情况A44,则有120-24=96，选择C。

【答案】D

【解析】n个顶点的组成的树有n-1条边，但是没有保证为连通图，所以不能判断是否存在最小生成树，选择D。

【答案】A

【解析】本题是数学题目，三角形的面积是(底*高)/2，其中，如果以b为底，还缺少高，通过三角函数，h=a*sin(theta)，带入公式，a*b* sin(theta)/2，选择A。

【答案】C

【解析】树的遍历是将每个元素遍历一次，因此时间复杂度为O(n)，选择C。

【答案】A

【解析】本题是辗转相除法求最大公倍数，所以时间复杂度为O(log(n))，选择A。

【答案】C

【解析】本题是关于快速幂的程序，是计算a**n%mod，每次n的值都会/2，所以时间复杂度为O(logn)，选择C。

【答案】D

【解析】本题是使用了递归算法，并且对求出的值进行了记录，简化了算法的时间复杂度，通过打表的方法，记录对应的值，可以发现总共访问了m*(n-m)个元素，选择D。

【答案】B

【解析】邻接表存储示意图

【解析】结构体edge里的next指向的是下一条边，Node里的first指向的是每个点的第一条边，所以0号点指向1号点，1号点指向2,3号点，2号点指向3号点，3号点指向0号点，

概念图是

最接近的符合代码描述的选项是B。

【答案】B

【解析】本题是三重for循环，a,b,h取值范围都为(1,10],当满足条件(a+b)*h==20时，计数器+1。因为(a+b)*h==20,所以h的值有1,2,4,5,10，那对应的a+b的值有20,10,5,4,2 方案数分别为1,9,4,3,1，总共18种，选择B。

【答案】A

【解析】本题代码中要求a，b，c都是正整数，满足a+b+c<=30且a^2+b^2=c^2,符合要求的a,b,c有3 4 5；5 12 13；6 8 10共3种，选A。

【答案】C

【解析】本题要求计算从网格的左下角到右上角的最小时间消耗。二维数组v和h分别表示网格中的水平边和垂直边的时间消耗。程序使用动态规划方法计算这个最小时间。

动态规划状态转移方程需要根据网格的边长和时间消耗来设置。在第11行的输出dis[y][x]，我们注意到枚举的范围是<y和<x，因此第10行计算的是dis[i+1][j+1]。根据选项c的第一个转移dis[i][j+1]，可见这里是从第一维转移过来，类似于第5行也是从第一维转移过来，使用的是v数组。因此，选项c正确。 

【答案】错误

【解析】本题中x*2-4=0既不是赋值语句，也不是判断语句，所以不能通过编译。错误。

【答案】正确

【解析】将所有情况进行枚举，分别为：红红红，红红蓝，红蓝红，蓝红红，红蓝蓝，蓝红蓝，蓝蓝红。正确。

【答案】正确

【解析】本题是历史题，杨辉三角，是二项式系数在三角形中的一种几何排列，在中国南宋数学家杨辉所著的《详解九章算法》中出现。正确。

【答案】错误

【解析】有向完全图，(x,y)和(y,x)不算同一条边，所以有n*(n-1)条边。错误。

【答案】正确

【解析】在极端情况下，可以先将待查找元素放进哈希表中，再根据位置构造一个由if-else判断组成的哈希函数：当查找元素与某一项待查找相同时，返回对应的位置。虽然这样构造的哈希函数的时间复杂度较高，但满足不会产生冲突。正确。

【答案】正确

【解析】动态规划的时间复杂度⼀般为状态数*转移复杂度。正确。

【答案】错误

【解析】本题考察梯形的面积公式，正确。

【答案】错误

【解析】还可以使用深度优先算法。错误。

【答案】错误

【解析】最好的情况下是O(1)，一次就可以找到。错误。

【答案】正确

【解析】二分法要求查找的元素是有序排列的，f(x)=x^1/2在x∈[0,+∞)上是单调递增。正确。

【解题思路】根据样例1中是数据，3 2 1 2，人数n=3，种类m=2，商品总数为1+2=3个，商品数和人数相同，所以可以使用组合数来统计有多少种方案，C(3,1)*C(2,2)=3。

3 2 1 3，人数n=3，种类m=2，商品总数1+3=4个，此时商品数大于人数，我们可以不必要考虑人数，只考虑商品数，所以使用组合数得到：C(4,1)*C(3,3)=4个。

因此我们发现用组合数来处理排列方式，可以使用杨辉三角预处理下所有情况的组合数，放到列表C中，然后再根据实际情况n和m的组合，寻找到相应的值。

【参考程序】

def main():

    P = 10**9 + 7

    max_n = 1001

    C = [[0 for _ in range(max_n + 1)] for __ in range(max_n + 1)]

    for i in range(max_n + 1):

        for j in range(i + 1):

            if j == 0 or j == i:

                C[i][j] = 1

            else:

                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P

    T = int(input())

    for t in range(T):

        inp = list(map(int, input().strip().split(' ')))

        n = inp[0]

        a = inp[2:]

        if n + 1 == sum(a):

            n += 1

        ans = 1

        for m in a:

            ans = ans * C[n][m] % P

            n -= m

        assert n == 0

        print(ans)

if __name__ == "__main__":

    main()

【解题思路】分析样例可得本题是求最近的共同祖先问题。从样例1中可得3,4的最近共同祖先是2；2,3,4的共同祖先是2；1,4的共同祖先是0。我们可以先把所有元素的祖先进行预处理，放到列表中，然后每个元素的深度也存储到列表中，通过BFS搜索算法来求出元素的共同祖先，并记录在列表中。

【参考程序】

def main():

    n = int(input())

    father = [-1] + list(map(int, input().split(' ')))

    child = [[] for i in range(n)]

    for i in range(1, n):

        child[father[i]].append(i)

    depth = [0 for i in range(n)]

    anc = [[] for i in range(n)]

    max_anc_id = [i for i in range(n)]

    queue = [0]

    # BFS

    while queue:

        node = queue[0]

        queue = queue[1:]

        anc[node].append(father[node])

        for i in range(1, 20):

            if anc[node][i - 1] == -1:

                anc[node].append(-1)

            else:

                anc[node].append(anc[anc[node][i - 1]][i - 1])

        for c in child[node]:

            depth[c] = depth[node] + 1

            max_anc_id[c] = max(c, max_anc_id[node])

            queue.append(c)

    def lca(u, v):

        if depth[u] > depth[v]:

            u, v = v, u

        for i in range(20):

            if (depth[v] - depth[u]) & (1 << i):

                v = anc[v][i]

        assert depth[u] == depth[v]

        if u == v:

            return u

        for i in range(len(anc[u]) - 1, -1, -1):

            if anc[u][i] != anc[v][i]:

                u = anc[u][i]

                v = anc[v][i]

        if father[u] != father[v]:

            _u, _v = u, v

            while u != -1 and v != -1:

                u = father[u]

                v = father[v]

            u, v = _u, _v

        assert father[u] == father[v]

        return father[u]

    q = int(input())

    for _ in range(q):

        x = list(map(int, input().split(' ')))[1:]

        ans = x[0]

        for u in x[1:]:

            ans = lca(ans, u)

        print(max_anc_id[ans])

if __name__ == "__main__":

    main()

【联系我们】