一、单选题
1、通讯卫星在通信网络系统中主要起到（ ）的作用。
A、
信息过滤
B、 信号中继
C、
避免攻击
D、
数据加密
2、小杨想编写一个判断任意输入的整数N是否为素数的程序，下面哪个方法不合适？（ ）
A、
埃氏筛法
B、
线性筛法
C、 二分答案
D、
枚举法
3、内排序有不同的类别，下面哪种排序算法和冒泡排序是同一类？（ ）
A、
希尔排序
B、
快速排序
C、
堆排序
D、 插入排序
4、关于Python类和对象的说法，错误的是( )。
A、
在Python中，一切皆对象，即便是字面量如整数5等也是对象
B、
在Python中，可以自定义新的类，并实例化为新的对象
C、 在Python中，内置函数和自定义函数，都是类或者对象
D、
在Python中，不可以在自定义函数中嵌套定义新的函数
5、有关下面Python代码的说法，正确的是( )。
A、
第17行代码执行后将报错，因为 Rect 类没有定义 in 运算符
B、
第16行代码将 Point 对象作为参数，将导致错误
C、
in是成员运算符，不适用于 Rect 类
D、 由于 Rect 类定义了 __contains__ 魔术方法，因此第17行代码能正确执行
6、有关下面Python代码的说法，正确的是( )。
A、
第8行代码错误，第9行正确
B、
第9行代码错误，第8行代码正确
C、 第8、9两行代码都正确
D、
第4行代码可修改为 objCounter += 1
7、有关下面Python代码的说法，错误的是( )。
A、
上列Python代码适用于构造各种二叉树
B、
代码 Root = biTree(biTreeNode(5)) 构造二叉树的根节点
C、
代码 Root = biTree( ) 可以构造空二叉树，此时 Root 对象的 root 属性值为 None
D、 代码 Root = biTree(biTreeNode( )) 可以构造空二叉树，此时 Root 对象的 root 属性为 Node
8、基于上题类的定义，有关下面Python代码的说法错误的是（ ）。
A、
代码中 Search( ) 函数如果查找到查找值的节点，则返回该节点的对象
B、
代码中 Search( ) 函数先搜索左子树，如果搜索不到指定值，则搜索右子树
C、
代码中 Search( ) 函数采用递归方式实现二叉树节点的搜索
D、 代码中 Search( ) 函数采用动态规划方法实现二叉树节点的搜索
9、有关下面Python代码的说法正确的是（ ）。
A、 上述代码构成单向链表
B、
上述代码构成双向链表
C、
上述代码构成循环链表
D、
上述代码构成指针链表
10、对 hello world 使用霍夫曼编码（Huffman Coding），最少 bit（比特）为（ ）。
A、
4
B、 32
C、
64
D、
88
11、下面的 fiboA( ) 和 fiboB( ) 两个函数分别实现斐波那契数列，该数列第1、第2项值为1，其余各项分别为前两项之和。下面有关说法错误的是（ ）。
A、
fiboA( ) 采用递归方式实现斐波那契数列
B、
fiboB( ) 采用动态规划算法实现斐波那契数列
C、
当N值较大时， fiboA( ) 存在大量重复计算
D、 由于 fiboA( ) 代码较短，其执行效率较高
12、有关下面Python代码不正确的说法是（ ）。
A、
该代码可用于求解二叉树的深度
B、 代码中函数 getDepth( ) 的参数 root 表示根节点，非根节点不可以作为参数
C、
代码中函数 getDepth( ) 采用了递归方法
D、
代码中函数 getDepth( ) 可用于求解各种形式的二叉树深度，要求该二叉树节点至少有 left 和 right 属性
13、下面有关树的存储，错误的是（ ）.
A、
完全二叉树可以用 list 存储
B、
一般二叉树都可以用 list 存储，空子树位置可以用 None 表示
C、
满二叉树可以用 list 存储
D、 树数据结构，都可以用 list 存储
14、下面有关Python中 in 运算符的时间复杂度的说法，错误的是（ ）。
A、
当 in 运算符作用于 dict 时，其时间复杂度为O(1)
B、
当 in 运算符作用于 set 时，其时间复杂度为O(1)
C、
当 in 运算符作用于 list 时，其时间复杂度为O(N)
D、 当 in 运算符作用于 str 时，其时间复杂度为O(N)
15、下面有关 bool() 函数的说法，正确的是（ ）。
A、 如果自定义类中没有定义魔术方法 __bool__( ) ，将不能对该类的对象使用 bool( ) 函数
B、
如果自定义类中没有定义魔术方法 __bool__( ) ，将查找有无魔术方法 __len__( ) 函数，如果有__len__( ) 则按 __len__( ) 的值进行处理，如果该值为0则返回 False ，否则 True ，如果没有 __len__() ，则返回值为 True
C、
bool( ) 函数如果没有参数，返回值为 False
D、
表达式 bool(int) 的值为 False
二、判断题
16、小杨想写一个程序来算出正整数N有多少个因数，经过思考他写出了一个重复没有超过N/2次的循环就能够算出来了。（ ）
A 正确
B 错误
17、同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。（ ）
A 正确
B 错误
18、在面向对象中，方法（Event）在Python的class中表现为class内定义的函数。( )
A 正确
B 错误
19、在下面的Python代码被执行将报错，因为newClass没有 __init__( ) 魔术方法。（ ）
A 正确
B 错误
20、如果某个Python对象（object）支持下标运算符（方括号运算符），则该对象在所对应class中定义了名为__getitem__ 的魔术方法。( )
A 正确
B 错误
21、深度优先搜索（DFS，Depth First Search的简写）属于图算法，其过程是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。( )
A 正确
B 错误
22、哈夫曼编码（Huffman Coding）具有唯一性，因此有确定的压缩率。 ( )
A 正确
B 错误
23、Python虽然不支持指针和引用语法，但变量的本质是数据的引用（reference），因此可以实现各种C/C++数据结构。在下面Python代码中，由于删除了变量a，因此a所对应的数据也随之删除，故第4行代码被执行时，将报错。（ ）
A 正确
B 错误
24、二叉搜索树查找的平均时间复杂度为 。（ ）
A 正确
B 错误
25、二叉搜索树可以是空树（没有任何节点）或者单节点树（只有一个节点），或者多节点。如果是多节点，则左节点的值小于父节点的值，右节点的值大于父节点的值，由此推理，右节点树的值都大于根节点的值，左节点树的值都小于根节点的值。（ ）
A 正确
B 错误
三、实操题
26、闯关游戏
时间限制：2.0 s
内存限制：128.0 MB
问题描述
你来到了一个闯关游戏。
这个游戏总共有N关，每关都有M个通道，你需要选择一个通道并通往后续关卡。其中，第i个通道可以让你前进ai关，也就是说，如果你现在在第x关，那么选择第i个通道后，你将直接来到第x+ai关（特别地，如果x+ai≥N，那么你就通关了）。此外，当你顺利离开第s关时，你还将获得bs分。
游戏开始时，你在第0关。请问，你通关时最多能获得多少总分？
输入描述
第一行两个整数N,M，分别表示关卡数量和每关的通道数量。
接下来一行M个用单个空格隔开的整数a0,a1,……,aM-1。保证1≤ai≤N。
接下来一行N个用单个空格隔开的整数b0,b1,……,bN-1。保证|bi|≤105。
输出描述
一行一个整数，表示你通关时最多能够获得的分数。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
6 2 2 3 1 0 30 100 30 30
样例输出 1
131
样例解释 1
你可以在第0关选择第1个通道，获得1分并来到第3关；随后再选择第0个通道，获得100分并来到第5关；最后任选一个通道，都可以获得30分并通关。如此，总得分为1+100+30=131。
样例输入 2
6 2 2 3 1 0 30 100 30 -1
样例输出 2
101
样例解释 2
请注意，一些关卡的得分可能是负数。
数据规模
对于20%的测试点，保证M=1。
对于40%的测试点，保证N≤20；保证M≤2。
对于所有测试点，保证N≤104；保证M≤100。
参考答案：对于每个通道，我们可以计算出从当前关卡到下一关卡所需的步数，以及从当前关卡到下一关卡所能获得的分数。然后，我们可以使用动态规划算法来求解。首先，我们定义一个数组dp，其中dp[i]表示从第0关到第i关所能获得的最大分数。对于每个通道，我们可以计算出从当前关卡到下一关卡所需的步数，以及从当前关卡到下一关卡所能获得的分数。然后，我们可以更新dp数组，使得dp[i]等于dp[j]+score，其中j表示从当前关卡到下一关卡所需的关卡数，score表示从当前关卡到下一关卡所能获得的分数。最后，我们返回dp[N-1]，即从第0关到第N-1关所能获得的最大分数。
27、工作沟通
时间限制：2.0 s
内存限制：128.0 MB
问题描述
某公司有N名员工，编号从0至N-1。其中，除了0号员工是老板，其余每名员工都有一个直接领导。我们假设编号为i的员工的直接领导是fi。
该公司有严格的管理制度，每位员工只能受到本人或本人直接领导或间接领导的管理。具体来说，规定员工x可以管理员工y，当且仅当x=y，或f=fy，或x可以管理fy。特别地，0号员工老板只能自我管理，无法由其他任何员工管理。
现在，有一些同事要开展合作，他们希望找到一位同事来主持这场合作，这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工，他们希望找到编号最大的员工。你能帮帮他们吗？
输入描述
第一行一个整数N，表示员工的数量。
第二行N-1个用空格隔开的正整数，依次为f1,f2…,fN-1。
第三行一个整数Q，表示共有Q场合作需要安排。
接下来Q行，每行描述一场合作：开头是一个整数m（2≤m≤N），表示参与本次合作的员工数量；接着是m个整数，依次表示参与本次合作的员工编号（保证编号合法且不重复）。
保证公司结构合法，即不存在任意一名员工，其本人是自己的直接或间接领导。
输出描述
输出Q行，每行一个整数，依次为每场合作的主持人选。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
5 0 0 2 2 3 2 3 4 3 2 3 4 2 1 4
样例输出 1
2 2 0
样例解释 1
对于第一场合作，员工3,4有共同领导2，可以主持合作。
对于第二场合作，员工2本人即可以管理所有参与者。
对于第三场合作，只有0号老板才能管理所有员工。
样例输入 2
7 0 1 0 2 1 2 5 2 4 6 2 4 5 3 4 5 6 4 2 4 5 6 2 3 4
样例输出 2
2 1 1 1 0
数据规模
对于50%的测试点，保证N≤50。
对于所有测试点，保证3≤N≤300；Q≤100 。
参考答案：对于每一场合作，我们需要找到能够管理所有参与者的员工。我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历整个公司结构，找到能够管理所有参与者的员工。具体实现步骤如下：1. 遍历每一场合作，获取参与者的编号。2. 从参与者的直接领导开始，向上追溯，直到找到能够管理所有参与者的员工，或追溯到了老板。3. 如果找到了能够管理所有参与者的员工，输出其编号。4. 如果没有找到能够管理所有参与者的员工，输出0号员工（老板）。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
