文档介绍：第1章数据结构与算法
考试大纲
算法的基本概念，算法复杂度的概念和意义。
数据结构的定义，数据的逻辑结构与存储结构，数据结构的图形
表示，线性结构与非线性结构的概念。
线性表的定义，线性表的顺序存储结构及其插入与删除运算。
栈和队列的定义，栈和队列的顺序存储结构及其基本运算。
线性单链表、双向链表与循环链表的结构及其基本运算。
树的基本概念，二叉树的定义及其存储结构，二叉树的前序、中
序和后序遍历。
顺序查找与二分查找算法，基本排序算法(交换类排序、选择类
考纲提小
本章主要考查数据结构及相关基本概念，几种典型的数据结构及其操作，算法的概念
及算法复杂度，主要的查找及排序算法。这些在新考试大纲的公共基础部分中，约占 30%
的比例。
知识点归纳
【算法的基本概念】
算法是对解题方案准确而完整的描述。它是对特定问题求解步骤的一种描述，是指令
的有限序列，其中每条指令表示一个或多个操作。严格说来，一个算法必须具有下列 5个
主要特性。
有穷性。一个算法必须在执行有穷步之后结束(对任何合法的输入值) ，而且每 一步都必须在有穷时间内完成。
确定性。算法中每条指令必须有确切含义，且在任何条件下，算法只有惟一的一 条执行路径。
可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
有输入。一个算法有 0个或多个输入，这些输入取自于某个特定的对象集合。
有输出。一个算法有0个或多个输出，这些输出是同输入有着某些特定关系的量。
综上所述，算法是一组严谨的定义运算顺序的规则，而且每一个规则都是有效且明确 的，此顺序将在有限的次数下终止。
【算法的复杂度】
算法的复杂度是本章的重点也是难点。
选用算法首先要考虑正确性，还要考虑执行算法所耗费的时间和存储空间，同时，算 法应易于理解、编码和调试等。算法的复杂度可分为时间复杂度和空间复杂度，是衡量算 法优劣的量度。
算法的时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。一般情况下，算法中的基本操
作重复执行的次数是问题规模 n的某个函数f (n)。算法的时间量度记作：算法的工作量=f (n), 它表示随问题规模 n的增大，算法执行时间的增长率和 f (n)的增长率相同，称做算法的渐
进时间复杂度，简称时间复杂度。
算法的空间复杂度
一个算法的空间复杂度一般是指执行这个算法所需要的内存空间，即算法程序所占用 的空间、初始输入数据所占的存储空间，以及算法执行过程中所需要的额外空间。
【数据结构】
利用计算机进行数据处理是计算机应用的一个重要领域。数据结构作为计算机的一门
学科，主要研究和讨论以下 3个方面的问题。
数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。
在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。
对各种数据结构进行的运算。
简单地说，数据结构就是问题的数据模型。 一般说来，用计算机解决一个具体问题时， 大致需要经历下列几个步骤。
首先从具体问题中抽象出一个适当的数学模型。
然后设计一个解此数学模型的算法。
最后编写程序、进行测试、调整，直至得到最终解答。
寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含 有的关系，然后用数学的语言加以描述。
【数据的逻辑结构】
数据结构是指反映数据元素之间关系的数据集合的表示。更通俗地说，数据结构是指 带有结构的数据元素之间的前后件关系。因此，所谓结构，实际上就是指数据元素之间的 前后件关系。
数据的逻辑结构是指数据元素之间的逻辑关系，它可以用一个数据元素的集合和定义 在此集合上的若干关系来表示。
数据的逻辑结构是从逻辑关系上描述数据，它与数据在计算机中的存储位置无关，是 独立于计算机的。
【数据的存储结构】
数据的存储结构是本章的重要知识点。它是数据元素及其关系在计算机存储器内的表 示。数据的存储结构是逻辑结构用计算机语言的实现，即建立数据的机内表示。存储结构
的主要内容是指在存储空间中使用一个存储结点来存储一个数据元素；在存储空间中建立 各存储结点之间的关联，以表示数据元素之间的逻辑关系。其中存储结点是指一个数据元 素在存储结构中的存储。
一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用数据的存储 结构有如下4种。
顺序存储方式。每一个存储结点只含有一个数据元素。 所有的存储结点相继存储 在一个连续的存储区里。用存储结点之间的位置关系表示数据元素之间的逻辑关系。
链式存储方式。每一个存储结点不仅含有各数据元素，还包括指针。每一个指针
指向一个与本结点有逻辑关系的结点，即用指针表示逻辑关系。
索引存储方式。每一个存储结点