数据结构基础知识（数据结构基础知识点）

本篇文章给大家谈谈数据结构基础知识，以及数据结构基础知识点对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、计算机二级公共基础知识是什么啊
• 2、有没有数据结构(C语言版)的资料
• 3、数据结构基础知识：环、简单环、回路求助
• 4、数据结构与算法知识？
• 5、数据结构知识点

计算机二级公共基础知识是什么啊

一、基本数据结构与算法：

1、算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。

2、数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。

3、线性表的定义;线性表的顺序存储结构及其插入与删除运算。

4、栈和队列的定义;栈和队列的顺序存储结构及其基本运算。

5、线性单链表、双向链表与循环链表的结构及其基本运算。

6、树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。

7、顺序查找与二分法查找算法;基本排序算法(交换类排序，选择类排序，插入类亮让排序)。

二、程序设计基础：

1、程序设计方法与风格。

2、结构化程序设计。

3、面向对象的程序设计方法，对象，方法，属性及继承与多态性。

三、软件工程基础：

1、软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。

2、结构化分析方法，数据流图，数据字典，软件需求规格说明书。

3、结构化设计方法，总体设计与详细设计。

4、软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。

5、程序的调试，静态调试与报考调试。

四、数据库设计基础：

1、数据库的基本概念：数据库，数据库管理系统，数据库系统。

2、数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。

3、关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。

4、数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。

扩展资料：

计算机二级计分体制：

考试实行百分制计分，但以等级分数通知考生成绩。等级分数分为“不及格”、“及格”、“优秀”三等，划线分数为60和90。考试成绩在“及格”，即60~89分者，由教育部考试中心发合格证书，考试成绩在“优秀”，即90~100分者，由教育部考试中心发优秀敬轿局证书。

自2018年3月起，NCRE考试以等第形式通知考生成绩。成绩等第分为“优秀”、“良好”、“及格”、“不及格”四等。100-90分帆稿为“优秀”，89-80分为“良好”，79-60分为“及格”，59-0分为“不及格”。考试成绩优秀者，在证书上注明“优秀”字样；考试成绩良好者，在证书上注明“良好”字样；考试成绩及格者，在证书上注明“合格”字样。

参考资料来源：百度百科-计算机二级

参考资料来源：NCRE-中国教育考试网

[img]

有没有数据结构(C语言版)的资料

数据结构复习重点归纳笔记[清华严蔚敏版]

数据结构复习重点归纳[适于清华严版教材]

一、数据结构的章节结构及重点构成

数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。

对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。

按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：

概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。

线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题。如果有，也是与其它章节内容相结合。

栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。

串 ：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据KMP进数顷行算法分析。

多维数组及广义表

：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与“查找，排序”等章节结合来作为大题考查。

树和二叉树

：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。

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

查找

：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。

排序

：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。

二、数据结构各章节重点勾划：

第0章 概述

本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点：数据结构的基本概念，时间和空间复杂度的概念及度量方法，算法设计时的注意事项。本章考点不多，只要稍加注意理解即可。

第一章 线性表

作为线性结构的开篇章节，线性表一章在线性结磨贺构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。

总体来说，线性表一章可供考查的重要考点有以下几个方面：

1.线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。

2.线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。

3.线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动态分配。静态链表与顺序表的相似及不同之处。

4.线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。此外，近年来在不少学校中还多次出现要求用递归算法实现单链表输出（可能是顺序也可能是倒序）的问题。

在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的方式是不一样的，请大家注意。

5.线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。

第二章 栈与队列

栈与队列，是很多学习DS的同学遇到第一薯游陆只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。所以，理解栈与队列，是走向DS高手的一条必由之路，。

学习此章前，你可以问一下自己是不是已经知道了以下几点：

1.栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据（请注意包括：存和取两部分）的特点。

2.递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，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个结点的完全二叉树的深度，顺序存储二叉树时孩子结点与父结点之间的换算关系（左为：2*i，右为：2*i+1）。

二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。

2.二叉树的三种遍历算法

这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以直接根据三种递归算法改造而来（比如：求叶子个数），所以，掌握了三种遍历的非递归算法后，对付诸如：“利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。我会在另一篇系列文章（;bp=2bt=0）里给出三种遍历的递归和非递归算法的背记版，到时请大家一定熟记。

3.可在三种遍历算法的基础上改造完成的其它二叉树算法：

求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。

4.线索二叉树：

线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题）。

5.最优二叉树（哈夫曼树）：

最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，属送分题。

6.树与森林：

二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树，这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树。但是，对于普通的双分支树而言，不具有这种性质。

树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后根（对于森林而言称作：先序与后序遍历）。在难度比较大的考试中，也有基于此二种算法的基础上再进行扩展要求你利用这两种算法设计其它算法的，但一般院校很少有这种考法，最多只是要求你根据先根或后根写出他们的遍历序列。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。这一点成为很多学校的考点，考查的方式不一而足，有的直接考此句话，有的是先让你求解遍历序列然后回答这个问题。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表存储孩子及兄弟。

树一章，处处是重点，道道是考题，大家务必个个过关。

第六章 图

如果说，从线性结构向树形结构研究的转变，是数据结构学科对数据组织形式研究的一次升华，那么从树形结构的研究转到图形结构的研究，则进一步让我们看到了数据结构对于解决实际问题的重大推动作用。

图这一章的特点是：概念繁多，与离散数学中图的概念联系紧密，算法复杂，极易被考到，且容易出大题，尤其是名校，作为考研课程，如果不考查树与图两章的知识，几乎是不可想像的。

下面我们看一下图这一章的主要考点以及这些考点的考查方式：

1.考查有关图的基本概念问题：

这些概念是进行图一章学习的基础，这一章的概念包括：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等概念。与这些概念相联系的相关计算题也应该掌握。

2.考查图的几种存储形式：

图的存储形式包括：邻接矩阵，（逆）邻接表，十字链表及邻接多重表。在考查时，有的学校是给出一种存储形式，要求考生用算法或手写出与给定的结构相对应的该图的另一种存储形式。

3.考查图的两种遍历算法：深度遍历和广度遍历

深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点间是否存在长为K的简单路径问题”，就分别用到了广度遍历和深度遍历算法。

4.生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法。

考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。

5.拓扑排序问题：

拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。当然，后一种排序出来的结果是“逆拓扑有序”的。

6.关键路径问题：

这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。这个问题拿来直接考算法源码的不多，一般是要求按照书上的算法描述求解的过程和步骤。

在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为0。关键路径问题是工程进度控制的重要方法，具有很强的实用性。

7.最短路径问题：

与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法。注意区分。

第七章 查找

在不少数据结构的教材中，是把查找与排序放入高级数据结构中的。应该说，查找和排序两章是前面我们所学的知识的综合运用，用到了树、也用到了链表等知识，对这些数据结构某一方面的运用就构成了查找和排序。

现实生活中，search几乎无处不在，特别是现在的网络时代，万事离不开search，小到文档内文字的搜索，大到INTERNET上的搜索，search占据了我们上网的大部分时间。

在复习这一章的知识时，你需要先弄清楚以下几个概念：

关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的ASL值，应该记住。

在DS的教材中，一般将search分为三类：1st，在顺序表上的查找；2nd，在树表上的查找；3rd，在哈希表上的查找。下面详细介绍其考查知识点及考查方式：

1.线性表上的查找：

主要分为三种线性结构：顺序表，有序顺序表，索引顺序表。对于第一种，我们采用传统查找方法，逐个比较。对于及有序顺序表我们采用二分查找法。对于第三种索引结构，我们采用索引查找算法。考生需要注意这三种表下的ASL值以及三种算法的实现。其中，二分查找还要特别注意适用条件以及其递归实现方法。

2.树表上的查找：

这是本章的重点和难点。由于这一节介绍的内容是使用树表进行的查找，所以很容易与树一间的某些概念相混淆。本节内容与树一章的内容有联系，但也有很多不同，应注意规纳。树表主要分为以下几种：二叉排序树，平衡二叉树，B树，键树。其中，尤以前两种结构为重，也有部分名校偏爱考B树的。由于二叉排序树与平衡二叉树是一种特殊的二叉树，所以与二叉树的联系就更为紧密，二叉树一章学好了，这里也就不难了。

二叉排序树，简言之，就是“左小右大”，它的中序遍历结果是一个递增的有序序列。平衡二叉树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1。对于二叉排序树，“判断某棵二叉树是否二叉排序树”这一算法经常被考到，可用递归，也可以用非递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，所以应该掌握平衡二叉树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。

B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉....排序树。除B树的查找算法外，应该特别注意一下B树的插入和删除算法。因为这两种算法涉及到B树结点的分裂和合并，是一个难点。B树是报考名校的同学应该关注的焦点之一。

键树也称字符树，特别适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。

3.基本哈希表的查找算法：

哈希一词，是外来词，译自“hash”一词，意为：散列或杂凑的意思。哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个function，该函数对关键字进行转换后，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。

第八章 内部排序

内排是DS课程中最后一个重要的章节，建立在此章之上的考题可以有多种类型：填空，选择，判断乃至大型算法题。但是，归结到一点，就是考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标（时间复杂度）能否了如指掌。

这一章，我们对重点的规纳将跟以上各章不同。我们将从以下几个侧面来对排序一章进行不同的规纳，以期能更全面的理解排序一章的总体结构及各种算法。

从排序算法的种类来分，本章主要阐述了以下几种排序方法：插入、选择、交换、归并、计数等五种排序方法。

其中，在插入排序中又可分为：直接插入、折半插入、2路插入、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找。希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。

交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。快速排序，在处理的“问题规模”这个概念上，与希尔有点相反，快速排序，是先处理一个较大规模，然后逐渐把处理的规模降低，最终达到排序的目的。

选择排序，相对于前面几种排序算法来说，难度大一点。具体来说，它可以分为：简单选择、树选择、堆排。这三种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数；树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大（小）者，最终选出最小（大）数；而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。树选择排序，也曾经在一些学校中的大型算法题中出现，请大家注意。

归并排序，故名思义，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。

基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排序（扑克牌排序），链式排序（整数排序）。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。

本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的，学习时要多注意规纳、总结、对比。此外，对于教材中的10.7节，要求必须熟记，在理解的基础上记忆，这一节几乎成为很多学校每年的必考点。

至此，数据结构所有章节的章节重点问题，我们已经规纳完毕，使用清华严版教材的同学，在复习的同时，可以参照本贴给出的重点进行复习。但是，由于作者本人水平有限，可能有很多考点没有规纳出来，也可能有些考点规纳有误，在此，作者本人诚恳希望诸位朋友直面提出，我会不断完善和发布新的关于数据结构复习的总结以及笔记

严蔚敏数据结构为主的笔记二

第二章：线性表(包括习题与答案及要点)

--------------------------------------------------------------------------------

本章的重点是掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。

要求达到识记层次的内容有:线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。

要求达到综合应用层次的内容有：顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析，解决简单应用问题。

链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。

要求达到领会层次的内容就是顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。

--------------------------------------------------------------------------------

线性表的逻辑结构特征是很容易理解的，如其名，它的逻辑结构特征就好象是一条线，上面打了一个个结，很形象的，如果这条线上面有结，那么它就是非空表，只能有一个开始结点，有且只能有一个终端结点，其它的结前后所相邻的也只能是一个结点(直接前趋和直接后继)。

关于线性表上定义的基本运算，主要有构造空表、求表长、取结点、查找、插入、删除等。

--------------------------------------------------------------------------------

线性表的逻辑结构和存储结构之间的关系。在计算机中，如何把线性表的结点存放到存储单元中，就有许多方法，最简单的方法就是按顺序存储。就是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。

在顺序表中实现的基本运算主要讨论了插入和删除两种运算。相关的算法我们通过练习掌握。对于顺序表的插入和删除运算，其平均时间复杂度均为O(n)。

--------------------------------------------------------------------------------

线性表的链式存储结构。它与顺序表不同，链表是用一组任意的存储单元来存放线性表的结点，这组存储单元可以分布在内存中任何位置上。因此，链表中结点的逻辑次序和物理次序不一定相同。所以为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息(即

数据结构基础知识：环、简单环、回路求助

环是数据结构的概念通过指针把数据头尾相连起来就构成环，按功能应该有单向环、双向咐迹环两种。而回路应该游简携是电学的概念，一个信号发出去，经过若干节点后，信号能回到起始点，这个路径叫一个回路，所以回路是单向的，就可以称回路。因为电位差的神伏缘故，回路不可能是双向的，信号不可能由负极回到正极。

数据结构与算法知识？

对于大多数的程序员来说，在学习数据分析等技术的时候需要先了解关于数据结构以及算法等知识点，下面我们就给大家简单介绍一下什么是数据结构?什么是算法?

大部分数据结构和算法教材，在开篇都会给这两个概嫌唯乱念下一个明确的定义。但是，这些定义都很抽象，对理解这两个概念并没有实质山旁性的帮助，反倒会让你陷入死抠定义的误区。毕竟，我们现在学习，并不是为了考试，所以，概念背得再牢，不会用也就没什么用。

虽然我们说没必要深挖严格的定义，但是这并不等于不需要理解概念。下面我就从广义和狭义两个层面，来帮你理解数据结构与算法这两个概念。

从广义上讲，数据结构就是指一组数据的芹档存储结构。算法就是操作数据的一组方法。

图书馆储藏书籍你肯定见过吧?为了方便查找，图书管理员一般会将书籍分门别类进行“存储”。按照一定规律编号，就是书籍这种“数据”的存储结构。

那我们如何来查找一本书呢?有很多种办法，你当然可以一本一本地找，也可以先根据书籍类别的编号，是人文，还是科学、计算机，来定位书架，然后再依次查找。笼统地说，这些查找方法都是算法。

从狭义上讲，也就是我们专栏要讲的，是指某些著名的数据结构和算法，比如队列、栈、堆、二分查找、动态规划等。这些都是前人智慧的结晶，我们可以直接拿来用。我们要讲的这些数据结构和算法，都是前人从很多实际操作场景中抽象出来的，经过非常多的求证和检验，可以高效地帮助我们解决很多实际的开发问题。

那数据结构和算法有什么关系呢?为什么大部分书都把这两个东西放到一块儿来讲呢?

这是因为，数据结构和算法是相辅相成的。数据结构是为算法服务的，算法要作用在特定的数据结构之上。因此，我们无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。

比如，因为数组具有随机访问的特点，常用的二分查找算法需要用数组来存储数据。但如果IT培训选择链表这种数据结构，二分查找算法就无法工作了，因为链表并不支持随机访问。

数据结构是静态的，它只是组织数据的一种方式。如果不在它的基础上操作、构建算法，孤立存在的数据结构就是没用的。

数据结构知识点

1、继承不同

HashMap继承了AbstractMap，AbstractMap实现了Map接口

HashTable继承了Dictionary类

2、线程安全不同

HashMap不是线程安全的，HashTable是线程安全的

3、允许祥纤null值

HashMap允许key和value为空，而HashTable不允许

4、遍历方式实现不同

HashMap的迭代器是fail-fast迭代器，HashTable的enumerator迭代器不是fail-fast的

5、哈希值的使用不同

HashMap重新计算哈希值，HashTable直接使用对象的哈希值

6、初始容量和扩容方式不同

HashMap初始大小为16，扩容大小一定是2的指数

HashTable初始大雹宴陪小为11，扩容大小为old*2+1

7、hashmap新增红黑树结构

当碰撞链表过长时，就把链表转为红黑树

1、直接定址法

取关键字或关键字的某个线性函数值为散列地址

特点：关键字连续时较方便，但关键字不连续时将造成内存单元的大量浪费

2、数字分析法

取关键字中取值比较均匀的若干数位作为哈希值。

特点：适用于关键字全部已知，并要对关键字中每一位进行分析

3、平方取中法

取关键字平方后中间几位作为哈希地址

特点：因为平均值的中间部分跟关键字的每一位都有关，出现随机值的概率较大

4、分段叠加法

按哈希表地址位数将哈希表分为位数相等的几段（最后一段可以较短），然后将这几部分相加，舍弃最高位的进位得到哈希值。

具体分为：移位法与折叠法

移位法：将每部分低位对其相加

折叠法：从一段向另一端沿分割线来回折叠（奇数段为正序，偶数段为倒序）

例如关键字123603247112020,哈希表长度为1000，则应把关键字分成3位一段

移位法得到105，折叠法得到907

5、伪随机数法

采用伪随机函数作为哈希函数

6、除留余数法

用关键字除以某个不大于哈希表长度的数，取余数作为哈希值。

1、开放定址法

当关键字key的哈希值p=H（key）出现冲突时，以p为基础产生新的哈希值p1，如果p1仍冲突，则产生p2，以此类推。

函数形式如下：

Hi = (H(key) + di) % m

根据di的不同分为

（1）线性探测

di = 1， 2， 3， …… ，（m-1）

（2）平方探测

d i =1 2 ，-1 2 ，2 2 ，-2 2 ，…，k 2 ，-k 2 ( k=m/2 )

（3）伪随机探测

di = 伪随机数序列

2、再哈希法

构造多个不同的哈希函数，当出现冲突时，使用新的哈希函数

3、链地址法

将散列到同一位置的冲突元素存入一个链表中

4、建立一个公共溢出区

将哈希表分为基本表和源蠢溢出表

左旋：

右旋

红黑树是一颗特殊的二叉查找树，除了二叉查找树的所有性质

1、若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值

2、若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值

3、任意节点的左右子树也为二叉查找树

4、没有键值相等的节点

还满足

1、每个节点要么是红的要么是黑的

2、根节点是黑的

3、每个叶节点（null节点）是黑的

4、如果一个节点是红的，那么它的两个儿子都是黑的

5、任意节点到叶节点（null节点）的每条路径都包含相同数目的黑节点

红黑树保证没有一条路径比另一条路径长出两倍，保证了自身是接近平衡的二叉树，能保证在最坏的情况下查找的时间复杂度为O（logN），而二叉查找树最坏为O（N）

红黑树牺牲了严格的高度平衡为代价，只要求部分达到部分平衡条件，降低了对旋转的要求，从而提高了性能。红黑树能够以O（logN）的时间复杂度进行添加，删除，查找。由于它的设计，任何不平衡都可以在三次旋转之内解决。

1、相比BST（二叉搜索树）

红黑树的最长路径不大于最短路径两倍，保证了最差搜索效率为O（logN）,而二叉搜索树最差效率会达到O（N）

2、相比AVL（平衡二叉树）

（1）红黑树的查询性能略逊于平衡二叉树，因为它比平衡二叉树会最多多一层。

（2）红黑树在插入删除上要优于平衡二叉树，红黑树使用非严格的高度平衡换取增删节点时旋转次数的减少，任何不平衡都会在三次旋转之内解决，但是平衡二叉树旋转次数有时会比红黑树要多。所以红黑树的插入删除效率更高。

关于数据结构基础知识和数据结构基础知识点的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。