在一个循环队列中, front 是指向队头的指针, rear 指向队尾的指针,队列最大容量为 maxSize 。
判断队列已满的条件是?( )
在一个循环队列中, front 是指向队头的指针, rear 指向队尾的指针,队列最大容量为 maxSize 。
判断队列已满的条件是?( )
下列哪一项不是面向对象编程的基本特征?( )
为了让 Dog 类的构造函数能正确地调用其父类 Animal 的构造方法,横线线处应填入?( )
代码同上一题,代码执行结果是?( )
以下关于栈和队列的代码,执行后输出是?( )
( )只有最底层的节点未被填满,且最底层节点尽量靠左填充?
在使用数组表示完全二叉树时,如果一个节点的索引为 i(从 0 开始计数),那么其左子节点的索引通常是?( )
使用数组表示完全二叉树时,通常按照层次遍历的顺序存储节点。
假设根节点的索引为 0,对于任意节点索引 i,其左子节点的索引为 2*i+1,其右子节点的索引为 2*i+2。
已知一棵二叉树的前序遍历序列为 GDAFEMHZ ,中序遍历序列为 ADFGEHMZ ,则其后序遍历序列为?( )
设有字符集 {a, b, c, d, e},其出现频率分别为 {5, 8, 12, 15, 20},得到的哈夫曼编码为?( )
3位格雷编码中,编码 101 之后的下一个编码【不可能】是?( )
请将下列 C++ 实现的深度优先搜索(DFS)代码补充完整,横线处应填入?( )
给定一个二叉树,返回每一层中最大的节点值,结果以数组形式返回,横线处应填入?( )
下面代码实现一个二叉排序树的插入函数(没有相同的数值),横线处应填入?( )
以下关于动态规划算法特性的描述,正确的是?( )
给定 个物品和一个最大承重为 W 的背包,每个物品有一个重量 wt[i] 和价值 val[i],每个物品只能选择放或不放。
目标是选择若干个物品放入背包,使得总价值最大,且总重量不超过 W。关于下面代码,说法正确的是?( )
构造函数可以被声明为 virtual。( )
给定一组字符及其出现的频率,构造出的哈夫曼树是唯一的。( )
为了实现一个队列,使其出队操作( pop )的时间复杂度为 O(1) 并且避免数组删除首元素的 O(n) 问题,一种常见且有效的方法是使用环形数组,通过调整队首和队尾指针来实现。( )
使用环形数组实现队列时,出队操作只需移动队首指针并返回该位置的元素,无需移动其他元素,因此时间复杂度为O(1)。
在普通数组中,删除首元素需要将所有后续元素向前移动一位,时间复杂度为O(n)。而环形数组通过维护队首和队尾指针,出队时只需移动指针,避免了数据移动。
因此本题说法是正确。
对一棵二叉排序树进行中序遍历,可以得到一个递增的有序序列。( )
如果二叉搜索树在连续的插入和删除操作后,所有节点都偏向一侧,导致其退化为类似于链表的结构,这时其查找、插入、删除操作的时间复杂度会从理想情况下的 O(log n) 退化到 O(n log n)。( )
执行下列代码, my_dog.name 的最终值是 Charlie 。( )
下列 C++ 代码可以成功编译,并且子类 Child 的实例能通过其成员函数访问父类 Parent 的属性value 。( )
下列代码中的 tree 向量,表示的是一棵完全二叉树 ( -1 代表空节点)按照层序遍历的结果。( )
在树的深度优先搜索(DFS)中,使用栈作为辅助数据结构以实现“先进后出”的访问顺序。( )
下面代码采用动态规划求解零钱兑换问题:给定 n 种硬币,第 i 种硬币的面值为 coins[i - 1] ,目标金额为 amt ,每种硬币可以重复选取,求能够凑出目标金额的最少硬币数量;如果不能凑出目标金额,返回 -1 。( )
学习小组
时间限制:1 s,内存限制:512 MB
【问题描述】
班主任计划将班级里的 n 名同学划分为若干个学习小组,每名同学都需要分入某一个学习小组中。观察发现,如果一个学习小组中恰好包含 k 名同学,则该学习小组的讨论积极度为 ak。
给定讨论积极度 a1、a2、……、an,请你计算将这 n 名同学划分为学习小组的所有可能方案中,讨论积极度之和的最大值。
【输入描述】
第一行,一个正整数 n,表示班级人数。
第二行,n 个非负整数 a1、a2、……、an,表示不同人数学习小组的讨论积极度。
【输出描述】
输出共一行,一个整数,表示所有划分方案中,学习小组讨论积极度之和的最大值。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于40%测试点,保证 1 <= n <= 10。
对于所有测试点,保证 1 <= n <= 1000,0 <= ai <= 10000。
最大因数
时间限制:1 s,内存限制:512 MB
【问题描述】
给定一棵有 10^9 个结点的有根树,这些结点依次以 1、2、……、10^9编号,根结点的编号为 1。
对于编号为 k(2 <= k <= 10^9)的结点,其父结点的编号为 k 的因数中除 k 以外最大的因数。
现在有 q 组询问,第 i(1<= i <= q)组询问给定 xi、yi,请你求出编号分别为 xi、yi 的两个结点在这棵树上的距离。
两个结点之间的距离是连接这两个结点的简单路径所包含的边数。
【输入描述】
第一行,一个正整数 q,表示询问组数。
接下来 q 行,每行两个正整数 xi、yi,表示询问结点的编号。
【输出描述】
输出共 q 行,每行一个整数,表示结点 xi、yi 之间的距离。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于60%的测试点,保证 1 <= xi、yi <= 1000。
对于所有测试点,保证 1 <= q <= 1000,1 <= xi、yi <= 10^9。