最新自考02331数据结构重点总结(最终修订)

【2331】数据结构考试要点概论- 基本概念和术语（一）数据（Data）数据是信息的载体。

它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。

随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。

数据元素（Data Element）数据元素是数据的基本单位。

数据元素也称元素、结点、顶点、记录。

一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。

数据项是具有独立含义的最小标识单位。

数据结构（Data Structure）数据结构指的是数据之间的相互关系，即数据的组织形式。

1．数据结构一般包括以下三方面内容：①数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。

数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）；数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。

对机器语言而言，存储结构是具体的。

一般，只在高级语言的层次上讨论存储结构。

③数据的运算，即对数据施加的操作。

数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。

最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。

所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。

只有确定了存储结构之后，才考虑如何具体实现这些运算。

为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。

【例1．1】学生成绩表，见下表。

注意：在表中指出数据元素、数据项、开始结点和终端结点等概念（1）逻辑结构表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。

第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，可以由若干个数据项组成。

数据项是具有独立含义的最小标识单位。

数据结构的定义：逻辑结构：从逻辑结构上描述数据，独立于计算机。

线性结构：一对一关系。

线性结构：多对多关系。

存储结构：是逻辑结构用计算机语言的实现。

顺序存储结构：如数组。

链式存储结构：如链表。

索引存储结构：稠密索引：每个结点都有索引项。

稀疏索引：每组结点都有索引项。

散列存储结构：如散列表。

数据运算。

对数据的操作。

定义在逻辑结构上，每种逻辑结构都有一个运算集合。

常用的有：检索、插入、删除、更新、排序。

数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

原子类型：由语言提供。

结构类型：由用户借助于描述机制定义，是导出类型。

抽象数据类型ADT:是抽象数据的组织和与之的操作。

相当于在概念层上描述问题。

优点是将数据和操作封装在一起实现了信息隐藏。

程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。

算法取决于数据结构。

算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。

评价算法的好坏的因素：算法是正确的；执行算法的时间；执行算法的存储空间（主要是辅助存储空间）；算法易于理解、编码、调试。

时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。

渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。

评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。

算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。

时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n〃2)、立方阶O(n”)、……k次方阶O(n”)、指数阶O(2M)。

空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n的函数。

算法的时间复杂度和空间复杂度合称算法复杂度。

数据结构知识点总结数据结构知识点总结：一、数据结构概述数据结构定义及分类●线性结构●非线性结构●数组●链表●栈●队列●树●图●散列表二、线性结构⒈数组●定义●数组的操作：插入、删除、查找、更新●二维数组⒉链表●定义●特点●单链表●双链表●循环链表●链表的操作：插入、删除、查找、更新⒊栈●定义●特点●栈的顺序存储结构●栈的链式存储结构●栈的应用⒋队列●特点●队列的顺序存储结构●队列的链式存储结构●队列的应用三、非线性结构⒈树●定义●结点●树的类型：二叉树，多叉树，满二叉树，完全二叉树●二叉树的存储结构：顺序存储，链式存储●二叉树的遍历：先序遍历，中序遍历，后序遍历●二叉树的应用：赫夫曼树，二叉搜索树⒉图●定义●图的存储结构：邻接矩阵，邻接表●图的遍历：深度优先搜索，广度优先搜索●最短路径算法四、散列表（哈希表）●定义●散列函数●冲突解决方法：拉链法，开放地质法附件：无法律名词及注释：⒈数据结构：指在计算机科学中，数据组织、管理和存储的方式。

⒉线性结构：数据元素之间存在一对一关系的结构。

⒊非线性结构：数据元素之间存在一对多或多对多关系的结构。

⒋数组：一种线性结构，由相同数据类型的元素组成，通过下标进行访问。

⒌链表：一种线性结构，由一系列结点构成，每个结点中包含数据和指向下一个结点的指针。

⒍栈：一种特殊的线性结构，只能在一端进行插入和删除操作的数据结构。

⒎队列：一种特殊的线性结构，只能在一端进行插入操作，在另一端进行删除操作的数据结构。

⒏树：一种非线性结构，由结点和边组成，每个结点可以有多个子结点。

⒐图：一种非线性结构，由一组顶点和一组边组成，顶点之间可以有多种关系。

⒑散列表：一种根据关键字直接访问数据的数据结构，通过散列函数将关键字映射到相应的存储位置。

数据结构必考知识点总结在准备考试时，了解数据结构的基本概念和相关算法是非常重要的。

以下是一些数据结构的必考知识点总结：1. 基本概念数据结构的基本概念是非常重要的，包括数据、数据元素、数据项、数据对象、数据类型、抽象数据类型等的概念。

了解这些概念有助于更好地理解数据结构的本质和作用。

2. 线性表线性表是数据结构中最基本的一种，它包括顺序表和链表两种实现方式。

顺序表是将数据元素存放在一块连续的存储空间内，而链表是将数据元素存放在若干个节点中，每个节点包含数据和指向下一个节点的指针。

了解线性表的概念和基本操作是非常重要的。

3. 栈和队列栈和队列是两种特殊的线性表，它们分别具有后进先出和先进先出的特性。

栈和队列的实现方式有多种，包括数组和链表。

掌握栈和队列的基本操作和应用是数据结构的基本内容之一。

4. 树结构树是一种非线性的数据结构，它包括二叉树、多路树、二叉搜索树等多种形式。

了解树的基本定义和遍历算法是必考的知识点。

5. 图结构图是一种非线性的数据结构，它包括有向图和无向图两种形式。

了解图的基本概念和相关算法是非常重要的，包括图的存储方式、遍历算法、最短路径算法等。

6. 排序算法排序是一个非常重要的算法问题，掌握各种排序算法的原理和实现方式是必不可少的。

常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。

7. 查找算法查找是另一个重要的算法问题，包括顺序查找、二分查找、哈希查找、树查找等。

了解各种查找算法的原理和实现方式是必考的知识点之一。

8. 算法复杂度分析算法的时间复杂度和空间复杂度是评价算法性能的重要指标，掌握复杂度分析的方法和技巧是非常重要的。

9. 抽象数据类型ADT是数据结构的一种概念模型，它包括数据的定义和基本操作的描述。

了解ADT的概念和实现方式是非常重要的。

10. 动态存储管理动态存储管理是数据结构中一个重要的问题，包括内存分配、内存释放、内存回收等。

了解动态存储管理的基本原理和实现方式是必考的知识点之一。

第1章概论1.数据结构的作用、意义、基本概念和术语,要求达到“识记”层次。

1.1数据结构所研究的内容;在计算机科学中的作用和意义;Wirth关于程序的定义公式。

1.2数据、数据元素、数据对象、数据项、数据结构等概念的定义。

1.3数据的逻辑结构、存储结构及数据运算的含义及其相互关系。

1.4数据结构的两大类逻辑结构和四种常用的存储表示方法。

2.算法的描述和分析,要求达到“领会”层次。

2.1算法、算法的时间复杂度和空间复杂度等概念。

2.2一个完整算法需要满足的五个准则;算法与程序的关系。

2.3算法的分析方法;对于一般算法能分析其时间复杂度。

第2章线性表1.线性表的逻辑结构,要求达到“识记”层次。

1.1线性表的逻辑定义和性质。

1.2线性表上定义的基本运算。

2.线性表的顺序存储结构和基本运算,要求达到“领会”层次。

2.1顺序表的定义及特点。

2.2顺序表上进行插入和删除操作的实现及时间性能分析。

2.3理解求顺序表逆置和极值及定位两种算法的实现过程。

3.线性表链式存储结构的不同形式及基本运算,要求达到“领会”层次。

3.1单链表、循环链表、双向链表的定义及特点。

3.2单链表上实现建表、查找、插入和删除等基本算法,并分析其时间复杂度。

3.3用尾指针表示单循环链表的意义。

3.4双向链表上的插入和删除操作。

4.利用顺序表和链表设计算法解决应用问题,要求达到“综合应用”层次。

5.顺序表和链表的比较,要求达到“领会”层次。

第3章栈和队列1.栈的逻辑结构、存储结构及相关算法,要求达到“简单应用”层次。

1.1栈的逻辑定义、特点及运算。

1.2顺序栈和链栈上实现进栈、退栈等基本运算。

1.3顺序栈的上溢和下溢问题,如何防止溢出。

2.队列的逻辑结构、存储结构及相关算法,要求达到“简单应用”层次。

2.1队列的逻辑定义、特点及运算。

2.2顺序循环队列的表述;队空和队满的判定;顺序循环队列上入队、出队等基本算法。

2.3链队列的表述;带头结点和不带头结点两种情况下链队列上的基本算法。

一、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为：概论;线性表;栈和队列;串;多维数组和广义表;树和二叉树;图;查找;内排;外排;文件;动态存储分配..对于绝大多数的学校而言;“外排;文件;动态存储分配”三章基本上是不考的;在大多数高校的计算机本科教学过程中;这三章也是基本上不作讲授的..所以;大家在这三章上可以不必花费过多的精力;只要知道基本的概念即可..但是;对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史;那么这部分朋友就要留意这三章了..按照以上我们给出的章节以及对后三章的介绍;数据结构的章节比重大致为：概论：内容很少;概念简单;分数大多只有几分;有的学校甚至不考..线性表：基础章节;必考内容之一..考题多数为基本概念题;名校考题中;鲜有大型算法设计题..如果有;也是与其它章节内容相结合..栈和队列：基础章节;容易出基本概念题;必考内容之一..而相联系进行考查..串：基础章节;概念较为简单..专门针对于此章的大型算法设计题很少;较常见的是根据KMP进行算法分析..多维数组及广义表：基础章节;基于数组的算法题也是常见的;分数比例波动较大;是出题的“可选单元”或“侯补单元”..一般如果要出题;多数不会作为大题出..数组常与“查找;排序”等章节结合来作为大题考查..树和二叉树：重点难点章节;各校必考章节..各校在此章出题的不同之处在于;是否在本章中出一到两道大的算法设计题..通过对多所学校的试卷分析;绝大多数学校在本章都曾有过出大型算法设计题的历史..图：重点难点章节;名校尤爱考..如果作为重点来考;则多出现于分析与设计题型当中;可与树一章共同构成算法设计大题的题型设计..查找：重点难点章节;概念较多;联系较为紧密;容易混淆..出题时可以作为分析型题目给出;在基本概念型题目中也较为常见..算法设计型题中可以数组结合来考查;也可以与树一章结合来考查..排序：与查找一章类似;本章同属于重点难点章节;且概念更多;联系更为紧密;概念之间更容易混淆..在基本概念的考查中;尤爱考各种排序算法的优劣比较此类的题..算法设计大题中;如果作为出题;那么常与数组结合来考查..二、数据结构各章节重点勾划第0章概述本章主要起到总领作用;为读者进行数据结构的学习进行了一些先期铺垫..大家主要注意以下几点：数据结构的基本概念;时间和空间复杂度的概念及度量方法;算法设计时的注意事项..本章考点不多;只要稍加注意理解即可..第一章线性表作为线性结构的开篇章节;线性表一章在线性结构的学习乃至整个数据结构学科的学习中;其作用都是不可低估的..在这一章;第一次系统性地引入链式存储的概念;链式存储概念将是整个数据结构学科的重中之重;无论哪一章都涉及到了这个概念..总体来说;线性表一章可供考查的重要考点有以下几个方面：1. 线性表的相关基本概念;如：前驱、后继、表长、空表、首元结点;头结点;头指针等概念..2.3. 线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动态分配..静态链表与顺序表的相似及不同之处..4. 线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表;双向链表;双向循环链表..其中;单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式..此外;近年来在不少学校中还多次出现要求用递归算法实现单链表输出可能是顺序也可能是倒序的问题..在链表的小题型中;经常考到一些诸如：判表空的题..在不同的链表中;其判表空的方式是不一样的;请大家注意..5. 线性表的顺序存储及链式存储情况下;其不同的优缺点比较;即其各自适用的场合..单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处..第二章栈与队列栈与队列;是很多学习DS的同学遇到第一只拦路虎;很多人从这一章开始坐晕车;一直晕到现在..所以;理解栈与队列;是走向DS高手的一条必由之路..学习此章前;你可以问一下自己是不是已经知道了以下几点：1. 栈、队列的定义及其相关数据结构的概念;包括：顺序栈;链栈;共享栈;循环队列阶乘问题;fib数列问题;Hanoi问题;背包问题;二叉树的递归和非递归遍历问题;图的深度遍历与栈的关系等..其中;涉及到树与图的问题;多半会在树与图的相关章节中进行考查..3. 栈的应用：数值表达式的求解;括号的配对等的原理;只作原理性了解;具体要求考查此为题目的算法设计题不多..4. 循环队列中判队空、队满条件;循环队列中入队与出队算法..如果你已经对上面的几点了如指掌;栈与队列一章可以不看书了..注意;我说的是可以不看书;并不是可以不作题哦..第三章串经历了栈一章的痛苦煎熬后;终于迎来了串一章的柳暗花明..串;在概念上是比较少的一个章节;也是最容易自学的章节之一;但正如每个过来人所了解的;KMP算法是这一章的重要关隘;突破此关隘后;走过去又是一马平川的大好DS山河了;呵呵..串一章需要攻破的主要堡垒有：1. 串的基本概念;串与线性表的关系串是其元素均为字符型数据的特殊线性表;空串与空格串的区别;串相等的条件..2. 串的基本操作;以及这些基本函数的使用;包括：取子串;串连接;串替换;求串长等等..运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点..3. 顺序串与链串及块链串的区别和联系;实现方式..4. KMP算法思想..KMP中next数组以及nextval数组的求法..明确传统模式匹配算法的不足;明确next数组需要改进之外..其中;理解算法是核心;会求数组是得分点..不用我多说;这一节内容是本章的重中之重..可能进行的考查方式是：求next和nextval数组值;根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程..第四章数组与广义表学过程序语言的朋友;数组的概念我们已经不是第一次见到了;应该已经“一回生;二回熟”了;所以;在概念上;不会存在太大障碍..但作为考研课程来说;本章的考查重点可能与大学里的程序语言所关注的不太一样;下面会作介绍..广义表的概念;是数据结构里第一次出现的..它是线性表或表元素的有限序列;构成该结构的每个子表或元素也是线性结构的;所以;这一章也归入线性结构中..本章的考查重点有：1. 多维数组中某数组元素的position求解..一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数;然后要求你求出该数组中的某个元素所在的位置..2. 明确按行存储和按列存储的区别和联系;并能够按照这两种不同的存储方式求解1中类型的题..3. 将特殊矩阵中的元素按相应的换算方式存入数组中..这些矩阵包括：对称矩阵;三角矩阵;具有某种特点的稀疏矩阵等..熟悉稀疏矩阵的三种不同存储方式：三元组;带辅助行向量的二元组;十字链表存储..掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法..4. 广义表的概念;特别应该明确表头与表尾的定义..这一点;是理解整个广义表一节算法的基础..近来;在一些学校中;出现了这样一种题目类型：给出对某个广义表L若干个求了若干次的取头和取尾操作后的串值;要求求出原广义表L..大家要留意..5. 与广义表有关的递归算法..由于广义表的定义就是递归的;所以;与广义表有关的算法也常是递归形式的..比如：求表深度;复制广义表等..这种题目;可以根据不同角度广义表的表现形式运用两种不同的方式解答：一是把一个广义表看作是表头和表尾两部分;分别对表头和表尾进行操作；二是把一个广义表看作是若干个子表;分别对每个子表进行操作..第五章树与二叉树从对线性结构的研究过度到对树形结构的研究;是数据结构课程学习的一次跃变;此次跃变完成的好坏;将直接关系到你到实际的考试中是否可以拿到高分;而这所有的一切;将最终影响你的专业课总分..所以;树这一章的重要性;已经不说自明了..总体来说;树一章的知识点包括：二叉树的概念、性质和存储结构;二叉树遍历的三种算法递归与非递归;在三种基本遍历算法的基础上实现二叉树的其它算法;线索二叉树的概念和线索化算法以及线索化后的查找算法;最优二叉树的概念、构成和应用;树的概念和存储形式;树与森林的遍历算法及其与二叉树遍历算法的联系;树与森林和二叉树的转换..下面我们来看考试中对以上知识的主要考查方法：1. 二叉树的概念、性质和存储结构考查方法可有：直接考查二叉树的定义;让你说明二叉树与普通双分支树的区别；;普通二叉树的五个性质：第i层的最多结点数;深度为k的二叉树的最多结点数;n0=n2+1的性质;n个结点的完全二叉树的深度;顺序存储二叉树时孩子结点与父结点之间的换算关系左为：2i;右为：2i+1..二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合;二叉树的三叉链表表示方法..2. 二叉树的三种遍历算法这一知识点掌握的好坏;将直接关系到树一章的算法能否理解;进而关系到树一章的算法设计题能否顺利完成..二叉树的遍历算法有三种：先序;中序和后序..其划分的依据是视其每个算法中对根结点数据的访问顺序而定..不仅要熟练掌握三种遍历的递归算法;理解其执行的实际步骤;并且应该熟练掌握三种遍历的非递归算法..由于二叉树一章的很多算法;可以直接根据三种递归算法改造而来比如：求叶子个数;所以;掌握了三种遍历的非递归算法后;对付诸如：“利用非递归算法求二叉树叶子个数”树;查找值为n的某个指定结点;删除值为n的某个指定结点;诸如此类等等等等..如果你可以熟练掌握二叉树的递归和非递归遍历算法;那么解决以上问题就是小菜一碟了..4. 线索二叉树：线索二叉树的引出;是为避免如二叉树遍历时的递归求解..众所周知;递归虽然形式上比较好理解;但是消耗了大量的内存资源;如果递归层次一多;势必带来资源耗尽的危险;为了避免此类情况;线索二叉树便堂而皇之地出现了..对于线索二叉树;应该掌握：线索化的实质;三种线索化的算法;线索化后二叉树的遍历算法;基本线索二叉树的其它算法问题如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题..5. ：最优二叉树是为了解决特定问题引出的特殊二叉树结构;它的前提是给二叉树的每条边赋予了权值;这样形成的二叉树按权相加之和是最小的..最优二叉树一节;直接考查算法源码的很少;一般是给你一组数据;要求你建立基于这组数据的最优二叉树;并求出其最小权值之和;此类题目不难;属送分题..B树和B+数同样掌握B树的构建;添加节点与删除节点等操作8. 树与森林：二叉树是一种特殊的树;这种特殊不仅仅在于其分支最多为2以及其它特征;一个最重要的特殊之处是在于：二叉树是有序的即：二叉树的左右孩子是不可交换的;如果交换了就成了另外一棵二叉树;这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树..但是;对于普通的双分支树而言;不具有这种性质..树与森林的遍历;不像二叉树那样丰富;他们只有两种遍历算法：先根与后根对于森林而言称作：先序与后序遍历..在难度比较大的考试中;也有基于此二种算法的基础上再进行扩展要求你利用这两种算法设计其它算法的;但一般院校很少有这种考法;最多只是要求你根据先根或后根写出他们的遍历序列..此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历;而后根遍历对应二叉树的中序遍历..这一点成为很多学校的考点;考查的方式不一而足;有的直接考此句话;有的是先让你求解遍历序列然后回答这个问题..二叉树、树与森林之所以能有以上的对应关系;全拜二叉链表所赐..二叉树使用二叉链表分别存放他的左右孩子;树利用二叉链表存储孩子及兄弟称孩子兄弟链表;而森林也是利用二叉链表存储孩子及兄弟..树一章;处处是重点;道道是考题;大家务必个个过关..第六章图如果说;从线性结构向树形结构研究的转变;是数据结构学科对数据组织形式研究的一次升华;那么从树形结构的研究转到图形结构的研究;则进一步让我们看到了数据结构对于解决实际问题的重大推动作用..图这一章的特点是：概念繁多;与离散数学中图的概念联系紧密;算法复杂;极易被考到;且容易出大题;尤其是名校;作为考研课程;如果不考查树与图两章的知识;几乎是不可想像的..下面我们看一下图这一章的主要考点以及这些考点的考查方式：1. 考查有关图的基本概念问题：这些概念是进行图一章学习的基础;与这些概念相联系的相关计算题也应该掌握..2. 考查图的几种存储形式：在考查时;有的学校是给出一种存储形式;要求考生用算法或手写出3.基本的遍历算法;其中深度遍历相当于二叉树中的先序遍历;而广度遍历相当于二叉树中的层次遍历.这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性..在考查时;图一章的算法设计题常常是基于这两种基本的遍历算法而设计的;比如：“求最长的最短路径问题”和“判断两顶点间是否存在长为K的简单路径问题”;就分别用到了广度遍历和深度遍历算法..4.考查时;一般不要求写出算法源码;而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树..5. ;一是无前趋的顶点优先算法;二是无后继的顶点优先算法..换句话说;一种是“从前向后”的排序;一种是“从后向前”排..当然;后一种排序出来的结果是“逆拓扑有序”的..6. ：这个问题是图一章的难点问题..理解关键路径的关键有三个方面：一是何谓关键路径;二是最早时间是什么意思、如何求;三是最晚时间是什么意思、如何求..简单地说;最早时间是通过“从前向后”的方法求的;而最晚时间是通过“从后向前”的方法求解的;并且;要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行..这个问题拿来直接考算法源码的不多;一般是要求按照书上的算法描述求解的过程和步骤..在实际设计关键路径的算法时;还应该注意以下这一点：采用邻接表的存储结构;求最早时间和最晚时间要采用不同的处理方法;即：在算法初始时;应该首先将所有顶点的最早时间全部置为0..关键路径问题是工程进度控制的重要方法;具有很强的实用性..7. ：与关键路径问题并称为图一章的两只拦路虎..概念理解是比较容易的;关键是算法的理解..最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径..这个问题也具有非常实用的背景特色;一个典型的应该就是旅游景点及旅游路线的选择问题..解决第一个问题用DIJSKTRA算法;解决第二个问题用FLOYD算法..注意区分..注意区分关键路径问题与最短路径问题第七章查找在不少数据结构的教材中;是把查找与排序放入高级数据结构中的..应该说;查找和排序两章是前面我们所学的知识的综合运用;用到了树、也用到了链表等知识;对这些数据结构某一方面的运用就构成了查找和排序..现实生活中;search几乎无处不在;特别是现在的网络时代;万事离不开search;小到文档内文字的搜索;大到INTERNET上的搜索;search占据了我们上网的大部分时间..在复习这一章的知识时;你需要先弄清楚以下几个概念：关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果;特别是一些典型结构的ASL值;应该记住..在DS的教材中;一般将search分为三类：1st;在顺序表上的查找；2nd;在树表上的查找；3rd;在哈希表上的查找..下面详细介绍其考查知识点及考查方式：1. 线性表上的查找：主要分为三种线性结构：顺序表;有序顺序表;索引顺序表..对于第一种;我们采用传统查找方法;逐个比较..对于第三种索引结构;我们采用索引查找算法..考生需要注意这三种表下的ASL值以及三种算法的实现..其中;二分查找还要特别注意适用条件以及其递归实现方法..2. 树表上的查找：这是本章的重点和难点..由于这一节介绍的内容是使用树表进行的查找;所以很容易与树一间的某些概念相混淆..本节内容与树一章的内容有联系;但也有很多不同;应注意规纳..树表主要分为以下几种：;;;键树..其中;尤以前两种结构为重;也有部分名校偏爱考B树的..由于二叉排序树与平衡二叉树是一种特殊的二叉树;所以与二叉树的联系就更为紧密;二叉树一章学好了;这里也就不难了..二叉排序树;简言之;就是“左小右大”;它的中序遍历结果是一个递增的有序序列..平衡二叉树是二叉排序树的优化;其本质也是一种二叉排序树;只不过;平衡二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1..对于二叉排序树;“判断某棵二叉树是否二叉排序树”这一算法经常被考到;可用递归;也可以用非递归..平衡二叉树的建立也是一个常考点;但该知识点归根结底还是关注的平衡二叉树的四种调整算法;所以应该掌握平衡二叉树的四种调整算法;调整的一个参照是：调整前后的中序遍历结果相同..B树是报考名校的同学应该关注的焦点之一..键树也称字符树;特别适用于查找英文单词的场合..一般不要求能完整描述算法源码;多是根据算法思想建立键树及描述其大致查找过程..3. ：哈希一词;是外来词;译自“hash”一词;意为：散列或杂凑的意思..哈希表查找的基本思想是：根据当前待查找数据的特征;以记录关键字为自变量;设计一个function;该函数对关键字进行转换后;其解释结果为待查的地址..基于哈希表的考查点有：哈希函数的设计;冲突解决方法的选择及冲突处理过程的描述..第八章内部排序内排是DS课程中最后一个重要的章节;建立在此章之上的考题可以有多种类型：填空;选择;判断乃至大型算法题..但是;归结到一点;就是考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标时间复杂度能否了如指掌..这一章;我们对重点的规纳将跟以上各章不同..我们将从以下几个侧面来对排序一章进行不同的规纳;以期能更全面的理解排序一章的总体结构及各种算法..从排序算法的种类来分;本章主要阐述了以下几种排序方法：其中;在插入排序中又可分为：直接插入、折半插入、2路插入、希尔排序..这几种插入排序算法的最根本的不同点;说到底就是根据什么规则寻找新元素的插入点..直接插入是依次寻找;折半插入是折半寻找..希尔排序;是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的..;在交换排序的基础上改进又可以得到快速排序..快速排序的思想;一语以敝之：用中间数将待排数据组一分为二..快速排序;在处理的“问题规模”这个概念上;与希尔有点相反;快速排序;是先处理一个较大规模;然后逐渐把处理的规模降低;最终达到排序的目的..;相对于前面几种排序算法来说;难度大一点..具体来说;它可以分为：简单选择、树选择、堆排..这三种方法的不同点是;根据什么规则选取最小的数..简单选择;是通过简单的数组遍历方案确定最小数；树选择;是通过“锦标赛”类似的思想;让两数相比;不断淘汰较大小者;最终选出最小大数；而堆排序;是利用堆这种数据结构的性质;通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶..堆排序中的堆建立、堆调整是重要考点..树选择排序;也曾经在一些学校中的大型算法题中出现;请大家注意..;故名思义;是通过“归并”这种操作完成排序的目的;既然是归并就必须是两者以上的数据集合才可能实现归并..所以;在归并排序中;关注最多的就是算法思想比较简单;;是一种很特别的排序方法;也正是由于它的特殊;所以;基数排序就比较适合于一些特别的场合;比如扑克牌排序问题等..基数排序;又分为两种：多关键字的排序扑克牌排序;链式排序整数排序..基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小;并且;在排序的过程中;只要按照基排的思想;是不用进行关键字比较的;这样得出的最终序列就是一个有序序列..本章各种排序算法的思想以及伪代码实现;及其时间复杂度都是必须掌握的;学习时要多注意规纳、总结、对比..此外;对于教材中的10.7节;要求必须熟记;在理解的基础上记忆;这一节几乎成为很多学校每年的必考点..堆基于完全二叉树;又可分为大顶堆和小顶堆;掌握堆的构建;与删除节点操作;如删除顶点时先将最后一个叶子节点与顶点交换位置;然后进行再排序.。

02331数据结构一、单选题1.下列程序段的时间复杂度为( D )s=0；for(i=1；i<n ；i++)for(j=1；j<n ；j++)s+=i*j ；A.O(1)B.O(n)C.O(2n)D.O(n 2)2.假设某个带头结点的单链表的头指针为head ，则判定该表为空表的条件是( B )A.head==NULL ；B.head->next==NULL ；C.head!=NULL ；D.head->next==head ；3.栈是一种操作受限的线性结构，其操作的主要特征是( B )A.先进先出B.后进先出C.进优于出D.出优于进4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front 和rear 。

若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( B )A.(rear-front-1)％nB.(rear-front)％nC.(front-rear+1)％nD.(rear-front+n)％n5.判断两个串大小的基本准则是( D )52A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为( C )A.1012B.1017C.1034D.10367.高度为5的完全二叉树中含有的结点数至少为( A )A.16B.17C.31D.328.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( C )A.5B.8C.11D.189.下列关键字序列中，构成大根堆的是( D )A.5，8，1，3，9，6，2，7B.9，8，1，7，5，6，2，33C.9，8，6，3，5，l ，2，7D.9，8，6，7，5，1，2，310.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( B )A.1539B.1549C.1551D.155512.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的 ( A )。

自考《数据结构》各章要点一第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，可以由若干个数据项组成。

数据项是具有独立含义的最小标识单位。

数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。

·线性结构：一对一关系。

·线性结构：多对多关系。

·存储结构：是逻辑结构用计算机语言的实现。

·顺序存储结构：如数组。

·链式存储结构：如链表。

·稠密索引：每个结点都有索引项。

·稀疏索引：每组结点都有索引项。

·散列存储结构：如散列表。

·对数据的操作：定义在逻辑结构上，每种逻辑结构都有一个运算集合。

·常用的有：检索、插入、删除、更新、排序。

·数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

·原子类型：由语言提供。

·结构类型：由用户借助于描述机制定义，是导出类型。

抽象数据类型ADT：·是抽象数据的组织和与之的操作。

相当于在概念层上描述问题。

·优点是将数据和操作封装在一起实现了信息隐藏。

程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。

算法取决于数据结构。

算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。

评价算法的好坏的因素：·算法是正确的；·执行算法的时间；·执行算法的存储空间(主要是辅助存储空间)；·算法易于理解、编码、调试。

时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。

渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。

评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。

算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。

时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。

02331数据结构《02331 数据结构》在当今数字化的时代，数据结构作为计算机科学中的重要基石，对于解决各种实际问题起着至关重要的作用。

02331 数据结构这一特定的课程或者领域，涵盖了丰富而深入的知识体系，让我们一同来探索它的奥秘。

数据结构是什么？简单来说，它是组织和存储数据的方式，以便于能够高效地访问、操作和管理这些数据。

就好比我们整理自己的房间，如果东西随意堆放，找起来会非常麻烦，但如果我们把书籍放在书架上，衣服放进衣柜，杂物放进抽屉，那么就能迅速找到我们需要的东西。

在计算机中，数据结构就是为了让数据的存储和操作变得有序和高效。

在02331 数据结构中，常见的数据结构包括数组、链表、栈、队列、树和图等。

数组是一种最简单也最常见的数据结构。

它就像一排连续的格子，每个格子都有固定的位置和编号。

优点是可以通过索引快速访问元素，但缺点是插入和删除元素比较麻烦，因为可能需要移动大量的数据。

链表则与数组不同，它的元素不是连续存储的，每个元素都包含了指向下一个元素的指针。

这使得链表在插入和删除元素时非常方便，只需要修改指针的指向即可，但访问特定位置的元素就需要从头开始遍历。

栈和队列是两种特殊的线性结构。

栈遵循“后进先出”的原则，就像往一个桶里放东西，最后放进去的会最先被拿出来。

而队列则是“先进先出”，就像排队买票，先到的先买。

树是一种分层的数据结构，其中最常见的是二叉树。

二叉树的每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉搜索树则是一种特殊的二叉树，它的左子树中的节点值都小于根节点的值，右子树中的节点值都大于根节点的值。

这使得在二叉搜索树中查找、插入和删除元素的效率很高。

图是一种更为复杂的数据结构，用于表示对象之间的关系。

图由顶点和边组成，边可以有权重，表示顶点之间的连接强度或距离。

学习 02331 数据结构，不仅仅是了解这些数据结构的定义和特点，更重要的是要学会如何在实际问题中选择合适的数据结构。

自考数据结构重点(珍藏版)自考数据结构重点(珍藏版)一、介绍数据结构是计算机科学中非常重要的概念，它涉及到组织、管理和存储数据的方法。

掌握数据结构的核心概念对于程序设计和算法的实现至关重要。

本文将介绍自考数据结构课程的重点内容，帮助您更好地理解和应用这些知识。

二、线性表1. 数组数组是最简单的一种数据结构，它是一种线性表的结构，其中的元素按照一定顺序排列。

我们可以通过数组下标来访问和修改对应位置的元素。

2. 链表链表是另一种常用的线性表结构，它由一系列节点组成。

每个节点包含数据和指向下一个节点的指针。

链表的优点是插入和删除操作的效率较高，但访问任意位置的元素需要遍历整个链表。

三、栈和队列1. 栈栈是一种具有后进先出（LIFO）特点的数据结构，主要包含入栈和出栈两种操作。

入栈将元素压入栈顶，出栈将栈顶元素移除。

2. 队列队列是一种具有先进先出（FIFO）特点的数据结构，主要包含入队和出队两种操作。

入队将元素插入队尾，出队将队头元素移除。

四、树树是一种自然且常用的数据结构，它具有层次结构和分支结构的特点。

1. 二叉树二叉树是树结构中最简单且常见的一种形式。

每个节点最多有两个子节点，分别是左子节点和右子节点。

2. 二叉搜索树二叉搜索树是一种特殊的二叉树，它的左子树中的值都小于根节点，右子树中的值都大于根节点。

这个特点使得二叉搜索树在查找和插入操作上有较高的效率。

五、图图是一种非线性的数据结构，它由节点和边组成。

图的节点可以表示不同的实体，边表示节点之间的联系。

1. 有向图和无向图有向图中的边有方向性，而无向图中的边没有方向性。

2. 最短路径算法最短路径算法用于计算两个节点之间的最短路径长度。

常见的最短路径算法包括迪杰斯特拉算法和弗洛伊德算法。

六、排序算法排序算法用于将一组数据按照特定顺序进行排列。

1. 冒泡排序冒泡排序通过交换相邻的元素来进行排序。

它重复地遍历数列，每次比较相邻的两个元素，将较大的元素移动到后面。

数据结构考试重点必背在数据结构考试中，掌握并熟练运用一些重点概念和知识点是非常关键的。

这些重点知识点不仅能够帮助我们对数据结构的基本概念有深入的理解，还能够在解决实际的编程问题中发挥重要作用。

本文将详细介绍数据结构考试中的一些重点知识点，供大家参考。

一、线性表1. 线性表的定义和基本操作：线性表是由n个数据元素构成的有限序列，其中n为表的长度。

基本操作包括插入、删除、查找等。

2. 顺序存储结构与链式存储结构：顺序存储结构使用数组实现，查找效率高；链式存储结构使用链表实现，插入删除效率高。

3. 单链表、双链表与循环链表：单链表每个节点只有一个指针指向下一个节点，双链表每个节点有两个指针分别指向前一个和下一个节点，循环链表将尾节点的指针指向头节点。

二、栈和队列1. 栈的定义和基本操作：栈是一种特殊的线性表，只允许在一端进行插入和删除操作，称为栈顶。

基本操作包括入栈和出栈。

2. 栈的应用：括号匹配、四则运算表达式求值、迷宫求解等。

3. 队列的定义和基本操作：队列是一种特殊的线性表，采用先进先出的原则。

基本操作包括入队和出队。

4. 队列的应用：生产者消费者问题、打印任务调度等。

三、树与二叉树1. 树的定义和基本概念：树是n（n >= 0）个节点的有限集合，其中存在唯一的根节点，其余节点构成m个互不相交的子集，每个集合本身又可以看作一棵树。

2. 二叉树的基本概念：二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别为左子节点和右子节点。

3. 二叉树的遍历方式：前序遍历、中序遍历和后序遍历。

遍历过程分别为先遍历根节点、先遍历左子树再遍历右子树、先遍历右子树再遍历左子树。

四、图1. 图的定义和基本概念：图是由节点和边组成的一种数据结构，用于描述事物之间的关系。

节点表示事物，边表示事物之间的联系。

2. 图的分类：无向图、有向图、带权图等。

3. 图的遍历方式：深度优先遍历和广度优先遍历。

深度优先遍历使用栈实现，广度优先遍历使用队列实现。

第1章概论(一) 课程内容1.1 引言1.2 数据、逻辑结构和运算1.3存储实现和运算实现(二) 学习的目的与要求本章集中介绍贯穿和应用与数据结构课程始终的基本概念和主要工具，概括反映了后继各章的基本问题，为进入具体内容的学习提供了必要的引导。

本章总的要求是：理解数据、数据元素和数据项的概念及其相互关系；理解逻辑结构、基本运算和数据结构的概念、意义和分类；理解存储结构与逻辑结构的关系；了解机内表示的级别和四种基本存储方式；理解算法的概念；了解算法分析的基本概念、时间复杂性及其量级的概念。

本章重点是逻辑结构和数据结构的概念。

难点是算法的时间复杂性分析。

第2章线性表(一) 课程内容2.1 线性表的基本慨念2.2 线性表的顺序实现2.3 线性表的链实现2.4 其它运算在单链表上的实现2.5 其它链表2.6 顺序实现与链接实现的比较2.7 串(二) 学习的目的与要求顺序表和单链表分别是最简单、基本的顺序存储结构和链式存储结构。

顺序表和单链表上实现基本运算的算法是数据结构中最简单、基本的算法。

这些内容构成以下各章的重要基础，因此本章是本课程的重点之一。

维持对本章有较高的要求：深刻理解线性结构的定义和特点；理解线性表的概念；熟练掌握顺序表和单链表的组织方法及实现基本运算的算法；掌握在顺序表和单链表上进行算法设计的基本技能；了解顺序表与链表的优缺点；了解串的概念、运算和存储方法。

本章重点：线性结构的定义和特点；线性表的运算；顺序表和单链表的组织方法和算法设计。

难点：单链表上的算法设计。

第3章栈、队列和数组(一) 课程内容3.1 栈3.2 队列3.3 数组3.4 综合应用示例栈和队列的逻辑结构与线性表的逻辑结构相同，二维数组逻辑结构可以看成是线性结构的推广；而它们的运算都可以看成是线性表运算的限制。

本章总的要求是：理解栈和队列的定义、特点及与线性表的异同；熟悉顺序栈和链栈的组织方法，队满、队空的判断条件及其描述；掌握链队的组织方法、算法并能自行设计其它简单算法。

1、二叉树并非是树的特殊情形，它们是两种不同的数据结构。

2、在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。

而在二叉树中，即使是一个孩子也有左右之分。

3、在直接插入排序中，每次取出的未排序数字是从后往前依次比较的。

如：对于记录(54,38,96,23,15,72,60,45,83)，当把第7个记录60插入时，需比较3 次。

解：前6个已排序好记录15,23,38,54,72,96，所以从后往前要比较96,72和54。

在快速排序中，前后的i和j是从后面的j开始比较的，比较者不动，被替换者后(前)移如：对于记录(51,22,83,46,75,18,68,30)解：第一趟划分：哨兵R[0]=i=51,先从j=30比较，30<51,30替换51，i=22，i≯51，后移i=83,83>51,83替换30，j=68，依次继续。

冒泡排序中，最好与最坏时间复杂度不相同。

无论待排序列是否有序(即不受数据初始状态影响)，时间复杂度都是O(n2)的排序算法是直接选择排序。

记录关键字比较次数与记录的初始排列次序无关的是直接选择排序。

在待排序的记录关键字序列基本有序的前提下，效率最高的排序方法是直接插入排序，效率最低的是快速排序。

2013.1.23对同一个基本有序的待排序序列分别进行堆排序、快速排序和冒泡排序，最省时间的是4、对于哈夫曼编码，应该先构造哈夫曼树：每次取权值最小的两个结点(包含新生成的结点)放一起生成新结点。

至于左右孩子之分，按照编码字出现的先后顺序去决定(还是左小右大)。

关于哈夫曼树的一些解释：哈夫曼树不唯一，和你左右子树的编码有关。

但最小带权路径长度唯一。

你记住每次都是从集合中寻找两个最小元素，权值相加之后形成的那个元素得重新放入集合参与新的比较。

递归下去生成的树才没有问题，否则弄不好就是一个单枝树上去了。

你最好采取我建议的规则，自己设置一个优先级。

自考02331数据结构重点总结(最终修订)第一章概论1.瑞士计算机科学家沃思提出：算法+数据结构=程序。

算法是对数据运算的描述，而数据结构包括逻辑结构和存储结构。

由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。

2.数据是信息的载体。

数据元素是数据的基本单位。

一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。

数据对象是具有相同性质的数据元素的集合。

3.数据结构指的是数据元素之间的相互关系，即数据的组织形式。

数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算①数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。

数据的逻辑结构分类:线性结构和非线性结构。

线性表是一个典型的线性结构。

栈、队列、串等都是线性结构。

数组、广义表、树和图等数据结构都是非线性结构。

②数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构）。

数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。

③数据的运算。

最常用的检索、插入、删除、更新、排序等。

4.数据的四种基本存储方法:顺序存储、链接存储、索引存储、散列存储（1）顺序存储：通常借助程序设计语言的数组描述。

（2）链接存储：通常借助于程序语言的指针来描述。

（3）索引存储：索引表由若干索引项组成。

关键字是能唯一标识一个元素的一个或多个数据项的组合。

（4）散列存储：该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。

5.算法必须满足5个准则：输入，0个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限步后结束；确定性，每一条指令的含义都明确；可行性，算法是可行的。

算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。

数据结构复习重点归纳（适于清华严版教材)一、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。

对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。

所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。

但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。

按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。

线性表：基础章节，必考内容之一。

考题多数为基本概念题，名校考题中，鲜有大型算法设计题。

如果有，也是与其它章节内容相结合。

栈和队列：基础章节，容易出基本概念题，必考内容之一。

而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。

串：基础章节，概念较为简单。

专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。

多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。

一般如果要出题，多数不会作为大题出。

数组常与“查找，排序”等章节结合来作为大题考查。

树和二叉树：重点难点章节，各校必考章节。

各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。

通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。

图：重点难点章节，名校尤爱考。

如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。

查找：重点难点章节，概念较多，联系较为紧密，容易混淆。

出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。

算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。

第1章概论1.数据结构的作用、意义、基本概念和术语，要求达到“识记”层次。

1.1数据结构所研究的内容；在计算机科学中的作用和意义；Wirth关于程序的定义公式。

1.2数据、数据元素、数据对象、数据项、数据结构等概念的定义。

1.3数据的逻辑结构、存储结构及数据运算的含义及其相互关系。

1.4数据结构的两大类逻辑结构和四种常用的存储表示方法。

2.算法的描述和分析，要求达到“领会”层次。

2.1算法、算法的时间复杂度和空间复杂度等概念。

2.2一个完整算法需要满足的五个准则；算法与程序的关系。

2.3算法的分析方法；对于一般算法能分析其时间复杂度。

第2章线性表1.线性表的逻辑结构，要求达到“识记”层次。

1.1线性表的逻辑定义和性质。

1.2线性表上定义的基本运算。

2.线性表的顺序存储结构和基本运算，要求达到“领会”层次。

2.1顺序表的定义及特点。

2.2顺序表上进行插入和删除操作的实现及时间性能分析。

2.3理解求顺序表逆置和极值及定位两种算法的实现过程。

3.线性表链式存储结构的不同形式及基本运算，要求达到“领会”层次。

3.1单链表、循环链表、双向链表的定义及特点。

3.2单链表上实现建表、查找、插入和删除等基本算法，并分析其时间复杂度。

3.3用尾指针表示单循环链表的意义。

3.4双向链表上的插入和删除操作。

4.利用顺序表和链表设计算法解决应用问题，要求达到“综合应用”层次。

5.顺序表和链表的比较，要求达到“领会”层次。

第3章栈和队列1.栈的逻辑结构、存储结构及相关算法，要求达到“简单应用”层次。

1.1栈的逻辑定义、特点及运算。

1.2顺序栈和链栈上实现进栈、退栈等基本运算。

1.3顺序栈的上溢和下溢问题，如何防止溢出。

2.队列的逻辑结构、存储结构及相关算法，要求达到“简单应用”层次。

2.1队列的逻辑定义、特点及运算。

2.2顺序循环队列的表述；队空和队满的判定；顺序循环队列上入队、出队等基本算法。

2.3链队列的表述；带头结点和不带头结点两种情况下链队列上的基本算法。