GESP-C++六级 题库
给定一个二叉树,返回每一层中最大的节点值,结果以数组形式返回,横线处应填入?( )
以下关于动态规划算法特性的描述,正确的是?( )
给定 个物品和一个最大承重为 W 的背包,每个物品有一个重量 wt[i] 和价值 val[i],每个物品只能选择放或不放。
目标是选择若干个物品放入背包,使得总价值最大,且总重量不超过 W。关于下面代码,说法正确的是?( )
在面向对象编程中,类是一种重要的概念。下面关于类的描述中,【不正确】的是?( )
选项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 ,横线上应填写?( )
以下代码用于检查字符串中的括号是否匹配,横线上应填写?( )
关于下面代码,说法【错误】的是?( )