一、简答题 1、 链表：链表就是一串存储数据的链式结构。链式的优点在于，每个数据之间都是相关联的。 2、 线性结构： 线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。 3、 树与二叉树 二叉树是每个结点最多有两个子树的有序树； 树是由 n（n>=1）个有限节点组成一个具有层次关系的集合。 树和二叉树的 2 个主要差别： 1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为 2； 2. 树的结点无左、右之分，而二叉树的结点有左、右之分。 4、 堆 堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质： 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树。 5、 二叉排序树 二叉排序数的（递归）定义：1、若左子树非空，则左子树所有节点的值均小于它的根节点；2、若右子树非空，则右子树所有节点的值均大于于它的根节点；3、左右子树也分别为二叉排序树。 二、应用题 1、 树与二叉树 ① 前中后序遍历序列 一、已知前序、中序遍历，求后序遍历 例：前序遍历: GDAFEMHZ 中序遍历: ADEFGHMZ 画树求法： 第一步，根据前序遍历的特点，我们知道根结点为G 第二步，观察中序遍历ADEFGHMZ。其中root 节点G 左侧的ADEF 必然是root 的左子树，G 右侧的HMZ 必然是 root 的右子树。 第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root 的leftchild。在前序遍历中，大树的root 的leftchild 位于 root 之后，所以左子树的根节点为D。 第四步，同样的道理，root 的右子树节点HMZ 中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把 root 和 root 的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。 ② 树与二叉树的转换 树转换为二叉树： 二叉树转换为树： ③ 二叉树线索化 注意： 图中的实线表示指针，虚线表示线索。 结点C 的左线索为空，表示C 是中序序列的开始结点，无前趋； 结点E 的右线索为空，表示E 是中序序列的终端结点，无后继。 线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1。 2、 图 ① 邻接表 一、邻接表 邻接表是图的一种链式存储结构。 邻接表中，对图中每个顶点建立一个单链表，第 i个单链表中的结点表示依附于顶点Vi的边（对有向图是以...
