2021年自考02331数据结构重点总结最终修订
- 格式：doc
- 大小：1.62 MB
- 文档页数：28
下载文档原格式
合集下载
(完整版)数据结构知识点总结
数据结构知识点概括第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，可以由若干个数据项组成。
数据项是具有独立含义的最小标识单位。
数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。
·线性结构：一对一关系。
·线性结构：多对多关系。
·存储结构：是逻辑结构用计算机语言的实现。
·顺序存储结构：如数组。
·链式存储结构：如链表。
·索引存储结构：·稠密索引：每个结点都有索引项。
·稀疏索引：每组结点都有索引项。
·散列存储结构：如散列表。
·数据运算。
·对数据的操作。
定义在逻辑结构上，每种逻辑结构都有一个运算集合。
·常用的有：检索、插入、删除、更新、排序。
数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。
·结构类型：由用户借助于描述机制定义，是导出类型。
抽象数据类型ADT：·是抽象数据的组织和与之的操作。
相当于在概念层上描述问题。
·优点是将数据和操作封装在一起实现了信息隐藏。
程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。
算法取决于数据结构。
算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。
评价算法的好坏的因素：·算法是正确的；·执行算法的时间；·执行算法的存储空间（主要是辅助存储空间）；·算法易于理解、编码、调试。
时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。
渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。
评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。
算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。
时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。
数据结构复习重点归纳
一、数据结构得章节结构及重点构成数据结构学科得章节划分基本上为:概论,线性表,栈与队列,串，多维数组与广义表，树与二叉树，图，查找，内排,外排,文件,动态存储分配.对于绝大多数得学校而言,“外排,文件,动态存储分配”三章基本上就是不考得,在大多数高校得计算机本科教学过程中,这三章也就是基本上不作讲授得。
所以，大家在这三章上可以不必花费过多得精力,只要知道基本得概念即可。
但就是，对于报考名校特别就是该校又有在试卷中对这三章进行过考核得历史，那么这部分朋友就要留意这三章了。
按照以上我们给出得章节以及对后三章得介绍，数据结构得章节比重大致为：概论：内容很少,概念简单,分数大多只有几分，有得学校甚至不考.线性表:基础章节，必考内容之一。
考题多数为基本概念题，名校考题中，鲜有大型算法设计题.如果有，也就是与其它章节内容相结合.栈与队列：基础章节,容易出基本概念题，必考内容之一。
而相联系进行考查。
串：基础章节,概念较为简单.专门针对于此章得大型算法设计题很少，较常见得就是根据KMＰ进行算法分析。
多维数组及广义表:基础章节，基于数组得算法题也就是常见得,分数比例波动较大，就是出题得“可选单元”或“侯补单元”.一般如果要出题,多数不会作为大题出.数组常与“查找,排序”等章节结合来作为大题考查。
树与二叉树:重点难点章节，各校必考章节。
各校在此章出题得不同之处在于,就是否在本章中出一到两道大得算法设计题。
通过对多所学校得试卷分析,绝大多数学校在本章都曾有过出大型算法设计题得历史。
图:重点难点章节，名校尤爱考。
如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题得题型设计。
查找:重点难点章节,概念较多，联系较为紧密,容易混淆。
出题时可以作为分析型题目给出,在基本概念型题目中也较为常见。
算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。
排序:与查找一章类似,本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。
【2331】数据结构各章考试复习要点(打印版)
【2331】数据结构考试要点概论- 基本概念和术语（一）数据（Data）数据是信息的载体。
它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。
随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。
数据元素（Data Element）数据元素是数据的基本单位。
数据元素也称元素、结点、顶点、记录。
一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。
数据项是具有独立含义的最小标识单位。
数据结构（Data Structure）数据结构指的是数据之间的相互关系，即数据的组织形式。
1．数据结构一般包括以下三方面内容：①数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。
数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）；数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。
对机器语言而言，存储结构是具体的。
一般，只在高级语言的层次上讨论存储结构。
③数据的运算，即对数据施加的操作。
数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。
最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。
所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。
只有确定了存储结构之后，才考虑如何具体实现这些运算。
为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。
【例1．1】学生成绩表，见下表。
注意：在表中指出数据元素、数据项、开始结点和终端结点等概念（1）逻辑结构表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。
全国2021年10月数据结构试题及答案
全国2021年10月数据结构试题及答案课程代码：02331第一部份选择题(30分)一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。
1．算法指的是（）A．计算机程序 B．解决问题的计算方式C．排序算法 D．解决问题的有限运算序列2．线性表采用链式存储时，结点的存储地址（）A．必需是不持续的B．持续与否都可C．必需是持续的D．和头结点的存储地址相持续3．将长度为n的单链表链接在长度为m的单链表以后的算法的时间复杂度为（） A．O（1） B．O（n） C．O（m） D．O（m+n）4．由两个栈共享一个向量空间的益处是：（）A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢发生的机率C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢发生的机率5．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A．front=front+1 B．front=(front+1)%(m-1)C．front=(front-1)%m D．front=(front+1)%m6．如下陈述中正确的是（）A．串是一种特殊的线性表 B．串的长度必需大于零C．串中元素只能是字母 D．空串就是空白串7．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（）A．O（） B．O（n） C．O（n2） D．O（n3）8．一个非空广义表的表头（）A．不可能是子表 B．只能是子表C．只能是原子 D．可以是子表或原子9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表0 2 3 3 5对应的稀疏矩阵是（）10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )A．4 B．5 C．6 D．711．在含n个极点和e条边的无向图的邻接矩阵中,零元素的个数为( )A．e B．2e C．n2－e D．n2－2e12．假设一个有n个极点和e条弧的有向图用邻接表表示,则删除与某个极点vi相关的所有弧的时间复杂度是( )A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．用某种排序方式对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的转变情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方式是（）A．选择排序 B．希尔排序 C．归并排序 D．快速排序14．适于对动态查找表进行高效率查找的组织结构是（）A．有序表 B．分块有序表 C．三叉排序树 D．线性链表15．不定长文件是指（）A．文件的长度不固定 B．记录的长度不固定C．字段的长度不固定 D．关键字项的长度不固定第二部份非选择题（共70分）二、填空题（本大题共10小题，每小题2分，如有两个空格，每一个空格1分，共20分）不写解答进程，将正确的答案写在每小题的空格内。
数据结构必考知识点总结
数据结构必考知识点总结在准备考试时，了解数据结构的基本概念和相关算法是非常重要的。
以下是一些数据结构的必考知识点总结：1. 基本概念数据结构的基本概念是非常重要的，包括数据、数据元素、数据项、数据对象、数据类型、抽象数据类型等的概念。
了解这些概念有助于更好地理解数据结构的本质和作用。
2. 线性表线性表是数据结构中最基本的一种，它包括顺序表和链表两种实现方式。
顺序表是将数据元素存放在一块连续的存储空间内，而链表是将数据元素存放在若干个节点中，每个节点包含数据和指向下一个节点的指针。
了解线性表的概念和基本操作是非常重要的。
3. 栈和队列栈和队列是两种特殊的线性表，它们分别具有后进先出和先进先出的特性。
栈和队列的实现方式有多种，包括数组和链表。
掌握栈和队列的基本操作和应用是数据结构的基本内容之一。
4. 树结构树是一种非线性的数据结构，它包括二叉树、多路树、二叉搜索树等多种形式。
了解树的基本定义和遍历算法是必考的知识点。
5. 图结构图是一种非线性的数据结构，它包括有向图和无向图两种形式。
了解图的基本概念和相关算法是非常重要的，包括图的存储方式、遍历算法、最短路径算法等。
6. 排序算法排序是一个非常重要的算法问题，掌握各种排序算法的原理和实现方式是必不可少的。
常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。
7. 查找算法查找是另一个重要的算法问题，包括顺序查找、二分查找、哈希查找、树查找等。
了解各种查找算法的原理和实现方式是必考的知识点之一。
8. 算法复杂度分析算法的时间复杂度和空间复杂度是评价算法性能的重要指标，掌握复杂度分析的方法和技巧是非常重要的。
9. 抽象数据类型ADT是数据结构的一种概念模型，它包括数据的定义和基本操作的描述。
了解ADT的概念和实现方式是非常重要的。
10. 动态存储管理动态存储管理是数据结构中一个重要的问题，包括内存分配、内存释放、内存回收等。
了解动态存储管理的基本原理和实现方式是必考的知识点之一。
自考02331数据结构大纲
第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链队列的表述;带头结点和不带头结点两种情况下链队列上的基本算法。
数据结构重点整理
数据结构重点整理简介数据结构是计算机科学中的重要概念，指的是组织和存储数据的方式。
本文整理了数据结构的重点内容，包括以下章节：1. 数组2. 链表3. 栈4. 队列5. 树6. 图7. 哈希表8. 堆9. 排序算法10. 查找算法1. 数组1.1 定义和基本操作- 数组是一种线性数据结构，用于存储一组相同类型的元素。
每个元素可以通过索引访问。
- 基本操作包括：创建数组、访问元素、修改元素、插入元素、删除元素、获取数组长度等。
1.2 复杂度分析- 时间复杂度：对于不同操作，如访问、插入、删除等，时间复杂度可能不同。
- 空间复杂度：数组的存储空间通常为固定大小，空间复杂度为O(n)。
2. 链表2.1 定义和基本操作- 链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
- 基本操作包括：创建链表、插入节点、删除节点、访问节点、反转链表等。
2.2 复杂度分析- 时间复杂度：链表的操作时间复杂度与操作位置有关，访问节点的时间复杂度为O(n)。
- 空间复杂度：链表的空间复杂度为O(n)。
3. 栈3.1 定义和基本操作- 栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。
- 基本操作包括：入栈、出栈、获取栈顶元素、判断栈是否为空等。
3.2 应用场景- 括号匹配- 表达式求值- 浏览器的前进和后退功能4. 队列4.1 定义和基本操作- 队列是一种先进先出（FIFO）的数据结构，可以在队尾插入元素，在队头删除元素。
- 基本操作包括：入队、出队、获取队头元素、判断队列是否为空等。
4.2 应用场景- 广度优先搜索（BFS）- 缓存5. 树5.1 定义和基本操作- 树是一种非线性数据结构，由节点和边组成，每个节点可以有多个子节点。
- 基本操作包括：创建树、插入节点、删除节点、遍历树等。
5.2 常见的树结构- 二叉树：每个节点最多有两个子节点。
- 二叉搜索树：左子树的键值小于根节点，右子树的键值大于根节点。
《数据结构》知识点总结
《数据结构》知识点总结数据结构知识点总结数据结构是计算机科学的重要基础学科，它研究各种数据元素之间的关系、组织和存储方式，以及在不同操作下的效率和性能。
掌握数据结构的基本概念和常见算法，对于编程和软件开发等领域都具有重要的意义。
本文将对数据结构的一些关键知识点进行总结和说明。
一、线性表线性表是数据结构中最基本和常见的一种类型，它包含了一组按顺序排列的元素。
线性表常见的表示方法有数组和链表两种。
1.1 数组数组是一段连续的内存空间，其中的元素通过索引来访问。
数组具有随机访问的特性，插入和删除元素的效率较低。
1.2 链表链表是由一系列节点构成，每个节点包含了数据和指向下一个节点的指针。
链表的插入和删除操作具有较高的效率，但随机访问的效率较低。
二、栈和队列栈和队列是两种特殊的线性表，它们限制了数据的插入和删除位置，使得操作具有明确的顺序。
2.1 栈栈是一种后进先出（LIFO）的数据结构，只允许在栈的顶端进行插入和删除操作。
栈的应用场景包括函数调用、表达式求值等。
2.2 队列队列是一种先进先出（FIFO）的数据结构，只允许在队列的一端插入元素，在另一端删除元素。
队列可以用于实现广度优先搜索、任务调度等。
三、树树是一种非线性的数据结构，它由一系列的节点和边构成。
树的组织方式使得运算效率更高，常见的树结构包括二叉树、堆和二叉搜索树等。
3.1 二叉树二叉树是一种每个节点最多有两个子节点的树结构。
它的遍历方式包括前序、中序和后序遍历，常用于表达式求值、文件系统等的表示和操作。
3.2 堆堆是一种特殊的树结构，它满足堆序性质，即父节点的键值总是大于（或小于）子节点的键值。
堆常用于实现优先队列和排序算法。
3.3 二叉搜索树二叉搜索树是一种有序的二叉树，它的左子树中的节点键值都小于根节点的键值，右子树中的节点键值都大于根节点的键值。
二叉搜索树可用于高效地进行查找、插入和删除操作。
四、图图是一种由节点和边构成的非线性数据结构，它用于描述事物之间的相关关系。
2331数据结构自考大纲
第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 综合应用示例栈和队列的逻辑结构与线性表的逻辑结构相同，二维数组逻辑结构可以看成是线性结构的推广；而它们的运算都可以看成是线性表运算的限制。
本章总的要求是：理解栈和队列的定义、特点及与线性表的异同；熟悉顺序栈和链栈的组织方法，队满、队空的判断条件及其描述；掌握链队的组织方法、算法并能自行设计其它简单算法。
10月自考数据结构02331试题及答案解析
10月自考数据结构02331试题及答案解析10月自考数据结构02331试题及答案解析lO月高等教育自学考试全国统一命题考试数据结构试卷(课程代码02331)本试卷共8页。
满分l00分。
考试时间l50分钟。
考生答题注意事项：1．本卷所有试题必须在答题卡上作答。
答在试卷上无效，试卷空白处和背面均可作草稿纸. 2．第一部分为选择题。
必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。
3．第二部分为非选择题。
必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。
4．合理安排答题空间．超出答题区域无效。
第一部分选择题一、单项选择题(本大题共l5小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。
未涂、错涂或多涂均无分。
1．下列选项中，不属于线性结构的是A．网 B．栈 C．队列D．线性表2．长度为n的顺序表，删除位置i上的元素(0≤i≤n一1)，需要移动的元素个数为A．n—i B．n—i—l C．i D．i+13．栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是A．顺序栈需要判定栈空，链栈也需要判定B．顺序栈需要判定栈空，而链栈不需要判定C．顺序栈不需要判定栈空，而链栈需要判定D．顺序栈不需要判定栈空，链栈也不需要判定4．若一个栈以数组V[0．．n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是A．top=top+1；V[top]=x B．V[top]=x；top=top+1 C．top=top一1；V[mp]=x D．V[top]=x；top=top—l 5．在二维数组a[9][10]中：每个数组元素占用3个存储空间，从首地址SA开始按行优先连续存放，则元素a[8][5]的起始地址是A．SA+141 B．SA+144 C．SA+222 D．SA+2556．广义表A=(x，((y)，((a))，A))的深度是A．2 B．3 C．4 D．∞7．一棵左子树为空的二叉树在前序线索化后，其空指针域个数为A．0 B．1 C．2 D．不确定8．下列关于哈夫曼树的叙述中，错误的是A．用n个结点构造的哈夫曼树是唯一的B．哈夫曼树中只有度为0或度为2的结点C．树中两个权值最小的结点可能是兄弟结点D．同一结点集构造的二叉树中，哈夫曼树的WPL最小9．6个顶点的强连通图中，含有的边数至少是A．4 B．5 C．6 D．710．对题l0图进行深度优先搜索遍历，下列选项中，正确的遍历序列是12．有向图采用邻接矩阵存储，某一行中非零元素的个数等于A．对应顶点v的度B．对应顶点v的出度C．对应顶点v的入度D．依附于对应顶点v的边数13．下列选项中，符合堆定义的是A．{102，24，55，60，89，93}B．{24，89，55，60，93，102}C．{102，93，55，60，89，24}D．{102，60。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
自考02331数据构造重点总结(最后修订)第一章概论1.瑞士计算机科学家沃思提出：算法+数据构造=程序。
算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。
由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。
2.数据是信息载体。
数据元素是数据基本单位。
一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。
数据对象是具备相似性质数据元素集合。
3.数据构造指是数据元素之间互有关系，即数据组织形式。
数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。
数据逻辑构造分类：线性构造和非线性构造。
线性表是一种典型线性构造。
栈、队列、串等都是线性构造。
数组、广义表、树和图等数据构造都是非线性构造。
②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。
数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。
③数据运算。
最惯用检索、插入、删除、更新、排序等。
4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储（1）顺序存储：普通借助程序设计语言数组描述。
（2）链接存储：普通借助于程序语言指针来描述。
（3）索引存储：索引表由若干索引项构成。
核心字是能唯一标记一种元素一种或各种数据项组合。
（4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。
5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。
算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。
当前惯用描述算法语言有两类：类Pascal和类C。
6.评价算法优劣：算法"对的性"是一方面要考虑。
此外，重要考虑如下三点：①执行算法所耗费时间，即时间复杂性；②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性；③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。
以上几点最重要是时间复杂性，时间复杂度惯用渐进时间复杂度表达。
7.算法求解问题输入量称为问题规模,用一种正整数n表达。
8.常用时间复杂度按数量级递增排列依次为：常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(n k)、指数阶0(2n)和阶乘阶0(n!)。
9.一种算法空间复杂度S(n)定义为该算法所耗费存储空间，它是问题规模n函数,它涉及存储算法自身所占存储空间、算法输入输出数据所占存储空间和算法在运营过程中暂时占用存储空间。
第二章线性表1.数据运算是定义在逻辑构造上，而运算详细实现是在存储构造上进行。
2.只要拟定了线性表存储起始位置，线性表中任意一种元素都可随机存取，因此顺序表是一种随机存取构造。
3.常用线性表基本运算:(1)置空表InitList（L）构造一种空线性表L。
(2)求表长ListLength（L）求线性表L中结点个数，即求表长。
(3)GetNode（L，i）取线性表L中第i个元素。
(4)LocateNode（L，x）在L中查找第一种值为x 元素，并返回该元素在L中位置。
若L中没有元素值为x ，则返回0值。
(5)InsertList（L，i，x）在线性表L第i个元素之前插入一种值为x 新元素，表L长度加1。
(6)DeleteList（L，i）删除线性表L第i个元素，删除后表L长度减1。
4.顺序存储办法：把线性表数据元素按逻辑顺序依次存储在一组地址持续存储单元里办法。
顺序表（Sequential List）：用顺序存储办法存储线性表称为顺序表。
顺序表是一种随机存取构造,顺序表特点是逻辑上相邻结点其物理位置亦相邻。
顺序表中结点a i存储地址：LOC（a i）= LOC（a1）+（i-1）*c 1≤i≤n，5.顺序表上实现基本运算：（1）插入：该算法平均时间复杂度是O(n)，即在顺序表上进行插入运算，平均要移动一半结点（n/2）。
在第i个位置插入一种结点移动次数为n-i+1（2）删除：顺序表上做删除运算，平均要移动表中约一半结点（n-1）/2，平均时间复杂度也是O(n)。
删除第i个结点移动次数为n-i6.采用链式存储构造可以避免频繁移动大量元素。
一种单链表可由头指针唯一拟定，因而单链表可以用头指针名字来命名。
①生成结点变量原则函数 p=( ListNode *)malloc(sizeof(ListNode))； //函数malloc分派一种类型为ListNode 结点变量空间,并将其首地址放入指针变量p中②释放结点变量空间原则函数free(p)；//释放p所指结点变量空间③结点分量访问办法二：p-﹥data和p-﹥next④指针变量p和结点变量*p关系：指针变量p值——结点地址，结点变量*p值——结点内容7.建立单链表：（1）头插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode));①//生成新结点p->data=ch;② //将读入数据放入新结点数据域中p->next=head;③ head=p;④（2）尾插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode))；①//生成新结点p->data=ch; ② //将读入数据放入新结点数据域中if (head==NULL) head=p;//新结点插入空表else rear->next=p;③//将新结点插到*r之后rear=p;④//尾指针指向新表尾（3）尾插法建带头结点单链表：头结点及作用：头结点是在链表开始结点之前附加一种结点。
它具备两个长处:⒈由于开始结点位置被存储在头结点指针域中,因此在链表第一种位置上操作就和在表其他位置上操作一致,不必进行特殊解决;⒉无论链表与否为空，其头指针都是指向头结点非空指针（空表中头结点指针域空），因而空表和非空表解决也就统一了。
头结点数据域阴影表达该某些不存储信息。
在有应用中可用于存储表长等附加信息。
详细算法：r=head;// 尾指针初值也指向头结点while((ch=getchar())!='\n'){s=(ListNode *)malloc(sizeof(ListNode));//生成新结点s->data=ch; //将读入数据放入新结点数据域中r->next=s;r=s;}r->next=NULL;//终端结点指针域置空，或空表头结点指针域置空以上三个算法时间复杂度均为O(n)。
8.单链表上查找：（带头结点）（1）按结点序号查找：序号为0是头结点。
算法：p=head;j=0;//从头结点开始扫描while(p->next&&j<i){//顺指针向后扫描，直到p->next为NULL或i=j为止p=p->next;j++;}if(i==j) return p;//找到了第i个结点else return NULL;//当i<0或i>0时，找不到第i个结点时间复杂度：在等概率假设下，平均时间复杂度为：为n/2=O(n)（2）按结点值查找：详细算法：ListNode *p=head->next;//从开始结点比较。
表非空，p初始值指向开始结点 while(p&&p->data!=key)//直到p为NULL或p->data为key为止p=p->next;//扫描下一结点return p;//若p=NULL，则查找失败，否则p指向值为key结点时间复杂度为：O(n)9.插入运算：插入运算是将值为x新结点插入到表第i个结点位置上，即插入到a i-1与a i之间。
s=(ListNode *)malloc(sizeof(ListNode))；② s->data=x;③ s->next=p->next;④ p->next=s;⑤算法时间重要耗费在查找结点上，故时间复杂度亦为O(n)。
10.删除运算r=p->next;②//使r指向被删除结点a i p->next=r->next③;//将a i从链上摘下free(r);④//释放结点a i空间给存储池算法时间复杂度也是O（n）.p指向被删除前一种结点。
链表上实现插入和删除运算，不必移动结点，仅需修改指针。
11.单循环链表—在单链表中，将终端结点指针域NULL改为指向表头结点或开始结点即可。
判断空链表条件是head==head->next;12.仅设尾指针单循环链表：用尾指针rear表达单循环链表对开始结点a1和终端结点a n查找时间都是O(1)。
而表操作经常是在表首尾位置上进行，因而，实用中多采用尾指针表达单循环链表。
判断空链表条件为rear==rear->next;13.循环链表：循环链表特点是不必增长存储量，仅对表链接方式稍作变化，即可使得表解决更加以便灵活。
若在尾指针表达单循环链表上实现，则只需修改指针，不必遍历，其执行时间是O(1)。
详细算法：LinkList Connect(LinkList A,LinkList B) {//假设A，B为非空循环链表尾指针LinkList p=A->next;//①保存A表头结点位置A->next=B->next->next;//②B表开始结点链接到A表尾free(B->next);//③释放B表头结点B->next=p;//④return B;//返回新循环链表尾指针循环链表中没有NULL指针。
涉及遍历操作时，其终结条件就不再是像非循环链表那样鉴别p或p-＞next与否为空，而是鉴别它们与否等于某一指定指针，如头指针或尾指针等。
在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前其他结点。
而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一长处使某些运算在单循环链表上易于实现。
14.双向链表：双（向）链表中有两条方向不同链，即每个结点中除next域存储后继结点地址外，还增长一种指向其直接前趋指针域prior。
①双链表由头指针head惟一拟定。
②带头结点双链表某些运算变得以便。
③将头结点和尾结点链接起来，为双（向）循环链表。
15.双向链表前插和删除本结点操作①双链表前插操作void DInsertBefore(DListNode *p,DataType x){//在带头结点双链表中，将值为x新结点插入*p之前，设p≠NULL DListNode *s=malloc(sizeof(DListNode));//①s->data=x;//②s->prior=p->prior;//③s->next=p;//④p->prior->next=s;//⑤p->prior=s;//⑥}②双链表上删除结点*p自身操作void DDeleteNode(DListNode *p){//在带头结点双链表中，删除结点*p，设*p为非终端结点p->prior->next=p->next;//①p->next->prior=p->prior;//②free(p)；}//③与单链表上插入和删除操作不同是，在双链表中插入和删除必要同步修改两个方向上指针。