一、单选题
1、关于C++类和对象的说法，错误的是( )。
A、
在C++中，一切皆对象，即便是字面量如整数5等也是对象
B、
在C++中，可以自定义新的类，并实例化为新的对象
C、 在C++中，内置函数和自定义函数，都是类或者对象
D、
在C++中，可以在自定义函数中嵌套定义新的函数
2、有关下面C++代码的说法，错误的是( )。
A、
C++中类内部可以嵌套定义类
B、
在类中定义的类被称为内部类，定义类的类被称为外部类
C、 内部类可以随便访问，不需要通过外部类来访问
D、
代码中 Point 被称为内部类，可以通过外部类 Rectangle 来访问， Rectangle::Point
3、有关下面C++代码的说法，正确的是( )。
A、
第14行代码错误，第15行正确
B、
第15行代码错误，第14行代码正确
C、 第14、15两行代码都正确
D、
第6行代码可修改为 objCounter += 1
4、有关下面C++代码的说法，错误的是( )。
A、
上列C++代码适用于构造各种二叉树
B、
代码 struct BiNode 用于构造二叉树的节点
C、 代码 BiTree(){root=Creat();} 用于构造二叉树
D、
析构函数不可以省略
5、基于第4题的定义，有关下面C++代码的说法正确的是（ ）。
A、
代码中 Order( ) 函数是中序遍历二叉树的方法
B、
代码中 Order( ) 先访问根节点，然后对左子树进行前序遍历，再对右子树前序遍历
C、 代码中 Order( ) 先访问中序遍历左子树，然后访问根节点，最后则是中序遍历右子树
D、
代码中 Order( ) 先后序遍历左子树，然后后序遍历右子树，最后访问根节点
6、有关下面C++代码的说法正确的是（ ）。
A、 上述代码构成单向链表
B、
上述代码构成双向链表
C、
上述代码构成循环链表
D、
上述代码构成指针链表
7、对 hello world 使用霍夫曼编码（Huffman Coding），最少 bit（比特）为（ ）。
A、
4
B、 32
C、
64
D、
88
8、下面的 fiboA() 和 fiboB() 两个函数分别实现斐波那契数列，该数列第1、第2项值为1，其余各项分别为前两项之和。下面有关说法错误的是（ ）。
A、
fiboA() 采用递归方式实现斐波那契数列
B、
fiboB() 采用动态规划算法实现斐波那契数列
C、
当N值较大时， fiboA() 存在大量重复计算
D、 由于 fiboA() 代码较短，其执行效率较高
9、有关下面C++代码不正确的说法是（ B ）。
A、
该代码可用于求解二叉树的深度
B、 代码中函数 Depth( ) 的参数 T 表示根节点，非根节点不可以作为参数
C、
代码中函数 Depth( ) 采用了递归方法
D、
代码中函数 Depth( ) 可用于求解各种形式的二叉树深度，要求该二叉树节点至少有 left 和right 属性
10、下面有关树的存储，错误的是（ ）。
A、
完全二叉树可以用 list 存储
B、
一般二叉树都可以用 list 存储，空子树位置可以用 None 表示
C、
满二叉树可以用 list 存储
D、 树数据结构，都可以用 list 存储
11、构造二叉树 [1,2,3,null,4] （ ）。
A、 1(2()(4))(3)
B、
1(2(3)())(4)
C、
(1,2(3),(4))
D、
(1,(2)(3),(4))
12、下面有关布尔类型的函数的说法，正确的是（ ）。
A、 bool 类型函数只能返回0或者1两种值
B、
bool 类型函数可以返回任何整数值
C、
bool 类型函数必须有参数传递
D、
bool 类型函数没有返回值
13、通讯卫星在通信网络系统中主要起到（ ）的作用。（2023年12月C++六级）
A、
信息过滤
B、 信号中继
C、
避免攻击
D、
数据加密
14、小杨想编写一个判断任意输入的整数N是否为素数的程序，下面哪个方法不合适？（ ）（2023年12月C++六级）
A、
埃氏筛法
B、
线性筛法
C、 二分答案
D、
枚举法
15、内排序有不同的类别，下面哪种排序算法和冒泡排序是同一类？（ ）（2023年12月C++六级）
A、
希尔排序
B、
快速排序
C、
堆排序
D、 插入排序
二、判断题
16、在面向对象中，方法在C++的class中表现为class内定义的函数。( )
A 正确
B 错误
17、C++类的定义中，可以没有构造函数，会给出默认的构造函数（ ）
A 正确
B 错误
18、如果某个C++对象（object）支持下标运算符（方括号运算符），则该对象在所对应class中以成员函数的形式进行了重载。( )
A 正确
B 错误
19、深度优先搜索（DFS，Depth First Search的简写）属于图算法，其过程是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。( )（2023年12月C++六级）
A 正确
B 错误
20、哈夫曼编码（Huffman Coding）具有唯一性，因此有确定的压缩率。 ( )（2023年12月C++六级）
A 正确
B 错误
21、在下面C++代码中，由于删除了变量 ptr ，因此 ptr 所对应的数据也随之删除，故第8行代码被执行时，将报错。（ ）
A 正确
B 错误
22、二叉搜索树查找的平均时间复杂度为O(logN)。（ ）
A 正确
B 错误
23、二叉搜索树可以是空树（没有任何节点）或者单节点树（只有一个节点），或者多节点。如果是多节点，则左节点的值小于父节点的值，右节点的值大于父节点的值，由此推理，右节点树的值都大于根节点的值，左节点树的值都小于根节点的值。（ ）（2023年12月C++六级）
A 正确
B 错误
24、小杨想写一个程序来算出正整数N有多少个因数，经过思考他写出了一个重复没有超过N/2次的循环就能够算出来了。（ ）（2023年12月C++六级）
A 正确
B 错误
25、同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。（ ）（2023年12月C++六级）
A 正确
B 错误
三、实操题
26、闯关游戏
时间限制：1.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[0]为0，对于第i个通道，dp[i+a[j]-1] = max(dp[i+a[j]-1], dp[i] + b[i+a[j]-1])。最后，遍历dp数组，找到最大的值即为最大得分。
27、工作沟通
时间限制：1.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 。
参考答案：br />由于本题的数据规模较大，且每场合作的人数可能为任意人，需要高效且准确地进行求解。对于每一场合作，我们需要找到能管理所有参与者的最大编号员工。可以通过遍历每个员工，判断其是否能管理所有参与者来实现。具体步骤如下：1. 对于每场合作，遍历所有参与者，将其标记为已选中。2. 遍历所有员工，对于每个员工，检查其是否能管理所有已选中的参与者。如果能，则找到一个可能的主持人。3. 如果在遍历完所有员工后，没有找到能管理所有参与者的员工，则说明不存在满足条件的主持人。4. 在找到可能的主持人后，如果存在多个主持人，则选择编号最大的那个。5. 重复上述步骤，直到处理完所有的合作。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
