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

今天为大家带来的是2023年12月认证Python六级真题解析回顾。

CCF编程能力等级认证，英文名Grade Examination of Software Programming（以下简称GESP），由中国计算机学会发起并主办，是为青少年计算机和编程学习者提供学业能力验证的平台。GESP覆盖中小学全学段，符合条件的青少年均可参加认证。GESP旨在提升青少年计算机和编程教育水平，推广和普及青少年计算机和编程教育。

GESP考察语言为图形化（Scratch）编程、Python编程及C++编程，主要考察学生掌握相关编程知识和操作能力，熟悉编程各项基础知识和理论框架，通过设定不同等级的考试目标，让学生具备编程从简单的程序到复杂程序设计的编程能力，为后期专业化编程学习打下良好基础。

本次为大家带来的是2023年12月份Python 六级认证真题解析。

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

1、通讯卫星在通信⽹络系统中主要起到（） 的作⽤ 。

  A. 信息过滤

  B. 信号中继

  C. 避免攻击

  D. 数据加密

【答案】B 

【解析】本题主要是考察计算机网络相关的知识点。通讯卫星在通信网络系统中主要起到信号中继的作用，即使用中继设备来增强或传递信号。B选项中信息过滤通常由其他网络设备来处理，如防火墙或路由器。C选项中，网络安全通常涉及其他专门的设备和协议。通讯卫星可以传递经过加密的数据，但它本身并不负责数据加密。D选项中数据加密通常是由通信的两端设备负责的，而卫星主要负责传递加密后的数据。故本题选择B选项。

2、⼩杨想编写⼀个判断任意输⼊的整数N是否为素数的程序 ，下⾯哪个⽅法不合适？  (   )

  A. 埃⽒筛法

  B. 线性筛法

  C. ⼆分答案

  D. 枚举法

【答案】C 

【解析】本题主要考查初等数论中对素数的判定。A选项中埃氏筛法（埃拉托斯特尼筛法）是用于生成素数的一种经典算法，该算法的基本思想是从小到大遍历自然数，将素数的倍数标记为非素数。通过这种方式，最终留下的未被标记的数就是素数。B选项中线性筛法，也是一种用于生成素数的高效算法。D选项中枚举法是一种直观而朴素的方法，用于判断一个整数是否为素数，它的基本思想是逐一检查该整数是否有除了1和它本身以外的其他因数，如果有，那么该整数就不是素数；否则，它就是素数。C选项中二分答案通常用于在有序数据中搜索某个目标值，但在判断素数时，并不涉及有序数据的搜索。故本题选择C选项。

3、内排序有不同的类别 ，下⾯哪种排序算法和冒泡排序是同⼀类？  (  )

  A. 希尔排序

  B. 快速排序

  C. 堆排序

  D. 插⼊排序

【答案】B 

【解析】本题主要考查几种排序算法。冒泡排序和快速排序都是内排序中比较排序类算法，并且属于交换排序的类型。A选项希尔排序和D选项插入排序是属于比较排序类算法中的插入排序类型。而C选项堆排序是属于比较排序类算法中的选择排序类型。故本题选择B选项。

4、关于Python类和对象的说法 ，错误的是(      )。

  A. 在Python中 ，⼀切皆对象， 即便是字⾯量如整数5等也是对象

  B. 在Python中 ，可以⾃定义新的类 ，并实例化为新的对象

  C. 在Python中， 内置函数和⾃定义函数 ，都是类或者对象

  D. 在Python中 ，不可以在⾃定义函数中嵌套定义新的函数

【答案】D 

【解析】本题主要考查学生对面向对象中类和对象的理解。A选项，在Python中，一切皆对象，这是Python的一个基本特性，它使得所有的数据类型、函数、方法甚至于类都可以被视为对象。B选项，在Python中，可以自定义新的类，并实例化为新的对象。这是面向对象编程的特点，Python支持面向对象(OOP)的编程。C选项，在Python中，函数也是对象，包括内置函数和自定义函数。这是因为在Python中，一切皆为对象，函数是一种可调用的对象。D选项中，在Python中，是可以在自定义函数中嵌套定义新的函数的。Python允许在函数内定义函数，这被称为嵌套函数。故本题选择D选项。

5、有关下⾯Python代码的说法 ，正确的是(      )。

A. 第17⾏代码执⾏后将报错， 因为Rect 类没有定义in运算符

B. 第16⾏代码将Point 对象作为参数 ，将导致错误

C. in是成员运算符 ，不适⽤于Rect 类

D. 由于Rect类定义了 __contain__魔术⽅法， 因此第17⾏代码能正确执⾏

【答案】D 

【解析】本题主要考察面向对象中魔法方法的使用。__contains__是Python中的一个魔术方法（特殊方法），用于支持in运算符。当对象使用in运算符时，解释器会尝试调用该对象的__contains__方法，以确定指定的元素是否包含在对象中。也就是说，如果一个类实现了__contains__方法，那么该类的实例可以使用in运算符。__contains__方法应该返回一个布尔值，表示对象是否包含给定的值。另外，面向对象编程支持一个类实例化出的对象作为参数传递给当前类的构造函数或其他方法，这样就在两个类之间建立了关联。故本题选择D选项。

6、有关下⾯Python代码的说法 ，正确的是(       )。

A. 第8⾏代码错误 ，第9⾏正确

B. 第9⾏代码错误 ，第8⾏代码正确

C. 第8 、9两⾏代码都正确

D. 第4⾏代码可修改为objCounter += 1

【答案】C 

【解析】本题主要考查学生对面向对象中类属性的掌握。代码中先定义了一个类newClass，定义了一个类属性objCounter，以及构造函数，接下来实例化出两个对象，第8行中，打印了newClass.objCounter的值，第9行打印了实例对象a的objCounter属性的值，两行代码都正确。第4行代码，通过newClass.objCounter+=1改变类的属性值，如果修改成objCounter+=1会出错，故本题选择C选项。

7、有关下⾯Python代码的说法 ，错误的是(      )。

 A. 上列Python代码适⽤于构造各种⼆叉树

 B. 代码Root = biTree(biTreeNode(5)) 构造⼆叉树的根节点

 C. 代码Root = biTree( ) 可以构造空⼆叉树，此时Root对象的Root属性值为None

 D. 代码 Root = biTree(biTreeNode(  ))可以构造空⼆叉树 ，此时Root对象的root属性为Node

【答案】D 

【解析】首先我们先分析给出的代码：biTreeNode类定义了一个二叉树的节点，它有三个属性：val、left和right。biTree类定义了一个二叉树，它有一个属性：root。

biTreeNode类定义了二叉树的节点，而biTree类定义了二叉树的结构，可以用于构造各种二叉树，A选项正确；B选项中首先使用biTreeNode(5)创建一个值为5的节点，然后使用biTree()构造一个二叉树，其根节点是刚刚创建的值为5的节点，所以也正确；C选项中，代码Root = biTree()创建一个新的二叉树时，没有给定参数，所以root值为默认值None，所以C选项也正确；D选项中，使用biTree(biTreeNode())创建二叉树时，它仍然是一个空的二叉树，但此时Root对象的root属性值为一个空biTreeNode对象，而不是“Node”。故本题选择D选项。

8、基于上题类的定义 ，有关下⾯Python代码的说法错误的是（    ）。

  A. 代码中Search（ ）函数如果查找到查找值的节点 ，则返回该节点的对象

  B. 代码中Search（ ）函数先搜索左⼦树 ，如果搜索不到指定值 ，则搜索右⼦树

  C. 代码中Search（ ）函数采⽤递归⽅式实现⼆叉树节点的搜索

  D. 代码中Search（ ）函数采⽤动态规划⽅法实现⼆叉树节点的搜索

【答案】D 

【解析】代码中的Search函数接收两个参数：root和val。如果root是None（也就是说，当前节点为空），则函数返回None。如果root.val等于要搜索的值val，则返回当前节点。否则，首先在左子树中搜索值，如果找到，返回该节点。如果在左子树中没有找到，则在右子树中搜索。并且在这个例子中，只是通过递归在二叉树中搜索一个值，并没有使用动态规划的方法。故本题D选项错误。

9、有关下⾯Python代码的说法正确的是（    ）。

A. 上述代码构成单向链表

B. 上述代码构成双向链表

C. 上述代码构成循环链表

D. 上述代码构成指针链表

【答案】B 

【解析】首先分析下这段代码，定义了一个名为Node的类，它有三个属性：Value、Prev和Next。Value用于存储节点的值，Prev和Next分别代表该节点的前一个和后一个节点。接下来，创建了一个名为firstNode的节点，并为其赋值为100；接下来设置了firstNode的Next属性为另一个新创建的节点，其值为100，并将firstNode设置为这个新节点的Prev属性；最后设置了新创建的节点的Next属性为另一个新创建的节点，其值为111，并将新创建的节点（值为100）设置为这个新节点的Prev属性。故本题构成了一个双向链表，选择B选项。

10、对hello world使⽤霍夫曼编码（Huffman Coding），最少bit（⽐特）为（   ）。

A. 4

B.32

C. 64

D. 88

【答案】B 

【解析】霍夫曼编码，其编码方式是根据字符出现的概率来确定的。具体来说，出现概率越高的字符，其对应的编码长度越短；出现概率越低的字符，其对应的编码长度越长。霍夫曼编码的流程主要包括以下几个步骤：

1、统计字符集中每个字符出现的频率

2、根据字符出现的频率构建霍夫曼树

3、根据霍夫曼树为每个字符分配二进制编码

我们根据上述的这三个步骤来构建下本题的霍夫曼树：

1、统计字符集中每个字符出现的频率：

hello world 中各字符出现的次数：h（1）、e（1）、l（3）、o（2）、w（1）、r（1）、d（1）、空格（1）。

2、根据字符出现的频率构建霍夫曼树：

3、根据霍夫曼树为每个字符分配二进制编码：

针对霍夫曼树，从根节点开始，我们将左叶子节点编为0，右叶子节点编为1，如下:

每个字符的霍夫曼编码即为从根节点到此字符的路径，

e编码000，占3位，出现次数1，总占位3*1=3;

w编码001，占3位，出现次数1，总占位3*1=3;

r编码010，占3位，出现次数1，总占位3*1=3;

d编码011，占3位，出现次数1，总占位3*1=3;

l编码10，占2位，出现次数3，总占位2*3=6;

o编码110，占3位，出现次数2，总占位3*2=6;

空格编码1110，占4位，出现次数1，总占位4*1=4;

h编码1111，占4位，出现次数1，总占位4*1=4;

总占用：3*4+6*2+4*2=32，故本题选择B选项。

11、下⾯的fiboA（ ）和 fiboB (  ) 两个函数分别实现斐波那契数列，该数列第1、第2项值为1，其余各项分别为前两项之和。下⾯有关说法错误的是（  ）。

  A.  fiboA（ ）采⽤递归⽅式实现斐波那契数列

  B.  fiboB（ ）采⽤动态规划算法实现斐波那契数列

  C. 当N值较⼤时，fiboA (  )存在⼤量重复计算

  D. 由于 fiboA (  ) 代码较短 ，其执⾏效率较⾼

【答案】D 

【解析】fiboA()通过递归的方式实现的斐波那契数列，fiboB()通过动态规划算法实现的斐波那契数列，从时间复杂度和空间复杂度的角度来看，动态规划方法比递归方法更高效。故本题D选项错误

12、有关下⾯Python代码不正确的说法是（    ）。

A. 该代码可⽤于求解⼆叉树的深度

B. 代码中函数getDepth( ) 的参数root表⽰根节点 ，⾮根节点不可以作为参数

C. 代码中函数getDepth( ) 采⽤了递归⽅法

D. 代码中函数getDepth( )可⽤于求解各种形式的⼆叉树深度 ，要求该⼆叉树节点⾄少有left和right 属性

【答案】B 

【解析】首先来分析下这段代码：这段代码定义了一个函数getDepth，它采用递归的方式计算二叉树的深度。它首先会检查根节点是否为空，如果为空则返回0。然后它递归的计算左子树和右子树的深度，并返回两者中的较大值加1。B选项，除了根节点之外，其它的非根节点也可以作为参数传递给函数。D选项，给定的代码明确地使用了root.left和root.right来访问节点的左子节点和右子节点。这意味着它适用于有这两个属性的二叉树节点，否则会报错。故本题选择B选项。

13、下⾯有关树的存储 ，错误的是（    ）.

  A. 完全⼆叉树可以⽤list存储

  B. ⼀般⼆叉树都可以⽤list存储 ，空⼦树位置可以⽤None表⽰

  C. 满⼆叉树可以⽤list存储

  D. 树数据结构 ，都可以⽤list存储

【答案】D 

【解析】A选项中完全二叉树可以用list存储，完全二叉树是一种特殊的二叉树，可以按照层次顺序依次存储在一个线性的列表中。B选项中一般二叉树可以使用列表存储，但需要采用适当的方式来表示树的结构，并对列表中的元素进行合理的编号，空子树位置可以用None表示。C选项中满二叉树是一种特殊的二叉树，所有非叶子节点都有两个子节点，满二叉树的节点数量是确定的，可以按照层次顺序存储在一个线性的列表中，因此也可以用列表存储。D选项中一般的树结构并不适合直接使用列表来存储，树结构可能具有不定的分支数，而列表是线性的结构，无法直接表示树状关系，对于一般的树，更常见的做法是使用节点和指针或引用来表示。故本题选择D选项。

14、下⾯有关Python中in运算符的时间复杂度的说法 ，错误的是（  ）。

  A. 当in运算符作⽤于dict时 ，其时间复杂度为0(1)

  B. 当in运算符作⽤于set时 ，其时间复杂度为0(1)

  C. 当in 运算符作⽤于list 时 ，其时间复杂度为0(N)

  D. 当in运算符作⽤于str 时 ，其时间复杂度为0(N)

【答案】D 

【解析】字典dict和集合set底层都是由哈希表实现的，所以其时间复杂度为O(1)；对于列表来说，是一个线性结构，需要一个一个遍历查看，所以时间复杂度为O(N)；而对于字符串str，采用一种朴素匹配算法，效率较低，时间复杂度为O(m*n)，故本题D选项错误。

15、下⾯有关bool( ) 函数的说法 ，正确的是（  ）。

A. 如果⾃定义类中没有定义魔术⽅法  __bool__( )，将不能对该类的对象使⽤bool( )函数

B. 如果⾃定义类中没有定义魔术⽅法 __bool__( )，将查找有⽆魔术⽅法__len__( )函数 ，如果有__len__( ) 则按 __len__( ) 的值进⾏处理 ，如果该值为0则返回False ，否则True，如果没有__len__( ),则返回值为True

C.  bool( )函数如果没有参数 ，返回值为True

D. 表达式bool(int)的值为False

【答案】B 

【解析】A选项，这个说法是不正确的，如果一个类没有定义__bool__()方法，Python会尝试查找__len__()方法。如果找到了__len__()方法，并且它的返回值是非零，那么bool()函数会返回True，否则返回False。 如果一个类的__len__()或__bool__()均未定义，则其所有实例都将被视为具有真值。所以B选项正确。C选项，bool() 函数如果没有参数，返回值为False。D选项中bool(int)的结果为True，故本题选择B选项。

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

 1、⼩杨想写⼀个程序来算出正整数N有多少个因数，经过思考他写出了⼀个重复没有超过N/2次的循环就能够算出来了。  (  )

【答案】正确 

【解析】本题首先要理解什么是因数，因数是能够整除给定数字的整数。例如，对于数字12，因数有1、2、3、4、6和12。要计算一个数字N的因数个数，我们可以使用一个循环，从1遍历到N/2(因为大于N/2的数除了它本身不可能是N的因数)，在循环中，我们检查每个数字i是否是N的因数，如果N能够被i整除，那么i就是N的一个因数。例如，如果N是100，那么我们只需要检查1到50的数字是否能够整除100。因此，对于给定的正整数N，我们可以通过一个循环，循环次数不超过N/2次，来计算出N的因数个数。故本题中正确。

2、同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。  (  )

【答案】正确 

【解析】冒泡排序是一种简单的排序算法，其基本思想是反复比较相邻的两个元素，如果他们的顺序错误就把他们交换过来，直到没有再需要交换的数为止。这个过程需要对每个元素进行比较和交换。单链表和双向链表在存储结构上有所不同，单链表每个节点只有一个指向下一个节点的链接，而双向链表除了有一个指向下一个节点的链接外，还有一个指向前一个节点的链接。但是，对于冒泡排序来说，这两种链表结构并没有实质性的影响。因为冒泡排序需要遍历整个链表，访问每个节点一次，比较相邻的节点并进行交换。这个过程在单链表和双向链表上是一样的。故本题正确。

3、在⾯向对象中，⽅法（Event）在Python的class中表现为class内定义的函数。(     )

【答案】正确 

【解析】在面向对象编程中，方法（Event）在Python的类中是通过在类内部定义函数来表现的。类是创建对象的模板，而方法则是与对象关联的函数。故本题正确。

4、在下⾯的Python代码被执⾏将报错，因为newClass没有__init__（）魔术⽅法。  (     )

【答案】错误 

【解析】我们定义类时，可以编写构造函数__init__（）对类的实例进行初始化操作，不过构造函数__init__（）不是必须要有的。在这段代码中定义了一个名为newClass的空类，然后创建了这个类的一个实例myNewClass，newClass类是空的，它不需要任何初始化操作，所以没有定义__init__()方法也不会导致错误。故本题错误。

5、如果某个Python对象（ object）⽀持下标运算符（⽅括号运算符） ，则该对象在所对应class中定义了名为 __getitem__的魔术⽅法 。(     )

【答案】正确 

【解析】在Python中，我们可以使用下标运算符（由方括号表示，例如obj[index]）来访问序列类型的对象（如列表、元组和字符串）中的元素。此外，这个运算符也可以用于字典来获取键对应的值。当我们使用下标运算符来访问一个对象时，会自动调用该对象的__getitem__()方法。所以，为了使一个对象支持下标运算符，我们需要在这个对象的类中定义__getitem__()方法。故本题正确。

6、深度优先搜索（DFS ，Depth First Search的简写）属于图算法 ，其过程是对每⼀个可能的分⽀路径深⼊到不 能再深⼊为⽌ ，⽽且每个节点只能访问⼀次 。(        )

【答案】正确 

【解析】深度优先搜索算法，也称为DFS算法，是一种遍历图或树的搜索算法，它先沿着一条路径一直走到底，然后回溯到上一个节点，继续沿着另一条路径走到底，直到所有节点都被遍历。深度优先算法有“后进先出”、“尽可能深的搜索”、“每个节点只访问一次”这几个特性。故本题正确。

7、哈夫曼编码（Huffman Coding）具有唯⼀性，因此有确定的压缩率。(    )

【答案】错误 

【解析】哈夫曼编码，其编码方式是根据字符出现的概率来确定的。具体来说，出现概率越高的字符，其对应的编码长度越短，出现概率越低的字符，其对应的编码长度越长。并且哈夫曼编码并不是唯一的，因为对于同一个字符集和对应的概率分布，可以构造出多个不同的哈夫曼树，从而得到不同的哈夫曼编码。所以，哈夫曼编码并不具有唯一性。故本题错误。

8、Python虽然不⽀持指针和引⽤语法，但变量的本质是数据的引⽤（reference）， 因此可以实现各种C/C++数据结构。在下⾯Python代码中，由于删除了变量a， 因此a所对应的数据也随之删除，故第4⾏代码被执⾏时，将报错。  (  )

【答案】错误 

【解析】第一行代码给变量a和b进行赋值，第二行给变量c赋值，需要清楚的是数据保存在内存中，而变量只是一个链接，指向内存地址，变量的赋值的本质是，新的变量也指向内存中的相同地址，只有所有链接都被删除了，那块内存才会被回收，那块内存区域中保存的数据就不复存在了。del语句删除的是变量，而不是数据。所以第三行del a，使用del语句，删除的只是变量到对象的引用和变量名称本身，del作用在变量上，而不是数据对象上。所以第四行打印c的结果应该是不被第三行的删除影响的，不会报错，结果为[[1, 2, 3], [3, 4, 5]]。故本题错误。

9、⼆叉搜索树查找的平均时间复杂度为0(logN) 。  (  )

【答案】正确 

【解析】二叉搜索树查找过程如下：

1.从根节点开始。

2.如果当前节点的值等于目标值，查找成功。

3.如果目标值小于当前节点的值，则在左子树中继续查找。

4.如果目标值大于当前节点的值，则在右子树中继续查找。

重复步骤2-4，直到查找成功或搜索路径为空（即目标值不存在于树中）。

在最好的情况下（即树是完全平衡的），查找的深度为 O(log N)，其中N是树中节点的数量。在最坏的情况下（即树退化为链表），查找的深度为O(N)。在平均情况下，二叉搜索树保证了树的平衡性，查找的平均时间复杂度仍然是O(log N)。

10、⼆叉搜索树可以是空树（没有任何节点）或者单节点树（只有⼀个节点） ，或者多节点 。如果是多节点 ， 则左节点的值⼩于⽗节点的值 ，右节点的值⼤于⽗节点的值， 由此推理 ，右节点树的值都⼤于根节点的值 ，左节点 树的值都⼩于根节点的值 。  (  )

【答案】正确 

【解析】这道题目主要考察二叉搜索树的性质。首先，二叉搜索树可以是空树，即没有任何节点。其次，二叉搜索树也可以是单节点树，这种情况下只有根节点，没有左子树或右子树。如果二叉搜索树是多节点树，那么它的左子树上所有节点的值都必须小于根节点的值，而右子树上所有节点的值都必须大于根节点的值。这是二叉搜索树最核心的性质。故本题正确。

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

1、闯关游戏

问题描述

你来到了⼀个闯关游戏。

这个游戏总共有N关 ，每关都有M个通道，你需要选择⼀个通道并通往后续关卡。其中 ，第i个通道可以让你前进a_i关，也就是说 ，如果你现在在第x关 ，那么选择第i个通道后，你将直接来到第x＋a_i 关（特别地，如果x + a_i ≥ N，那么你就通关了）。此外，当你顺利离开第S关时，你还将获得b_s 分。

游戏开始时，你在第0关。请问，你通关时最多能获得多少总分？

输入描述

第⼀⾏两个整数 N, M ，分别表⽰关卡数量和每关的通道数量。

接下来⼀⾏ M 个⽤单个空格隔开的整数a₀ , a₁, … ,a_M-1。保证 1 ≤ a_i ≤ N  。

接下来⼀⾏ N 个⽤单个空格隔开的整数b₀ , b₁, … ,b_N-1。保证｜b_i｜≤ 10⁵。

输出描述

一行一个整数，表示你通关时最多能够获得的分数。 

特别提醒

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

样例输入 1  

样例输出1 

样例解释1

你可以在第 0关选择第1个通道，获得 1分并来到第 3 关;随后再选择第 0个通道，获得 100 分并来到第 5关;最后任选一个通道，都可以获得 30 分并通关。如此，总得分为 1+ 100 + 30 = 131。 

样例输入2 

样例输出2 

样例解释2

请注意，一些关卡的得分可能是负数。 

数据规模

对于20%的测试点 ，保证 M = 1 。

对于40%的测试点 ，保证N ≤ 20 ；保证 M ≤ 2。

对于所有测试点 ，保证 N ≤ 10⁴ ；保证 M ≤ 100。

【题目大意】

输入关卡数、每关的通道数量，以及每个通道可以前进的关数和每关通过可以得到的分数，找出从第0关开始，通关之后能获得的最高分数。

【解题思路】

本题主要考察学生对动态规划这一利用之前计算的结果来求解更大的问题的解决问题方法的使用。

1.完成输入，关卡数量N，通道数量M，每个通道前进的关卡数a_i，以及每个关卡获得的分数b_s。

2.使用列表f来记录每个关卡通关时的最大得分。从第一个关卡开始，逐次计算每个关卡通关时的最大得分。对于每个关卡，遍历所有可选的通道，找到最大值更新f[i]（如果当前分数已经计算过（即f[i]不是None），则取当前分数和前一关分数的较大值；否则，将前一关分数设置为当前分数）。

3.在计算的过程中，如果达到通关条件时更新最大总分数ans。

【参考程序】

2、工作沟通

问题描述

某公司有N名员⼯，编号从0⾄N - 1 。其中，除了0号员⼯是⽼板，其余每名员⼯都有⼀个直接领导。我们假设编号为i的员⼯的直接领导是f_i。

该公司有严格的管理制度，每位员⼯只能受到本⼈或本⼈直接领导或间接领导的管理。具体来说，规定员⼯x可以管理员⼯y，当且仅当x=y，或x =  f_y ，或x可以管理 f_y。特别地，0号员⼯⽼板只能⾃我管理，⽆法由其他任何员⼯管理。现在，有⼀些同事要开展合作，他们希望找到⼀位同事来主持这场合作，这位同事必须能够管理参与合作的所有同事。如果有多名满⾜这⼀条件的员⼯，他们希望找到编号最⼤的员⼯。你能帮帮他们吗？

输入描述

第⼀⾏⼀个整数N，表⽰员⼯的数量。

第⼆⾏N-1个⽤空格隔开的正整数，依次为  f₁ , f₂ ，...， f_N-1。

第三⾏⼀个整数Q ，表⽰共有Q 场合作需要安排。

接下来Q ⾏，每⾏描述⼀场合作：开头是⼀个整数 m（2 ≤ m ≤ N），表⽰参与本次合作的员⼯数量；接着是m个整数，依次表⽰参与本次合作的员⼯编号（保证编号合法且不重复）。

保证公司结构合法，即不存在任意⼀名员⼯，其本⼈是⾃⼰的直接或间接领导。

输出描述

输出Q⾏，每⾏⼀个整数，依次为每场合作的主持⼈选。

特别提醒

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

样例输入 1 

样例输出 1 

样例解释

对于第一场合作，员工3，4 有共同领导2，可以主持合作。 

对于第二场合作，员工2本人即可以管理所有参与者。 

对于第三场合作，只有0号老板才能管理所有员工。 

样例输入 2 

样例输出 2 

数据规模

对于50%的测试点，保证 N ≤ 50。

对于所有测试点，保证 3 ≤ N ≤ 300 ；Q ≤ 100。

【题目大意】

某公司员工之间有一定的管理制度，只能受到本人、直接领导或者间接领导的管理。现在有一些合作场合，需要找到一位员工来主持，这位员工必须能够管理参与合作的所有同事，要求找到编号最大的员工。

【解题思路】

本题主要考察通过使用深度优先搜索（DFS）来判断每个员工是否能够管理参与合作的所有同事这一内容。

1.完成输入员工数量n和员工i的直接领导father，然后创建一个列表child，通过遍历father列表，填充child员工列表。

2.接下来输入合作的数量q，然后进入循环处理每个合作场合。每次先完成输入参与本次合作的员工数量，以及参与本次合作的员工编号。

3.然后使用深度优先搜索（DFS）来判断每个员工是否能够管理参与合作的所有同事。在每次DFS后，通过检查是否所有参与员工都被访问到，来判断当前员工是否能够管理合作的同事。如果是，则更新ans为当前员工的编号。

【参考程序】

【联系我们】

1. GESP微信：关注“CCF GESP”公众号，将问题以文字方式留言即可得到回复。

2. GESP邮箱：[e-mail]

注：请在邮件中详细描述咨询的问题并留下考生的联系方式及姓名、身份证号，以便及时有效处理。

3. GESP电话：[phone]

咨询时间：周一至周五(法定节假日除外）: 上午 8:30-12:00；下午 13:00-17:30

GESP第五期认证报名已启动，扫描下方二维码，关注GESP公众号即可报名

点击“阅读原文”，进入官网。