第 1 章数据结构与算法考试大纲考纲提示本章主要考查数据结构及相关基本概念，几种典型的数据结构及其操作，算法的概念及算法复杂度，主要的查找及排序算法。这些在新考试大纲的公共基础部分中，约占30%的比例。知识点归纳【算法的基本概念】算法是对解题方案准确而完整的描述。它是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。严格说来，一个算法必须具有下列5 个主要特性。（1）有穷性。一个算法必须在执行有穷步之后结束（对任何合法的输入值），而且每一步都必须在有穷时间内完成。（2）确定性。算法中每条指令必须有确切含义，且在任何条件下，算法只有惟一的一条执行路径。（3）可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。（4）有输入。一个算法有0 个或多个输入，这些输入取自于某个特定的对象集合。（5）有输出。一个算法有0 个或多个输出，这些输出是同输入有着某些特定关系的量。综上所述，算法是一组严谨的定义运算顺序的规则，而且每一个规则都是有效且明确的，此顺序将在有限的次数下终止。（ 1）算法的基本概念，算法复杂度的概念和意义。（ 2）数据结构的定义，数据的逻辑结构与存储结构，数据结构的图形表示，线性结构与非线性结构的概念。（ 3）线性表的定义，线性表的顺序存储结构及其插入与删除运算。（ 4）栈和队列的定义，栈和队列的顺序存储结构及其基本运算。（ 5）线性单链表、双向链表与循环链表的结构及其基本运算。（ 6）树的基本概念，二叉树的定义及其存储结构，二叉树的前序、中序和后序遍历。（ 7）顺序查找与二分查找算法，基本排序算法（交换类排序、选择类2 二级 Visual FoxPro 数据库程序设计【算法的复杂度】算法的复杂度是本章的重点也是难点。选用算法首先要考虑正确性，还要考虑执行算法所耗费的时间和存储空间，同时，算法应易于理解、编码和调试等。算法的复杂度可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。1．算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。一般情况下，算法中的基本操作重复执行的次数是问题规模n 的某个函数 f (n)。算法的时间量度记作： 算法的工作量 = f (n) ，它表示随问题规模n 的增大，算法执行时间的增长率和f (n) 的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。2．算法的空间复杂度一个算法的空间复杂度一般是指执行这个算法所需要...
