数据结构与算法-等级考试试题(程序员软考 2016年春树的概念与性质)

单项选择（2016年春程序员软考）

某二又树的先序遍历序列为 ABCDFGE，中序遍历序列为 BAFDGCE。以下关于该二又树的叙述中，正确的是【】。

A、该二叉树的高度(层次数)为4

B、该二叉树中结点D是叶子结点

C、该二叉树是满二叉树(即每层的结点数达到最大值)

D、该二叉树有5个叶子结点

答案解析

A根据一个二叉树的先序遍历序列和中序遍历序列可以重构该二叉树。先序遍历序列可以确定二叉树(包括子二叉树)的根结点，然后在中序遍历序列中找到根结点，从而可以分出左子树和右子树中各自的结点。题中的二叉树的...

查看完整答案

讨论

数据结构与算法

对二叉树中的结点如下编号：树根结点编号为1，根的左孩子结点编号为2、右孩子结点编号为3，以此类推，对于编号为i的结点，其左孩子编号为2i、右孩子编号为2i+1。例如，下图所示二又树中有6个结点，结点a、b、c、d、e、f的编号分别为1、2、3、5、7、11。那么，当结点数为n(n>0)的【】时，其最后一个结点编号为2n-1。

队列采用如下图所示的循环单链表表示，左图表示队列为空，右图为e1、e2、e3依次入队列后的状态，其中，rear指针指向队尾元素所在结点，size为队列长度。以下叙述中，正确的是【】。

设有初始为空的栈S，对于入栈序列a、b、c、d，经由一个合法的进栈和出栈操作序列后(每个元素进栈、出栈各1次)，以c作为第一个出栈的元素时，不能得到的序列为【】。

对于长度为n的线性表(即n个元素构成的序列)，若采用顺序存储结构(数组存储)，则在等概率下，删除一个元素平均需要移动的元素数为【】。

递归函数执行时，其调用和返回控制是利用【】来进行的。

与算术表达式3-(2+7)/4对应的二又树为【】。

在待排序的一组关键码序列k1，k2，…，kn中，若ki和kj相同，且在排序前ki领先于kj，那么排序后，如果ki和kj的相对次序保持不变，ki仍领先于kj，则称此类排序为稳定的。若在排序后的序列中有可能出现kj领先于ki的情形，则称此类排序为不稳定的。【】是稳定的排序方法。

若待排序记录按关键字基本有序，则宜采用的排序方法是【】。

【】不符合二叉排序树的定义。

某有向图G及其邻接矩阵如下所示。以下关于图的邻接矩阵存储的叙述中，错误的是【】。

树的概念与性质

如果只考虑有序树的情形，那么具有7个结点的不同形态的树共有【】

已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，...，Nm个度为m的结点。试问该树中有多少个叶子结点？

树是结点的集合，它的根结点数目是【】

对下图所示的二叉树进行中序遍历(左子树、根结点、右子树)的结果是【】。

对于一般的树结构，可以采用孩子-兄弟表示法，即每个结点设置两个指针域，一个指针(左指针)指示当前结点的第一个孩子结点，另一个指针(右指针)指示当前结点的下一个兄弟结点。某树的孩子-兄弟表示如下图所示。以下关于结点 D 与 E 的关系的叙述中，正确的是【】。

算术表达式a*(b-c)+d的后缀式是【】(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

在数据结构中，【】是与存储结构无关的术语。

对于顺序栈和链栈，【】不是两者共有的运算特征。

按照逻辑关系的不同可将数据结构分为【】。

若栈采用链式存储且仅设头指针，则【】时入栈和出栈操作最方便。

树和二叉树

证明，由一棵二叉树的前序序列和中序序列可唯一地确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为DGBEAFHC，试画出该二叉树。

已知一棵二叉树的前序遍历结果是ADCEBFIHGJ，中序遍历结果是CDEBAFHGIJ，试画出这棵二叉树。

用一维数组存放的一棵完全二叉树如下：A、B、C、D、E、F、G、H、I、J、K、L写出后序遍历该二叉树时访问结点的顺序。

一棵二叉树按中序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序能否唯一确定这棵二叉树的结构？为什么？若已知一棵二叉树按先序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序，能否唯一确定这棵二叉树的结构？为什么？

对于二叉树T 的两个结点 n1 和 n2 ，我们应该选择树 T 结点的前序、中序和后序中哪两个序列来判断结点 n1 必定是结点 n2的祖先，并给出判断的方法。不需证明判断方法的正确性。

证明一棵二叉树无论进行先序、中序、后序遍历，其叶子结点的相对次序不发生改变。

对二叉排序树进行【】遍历，可以得到该二叉树所有结点构成的排序序列。

若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用【】遍历方法最合适。

已知一棵二叉树，如果先序遍历的顺序是ADCEFGHB，中序遍历的顺序是CDFEGHAB，则后序遍历的结果为【】。

具有n个叶子的二叉树，每个叶子的权值为wi（1≤i≤n），其中带权路径长度最小的二叉树称为__________。