数据结构与考研开场白.docVIP

2002 2001 2000 1999 线性 结构 栈的进出序列的总数 next值（5） 线性表的归并（12） 两个栈模拟队列（12） 树型 结构 树和二叉树的定义 按层次＋后序的树的遍历 哈夫曼编码和求解 二叉树性质：最少层数，叶子总数 二叉排序树的平均查找长度 二叉排序树的第I个结点和结点的插入 建树：层号＋前序 遍历序列 二叉树〈=〉森林 树的基本概念 在二叉树上求结点的祖先 三次树前后序确定树（5） 中序线索树上求后序后继（20） 判断二叉树相似（8） 按层次顺序遍历二叉树（12） 先序+中序建立二叉树（12） 图状 结构 关键路径 （逆）邻接表的生成 图的深度优先，广度优先，最小生成树（12） 集合： 查找 排序 外排 快速排序的时间复杂性及推导 顺序查找的平均查找长度 二分查找法的最坏情况下的查找长度 最小化堆的最大元 建堆：n－1个元素已是堆，建立n个元素的堆 (时间：O(log log n)) 最佳归并树的虚段 平衡二叉树 二叉排序树 ASL分析 Hash表平均查找长度公式（5） B-树的深度定义（5） 各类排序复杂度（8） 排序时间复杂度证明（8) 有序表查找长度证明（8） 置换-选择排序（8） 删除二叉树结点（12） Hash表的删除（12） 二叉排序树，平衡二叉树（7） 内部排序第一趟结果（9） 堆定义、堆排序与其它排序的比较（8） 置换-选择排序（4） 算法设计与分析 递归方程求解 递归方程求解 程序题 所占比例 4/10 35’ 2/10 35’ 3/12 40’ 5/10 60’ 2003 2004 2005 2006 ? 线性 结构 Nextval的求法 KMP算法时间复杂度 出栈顺序 链表查找 树型 结构 树和二叉树的定义 存储表示 线索二叉树 二叉树的遍历 二叉排序树和线索二叉树的创建 线索二叉树 非递归后序遍历 二叉树结点个数/高度 完全二叉树的性质 线索二叉树 图状 结构 图的存储方式优劣 图的顶点和边的查找、删除等操作。 AOE网络求最迟发生时间 最小生成树算法 集合： 查找 排序 外排 求最大和次最大值 外部排序比较次数 K 值的选取和内存的关系。 堆排序时间复杂度证明 二叉排序树和平衡二叉树的查找分析 置换-选择排序 二叉排序树的查找 折半查找 各类排序复杂度 算法设计与分析 程序题 所占比例 5/12 80/150 45/70 50/70 总结所考知识点分布： 线性结构： KMP算法中next数组的值 线性表的归并 两个栈模拟队列 栈的输出序列 栈、队列基本操作的时间复杂度 树： 二叉树和树的定义 二叉树的前序、中序、后序、层次遍历 哪些遍历序列可唯一决定二叉树 二叉树的结点查找 二叉树的相似判断 求二叉树结点的祖先结点 中序线索二叉树及中序遍历线索二叉树 在中序线索二叉树上求其他序的前驱、后继 Huffman树的构造 森林（树）与二叉树的转换 图： 图的深度优先、广度优先遍历 生成树 最小生成树的Kruskal算法 （逆）邻接表的生成 拓扑排序 关键路径 最短路径Dijkstra算法、Floyd算法 查找： 有序表ASL证明 索引排序表的查找 二叉排序树的插入、删除、ASL分析 平衡二叉树的插入、删除、 B-树的定义、深度、插入 Hash表的构造、查找、删除及ASL分析 排序： 各类排序的时间空间复杂度分析 稳定性分析 基于比较的排序在最坏情况下能达到的最好的时间复杂度证明 各类排序的第一趟排序结果 堆的定义 置换选择排序的初始归并段构造 初始归并段平均长度的证明 最佳归并树的虚段 算法设计与分析： 递归方程求解 例题分析 例：假设有两个按元素值非递减有序排列的线性表A和B，均以单链表作存储结构，请编写算法将表A和表B归并成一个按元素非递减有序（允许值相同）排列的线性表C，并要求利用原表（即表A和表B）的结点空间存放表C。 void MergeList_L(LinkList La, LinkList Lb,LinkList Lc) //已知单链线性表La和Lb的元素按值非递减排列。 //归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。 { pa=La-next;pb=Lb-next; Lc=pc=La; //用La的头结点作为Lc的头结点 while(papb) { if(pa-data=pb-data) { pc-next=pa; pc=pa;pa=pa-next;} else {pc-next=pb;pc=pb;pb=pb-next;} } pc-next=pa?pa:pb; //