数据结构与算法-等级考试试题(二级考试 2006年线索二叉树)

单项选择（2006年二级考试）

线索二叉树是一种【】结构。

A、物理

B、逻辑

C、存储

D、线性

答案解析

A

讨论

二叉树

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

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

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

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

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

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

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

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

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

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

线索二叉树

二叉树在线索化后，仍不能有效求解的问题是【】。

算法的空间复杂度是指【】

下列描述中，正确的是【】

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

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

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

对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为__________。

按照“后进先出”原则组织数据的数据结构是【】

支持子程序调用的数据结构是【】。

如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是【】。

树和二叉树

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

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

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

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

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

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

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

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

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

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