下载文档原格式
一、数据结构得章节结构及重点构成数据结构学科得章节划分基本上为:概论,线性表,栈与队列,串，多维数组与广义表，树与二叉树，图，查找，内排,外排,文件,动态存储分配.对于绝大多数得学校而言,“外排,文件,动态存储分配”三章基本上就是不考得,在大多数高校得计算机本科教学过程中,这三章也就是基本上不作讲授得。
所以，大家在这三章上可以不必花费过多得精力,只要知道基本得概念即可。
但就是，对于报考名校特别就是该校又有在试卷中对这三章进行过考核得历史，那么这部分朋友就要留意这三章了。
按照以上我们给出得章节以及对后三章得介绍，数据结构得章节比重大致为：概论：内容很少,概念简单,分数大多只有几分，有得学校甚至不考.线性表:基础章节，必考内容之一。
考题多数为基本概念题，名校考题中，鲜有大型算法设计题.如果有，也就是与其它章节内容相结合.栈与队列：基础章节,容易出基本概念题，必考内容之一。
而相联系进行考查。
串：基础章节,概念较为简单.专门针对于此章得大型算法设计题很少，较常见得就是根据KMＰ进行算法分析。
多维数组及广义表:基础章节，基于数组得算法题也就是常见得,分数比例波动较大，就是出题得“可选单元”或“侯补单元”.一般如果要出题,多数不会作为大题出.数组常与“查找,排序”等章节结合来作为大题考查。
树与二叉树:重点难点章节，各校必考章节。
各校在此章出题得不同之处在于,就是否在本章中出一到两道大得算法设计题。
通过对多所学校得试卷分析,绝大多数学校在本章都曾有过出大型算法设计题得历史。
图:重点难点章节，名校尤爱考。
如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题得题型设计。
查找:重点难点章节,概念较多，联系较为紧密,容易混淆。
出题时可以作为分析型题目给出,在基本概念型题目中也较为常见。
算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。
排序:与查找一章类似,本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。
2010年自学考试《数据结构》各章复习要点总结(4)龙耒为你整理：第七章图图的逻辑结构特征就是其结点(顶点)的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。
图GraphG=(V，E)，V是顶点的有穷非空集合，E是顶点偶对的有穷集。
有向图Digraph：每条边有方向;无向图Undigraph：每条边没有方向;有向完全图：具有n*(n-1)条边的有向图;无向完全图：具有n*(n-1)/2条边的无向图;有根图：有一个顶点有路径到达其它顶点的有向图;简单路径：是经过顶点不同的路径;简单回路：是开始和终端重合的简单路径;网络：是带权的图。
图的存储结构：·邻接矩阵表示法：用一个n阶方阵来表示图的结构是唯一的，适合稠密图。
·无向图：邻接矩阵是对称的。
·有向图：行是出度，列是入度。
建立邻接矩阵算法的时间是O(n+n^2+e)，其时间复杂度为O(n^2)·邻接表表示法：用顶点表和邻接表构成不是唯一的，适合稀疏图。
·顶点表结构 vertex | firstedge，指针域存放邻接表头指针。
·邻接表：用头指针确定。
·无向图称边表;·有向图又分出边表和逆邻接表;·邻接表结点结构为 adjvex | next，时间复杂度为O(n+e)，空间复杂度为O(n+e)。
图的遍历：·深度优先遍历：借助于邻接矩阵的列。
使用栈保存已访问结点。
·广度优先遍历：借助于邻接矩阵的行。
使用队列保存已访问结点。
生成树的定义：若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图称作该图的生成树。
最小生成树：图的生成树不唯一，从不同的顶点出发可得到不同的生成树，把权值最小的生成树称为最小生成树(MST)。
构造最小生成树的算法：·Prim算法的时间复杂度为O(n^2)与边数无关适于稠密图。
2010年自考《数据结构》复习要点总结第一章第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，可以由若干个数据项组成。
数据项是具有独立含义的最小标识单位。
数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。
·线性结构：一对一关系。
·线性结构：多对多关系。
·存储结构：是逻辑结构用计算机语言的实现。
·顺序存储结构：如数组。
·链式存储结构：如链表。
·稠密索引：每个结点都有索引项。
·稀疏索引：每组结点都有索引项。
·散列存储结构：如散列表。
·对数据的操作：定义在逻辑结构上，每种逻辑结构都有一个运算集合。
·常用的有：检索、插入、删除、更新、排序。
·数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。
·原子类型：由语言提供。
·结构类型：由用户借助于描述机制定义，是导出类型。
抽象数据类型ADT：·是抽象数据的组织和与之的操作。
相当于在概念层上描述问题。
·优点是将数据和操作封装在一起实现了信息隐藏。
程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。
算法取决于数据结构。
算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。
评价算法的好坏的因素：·算法是正确的;·执行算法的时间;·执行算法的存储空间(主要是辅助存储空间);·算法易于理解、编码、调试。
时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。
渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。
评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。
算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。
时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。
：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。
：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称。
数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的基本单位。
数据项：是数据元素中有独立含义的、不可分割的最小标识单位。
数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作。
数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合定义在此集合上的若干关系来表示，数据结构可以分为三种：线性结构、树结构和图。
：数据元素及其关系在计算机中的存储表示称为数据的存储结构，也称为物理结构。
数据的存储结构基本形式有两种：顺序存储结构和链式存储结构。
：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。
算法规则需满足以下五个特性：输入——算法有零个或多个输入数据。
输出——算法有一个或多个输出数据，与输入数据有某种特定关系。
有穷性——算法必须在执行又穷步之后结束。
确定性——算法的每个步骤必须含义明确，无二义性。
可行性——算法的每步操作必须是基本的，它们的原则上都能够精确地进行，用笔和纸做有穷次就可以完成。
有穷性和可行性是算法最重要的两个特征。
：算法与数据结构：算法建立数据结构之上，对数据结构的操作需用算法来描述。
算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。
：算法的设计应满足五个目标：正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标。
健壮性：即使输入数据不合适，算法也能做出适当的处理，不会导致不可控结高时间效率：算法的执行时间越短，时间效率越高。
果。
高空间效率：算法执行时占用的存储空间越少，空间效率越高。
可读性：算法的可读性有利于人们对算法的理解。
：度量算法的时间效率，时间复杂度，（课本39页）。
：递归定义：即用一个概念本身直接或间接地定义它自己。
第1章绪论1.1 数据结构的基本概念数据元是数据的基本单位，一个数据元素可由若干个数据项完成，数据项是构成数据元素的不可分割的最小单位。
例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。
数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
数据类型是一个值的集合和定义在此集合上一组操作的总称。
•原子类型：其值不可再分的数据类型•结构类型：其值可以再分解为若干成分（分量）的数据类型•抽象数据类型：抽象数据组织和与之相关的操作抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。
抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。
通常用（数据对象、数据关系、基本操作集）这样的三元组来表示。
#关键词：数据，数据元素，数据对象，数据类型，数据结构数据结构的三要素：1.逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，独立于计算机。
分为线性结构和非线性结构，线性表、栈、队列属于线性结构，树、图、集合属于非线性结构。
2.存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构，包括数据元素的表示和关系的表示，依赖于计算机语言，分为顺序存储（随机存取）、链式存储（无碎片）、索引存储（检索速度快）、散列存储（检索、增加、删除快）。
3.数据的运算：包括运算的定义和实现。
运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。
1.2 算法和算法评价算法是对特定问题求解步骤的一种描述，有五个特性：有穷性、确定性、可行性、输入、输出。
一个算法有零个或多个的输入，有一个或多个的输出。
时间复杂度是指该语句在算法中被重复执行的次数，不仅依赖于问题的规模n，也取决于待输入数据的性质。
一般指最坏情况下的时间复杂度。
空间复杂度定义为该算法所耗费的存储空间。
算法原地工作是指算法所需辅助空间是常量，即O(1)。
第2章线性表2.1 线性表的定义和基本操作线性表是具有相同数据类型的n个数据元素的有限序列。
2010年自学考试《数据结构》各章复习要点总结(5)龙耒为你整理：第九章查找查找的同时对表做修改操作(如插入或删除)则相应的表称之为动态查找表，否则称之为静态查找表。
衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数(即平均查找长度ASL)。
线性表查找的方法：·顺序查找：逐个查找，ASL=(n+1)/2;·二分查找：取中点int(n/2)比较，若小就比左区间，大就比右区间。
用二叉判定树表示。
ASL=(∑(每层结点数*层数))/N;·分块查找：要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中的最大关键字及其位置建立有序索引表。
二叉排序树(BST)定义是二叉排序树是空树或者满足如下性质的二叉树：·若它的左子树非空，则左子树上所有结点的值均小于根结点的值;·若它的右子树非空，则右子树上所有结点的值均大于根结点的值;·左、右子树本身又是一棵二叉排序树。
二叉排序树的插入、建立、删除的算法平均时间性能是O(nlog2n)。
二叉排序树的删除操作可分三种情况进行处理：·*P是叶子，则直接删除*P，即将*P的双亲*parent中指向*P的指针域置空即可。
·*P只有一个孩子*child，此时只需将*child和*p的双亲直接连接就可删去*p。
·*p有两个孩子，则先将*p结点的中序后继结点的数据到*p，删除中序后继结点。
关于B-树(多路平衡查找树)。
它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。
建立的方式是从下向上拱起。
散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。
散列函数的选择有两条标准：简单和均匀。
常见的散列函数构的造方法：·平方取中法：hash=int((x^2)0)·除余法：表长为m，hash=x%m·相乘取整法：hash=int(m*(x*A-int(x*A));A=0.618·随机数法：hash=random(x)。
数据结构知识点概括第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，可以由若干个数据项组成。
数据项是具有独立含义的最小标识单位。
数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。
·线性结构：一对一关系。
·线性结构：多对多关系。
·存储结构：是逻辑结构用计算机语言的实现。
·顺序存储结构：如数组。
·链式存储结构：如链表。
·索引存储结构：·稠密索引：每个结点都有索引项。
·稀疏索引：每组结点都有索引项。
·散列存储结构：如散列表。
·数据运算。
·对数据的操作。
定义在逻辑结构上，每种逻辑结构都有一个运算集合。
·常用的有：检索、插入、删除、更新、排序。
数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。
·结构类型：由用户借助于描述机制定义，是导出类型。
抽象数据类型ADT：·是抽象数据的组织和与之的操作。
相当于在概念层上描述问题。
·优点是将数据和操作封装在一起实现了信息隐藏。
程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。
算法取决于数据结构。
算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。
评价算法的好坏的因素：·算法是正确的；·执行算法的时间；·执行算法的存储空间（主要是辅助存储空间）；·算法易于理解、编码、调试。
时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。
渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。
评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。
算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。
时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。
