编号为i的结点有右兄弟的条件是什么其右兄弟结点的编号是多少

问答题

已知一棵二叉树的前序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ，试画出这棵二叉树并写出它的后序遍历序列。

答案：当前序序列为ABECDFGHU，中序序列为EBCDAFHIGJ时，逐步形成二叉树的过程如下图所示。

问答题

一棵高度为h的满m叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：各层的结点个数是多少

答案：可以参照二叉树的性质，将其扩展到m叉树。
因为第1层有1个结点，第2层有m个结点，第3层有m²

问答题

设二叉树根结点在第1层，树的深度d为距离根最远的叶结点所在层次，试给出：深度为d的完全二叉树的不同二叉树棵数。

答案：深度为d的完全二叉树的1到d-1层都是满的，第d层有多少结点就有多少种选择。第d层最多有2d-1个结点，所以不同二叉树的...

问答题

针对二叉树BiTree，利用二叉树遍历的思想编写解决下列问题的递归算法。int size(BiTNode ^* t)； //返回以 ^* t为根的二叉树中所有结点个数

答案：返回以^*t为根的二叉树中所有结点个数：
int size(BinTreeNode

问答题

给定一个关键字集合{25，18，34，9，14，27，42，51，38}，假定查找各关键字的概率相同，请画出其最佳二叉排序树。

答案：当各关键字的查找概率相等时，最佳二叉排序树应是高度最小的二叉排序树。构造过程分两步走：首先对各关键字值从小到大排序，然后...

问答题

已知一棵树的先根次序遍历的结构与其对应二叉树表示(子女-兄弟链表表示)的前序遍历结果相同，树的后根次序遍历结果与其对应二叉树表示的中序遍历结果相同。请回答以下问题：利用树的先根遍历结果和后根遍历结果能否唯一确定一棵树举例说明。

答案：因为给出二叉树的前序遍历序列和中序遍历序列能够唯一地确定这棵二叉树，因此，根据题目给出的条件，利用树的先根次序遍历结果和...

问答题

设二叉树根结点在第1层，树的深度d为距离根最远的叶结点所在层次，试给出：深度为d的满二叉树的不同二叉树棵数。

答案：深度为d的不同的满二叉树只有1棵。

问答题

针对二叉树BiTree，利用二叉树遍历的思想编写解决下列问题的递归算法。int leaves(BiTNode ^* t)； //返回以 ^* t为根的二叉树的叶结点个数

答案：返回以^*t为根的二叉树中叶结点个数：
int leayes(BiTNode^*<...

问答题

一棵高度为h的满m叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：编号为i的结点的父结点(若存在)的编号是多少

答案：在m叉树的情形，结点i的第1个子女编号为j=(i-1)×m+2。反过来，结点i的双亲的编号是
，根结点没有双亲...

问答题

画出一个二叉树，使得它既满足大根堆的要求又满足二叉排序树的要求。

答案：大根堆要求根结点的关键字值既大于或等于左子女的关键字值又大于或等于右子女的关键字值，二叉排序树要求根结点的关键字值大于左...

问答题

已知一棵树的先根次序遍历的结构与其对应二叉树表示(子女-兄弟链表表示)的前序遍历结果相同，树的后根次序遍历结果与其对应二叉树表示的中序遍历结果相同。请回答以下问题：n个结点的不同形状的树有多少种

答案：确定n个结点的不同树的数目可以归结到确定其对应二叉树的计数。因为树转化为二叉树后，根结点没有右子女，该二叉树的计数归结到...

问答题

针对二叉树BiTree，利用二叉树遍历的思想编写解决下列问题的递归算法。int height(BiTNode ^* t)； //返回以 ^* t为根的二叉树的高度

答案：返回以^*t为根的二叉树的高度：
int height(BiTNode^*

问答题

一棵高度为h的满m叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：编号为i的结点的第k个子女结点(若存在)的编号是多少

答案：因为结点i的第1个子女编号为(i-1)×m+2，若设该结点子女的序号为k=1，2，…，m，则第k个子女结点的编号为(i-...

问答题

下面是一个二叉树的前序遍历的递归算法。
void PreOrder(BiTNode ^* t){
if(t!=NULL){ //递归结束条件
cout＜＜t-＞data; //访问(输出)根结点
Preorder(t-＞lchild); //前序遍历根的左子树
Preorder(t-＞rchild); //前序遍历根的右子树
}
}改写PreOrder算法，消去第二个递归调用PreOrder(t-＞rchild)；

答案：消去第二个递归语句时，视第一个递归语句为一般语句，按尾递归处理。
void preOrder(BiTNode<...

问答题

针对二叉树BiTree，利用二叉树遍历的思想编写解决下列问题的递归算法。int level(BiTNode ^* t，BiTNode ^* p)；//返回二叉树指定结点 ^* p在以 ^* t为根的子树中的层次

答案：返回以^*t为根的二叉树中指定结点^*p所在层次：
int level...

问答题

一棵高度为h的满m叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：编号为i的结点有右兄弟的条件是什么其右兄弟结点的编号是多少

答案：当结点i不是其双亲的第m个子女时才有右兄弟。若设其双亲编号为j，可得j=
，结点j的第m个子女的编号为：(j-...

问答题

下面是一个二叉树的前序遍历的递归算法。
void PreOrder(BiTNode ^* t){
if(t!=NULL){ //递归结束条件
cout＜＜t-＞data; //访问(输出)根结点
Preorder(t-＞lchild); //前序遍历根的左子树
Preorder(t-＞rchild); //前序遍历根的右子树
}
}利用栈改写PreOrder算法，消去两个递归调用。

答案：定义一个栈，在访问某一个结点时保存其右、左子女结点的地址。下一步将先从栈中退出右子女结点，对其进行遍历，然后从栈中退出左...

问答题

请回答下列关于图的一些问题：有n个顶点的有向强连通图最多有多少条边最少有多少条边

答案：有n个顶点的有向强连通图最多有n(n-1)条边，最少有n条边。

问答题

针对二叉树BiTree，利用二叉树遍历的思想编写解决下列问题的递归算法。void reflect(BiTNode ^* t)； //交换以 ^* t为根的二叉树中每个结点的两个子女

答案：交换以^*t为根的二叉树中每个结点的两个子女：
void reflect(BiTNode<...

问答题

一棵高度为h的满m叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：若结点个数为n，则高度h是n的什么函数关系

答案：若结点个数为n，则有

反之，有h=logm(n×(m-1)+1)。

问答题

请回答下列关于图的一些问题：表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素是否为稀疏矩阵

答案：有1000个顶点、1000条边的有向图的邻接矩阵有1000000个矩阵元素，其中只有1000个非零元素，是一个稀疏矩阵。...

问答题

针对二叉树BiTree，利用二叉树遍历的思想编写解决下列问题的递归算法。void defoliate(BiTNode ^* &t)； //从以 ^* t为根的二叉树中删去所有叶结点

答案：从以^*t为根的二叉树中删去所有叶结点：
void defoliate(BiTNode

问答题

请回答下列关于图的一些问题：对于一个有向图，不用拓扑排序，如何判断图中是否存在环

答案：对一个有向图，还可以用以下方法判断图中是否存在环：①如果图中所有顶点的出度至少为1，入度也至少为1，则图中存在环。这个条...

问答题

在有关图的算法中常用到两个图的操作：
int getFirstNeighbor (Graph G,int v); //取顶点v的第一个邻接顶点
int getNextNeighbor(Graph G,int v,int w); //取邻接顶点w的下一邻接顶点
试分别给出在邻接矩阵和邻接表为存储结构的情形下它们的实现。

答案： (1)用邻接矩阵做存储结构的场合。
为了找到顶点v的第一个临界顶点，顺序地检测邻接矩阵的第v行，最先遇到的非零...

你可能感兴趣的试题