数据结构-2011年上半年

线性表(4/20/2011- 4/30/2011)

·         线性表的概念？

·         顺序表的概念？如何表示？插入/删除元素如何实现？平均移动多少元素？

·         链表的概念？如何表示？插入删除操作如何实现？

·         顺序表和链表分别用什么优缺点/各适用于什么情况？

·         链表的变形：循环链表，双向链表（插入删除操作的实现）。

·         什么是栈？顺序栈如何表示？Push和Pop操作如何实现？有哪些基本应用（进制数的转换、括号匹配、行编辑程序）？是如何应用的？

·         什么是队列？了解双端队列、输入受限队列、输出受限队列。

·         队列的链式表示方法，队列的基本操作的(带头结点)实现，初始化、入队操作，出队操作的实现，注意出队操作时最后一个节点出队时的处理。

·         循环队列的表示方法，基本操作的实现。循环队列实现时与普通的本书中之前提到的顺序表，顺序栈有何不同（或者说实现起来最需要注意的问题是什么）？

串

·         略。

数组(4/30/2011-5/3/2011)

·         多维数组如何表示？n维数组第i维的元素个数为Bi,则数组一共有多少个元素？当采用行主虚存储时，A[j1,j2,…,jn]与元素A[0,0,…,0]之间的关系？第i维的数值增加一跨越多少个元素(Ci)？Ci和Ci-1有何关系？

·         对称矩阵指的是什么样的矩阵（图）？对称矩阵的元素A[i,j]（1<=i<=n, 1<=j<=n）的位置如何计算？

·         什么是上三角矩阵？

·         什么是稀疏矩阵？了解稀疏矩阵的两种表示方式：三元组顺序表、行逻辑表。

·         什么是矩阵转置？矩阵相乘？掌握普通的矩阵相乘的算法的过程。简单了解行行逻辑连接表表示的矩阵的乘法运算。

·         理解三元组顺序表示的稀疏矩阵转置的两种方法的思想。

·         什么是十字链表？理解为什么十字链表表示的矩阵比顺序表示的矩阵更适合进行矩阵的加减运算。简单了解十字链表的表示方法及创建过程。

·         广义表的相关概念。原子、子表、表头、表尾（重要）、表的长度（递归表的长度是2）、深度。理解任何一个广义表的表头何以是原子也可以是列表，而表尾一定是列表。

·         理解为什么广义表通常用链式结构表示。知道广义表的两种表示结构，理解为什么。

·         理解为什么不适合用线性表表示多元多项式。理解教材中给出的求广义表深度的算法及复制广义表递归算法出发的不同。

 

 

树和二叉树（5/3/2011-5/4/2011）

·         树的相关概念。节点的度，树的度，数的深度。

·         二叉树的定义。由二叉树的定义推导出的二叉树的相关性质。层数i与第i层的节点的最大数目之间的关系，进而导出k层的二叉树的最大节点数。叶子节点与度数为2的节点之间的数目关系。

·         知道什么样的树是完全二叉树。完全二叉树的层数k与节点数目n的关系。

·         二叉树的先序遍历、中序遍历、后序遍历。

·         树的顺序表示（这里指的是按照满二叉树的方式进行编号）较链式表示有何缺点？

·         为什么要有线索二叉树？表示线索二叉树的结构该如何设计？中序线索二叉树中叶子节点的前驱和后继。后续线索二叉树的后继。

·         简单了解将一棵二叉树中序线索化的算法。

·         树的表示结构：双亲表示法有何优点？有何缺点？孩子表示法中节点的设计有哪两种方法？孩子表示法的结构（顺序存储所有节点）？

·         知道孩子兄弟表示法。能够把树转换成二叉树，树在使用二叉树表示时结构唯一吗？

·         树的两种遍历方式先根遍历（先序）、后根遍历（中序）。想想为什么树的遍历方式比二叉树的遍历方式少？理解两种遍历方式的过程，能够根据图给出正确的遍历顺序。

·         关系的自反、对称和传递。等价关系的定义。什么是等价类？

·         带权路径与树的带权路径长度。

·         重点掌握赫夫曼树。赫夫曼树是一颗带权的且路径最短的二叉树。赫夫曼树的构造过程。可以使用赫夫曼树减少判定次数，能够从数学角度对减少的次数进行量化的分析。

·         有n个叶子节点的赫夫曼树有2n-1个节点的推理：赫夫曼树没有度为1的节点，而叶子节点与度为2的节点的数目关系为n0=n2+1。节点总数N=n0+n2。

·         理解求赫夫曼编码的算法的数据结构为何那样设计？函数结构为何那样设计？或者说如何根据算法描述设计数据结构并设计算法？

·         能够将给出的权重数值转换为赫夫曼树。这里需要注意的问题是出现叶子节点与合并的树权重相等的情况。当对树进行组合时，总是吧最小的值放在左子树上，出现相等权重的情况，按从左到右的顺序放。

·         如何把求集合的幂集问题转换为树的构造问题？集合中元素的个数与树的层数有什么关系？

·         树的构造与4皇后问题的转换。

·         什么是树的计数问题？具有3个节点的二叉树有多少中不同的形态？

·         由中序遍历序列和前序遍历序列可以得到一颗唯一的二叉树。掌握这个过程。

·         判断一个出栈序列是否可以有一组给定的入栈序列得到。

·         二叉树的应用总结：减少判定次数，利用最优二叉树进行前缀编码，求集合的幂集。

树的应用：解决4皇后问题，迷宫问题，最优问题。

·         二叉搜索树的实验。

 图（5/11/2011-5/17/2011）

·         <v,w>,v为弧尾，w为弧头。

·         n个节点的无向完全图有n(n-1)/2条边。n个节点的有向完全图有n(n-1)条边。

·         在有向图中<v,w>的邻接关系描述为v邻接到w。

·         基本概念顶点的度，入度，出度，路径，路径长度，回路，简单路径，简单回路，

·         无向图中的连通，连通图，连通分量（极大连通子图）

·         有向图中的强连通，强连通分量。

·         一个连通图的生成树是一个极小连通子图，该树包含了n个节点以及n-1条边

·         图的邻接矩阵表示。邻接矩阵表示可以很容易的得知两个顶点之间是否有邻接关系，并且可以很容易的求得一个顶点的（出/入）度。

·         理解邻接表表示法。能画出示意图，理解这种表示方式现对于邻接矩阵表示的优点（在边的条数远小于点的个数时节省存储空间）。如何在这种结构上求图的中点的度（有向图和无向图）？

·         表示有向图的十字链表。

·         表示无向图的多重链表。解决邻接表中的一条边被存放两次的问题。

·         深度优先算法和广度优先算法的算法描述。

·         掌握Prim算法找最小生成树的过程。克鲁斯卡尔算法找最小生成树的过程。

·         知道什么是关节点（割点）。了解关节点在深度优先生成树中的两个特性：根节点有两个或两个以上的子树时，根节点为一个关节点；当某个节点v的子树中没有任何节点存在指向v的祖先的回路时，该节点为关节点。

·         了解重连通图的概念。航线、电路设计最好是重连通的。

·         连通图与关节点的关系。不要求掌握求关节点的算法，知道可以通过深度优先算法求得。

·         什么是有向无环图？知道可以用有向无环图来表示一个表达式，这表示方法在有重复项时，可以比二叉树表示方式节省空间。

·         无向图是否存在环路可以通过检查深度优先遍历的过程中是否存在回边来判断。

·         在对有向图进行深度优先遍历的过程中，如果在对v的子树的SDF算法执行完毕之前出现了顶点u到顶点v的回边，则有向图中必定存在环。

·         偏序关系是自反的，反对衬的，传递的。全序关系要求集合中所有的关系都是可比的。拓扑排序是由偏序关系得到的一个全序关系。

·         拓扑算法的算法描述。算法实现方案一：用入度的减少来表示将边从原图中移除，当入度为0时，表示该点可以输出，使用Stack记录度为0的点，出栈则表示点从图中移除放入的结果集中；方案二：深度优先算法访问顺序倒序输出各个节点。

·         拓扑序列AOV指出了活动之间的先后依赖关系。

·         AOE(Activity of Edge)活动网。顶点表示事件，边表示活动，边的权值表示活动的持续时间。只有唯一的起点和一个唯一的终点。关键路径是指从起点到重点最长的路径。活动网上的点i都会有一个最早开始时间e(i)以及一个最晚开始时间l(i),e(i)=l(i)的点就是关键活动了。

·         带权有向图的最短路径。v到j的最短路径要么是<v,j>,要么是经过某个顶点k的路径v->k->j

查找（5/18/2011-5/25/2011）

·         静态查找表指只进行查询的表。动态查找表指在查询过程中需要进行插入和删除操作的表。

·         理解查找方法的选择依赖于数据的组织结构。

·         顺序查找方式查找长度的计算（只考虑查找成功的情况）。

·         掌握折半查找算法（非递归实现）。知道什么是判定树，根据判定树的性质来计算折半查找的平均查找长度（假设每个元素的查找概率相等）

·         知道态查找最优树是用来解决不等概率查找最优问题的。

·         理解索引表的构建思想。将数组分块，保证其块间有序，为这些块建立一张索引表。索引表的每个项纪录了两个值，块内元素的最大值和块的起始位置。

·         二叉搜索树删除节点时的三种不同情况，当删除一个有两棵子树的节点时的两种处理方式的思想（重组、替代）

·         了解什么是最优二叉树、平衡因子。

·         什么是B-树？（定义）B樹索引是数据库中存取和查找文件(称为记录或键值)的一种方法。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。

·         B+ 树通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树不需要象其他自平衡二叉查找树那样经常的重新平衡。

·         了解Trie。

·         哈希表的思想：希望有一种办法能够通过计算来减少比较的次数。哈希函数的要求：产生的key值在规定的范围内，尽可能的分散。哈希表实现还要考虑冲突的处理问题。

·         哈希表的冲突处理方法的比较：

?  开放地址（二次再散列）。增加了“二次聚集”问题。

?  再hash。增加了计算时间。

?  链地址法。

?  公共溢出区。

排序算法（5/26/2011-5/29/2011）

·         排序算法稳定性的概念。内部排序和外部排序的概念。

·         掌握最基本的插入排序算法（内层的插入比较过程实际上有两种方式，一种是从左到右，一种是从右至左，注意这里的抉择过程，不要Take it for granted）。理解折半插入排序的思想。理解二路插入排序的插入过程，二路插入排序可以减少记录的移动次数（在关键字不是已排序的情况下）。可以使用静态链表存储结构来避免移动元素，但是这仅仅是把元素的移动工作变成了指针变量的修改。希尔排序算法减少时间复杂度算法的思想：跳跃式移动元素。

·         掌握快速排序算法的实现思想并能够自己写出快速排序的代码。

·         堆排序。堆的性质：第n/2个元素为最后一个非叶子节点。堆排序算法的实现。

·         通过合并排序算法理解分治法算法设计，并与快速排序进行比较。掌握其代码实现思路。多选择：合并数组时有两种思路，一种是以原数组为依据进行迭代，另一种是以目标数组为依据进行迭代。

·         多关键字排序的两种思路（MSD、LSD）。比较两种排序算法的的区别。理解为什么基数排序要求是稳定的。

·         链式基数排序的算法过程。

·         利用二叉树分析得出结论：基于比较的排序的最低时间下界为log2(n!)。