文档介绍：全国计算机等级考试二级公共基础知识第一章数据结构与算法(30%) ?考试大纲 1. 算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。 2. 数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。 3. 线性表的定义;线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义;栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序)。知识点归纳?算法的基本概念?所谓算法是指解题方案的准确而完整的描述。严格来说,一个算法必须具有以下五个主要特征: 算法的基本特征一个算法应该具有以下五个重要的特征: ?有穷性?确定性?输入?输出?可行性算法原则上能够精确地运行一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的; 一个算法有 0个或多个输入,以刻画运算对象的初始情况,所谓 0个输入是指算法本身定义了初始条件; 算法的每一步骤必须有确切的定义; 一个算法必须保证执行有限步之后结束; 算法的基本概念?算法的组成要素?算法中对数据的运算和操作?算法的控制结构?算法设计基本方法?列举法?归纳法?递推?递归?减半递推?回溯法基本运算和操作基本运算和操作?算术运算?关系运算?逻辑运算?数据传输控制结构控制结构?顺序?选择?循环算法的复杂度?算法的复杂度可分为时间复杂度和空间复杂度,是衡量算法优劣的量度。 ?算法的时间复杂度是指执行算法所需要的工作量。一般情况下,算法中的基本操作重复执行的次数是问题规模 n的某个函数 f(n )。算法的复杂度?算法的空间复杂度?算法的空间复杂度是指执行这个算法所需要的内存空间。空间复杂度作为算法所需存储空间的量度数据结构?利用计算机进行数据处理是计算机应用的一个重要领域。数据结构主要研究和讨论以下三个方面的问题: ,即数据的逻辑结构。 ,各数据元素在计算机中的存储关系,即数据的存储结构。 。数据的逻辑结构?数据逻辑结构是对数据元素之间存在的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合上的若干关系表示。?与数据在计算机中的存储位置无关,是独立于计算机的。数据的存储结构?数据的存储结构是数据元素及其关系在计算机存储器中的表示。存储结构的主要内容是指在存储空间中使用一个存储结点来存储一个数据元素,在存储空间中建立各存储结点之间的关联,来表示数据元素之间的逻辑关系。?常见的存储结构: ?顺序存储结构?链式存储结构?索引存储结构?散列存储结构