下载文档原格式
一、数据结构得章节结构及重点构成数据结构学科得章节划分基本上为:概论,线性表,栈与队列,串，多维数组与广义表，树与二叉树，图，查找，内排,外排,文件,动态存储分配.对于绝大多数得学校而言,“外排,文件,动态存储分配”三章基本上就是不考得,在大多数高校得计算机本科教学过程中,这三章也就是基本上不作讲授得。
所以，大家在这三章上可以不必花费过多得精力,只要知道基本得概念即可。
但就是，对于报考名校特别就是该校又有在试卷中对这三章进行过考核得历史，那么这部分朋友就要留意这三章了。
按照以上我们给出得章节以及对后三章得介绍，数据结构得章节比重大致为：概论：内容很少,概念简单,分数大多只有几分，有得学校甚至不考.线性表:基础章节，必考内容之一。
考题多数为基本概念题，名校考题中，鲜有大型算法设计题.如果有，也就是与其它章节内容相结合.栈与队列：基础章节,容易出基本概念题，必考内容之一。
而相联系进行考查。
串：基础章节,概念较为简单.专门针对于此章得大型算法设计题很少，较常见得就是根据KMＰ进行算法分析。
多维数组及广义表:基础章节，基于数组得算法题也就是常见得,分数比例波动较大，就是出题得“可选单元”或“侯补单元”.一般如果要出题,多数不会作为大题出.数组常与“查找,排序”等章节结合来作为大题考查。
树与二叉树:重点难点章节，各校必考章节。
各校在此章出题得不同之处在于,就是否在本章中出一到两道大得算法设计题。
通过对多所学校得试卷分析,绝大多数学校在本章都曾有过出大型算法设计题得历史。
图:重点难点章节，名校尤爱考。
如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题得题型设计。
查找:重点难点章节,概念较多，联系较为紧密,容易混淆。
出题时可以作为分析型题目给出,在基本概念型题目中也较为常见。
算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。
排序:与查找一章类似,本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。
【2331】数据结构考试要点概论- 基本概念和术语（一）数据（Data）数据是信息的载体。
它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。
随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。
数据元素（Data Element）数据元素是数据的基本单位。
数据元素也称元素、结点、顶点、记录。
一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。
数据项是具有独立含义的最小标识单位。
数据结构（Data Structure）数据结构指的是数据之间的相互关系，即数据的组织形式。
1．数据结构一般包括以下三方面内容：①数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。
数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）；数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。
对机器语言而言，存储结构是具体的。
一般，只在高级语言的层次上讨论存储结构。
③数据的运算，即对数据施加的操作。
数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。
最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。
所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。
只有确定了存储结构之后，才考虑如何具体实现这些运算。
为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。
【例1．1】学生成绩表，见下表。
注意：在表中指出数据元素、数据项、开始结点和终端结点等概念（1）逻辑结构表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。
第六章树 树是n个结点的有限集合，⾮空时必须满⾜：只有⼀个称为根的结点；其余结点形成m个不相交的⼦集，并称根的⼦树。
根是开始结点；结点的⼦树数称度；度为0的结点称叶⼦（终端结点）；度不为0的结点称分⽀结点（⾮终端结点）；除根外的分⽀结点称内部结点； 有序树是⼦树有左，右之分的树；⽆序树是⼦树没有左，右之分的树；森林是m个互不相交的树的集合； 树的四种不同表⽰⽅法：·树形表⽰法；·嵌套集合表⽰法；·凹⼊表⽰法·⼴义表表⽰法。
⼆叉树的定义：是n≥0个结点的有限集，它是空集（n=0）或由⼀个根结点及两棵互不相交的分别称作这个根的左⼦树和右⼦树的⼆叉树组成。
⼆叉树不是树的特殊情形，与度数为2的有序树不同。
⼆叉树的4个重要性质： ·。
⼆叉树上第i层上的结点数⽬最多为2^（i-1）（i≥1）。
； ·深度为k的⼆叉树⾄多有（2^k）-1个结点（k≥1）； ·。
在任意⼀棵⼆叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1； ·。
具有n个结点的完全⼆叉树的深度为int（log2n）+1. 满⼆叉树是⼀棵深度为k，结点数为（2^k）-1的⼆叉树；完全⼆叉树是满⼆叉树在最下层⾃右向左去处部分结点； ⼆叉树的顺序存储结构就是把⼆叉树的所有结点按照层次顺序存储到连续的存储单元中。
（存储前先将其画成完全⼆叉树） 树的存储结构多⽤的是链式存储。
BinTNode的结构为lchild|data|rchild，把所有BinTNode类型的结点，加上⼀个指向根结点的BinTree型头指针就构成了⼆叉树的链式存储结构，称为⼆叉链表。
它就是由根指针root确定的。
共有2n个指针域，n+1个空指针。
根据访问结点的次序不同可得三种遍历：先序遍历（前序遍历或先根遍历），中序遍历（或中根遍历）、后序遍历（或后根遍历）。
时间复杂度为O（n）。
：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。
：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称。
数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的基本单位。
数据项：是数据元素中有独立含义的、不可分割的最小标识单位。
数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作。
数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合定义在此集合上的若干关系来表示，数据结构可以分为三种：线性结构、树结构和图。
：数据元素及其关系在计算机中的存储表示称为数据的存储结构，也称为物理结构。
数据的存储结构基本形式有两种：顺序存储结构和链式存储结构。
：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。
算法规则需满足以下五个特性：输入——算法有零个或多个输入数据。
输出——算法有一个或多个输出数据，与输入数据有某种特定关系。
有穷性——算法必须在执行又穷步之后结束。
确定性——算法的每个步骤必须含义明确，无二义性。
可行性——算法的每步操作必须是基本的，它们的原则上都能够精确地进行，用笔和纸做有穷次就可以完成。
有穷性和可行性是算法最重要的两个特征。
：算法与数据结构：算法建立数据结构之上，对数据结构的操作需用算法来描述。
算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。
：算法的设计应满足五个目标：正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标。
健壮性：即使输入数据不合适，算法也能做出适当的处理，不会导致不可控结高时间效率：算法的执行时间越短，时间效率越高。
果。
高空间效率：算法执行时占用的存储空间越少，空间效率越高。
可读性：算法的可读性有利于人们对算法的理解。
：度量算法的时间效率，时间复杂度，（课本39页）。
：递归定义：即用一个概念本身直接或间接地定义它自己。
数据结构考试大纲第一章绪论1、数据结构的基本概念和术语2、算法的描述第二章线性表1、线性表的逻辑结构2、线性表的存储结构及基本操作3、线性表的应用第三章栈和队列1、栈和队列的逻辑结构定义2、栈和队列的存储结构及基本操作3、栈和队列的应用第四章串1、串的逻辑结构定义2、串的存储结构及基本操作3、串的应用第五章数组和广义表1、数组和广义表的定义、存储结构2、数组的运算3、矩阵的压缩存储4、数组的应用第六章树和二叉树1、树的结构定义和基本操作2、二叉树的定义、性质和存储结构3、遍历二叉树和线索二叉树4、树和森林（存储结构、互相转换、遍历）5、树的应用第七章图1、图的定义和术语2、图的存储结构3、图的遍历4、图的应用第八章查找1、线性表、有序表的查找及其分析2、二叉排序树和平衡二叉树3、散列（Hash）表的定义，Hash 叉数的构造方式、冲突处理和Hash 表的查找及其分析第九章内部排序1、排序的基本概念2、各种排序方法及其分析第十章外部排序1、外存信息存取的基本概念2、磁盘、磁带归并排序第十一章文件1、有关文件的基本概念2、顺序文件、索引文件、索引顺序文件、直接存取文件、多重链表文件、倒排文件等的存取方法。
第一章绪论1、数据结构的基本概念和术语数据：是描述客观事物的数、字符以及所有能输入到计算机中被计算机程序加工处理的信息的集合。
数据元素：数据的基本单位。
(一个数据项或多个数据项(域) 。
数据项是数据的最小单位。
结点、顶点、记录。
数据对象：是性质相同的数据元素的集合。
数据结构：相互之间存在着某种逻辑关系的数据元素的集合。
数据之间的相互关系，即数据的组织形式。
四类基本结构：集合、线性结构、树形结构、图状结构或网状结构。
1) 数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；2) 数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。
3) 数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。
自考冲刺资料——数据结构重点章节讲解特别鸣谢：第二章线性表线性表是一种最简单、最常见的数据结构。
一、本章总述本章主要讨论了线性表及它的两种存储实现：顺序实现和链接实现。
线性表是一种最简单、最常见的数据结构。
线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。
用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。
二、本章重点熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析。
三、本章难点使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。
四、本章知识点1、线性表的逻辑结构的基本特征图2-1 线性表线性结构是一个数据元素的有序(次序)集1).集合中必存在唯一的一个“第一元素”；2).集合中必存在唯一的一个“最后元素”3).除最后元素之外，均有唯一的后继；4).除第一元素之外，均有唯一的前驱。
2、线性表的顺序存储实现顺序表是线性表的顺序存储结构。
用一组地址连续的存储单元依次存储线性表的元素。
顺序表特点：逻辑顺序与物理顺序一致属随机存取的存储结构，即存取每个元素所花时间相等假设线性表中每个元素需占用c个存储单元，计算结点存储地址公式：LOC(ai+1)=LOC(ai)+c (1)LOC(ai)=LOC(a1)+(i-1)*c (2)顺序表上实现基本运算及时间复杂度分析。
1)插入算法：假设在第 i 个元素之前插入的概率为 pi，则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行插入的概率都相等，则移动元素的期望值为：插入算法的平均时间复杂性为，平均时间复杂性量级为O(n)。
2)删除算法：假设删除第 i 个元素的概率为qi , 则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：删除算法的平均时间复杂性为，平均时间复杂性量级为O(n)。
数据结构复习重点归纳（适于清华严版教材）一、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。
对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。
所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。
但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。
按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。
线性表：基础章节，必考内容之一。
考题多数为基本概念题，名校考题中，鲜有大型算法设计题。
如果有，也是与其它章节内容相结合。
栈和队列：基础章节，容易出基本概念题，必考内容之一。
而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。
串：基础章节，概念较为简单。
专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。
多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。
一般如果要出题，多数不会作为大题出。
数组常与“查找，排序”等章节结合来作为大题考查。
树和二叉树：重点难点章节，各校必考章节。
各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。
通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。
图：重点难点章节，名校尤爱考。
如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。
查找：重点难点章节，概念较多，联系较为紧密，容易混淆。
出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。
算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。
2009年自学考试《数据结构》各章要点第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，可以由若干个数据项组成。
数据项是具有独立含义的最小标识单位。
数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。
·线性结构：一对一关系。
·线性结构：多对多关系。
·存储结构：是逻辑结构用计算机语言的实现。
·顺序存储结构：如数组。
·链式存储结构：如链表。
·稠密索引：每个结点都有索引项。
·稀疏索引：每组结点都有索引项。
·散列存储结构：如散列表。
·对数据的操作：定义在逻辑结构上，每种逻辑结构都有一个运算集合。
·常用的有：检索、插入、删除、更新、排序。
·数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。
·原子类型：由语言提供。
·结构类型：由用户借助于描述机制定义，是导出类型。
抽象数据类型ADT：·是抽象数据的组织和与之的操作。
相当于在概念层上描述问题。
·优点是将数据和操作封装在一起实现了信息隐藏。
程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。
算法取决于数据结构。
算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。
评价算法的好坏的因素：·算法是正确的;·执行算法的时间;·执行算法的存储空间(主要是辅助存储空间);·算法易于理解、编码、调试。
时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。
渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。
评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。
算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。
时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。
空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n的函数。
算法的时间复杂度和空间复杂度合称算法复杂度。
第二章线性表线性表是由n≥0个数据元素组成的有限序列。
n=0是空表;非空表，只能有一个开始结点，有且只能有一个终端结点。
线性表上定义的基本运算：·构造空表：Initlist(L)·求表长：Listlength(L)·取结点：GetNode(L，i)·查找：LocateNode(L，x)·插入：InsertList(L，x，i)·删除：Delete(L，i)顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。
在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。
地址计算：LOCa(i)=LOCa(1)+(i-1)*d;(首地址为1) /考试大收集整理/在顺序表中实现的基本运算：·插入：平均移动结点次数为n/2;平均时间复杂度均为O(n)。
·删除：平均移动结点次数为(n-1)/2;平均时间复杂度均为O(n)。
线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息(即指针或链)。
这两部分信息组成链表中的结点结构。
一个单链表由头指针的名字来命名。
单链表运算：·建立单链表·头插法：s->next=head;head=s;生成的顺序与输入顺序相反。
平均时间复杂度均为O(n)。
·尾插法：head=rear=null;if(head=null) head=s;else r->next=s;r=s; 平均时间复杂度均为O(n)·加头结点的算法：对开始结点的操作无需特殊处理，统一了空表和非空表。
·查找·按序号：与查找位置有关，平均时间复杂度均为O(n)。
·按值：与输入实例有关，平均时间复杂度均为O(n)。
·插入运算：p=GetNode(L，i-1);s->next=p->next;p->next=s;平均时间复杂度均为O(n)·删除运算：p=GetNode(L，i-1);r=p->next;p->next=r->next;free(r);平均时间复杂度均为O(n)单循环链表是一种首尾相接的单链表，终端结点的指针域指向开始结点或头结点。
链表终止条件是以指针等于头指针或尾指针。
采用单循环链表在实用中多采用尾指针表示单循环链表。
优点是查找头指针和尾指针的时间都是O(1)，不用遍历整个链表。
双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior，形成两条不同方向的链。
由头指针head惟一确定。
双链表也可以头尾相链接构成双(向)循环链表。
双链表上的插入和删除时间复杂度均为O (1)。
顺序表和链表的比较：·基于空间：·顺序表的存储空间是静态分配，存储密度为1;适于线性表事先确定其大小时采用。
·链表的存储空间是动态分配，存储密度<1;适于线性表长度变化大时采用。
·基于时间：·顺序表是随机存储结构，当线性表的操作主要是查找时，宜采用。
·以插入和删除操作为主的线性表宜采用链表做存储结构。
·若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。
第三章栈和队列栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。
表中无元素时为空栈。
栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(Last In First Out)。
通常栈有顺序栈和链栈两种存储结构。
栈的基本运算有六种：·构造空栈：InitStack(S)·判栈空：StackEmpty(S)·判栈满：StackFull(S)·进栈：Push(S，x)·退栈：Pop(S)·取栈顶元素：StackTop(S) 在顺序栈中有“上溢”和“下溢”的现象。
·“上溢”是栈顶指针指出栈的外面是出错状态。
·“下溢”可以表示栈为空栈，因此用来作为控制转移的条件。
顺序栈中的基本操作有六种：·构造空栈·判栈空·判栈满·进栈·退栈·取栈顶元素链栈则没有上溢的限制，因此进栈不要判栈满。
链栈不需要在头部附加头结点，只要有链表的头指针就可以了。
链栈中的基本操作有五种：·构造空栈·判栈空·进栈·退栈·取栈顶元素队列(Queue)是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear) ，队列的操作原则是先进先出的，又称作FIFO表(First In First Out) .队列也有顺序存储和链式存储两种存储结构。
队列的基本运算有六种：·置空队：InitQueue(Q)·判队空：QueueEmpty(Q)·判队满：QueueFull(Q)·入队：EnQueue(Q，x)·出队：DeQueue(Q)·取队头元素：QueueFront(Q)顺序队列的“假上溢”现象：由于头尾指针不断前移，超出向量空间。
这时整个向量空间及队列是空的却产生了“上溢”现象。
为了克服“假上溢”现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。
判定循环队列是空还是满，方法有三种：·一种是另设一个布尔变量来判断;·第二种是少用一个元素空间，入队时先测试((rear+1)%m = front)? 满：空;·第三种就是用一个计数器记录队列中的元素的总数。
队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。
为了便于在表尾进行插入(入队)的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。
链队列不存在队满和上溢的问题。
在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。
第四章串串是零个或多个字符组成的有限序列。
·空串：是指长度为零的串，也就是串中不包含任何字符(结点)。
·空白串：指串中包含一个或多个空格字符的串。
·在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。
·子串在主串中的序号就是指子串在主串中首次出现的位置。
·空串是任意串的子串，任意串是自身的子串。
串分为两种：·串常量在程序中只能引用不能改变;·串变量的值可以改变。
串的基本运算有：·求串长strlen(char*s)·串复制strcpy(char*to，char*from)·串联接strcat(char*to，char*from)·串比较charcmp(char*s1，char*s2)·字符定位strchr(char*s，charc)。
串是特殊的线性表(结点是字符)，所以串的存储结构与线性表的存储结构类似。
串的顺序存储结构简称为顺序串。
顺序串又可按存储分配的不同分为：·静态存储分配：直接用定长的字符数组来定义。
优点是涉及串长的操作速度快，但不适合插入、链接操作。
·动态存储分配：是在定义串时不分配存储空间，需要使用时按所需串的长度分配存储单元。
串的链式存储就是用单链表的方式存储串值，串的这种链式存储结构简称为链串。
链串与单链表的差异只是它的结点数据域为单个字符。
为了解决“存储密度”低的状况，可以让一个结点存储多个字符，即结点的大小。
顺序串上子串定位的运算：又称串的“模式匹配”或“串匹配”，是在主串中查找出子串出现的位置。
在串匹配中，将主串称为目标(串)，子串称为模式(串)。
这是比较容易理解的，串匹配问题就是找出给定模式串P在给定目标串T中首次出现的有效位移或者是全部有效位移。
最坏的情况下时间复杂度是O((n-m+1)m)，假如m与n同阶的话则它是O(n^2)。
链串上的子串定位运算位移是结点地址而不是整数。
第五章多维数组和广义表数组一般用顺序存储的方式表示。
