本文目录一览

1，数据结构要考些什么内容

顺序存储、链式存储；栈的出栈入栈、队列的出队入队、二叉树的遍历、图的遍历、几种常用的查找算法和排序算法。

数据结构要考些什么内容

2，数据结构的考点是什么

在计算机考研专业基础课统考科目中，一共考查数据结构、操作系统、计算机组成原理、计算机网络四门课程，满分为150分，其中数据结构占45分。 一、考查目标 (1)理解数据结构的基本概念，掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 (2)掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 (3)能够选择合适的数据结构和方法进行问题求解。 二、知识点解析 1.线性表 线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。 2.栈、队列和数组 栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。 一维数组属于线性表范畴，但多维数组不属于线性表。在这方面，主要掌握数组的存储结构，例如按行优先、按列优先等，某个元素存在的地址是什么。对于特殊矩阵(二维数组)的压缩存储原理也要搞清楚。 3、树与二叉树 二叉树和树是两种不同的概念，这一点是必须要搞清楚的。在这个部分，我们要掌握树的定义、二叉树的定义及主要特征(特殊的二叉树、二叉树的性质)。在二叉树的顺序存储结构和链式存储结构方面，特别是链式存储结构，因为很多应用都是建立在链式存储基础上，例如，二叉树的遍历(前序遍历、中序遍历、后序遍历)就是一种典型的应用。 在特殊的二叉树中，完全二叉树的概念是必须要搞清楚的，其次，线索二叉树的基本概念和构造、二叉排序树、平衡二叉树的基本概念和应用，特别是二叉排序树的基本性质和特点要能很好地理解。 多棵独立的树就组成了森林，树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识，也要有了了解。 最后就是树的应用，通常会作为综合应用类试题出现，包括等价类问题、哈夫曼(Huffman)树和哈夫曼编码等。 http://ky.educity.cn/sjjg/200808051202101241.htm

数据结构的考点是什么

3，数据结构知识归纳

第一章：数据结构概述 一、什么是数据结构 1、作者开篇谈到： 一般来说解决一个具体的问题时，大致需要经过下列几个步骤：首先要从具体的问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编写出程序代码，进行测试、调整直至得到最终的解决方案。 总结为：现实中具体的问题—>数学模型—>算法程序—>解决方案 动作为：抽象提取、设计编码、测试调整 2、数学角度阐述： 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。 3、定义数据结构： 描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构，因此，简单来说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作等的学科，用一句话来说就是，数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 研究对象：1、集合2、线性结构3、树形结构4、图状结构（网状结构） 结构分类：1、数据的逻辑结构2、数据的物理结构（存储结构） 关系表示：1、顺序映像2、非顺序映像，两者分别对应为顺序存储结构、链式存储结构 二、算法和算法分析 1、算法的五个特性：有穷性、确定性、可行性、输入和输出 2、算法设计的要求：正确性、可读性、健壮性以及效率与低存储量需求 3、算法的度量：时间复杂度和空间复杂度 总结：编写代码设计算法时候首先先考虑算法的正确性，确保程序能够满足要求，在正确性的前提下再进一步考虑算法的可读性、健壮性、拓展性以及算法的效率等。 第二章：线性表 一、线性表的定义 线性结构的特点是：在数据元素的非空有限集中（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中每个数据元素均只有一个前驱；（4）除最后一个元素之外，集合中每个数据元素均只有一个后继。 线性表是最常用并且最简单的一种数据结构，简单来说，一个线性表是n个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同，既可以是一个数也可以是一个符号等等。 二、线性表的操作 线性表是一个相当灵活的数据结构，它的长度可根据需要增长或者缩短，即对线性表的数据元素不但可以进行访问，还可以进行插入和删除等操作。线性表存储方式有两种，顺序存储和链式存储，下面通过代码进行简单模拟操作。 第三章：栈和队列 栈和队列是两种重要的线性结构，从数据结构的角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限制的线性表，因此可以称为限定性的数据结构。 一、栈的定义 栈是限定在表尾进行插入或删除操作的线性表，栈的特定是先进后出。栈的存储方式有两种，一种是顺序栈另外一种是链式栈，下面只通过代码简单模拟栈的操作。 二、栈的应用 栈的应用主要有数制转换、括号匹配的检验、迷宫问题求解以及表达式求值。另外栈递归实现的经典例子有八皇后问题、汉诺塔问题等。 三、队列的定义 队列和栈有点不同，队列是一种先进先出得线性表，它只能够在表的一端进行插入另外一头进行删除操作。队列在程序设计中比较常见的例子是操作系统中的作业排队。双端队列、循环队列有时间再进一步演进，暂时先了解些基本概念。 第四章：串 一、串的定义 计算机上的非数值处理的对象基本上都是字符串数据。串是由零个或多个字符组成的有限序列。串中字符的数目成为字符串的长度，零个字符的串成为空串。串的模式匹配算法经典的是KMP算法。 第五章：数组和广义表 一、数组和广义表定义 数组是读者已经很熟悉的一种数据类型，几乎所有的程序设计语言都把数组类型设为固有的类型。数组的应用中涉及到一个比较重要的数学知识，矩阵的压缩存储问题。广义表是线性表的推广，在java开发中好像用得不多，有时间再进一步学习。 第六章：树和二叉树 一、树的定义和基本操作 1、树的特点 树是一个结点n的有限集，在任意一颗树非空树中：1、有且只有一个根结点，2、当n>1时，其余结点分为m(m>0)个互不相交的有限集，其中每个集合本身又是一棵树，叫做根的子树。 关键词组：有限集、唯一性、对称性、递归性。 基本术语：结点、度、叶子、分支结点、孩子、双亲、兄弟、层次以及深度等。 基本操作：构造初始化树、取得左子树或右子树、插入结点、删除结点、树的遍历等等。 2、线性结构VS树结构 线性结构是一个“序列”，元素之间存在的是“一对一”的关系，而树是一个层次结构，元素之间存在的是“一对多”的关系。 二、二叉树的定义 1、二叉树的特点 每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能颠倒。 关键词组：对称、次序 2、二叉树的具体实例 满二叉树、完全二叉树、平衡二叉树等，具体区别参考书籍教材详解。 3、二叉树的存储结构 主要分为两种方式，一类是顺序结构（可使用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素），另外一类是链式存储结构，这两种存储方式各有利弊，具体要看实际操作的场合。 4、二叉树的遍历方式 遍历方案有先序遍历、中序遍历、后序遍历，具体的算法实现有递归的算法和非递归的算法。二叉树线索化初步了解，待有需要再进一步编码实战。 三、树的应用实例 1、树和森林 树的存储表示方式主要有三种：双亲表示法、孩子表示法以及孩子兄弟法。树和森林之间的相互转换也比较简单，不过多分析。 2、树的应用 （1）树的等价问题：离散数学中引入的等价和等价类的概念 （2）赫夫曼树及其应用（赫夫曼树又叫最优二叉树） （3）回溯法与树的遍历 （4）树的计数 四、代码实战参考题目 1、构造/初始化一颗二叉树 2、递归/非递归中序遍历该二叉树 3、二叉树和森林的相互转换模拟实现 //具体看存储的方式，比如孩子兄弟法 4、对平衡二叉树进行增加、删除结点操作 补充：参考学习资料： http://justsee.iteye.com/blog/1106693赫夫树、赫夫曼编码实现

数据结构知识归纳

4，数据结构考试重点

1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。2、面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象。由于目前关于这个问题有许多说法，我们采用了一种最流行的说法，即Coad与Yourdon 给出的定义：面向对象 = 对象 + 类 + 继承 + 通信。要点：·抽象数据类型的封装性·面向对象系统结构的稳定性·面向对象方法着眼点在于应用问题所涉及的对象3、数据结构的抽象层次：理解用对象类表示的各种数据结构4、算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。要点：·算法与程序的不同之处需要从算法的特性来解释·算法的正确性是最主要的要求·算法的可读性是必须考虑的·程序的程序步数的计算与算法的事前估计·程序的时间代价是指算法的渐进时间复杂性度量
第一章 数据结构基本概念1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。2、面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象。由于目前关于这个问题有许多说法，我们采用了一种最流行的说法，即Coad与Yourdon 给出的定义：面向对象 = 对象 + 类 + 继承 + 通信。要点：·抽象数据类型的封装性·面向对象系统结构的稳定性·面向对象方法着眼点在于应用问题所涉及的对象3、数据结构的抽象层次：理解用对象类表示的各种数据结构4、算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。要点：·算法与程序的不同之处需要从算法的特性来解释·算法的正确性是最主要的要求·算法的可读性是必须考虑的·程序的程序步数的计算与算法的事前估计·程序的时间代价是指算法的渐进时间复杂性度量第二章 数组1、作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储 要点：·数组元素的存放地址计算2、顺序表：顺序表的定义、搜索、插入与删除要点：·顺序表搜索算法、平均比较次数的计算·插入与删除算法、平均移动次数的计算3、多项式：多项式的定义4、字符串：字符串的定义及其操作的实现要点：·串重载操作的定义与实现第三章 链接表1、单链表：单链表定义、相应操作的实现、单链表的游标类。要点：·单链表的两种定义方式（复合方式与嵌套方式）·单链表的搜索算法与插入、删除算法·单链表的递归与迭代算法 2、循环链表：单链表与循环链表的异同3、双向链表：双向链表的搜索、插入与删除算法、链表带表头结点的优点4、多项式的链接表示第四章 栈与队列1、栈：栈的特性、栈的基本运算要点：·栈的数组实现、栈的链表实现·栈满及栈空条件、抽象数据类型中的先决条件与后置条件2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示3、队列：队列的特性、队列的基本运算要点：·队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件·队列的链表实现：链式队列中的队头与队尾指针的表示、4、双向队列：双向队列的插入与删除算法5、优先级队列：优先级队列的插入与删除算法第五章 递归与广义表 1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解要点：·链表是递归的数据结构，可用递归过程求解有关链表的问题2、递归实现时栈的应用要点：·递归的分层（树形）表示：递归树·递归深度（递归树的深度）与递归工作栈的关系·单向递归与尾递归的迭代实现3、广义表：广义表定义、广义表长度、广义表深度、广义表表头、广义表表尾要点：·用图形表示广义表的存储结构·广义表的递归算法第六章 树与森林1、树：树的定义、树的基本运算要点：·树的分层定义是递归的·树中结点个数与高度的关系2、二叉树：二叉树定义、二叉树的基本运算要点：·二叉树性质、二叉树中结点个数与高度的关系、不同种类的二叉树棵数·完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位置·二叉树的前序·中序·后序·层次遍历·前序·中序·后序的线索化二叉树、前驱与后继的查找方法3、霍夫曼树：霍夫曼树的构造方法、霍夫曼编码、带权路径长度的计算4、树的存储：树的广义表表示、树的双亲表示、树与二叉树的对应关系、树的先根·中根·后根·层次遍历。 5、堆：堆的定义、堆的插入与删除算法要点：·形成堆时用到的向下调整算法及形成堆时比较次数的上界估计·堆插入时用到的向上调整算法第七章 集合与搜索1、集合的概念：集合的基本运算、集合的存储表示要点：·用位数组表示集合时集合基本运算的实现·用有序链表表示集合时集合基本运算的实现2、并查集：并查集定义、并查集的三种基本运算的实现3、基本搜索方法 要点：·对一般表的顺序搜索算法（包括有监视哨和没有监视哨）·对有序顺序表的顺序搜索算法、用判定树（即扩充二叉搜索树）描述搜索，以及平均搜索长度（成功与不成功）的计算。·对有序顺序表的折半搜索算法、用判定树（即扩充二叉搜索树）描述搜索，以及平均搜索长度（成功与不成功）的计算。4、二叉搜索树：要点：·动态搜索树与静态搜索树的特性·二叉搜索树的定义、二叉搜索树上的搜索算法、二叉搜索树搜索时的平均搜索长度（成功与不成功）的计算。·AVL树结点上的平衡因子、AVL树的平衡旋转方法·高度为h的AVL树上的最少结点个数与最多结点个数· AVL树的搜索方法、插入与删除方法第八章 图1、图：图的定义与图的存储表示 要点：·邻接矩阵表示（通常是稀疏矩阵）·邻接表与逆邻接表表示·邻接多重表(十字链表)表示2、深度优先遍历与广度优先遍历要点：·生成树与生成树林的定义·深度优先搜索是个递归的过程，而广度优先搜索是个非递归的过程·为防止重复访问已经访问过的顶点，需要设置一个访问标志数组visited3、图的连通性要点：·深度优先搜索可以遍历一个连通分量上的所有顶点·对非连通图进行遍历，可以建立一个生成森林·对强连通图进行遍历，可能建立一个生成森林·关节点的计算和以最少的边构成重连通图4、最小生成树要点：·对于连通网络、可用不会构成环路的权值最小的n-1条边构成最小生成树·会画出用Kruskal算法及Prim算法构造最小生成树的过程5、单源最短路径要点：·采用逐步求解的方式求某一顶点到其他顶点的最短路径·要求每条边的权值必须大于零6、活动网络要点：·拓扑排序、关键路径、关键活动、AOE网·拓扑排序将一个偏序图转化为一个全序图。·为实现拓扑排序，要建立一个栈，将所有入度为零的顶点进栈·关键路径的计算第九章 排序1、基本概念：关键码、初始关键码排列、关键码比较次数、数据移动次数、稳定性、附加存储、内部排序、外部排序2、插入排序：要点：·当待排序的关键码序列已经基本有序时，用直接插入排序最快3、选择排序：要点：·用直接选择排序在一个待排序区间中选出最小的数据时，与区间第一个数据对调，而不是顺次后移。这导致方法不稳定。·当在n个数据（n很大）中选出最小的5 ~ 8个数据时，锦标赛排序最快·锦标赛排序的算法中将待排序的数据个数n补足到2的k次幂2k-1·在堆排序中将待排序的数据组织成完全二叉树的顺序存储。 4、交换排序： 要点： ·快速排序是一个递归的排序方法 ·当待排序关键码序列已经基本有序时，快速排序显著变慢。 5、二路归并排序： 要点： ·归并排序可以递归执行 ·归并排序需要较多的附加存储。可以采用一种"推拉法"（参见教科书上习题）实现归并排序，算法的时间复杂度为O (n)、空间复杂度为O(1) ·归并排序对待排序关键码的初始排列不敏感，排序速度较稳定 6、外排序 要点： ·多路平衡归并排序的过程、I/O缓冲区个数的配置 ·外排序的时间分析、利用败者树进行多路平衡归并 ·利用置换选择方法生成不等长的初始归并段 ·最佳归并树的构造及WPL的计算 第十章 索引与散列 1、线性索引： 要点： ·密集索引、稀疏索引、索引表计算 ·基于属性查找建立倒排索引、单元式倒排表 2、动态搜索树 要点： ·平衡的m路搜索树的定义、搜索算法 ·B树的定义、B树与平衡的m路搜索树的关系 ·B树的插入（包括结点分裂）、删除（包括结点调整与合并）方法 ·B树中结点个数与高度的关系 ·B+树的定义、搜索、插入与删除的方法 3、散列表 要点： ·散列函数的比较 ·装填因子 a 与平均搜索长度的关系，平均搜索长度与表长m及表中已有数据对象个数n的关系 ·解决地址冲突的（闭散列）线性探查法的运用，平均探查次数的计算 ·线性探查法的删除问题、散列表类的设计中必须为各地址设置三个状态 ·线性探查法中的聚集问题 ·解决地址冲突的（闭散列）双散列法的运用，平均探查次数的计算 ·双散列法中再散列函数的设计要求与表长m互质，为此m设计为质数较宜 ·解决地址冲突的（闭散列）二次散列法的运用，平均探查次数的计算 ·注意：二次散列法中装填因子 a 与表长m的设置 ·解决地址冲突的（开散列）链地址法的运用，平均探查次数的计算
这是我们老师要求的重点，即考点。打印出来，背一下就行了，准过！ 第一章：绪论 1.1：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。 1.2：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称。 数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的基本单位。 数据项：是数据元素中有独立含义的、不可分割的最小标识单位。 数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作。 1.3数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合定义在此集合上的若干关系来表示，数据结构可以分为三种：线性结构、树结构和图。 1.4：数据元素及其关系在计算机中的存储表示称为数据的存储结构，也称为物理结构。 数据的存储结构基本形式有两种：顺序存储结构和链式存储结构。 2.1：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。算法规则需满足以下五个特性： 输入——算法有零个或多个输入数据。 输出——算法有一个或多个输出数据，与输入数据有某种特定关系。 有穷性——算法必须在执行又穷步之后结束。 确定性——算法的每个步骤必须含义明确，无二义性。 可行性——算法的每步操作必须是基本的，它们的原则上都能够精确地进行，用笔和纸做有穷次就可以完成。 有穷性和可行性是算法最重要的两个特征。 2.2：算法与数据结构：算法建立数据结构之上，对数据结构的操作需用算法来描述。 算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。 2.3：算法的设计应满足五个目标： 正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标。 健壮性：即使输入数据不合适，算法也能做出适当的处理，不会导致不可控结 高时间效率：算法的执行时间越短，时间效率越高。 果。 高空间效率：算法执行时占用的存储空间越少，空间效率越高。 可读性：算法的可读性有利于人们对算法的理解。 2.4：度量算法的时间效率，时间复杂度，（课本39页）。 2.5：递归定义：即用一个概念本身直接或间接地定义它自己。递归定义有两个条件： 至少有一条初始定义是非递归的，如1！=1. 由已知函数值逐步递推计算出未知函数值，如用（n-1）！定义n！。 第二章：线性表 1.1线性表：线性表是由n(n>=0)个类型相同的数据元素a0,a1,a2,…an-1,组成的有限序列,记作： linearlist = (a0,a1,a2,…an-1) 其中，元素ai可以是整数、浮点数、字符、也可以是对象。n是线性表的元素个数，成为线性表长度。若n=0，则linearlist为空表。若n>0，则a0没有前驱元素，an-1没有后继元素，ai（0 p = head; while(p!=null) q = new node(x); (x); q.next = p.next; }else q=new node(x); 中间插入或尾插入都不会改变单表 q.next = head; 的头指针head。 head = q; } 单链表的删除操作： 头删除：head = head.next; 中间/尾删除：if(p.next!=null)=0）棵互不相干的树的集合。给森林加上一个根结点就变成一棵树，将树的根节点删除就变成森林。 二叉树的性质1：若根结点的层次为1，则二叉树第i层最多有2 的i-1次方（i>=1）个结点。 二叉树的性质2：在高度为k的二叉树中，最多有2的k次方减一个结点。 二叉树的性质3：设一棵二叉树的叶子结点数为n0,2度结点数为n2，则n0=n2+1。 一棵高度为k的满二叉树是具有2的k次方减一个结点的二叉树。满二叉树中每一层的结点数目都达到最大值。对满二叉树的结点进行连续编号，约定根节点的序号为0，从根节点开始，自上而下，每层自左至右编号。 一棵具有n个结点高度为k的二叉树，如果他的每个节点都与高度为k的满二叉树中序号为0~n-1 的结点一一对应，则这棵二叉树为为完全二叉树。 满二叉树是完全二叉树，而完全二叉树不一定是满二叉树。完全二叉树的第1~k-1层是满二叉树第k层不满，并且该层所有结点必须集中在该层左边的若干位置上。 二叉树的性质4：一棵具有n个结点的完全二叉树，其高度k=log2n的绝对值+1 二叉树的性质5：一棵具有n个结点的完全二叉树，对序号为i的结点，有 @若i=0，则i为根节点，无父母结点；若i>0，则i的父母结点的序号为[（i-1）/2]。 @若2i+1

5，数据结构的考试重点

这是我们老师要求的重点，即考点。打印出来，背一下就行了，准过！第一章：绪论1.1：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。1.2：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称。数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的基本单位。数据项：是数据元素中有独立含义的、不可分割的最小标识单位。数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作。1.3数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合定义在此集合上的若干关系来表示，数据结构可以分为三种：线性结构、树结构和图。1.4：数据元素及其关系在计算机中的存储表示称为数据的存储结构，也称为物理结构。 数据的存储结构基本形式有两种：顺序存储结构和链式存储结构。 2.1：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。算法规则需满足以下五个特性：输入——算法有零个或多个输入数据。 输出——算法有一个或多个输出数据，与输入数据有某种特定关系。 有穷性——算法必须在执行又穷步之后结束。 确定性——算法的每个步骤必须含义明确，无二义性。 可行性——算法的每步操作必须是基本的，它们的原则上都能够精确地进行，用笔和纸做有穷次就可以完成。 有穷性和可行性是算法最重要的两个特征。2.2：算法与数据结构：算法建立数据结构之上，对数据结构的操作需用算法来描述。 算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。2.3：算法的设计应满足五个目标：正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标。 健壮性：即使输入数据不合适，算法也能做出适当的处理，不会导致不可控结 高时间效率：算法的执行时间越短，时间效率越高。 果。 高空间效率：算法执行时占用的存储空间越少，空间效率越高。 可读性：算法的可读性有利于人们对算法的理解。 2.4：度量算法的时间效率，时间复杂度，（课本39页）。2.5：递归定义：即用一个概念本身直接或间接地定义它自己。递归定义有两个条件：至少有一条初始定义是非递归的，如1！=1. 由已知函数值逐步递推计算出未知函数值，如用（n-1）！定义n！。 第二章：线性表1.1线性表：线性表是由n(n>=0)个类型相同的数据元素a0,a1,a2,…an-1,组成的有限序列,记作： LinearList = (a0,a1,a2,…an-1)其中，元素ai可以是整数、浮点数、字符、也可以是对象。n是线性表的元素个数，成为线性表长度。若n=0，则LinearList为空表。若n>0，则a0没有前驱元素，an-1没有后继元素，ai（0<i<n-1）有且仅有一个直接前驱元素ai-1和一个直接后继元素ai+1。1.2线性表的顺序存储是用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存储次序与它们在线性表中的逻辑次序相同。线性表的数据元素数据同一种数据类型，设每个元素占用c字节，a0的存储地址为Loc（a0），则ai的存储地址Loc（ai）为：Loc（ai） = Loc（a0）+ i*c 数组是顺序存储的随机存储结构，它占用一组连续的存储单元，通过下标识别元素，元素地址是下标的线性函数。1.3：顺序表的插入和删除操作要移动数据元素。平均移动次数是 属数据表长度的一半。（课本第50页）1.4：线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。它有两个域组成：数据域和地址域。通常成为节点。（课本第55页及56页）1.5单链表（课本56页）单链表的遍历：Node<E> p = head; while(p!=null)单链表的插入和删除操作非常简便，只要改变节点间的链接关系，不需移动数据元素。单链表的插入操作：1）：空表插入/头插入 2)中间插入/尾插入 if(head == null) Node<E> q = new Node<E>(x); }else Node<E> q=new Node<E>(x); 中间插入或尾插入都不会改变单表 q.next = head; 的头指针head。 head = q; }单链表的删除操作：头删除：head = head.next; 中间/尾删除：if(p.next!=null)循环单链表：如果单链表最后一个节点的next链保存单链表的头指针head值，则该单链表成为环形结构，称为循环单链表。（课本67）若rear是单链表的尾指针，则执行（rear.next=head;）语句，使单链表成为一条循环单链表。当head.next==head时，循环单链表为空。1.6：双链表结构：双链表的每个结点有两个链域，分别指向它的前驱和后继结点， 当head.next==null时，双链表为空。 设p指向双链表中非两端的某个结点，则成立下列关系：p=p.next.prev=p.prev.next。双链表的插入和删除：1）插入 2)删除q=new DLinkNode（x）； p.prev.next = p.next;q.prev=p.prev;q.next =p; if(p.next=null)p.prev.next = q;p.prev=q; (p.next).prev = p.prev;}循环双链表：当head.next==head且head.prev==head时，循环双链表为空。第三章：栈和队列1.1栈：栈是一种特殊的线性表，其中插入和删除操作只允许在线性表的一端进行。允许操作的一端称为栈顶，不允许操作的一端称为栈底。栈有顺序栈和链式栈。栈中插入元素的操作称为入栈，删除元素的操作称为出栈。没有元素的中称为空栈。栈的进出栈顺序：后进先出，先进后出。（及75页的思考题）。1.2：队列：队列是一种特殊的线性表，其中插入和删除操作分别在线性表的两端进行。向队列中插入元素的过程称为入队，删除元素的过程称为出对，允许入队的一端称为队尾，允许出队的一端称为对头。没有元素的队列称为空队列。队列是先进先出。第四章：串1.1：串是一种特殊的线性表，其特殊性在于线性表中的每个元素是一个字符。一个串记为： s=“s0s1s2…sn-1” 其中n>=0,s是串名，一对双引号括起来的字符序列s0s1s2…sn-1是串值，si（i=0，1，2，…n-1）为特定字符集合中的一个字符。一个串中包含的字符个数称为串的长度。长度为0的串称为空串，记作“”，而由一个或多个空格字符构成的字符串称为空格串。子串：由串s中任意连续字符组成的一个子序列sub称为s的子串，s称为sub的主串。子串的序号是指该子串的第一个字符在主串中的序号。串比较：两个串可比较是否相等，也可比较大小。两个串（子串）相等的充要条件是两个串（子串）的长度相同，并且各对应位置上的字符也相同。两个串的大小由对应位置的第一个不同字符的大小决定，字符比较次序是从头开始依次向后。当两个串长度不等而对应位置的字符都相同时，较长的串定义为较“大”。第五章：数组和广义表1.1：数组是一种数据结构，数据元素具有相同的数据类型。一维数组的逻辑结构是线性表，多维数组是线性表的扩展。1.2：一维数组：一维数组采用顺序存储结构。一个一维数组占用一组连续的存储单元。设数组第一个元素a0的存储地址为Loc（a0），每个元素占用c字节，则数组其他元素ai的存储地址Loc（ai）为： Loc（ai）= Loc（a0）+i*c数组通过下标识别元素，元素地址是下标的线性函数。一个下标能够唯一确定一个元素，所划给的时间是O（1）。因此数组是随机存取结构，这是数组最大的优点。1.3：多维数组的遍历：有两种次序：行主序和列主序。行主序：以行为主序，按行递增访问数组元素，访问完第i行的所有元素之后再访问第i+1行的元素，同一行上按列递增访问数组元素。 a00,a01,…a0(n-1), a10,a11,…a1(n-1),…a(m-1)0,a(m-1)1,…,a(m-1)(n-1) 2)列主序：以列为主序，按列递增访问数组元素，访问完第j列的所有元素之后再访问第j+1列的元素，同一列上按列递增访问数组元素。 多维数组的存储结构：多维数组也是由多个一维数组组合而成，组合方式有一下两种。静态多维数组的顺序存储结构：可按行主序和列主序进行顺序存储。 按行主序存储时，元素aij的地址为：Loc（aij）= Loc（a00）+（i*n+j）*c按列主序存储时，Loc（aij）= Loc（a00）+（j*m+i）*c动态多维数组的存储结构。 二维数组元素地址就是两个下标的线性函数。无论采用哪种存储结构，多维数组都是基于一维数组的，因此也只能进行赋值、取值两种存取操作，不能进行插入，删除操作。第六章：树是数据元素（结点）之间具有层次关系的非线性结构。在树结构中，除根以外的结点只有一个直接前驱结点，可以有零至多个直接后继结点。根没有前驱结点。树是由n（n>=0）个结点组成的有限集合（树中元素通常称为结点）。N=0的树称为空树；n>0大的树T；@有一个特殊的结点称为根结点，它只有后继结点，没有前驱结点。@除根结点之外的其他结点分为m（m>=0）个互不相交的集合T0,T1,T3……..,Tm-1，其中每个集合Ti（0<=i<m）本身又是一棵树，称为根的子树。树是递归定义的。结点是树大的基本单位，若干个结点组成一棵子树，若干棵互不相交的子树组成一棵树。树的每个结点都是该树中某一棵子树的根。因此，树是由结点组成的、结点之间具有层次关系大的非线性结构。 结点的前驱结点称为其父母结点，反之，结点大的后继结点称为其孩子结点。一棵树中，只有根结点没有父母结点，其他结点有且仅有一个父母结点。拥有同一个父母结点的多个结点之间称为兄弟结点。结点的祖先是指从根结点到其父母结点所经过大的所有结点。结点的后代是指该结点的所有孩子结点，以及孩子的孩子等。结点的度是结点所拥有子树的棵数。度为0的结点称为叶子结点，又叫终端结点；树中除叶子结点之外的其他结点称为分支结点，又叫非叶子结点或非终端结点。树的度是指树中各结点度的最大值。结点的层次属性反应结点处于树中的层次位置。约定根结点的层次为1，其他结点的层次是其父母结点的层次加1。显然，兄弟结点的层次相同。树的高度或深度是树中结点的最大层次树。设树中x结点是y结点的父母结点，有序对（x，y）称为连接这两个结点的分支，也称为边。设（X0,X1,….,Xk-1）是由树中结点组成的一个序列，且（Xi，Xi+1）（0<=i<k-1）都是树中的边，则该序列称为从X0到Xk-1的一条路径。路径长度为路径上的边数。在树的定义中，结点的子树T0，T1…..,Tm-1之间没有次序，可以交换位置，称为无序树，简称树。如果结点的子树T0,T1……,Tm-1从左到右是有次序的，不能交换位置，则 称该树为有序树。森林是m（m>=0）棵互不相干的树的集合。给森林加上一个根结点就变成一棵树，将树的根节点删除就变成森林。二叉树的性质1：若根结点的层次为1，则二叉树第i层最多有2 的i-1次方（i>=1）个结点。二叉树的性质2：在高度为k的二叉树中，最多有2的k次方减一个结点。二叉树的性质3：设一棵二叉树的叶子结点数为n0,2度结点数为n2，则n0=n2+1。一棵高度为k的满二叉树是具有2的k次方减一个结点的二叉树。满二叉树中每一层的结点数目都达到最大值。对满二叉树的结点进行连续编号，约定根节点的序号为0，从根节点开始，自上而下，每层自左至右编号。一棵具有n个结点高度为k的二叉树，如果他的每个节点都与高度为k的满二叉树中序号为0~n-1的结点一一对应，则这棵二叉树为为完全二叉树。满二叉树是完全二叉树，而完全二叉树不一定是满二叉树。完全二叉树的第1~k-1层是满二叉树第k层不满，并且该层所有结点必须集中在该层左边的若干位置上。二叉树的性质4：一棵具有n个结点的完全二叉树，其高度k=log2n的绝对值+1二叉树的性质5：一棵具有n个结点的完全二叉树，对序号为i的结点，有@若i=0，则i为根节点，无父母结点；若i>0，则i的父母结点的序号为[（i-1）/2]。@若2i+1<n，则i的左孩子结点序号为2i+1；否则i无左孩子。@若2i+2<n，则i的右孩子结点的序号为2i+2，否则i无右孩子。二叉树的遍历二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点，并且每个结点仅被访问一次。二叉树的三种次序遍历1：先根次序；访问根节点，遍历左子树，遍历右子树。2：中根次序；遍历左子树，访问右子树，遍历右子树。3：后根次序；遍历左子树，遍历右子树，访问根节点。先根次序遍历时，最先访问根节点；后根次序遍历时，最后访问根节点；中根次序遍历时，左子树上的结点在根节点之前访问，右子树上的结点在根节点之后访问。二叉树的插入和删除操作P147二叉树的层次遍历P149习题P167 6—10，6—19第七章图是由定点集合及顶点间的关系集合组成的一种数据关边系。顶点之间的关系成为边。一个图G记为G=（V,E），V是顶点A的有限集合，E是边的有限集合。即 V=E=无向图中的边事没有方向，每条边用两个顶点的无序对表示。有向图中的边是有方向，每条边用两个顶点的有序对表示。完全图指图的边数达到最大值。n个顶点的完全图记为Kn。无向完全图Kn的边数为n*（n-1）/2,有向完全图Kn的边数为n*（n-1）。子图：设图G==(V,E),G=(V,E)，若V包含于V且E包含于E,则称图G是G的子图。若G是G的真子图。连通图：在无向图G中，若从顶点VI到Vj有路径，则称Vi和Vj是联通的。若图G中任意一对顶点Vi和Vj（Vi不等于Vj）都是联通的，则称G为连通图。非连通图的极大联通子图称为该图的联通分量。强连通图：在有向图中，若在每一对顶点Vi和Vj（Vi不等于Vj）之间都存在一条从Vi到Vj的路径，也存在一条从Vi到Vj的路径，也存在一条从Vi到Vj的路径，则称该图的强连通图。非强连通图的极大强连通子图称为该图的强连通图分量。图的遍历遍历图是指从图G中任意一个顶点V出发，沿着图中的边前行，到达并访问图中的所有顶点，且每个顶点仅被访问一次。遍历图要考虑一下三个问题：@指定遍历的第一个访问顶点@由于一个顶点可能与多个顶点相邻，因此要在多个邻接顶点之间约定一种访问次序。@由于图中可能存在回路，在访问某个顶点之后，可能沿着某条路径又回到该顶点。深度优先搜索图的深度优先搜索策略是，访问某个顶点v，接着寻找v的另一个未被访问的邻接顶点w访问，如此反复执行，走过一条较长路径到达最远顶点；若顶点v没有未被访问的其他邻接顶点，则回到前一个被访问顶点，再寻找其他访问路径。图的深度优先搜索遍历算法P188 联通的无回路的无向图，简称树。树中的悬挂点又成为树叶，其他顶点称为分支点。各连通分量均为树的图称为森林，树是森林。由于树中无回路，因此树中必定无自身环也无重边（否则他有回路）若去掉树中的任意一条边，则变成森林，成为非联通图；若给树加上一条边，形成图中的一条回路，则不是树。P191生成树和生成森林：一个连通无向图的生成树是该图的一个极小联通生成子图，它包含原图中所有顶点（n个）以及足以构成一棵树的n-1条边。 一个非联通的无向图，其各连通图分量的生成图组成该图的生成森林。图的生成图或生成森林不是唯一的，从不同顶点开始、采用不同遍历可以得到不同的生成树或森林。 在生成树中，任何树中，任何两个顶点之间只有唯一的一条路径。第八章折半查找算法描述 P206,P207二叉排序树及其查找：二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：@每个结点都有一个作为查找依据的关键字，所有结点的关键字互不相同。@若一个结点的左子树不空，则左子树上所有结点的关键字均小于这个节点的关键字；@每个结点的左右子树也分别为二叉排序树。在一棵二叉排序树中，查找值为value的结点，算法描述如下：@从根结点开始，设p指向根结点@将value与p结点的关键字进行比较，若两者相等，则查找成功；若value值较小，则在p的左子树中继续查找；若value值较大，则在p的右子树中继续查找。@重复执行上一步，直到查找成功或p为空，若p为空，则查找不成功。习题 8-6 第九章直接插入排序算法描述：p228冒泡排序算法的描述：p232快速排序算法描述p233直接选择排序算法描述p236直接选择排序算法实现如下：Public static void selectSort(int[]table) for(int i=0;i<table.length-1;i++) int min=I; for(int j=i+1;j<table.length;j++) if(table[j]<table[min]) min=j; if(min!=i) int temp=table[i]; table[i]==table[min]; table[min]=temp;}}}}堆排序是完全二叉树的应用，是充分利用完全二叉树特性的一种选择排序。堆定义：设n个元素的数据序列k1<=k2i+1且ki<=k2i+2 i=0,1,2,3,….,[n/2-1]或ki>==k2i+1且ki>=2i+2i=0,1,2,3,…..[n/2-1]时，序列希望对你会有所帮助。

文章TAG：数据  数据结构  结构  必考  数据结构必考知识点  
下一篇