在面向对象编程中,类是一种重要的概念。下面关于类的描述中,【不正确】的是?( )
查看答案与解析
选项D错误,类的属性和方法可以修改或扩展(如通过继承、补丁等)。
在面向对象编程中,类是一种重要的概念。下面关于类的描述中,【不正确】的是?( )
选项D错误,类的属性和方法可以修改或扩展(如通过继承、补丁等)。
哈夫曼编码是一种数据压缩算法。以下关于哈夫曼编码的描述中,【不正确】的是?( )
哈夫曼编码是一种基于字符出现频率的无损数据压缩算法,其核心思想是:
变长编码:频率高的字符用较短的编码,频率低的字符用较长的编码。
前缀编码:任何字符的编码都不是其他字符编码的前缀,确保解码唯一性。
贪心算法:通过合并频率最低的节点构建哈夫曼树。
选项B错误,哈夫曼树的构造规则是:频率越低的字符离根节点越远(路径更长),频率越高的字符离根节点越近(路径更短)。
以下代码实现了树的哪种遍历方式?( )
树的遍历主要方式:
前序遍历:访问顺序:根节点 → 左子树 → 右子树。
中序遍历:访问顺序:左子树 → 根节点 → 右子树。
后序遍历:访问顺序:左子树 → 右子树 → 根节点。
这段代码实现了树的 前序遍历(根→左→右)。
以下关于完全二叉树的代码描述,正确的是?( )
使用队列 q 进行层序遍历,hasNull 标记是否遇到过空节点(初始为 false)。
遍历过程:
每次从队列中取出一个节点 node。
如果 node 是 nullptr:设置 hasNull = true。
如果 node 非空:若之前已遇到空节点(hasNull == true),则直接返回 false(违反完全二叉树的定义)。
否则,将 node 的左右子节点(无论是否为空)加入队列。
代码实现了 完全二叉树的判断逻辑。
以下代码实现了二叉排序树的哪种操作?( )
程序中:
if (root == nullptr) return new TreeNode(val)
若目标值不存在,则在叶子节点位置创建新节点。
若目标值更小,递归查找左子树;若目标值更大,递归查找右子树。
这段代码通过递归查找插入位置并动态创建新节点,实现了 二叉排序树的插入操作。
给定字符集 {A, B, C, D} 的出现频率分别为 {5, 1, 6, 2} ,则正确的哈夫曼编码是?( )
关于动态规划的描述,正确的是?( )
选项B正确,动态规划问题的两个必要条件:
最优子结构确保问题可分解,重叠子问题使得记忆化有意义。
以下代码中,类的构造函数被调用了( )次?
MyClass obj1:调用 默认构造函数,输出 "Constructor called!"。
MyClass obj2 = obj1,调用的是隐式拷贝构造函数,不会触发默认构造函数。
因此 构造函数仅被调用 1 次。
以下代码实现了循环队列的哪种操作?( )
enQueue()函数(入队):
首先检查队列是否已满,如果已满则返回 false,表示入队失败。
如果队列为空(isEmpty()),初始化 front 为 0。
更新 rear 指针:rear = (rear + 1) % size,循环队列利用取模实现环形移动。
将新值 value 存入 arr[rear]。
返回 true 表示入队成功。
以下代码实现了二叉树的深度优先搜索(DFS),并统计叶子结点的数量,则横线上应填写?( )
空缺的位置在 while 循环的末尾,当前代码已经处理了右子树的压栈操作,需要补充左子树的处理逻辑。
程序使用栈(stack<TreeNode*>)来实现 DFS,空缺部分应该是一个类似的逻辑:如果 node 有左子节点,则将其压入栈。
本题答案为选项A。
以下代码实现了二叉树的广度优先搜索(BFS),并查找特定值的节点,则横线上应填写?( )
BFS 遍历:使用队列(queue)来实现 BFS。
初始时,将根节点 root 入队。
在 while 循环中,取出队首节点 current:
如果 current->val == target,则返回 current(找到目标节点)。
空缺部分需要将 current 的子节点(左子节点和右子节点)入队。
本题答案为选项A。
以下代码用于生成 n 位格雷编码。横线上应填写?( )
格雷码的特点是:
相邻两个编码只有 1 位不同。
可以通过递归方式生成:n 位格雷码 = "0" + (n-1 位格雷码) + "1" + (n-1 位格雷码的逆序)。
前半部分:在 prev 的每个编码前加 "0"("0" + s)。
后半部分:在 prev 的 逆序 每个编码前加 "1"("1" + prev[i])。
本题答案为选项A。
以下代码实现了0/1背包问题的动态规划解法。假设物品重量为 weights[] ,价值为 values[] ,背包容量为 W ,横线上应填写?( )
以下代码用于检查字符串中的括号是否匹配,横线上应填写?( )
关于下面代码,说法【错误】的是?( )
哈夫曼树在构造过程中,每次合并权值最小的两个节点,最终生成的树带权路径长度最小。( )
格雷编码的相邻两个编码之间必须有多位不同,以避免数据传输错误。( )
格雷码定义:相邻的两个格雷码之间仅一位不同。
在树的深度优先搜索(DFS)中,使用队列作为辅助数据结构以实现“先进后出”的访问顺序。( )
说法错误,在树的深度优先搜索(DFS)中,使用栈作为辅助数据结构以实现“先进后出”的访问顺序。
以下代码实现的是二叉树的中序遍历。( )
C++ 支持构造函数重载,但默认无参数的构造函数只能有一个。( )
二叉排序树(BST)中,若某节点的左子树为空,则该节点一定是树中的最小值节点。( )
在动态规划解决一维硬币找零问题时,若硬币面额为 [1, 3, 4] ,目标金额为 6 ,则最少需要 2 枚硬币(3+3)。( )
面向对象编程中,封装是指将数据和行为绑定在一起,并对外隐藏实现细节。( )
以下代码创建的树是一棵完全二叉树。( )
TreeNode* root = new TreeNode{1};
root->left = new TreeNode{2};
root->right = new TreeNode{3};
root->left->left = new TreeNode{4};
栈和队列均可以用双向链表实现,插入和删除操作的时间复杂度为 O(1) 。( )
树上漫步
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 有一棵 n 个结点的树,这些结点依次以 1、2、……、n标号。
小 A 想在这棵树上漫步。具体来说,小 A 会从树上的某个结点出发,每一步可以移动到与当前结点相邻的结点,并且小 A 只会在偶数步(可以是零步)后结束漫步。
现在小 A 想知道,对于树上的每个结点,从这个结点出发开始漫步,经过偶数步能结束漫步的结点有多少个(可以经过重复的节点)。
【输入描述】
第一行,一个正整数 n。
接下来 n - 1 行,每行两个整数 ui、vi,表示树上有一条连接结点 ui 和结点 vi 的边。
【输出描述】
一行, n 个整数,第 i 个整数表示从结点 i 出发开始漫步,能结束漫步的结点数量。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于 20% 的测试点,保证 1<=n<=1000。
对于所有测试点,保证 1<=n<=200000。
环线
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 喜欢坐地铁。地铁环线有 n 个车站,依次以 1、2、……、n标号。车站 i(1<=i<n )的下一个车站是车站 i+1。
特殊地,车站 n 的下一个车站是车站 1。
小 A 会从某个车站出发,乘坐地铁环线到某个车站结束行程,这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。
当小 A 乘坐地铁环线经过车站 i 时,小 A 会获得 ai 点快乐值。请你安排小 A 的行程,选择出发车站与结束车站,使得获得的快乐值总和最大。
【输入描述】
第一行,一个正整数 n,表示车站的数量。
第二行, n 个整数 a1、a2、……、an,分别表示经过每个车站时获得的快乐值。
【输出描述】
一行,一个整数,表示小 A 能获得的最大快乐值。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于 20% 的测试点,保证 1<=n<=200。
对于 40% 的测试点,保证 1<=n<=2000。
对于所有测试点,保证 1<=n<=200000, -10^9<=ai<=10^9。
正确答案: 暂无(答题 0次,答对 0次,正确率:0%)