GESP-C++六级 题库
以下代码实现了树的哪种遍历方式?( )
树的遍历主要方式:
前序遍历:访问顺序:根节点 → 左子树 → 右子树。
中序遍历:访问顺序:左子树 → 根节点 → 右子树。
后序遍历:访问顺序:左子树 → 右子树 → 根节点。
这段代码实现了树的 前序遍历(根→左→右)。
以下关于完全二叉树的代码描述,正确的是?( )
使用队列 q 进行层序遍历,hasNull 标记是否遇到过空节点(初始为 false)。
遍历过程:
每次从队列中取出一个节点 node。
如果 node 是 nullptr:设置 hasNull = true。
如果 node 非空:若之前已遇到空节点(hasNull == true),则直接返回 false(违反完全二叉树的定义)。
否则,将 node 的左右子节点(无论是否为空)加入队列。
代码实现了 完全二叉树的判断逻辑。
以下代码实现了二叉排序树的哪种操作?( )
程序中:
if (root == nullptr) return new TreeNode(val)
若目标值不存在,则在叶子节点位置创建新节点。
若目标值更小,递归查找左子树;若目标值更大,递归查找右子树。
这段代码通过递归查找插入位置并动态创建新节点,实现了 二叉排序树的插入操作。
以下代码实现了二叉树的深度优先搜索(DFS),并统计叶子结点的数量,则横线上应填写?( )
空缺的位置在 while 循环的末尾,当前代码已经处理了右子树的压栈操作,需要补充左子树的处理逻辑。
程序使用栈(stack<TreeNode*>)来实现 DFS,空缺部分应该是一个类似的逻辑:如果 node 有左子节点,则将其压入栈。
本题答案为选项A。
以下代码实现了二叉树的广度优先搜索(BFS),并查找特定值的节点,则横线上应填写?( )
BFS 遍历:使用队列(queue)来实现 BFS。
初始时,将根节点 root 入队。
在 while 循环中,取出队首节点 current:
如果 current->val == target,则返回 current(找到目标节点)。
空缺部分需要将 current 的子节点(左子节点和右子节点)入队。
本题答案为选项A。
N 个节点的双向循环链,在其中查找某个节点的平均时间复杂度是( )。
以下关于树的说法,( )是正确的。
根据下面二叉树和给定的代码,
给定以下二叉搜索树,调用函数 search(root,7) 时,输出的结果是( )。
阅读以下二叉树的深度优先搜索算法,横线上应填写( )。
阅读以下二叉树的广度优先搜索的代码,横线上应填写( )。
使用上题中的宽度优先搜索算法遍历以下这棵树,可能的输出是( )。
给定一棵二叉树,其前序遍历结果为:ABDECFG,中序遍历结果为:DEBACFG,则这棵树的正确后序遍历结果是( )。(2024.9-6)
在前序遍历中找根,在中序遍历中找根的左右子树,建好树后进行后序遍历。
一棵有 n 个结点的完全二叉树用数组进行存储与表示,已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点,则它的兄弟结点和右子结点的位置分别是( )。(2024.9-6)
完全二叉树兄弟结点一般是左偶右奇,9号结点的兄弟结点只能是8号,而右子结点即9*2+1 = 19,选C
二叉树的深度定义为从根结点到叶结点的最长路径上的结点数,则以下基于二叉树的深度优先搜索实现的深度计算函数中横线上应填写( )。
代码的思路是计算出当前根结点左子树的深度,右子树的深度,那么以根结点为子树的深度即max(左子树,右子树)+1,+1即将根结点的深度也计算在内,所以选C。
上一题的二叉树深度计算还可以采用二叉树的广度优先搜索来实现。以下基于二叉树的广度优先搜索实现的深度计算函数中横线上应填写( )。
二叉搜索树中的每个结点,其左子树的所有结点值都小于该结点值,右子树的所有结点值都大于该结点值。以下代码对给定的整数数组(假设数组中没有数值相等的元素),构造一个对应的二叉搜索树,横线上应填写():
对上题中的二叉搜素树,当输入数组为[5,3,7,2,4,6,8] 时,构建二叉搜索树,并采用如下代码实现的遍历方式,得到的输出是( )。
根据输入数组建BST,然后根据 “左根右”的遍历规则输出为: 2 3 4 5 6 7 8,选B
向一个栈顶为hs的链式栈中插入一个指针为s的结点时,应执行( )。
指针之间的赋值:A=B可以理解为A指向B,栈的结构为先进后出,因此S需要作为栈顶存在,hs需要指向S,即hs=s;但是在此之前,需要将S链接到hs,即S的下一个指针指向S,有S->next=hs;
二叉树的( )第一个访问的节点是根节点。
先序遍历先根再左子树再右子树,中序遍历先左子树再根再右子树,后序遍历先左子树再右子树再根。
