GESP-C++六级 题库
一棵有 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;
二叉树的( )第一个访问的节点是根节点。
先序遍历先根再左子树再右子树,中序遍历先左子树再根再右子树,后序遍历先左子树再右子树再根。
一棵5层的满二叉树中节点数为( )。
一个K层的满二叉树的节点个数为1+2+4+……+2k-1=2k-1 (等比数列/二进制)。
阅读以下二叉树的广度优先搜索代码:
使用以上算法,在以下这棵树搜索数值20时,可能的输出是( )。
该程序使用广搜方式,因此为二叉树层序遍历,答案选C
同上题中的二叉树,阅读以下二叉树的深度优先搜索代码:
使用以上算法,在二叉树搜索数值20时,可能的输出是( )。
该题目使用栈代替了DFS的递归形式,由输出和push的顺序,可以知道该题目为先序遍历,因此答案为A。
在上题的树中搜索数值3时,采用深度优先搜索一共比较的节点数为( )。
该二叉树中序遍历有序,同时从构造形态上,为一棵二叉排序树,但是程序并不是按照二叉排序树的规则,题目是先序遍历比较,因此比较的节点依次为:5、2、-4、3,共4次。
以下代码希望能在一棵二叉排序树中搜索特定的值,请在横线处填入( ),使其能正确实现相应功能。
阅读以下广度优先搜索的代码:
使用以上算法遍历以下这棵树,可能的输出是( )。

若一棵二叉树的先序遍历为:A, B, D, E, C, F、中序遍历为:D, B, E, A, F, C,它的后序遍历为( )。
有关下面C++代码的说法,错误的是( )。

C++中类内部可以嵌套定义类
在类中定义的类被称为内部类,定义类的类被称为外部类
内部类可以随便访问,不需要通过外部类来访问
代码中 Point 被称为内部类,可以通过外部类 Rectangle 来访问, Rectangle::Point
有关下面C++代码的说法,正确的是( )。

第14行代码错误,第15行正确
第15行代码错误,第14行代码正确
第14、15两行代码都正确
第6行代码可修改为 objCounter += 1
有关下面C++代码的说法,错误的是( )。

上列C++代码适用于构造各种二叉树
代码 struct BiNode 用于构造二叉树的节点
代码 BiTree(){root=Creat();} 用于构造二叉树
析构函数不可以省略