数据结构与算法-等级考试试题(程序员软考 2017年春二叉树)

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

某二叉树的先序遍历(根、左、右)序列为 EFHIGJK、中序遍历(左、根、右)序列为HFIEJKG，则该二叉树根结点的左孩子结点和右孩子结点分别是【】

A、I、K

B、F、I

C、F、G

D、I、G

答案解析

C对于一个非空的二叉树，其先序遍历序列、中序遍历序列和后序遍历序列都是唯一确定的。先序遍历是首先访问根结点，其次是先序遍历左子树，最后再先序遍历右子树，因此先序序列第一个元素是根结点。中序遍历是首先中序遍历左子树，然后访问根结点，最后中序遍历右子树，因此在已知根结点的情况下，可将左...

查看完整答案

讨论

数据结构与算法

采用【】算法对序列{18,12,10,11,23,2,7}进行一趟递增排序后，其元素的排列变为{12,10,11,18,2,7,23}。

表达式可采用后缀形式表示。例如，“a+b”的后缀式为“ab+”。那么，表达式“a*(b-c)+d”的后缀表示为【】

设某无向图的顶点个数为n，则该图最多有______条边;若将该图用邻接矩阵存储，则矩阵的行数和列数分别为______。

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度不超过255 字节。假设目前有一千万个查询记录(重复度比较高，其实互异的查询串不超过三百万个；显然，一个查询串的重复度越高，说明查询它的用户越多，也就是越热门)。现要统计最热门的 10 个查询串，且要求使用的内存不能超过 1GB。以下各方法中，可行且效率最高的方法是【】。

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

若要求对大小为n的数组进行排序的时间复杂度为 O(nlog2n)，且是稳定的(即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置不变)，则可选择的排序方法是【】

设元素a、b、c、d依次进入一个初始为空的栈，则不可能通过合法的栈操作序列得到【】。

若某线性表长度为n且采用顺序存储方式，则运算速度最快的操作是【】。

线性表采用单循环链表存储的主要特点是【】

在单 CPU 计算机系统中，完成相同功能的递归程序比非递归程序【】

二叉树

某二叉树中度为2的结点有18个，则该二叉树中有__________个叶子结点。

在深度为7的满二叉树中，叶子结点的个数为【】

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为【】

一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 __________。

深度为5的满二叉树有__________个叶子结点。

某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）【】

一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有结点个数为【】。

某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是【】。

对下列二叉树进行后序遍历的结果是【】

对于前序遍历和中序遍历结果相同的二叉树为__________；对于前序遍历和后序遍历结果相同的二叉树是为__________。一般二叉树只有根结点的二叉树要结点无左孩子的二叉树根结点无右孩子的二叉树所有结点只有左子树的二叉树所有结点只有右子树的二叉树

树和二叉树

有n个数顺序（依次）进栈，则出栈顺序有Cn种。Cn=×

由二叉树的前序和后序遍历序列【】唯一地确定这棵二叉树。

具有7个结点的互不相识的二叉树共有__________棵。

一个深度为 h 的满 m 叉树有如下性质：第 h 层上的结点都是叶结点，其各层上每个结点有 m 棵非空子树。问：（1）第 k 层最多有多少个结点？（k≤h )（2）整棵树最多有多少个结点？（3）若按层次从上到下，每层从左到右的顺序从1开始对全部结点编号，编号为 i 的结汽的双亲结点的编号是什么？编号为 i 的结点的第 j 个孩子结点（若存在）的编号是什么？

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

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

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

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

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

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