ess理论培训-数据结构与算法.ppt

全国计算机等级考试ess数据库
考试
考试类型:笔试和机试
考试时间:2009年9月19日,上午笔试,下午机试
笔试:选择题(35题,每题2分,共70分)和填空题(15题,每题2分,共30分)
机试:基本操作题(30分)、简单应用题(40分)、综合应用题(30分)
目录
数据结构与算法
程序设计基础
软件工程基础
数据库设计基础
Access数据库知识
一、数据结构与算法
算法
数据结构
线性表和线性链表
栈和队列
树和二叉树
查找技术
排序技术
1、算法
算法的定义
算法是对一个问题求解步骤的一种描述,是求解问题的方法,是指令的有限序列
算法的特征
有穷性:一个算法在执行有穷步后能够结束,并且在有限的时间内完成
确定性:算法中的每一步都有确切的含义
可行性:算法操作能够用已经实现的基本运算执行有限次来实现
输入:有0个或多个输入
输出:有1个或多个输出,以反映数据加工的结果
例子
问题处理方案的正确而完整的描述称为_算法___。
一个算法应该具有“确定性”等5个特性,下面对另外4个特性的描述中错误的是(B)
A、有零个或多个输入 B、有零个或多个输出
C、有穷性 D、可行性
1、算法
算法复杂度
是衡量一个算法好坏的度量
包括时间复杂度和空间复杂度
时间复杂度
指执行算法所需要的计算工作量
算法的工作量用算法所执行的基本运算次数来度量
空间复杂度
指执行这个算法所需要的内存空间
包括:算法代码所占的空间、初始数据所占的存储空间、算法执行过程中所需要的额外空间
2、数据结构
数据结构的定义
数据:对客观事物的符号表示,在计算机科学中,所有能输入到计算机并被处理的符号的总称
数据元素:数据的基本单位,由若干个数据项构成
数据结构:互相之间存在一种或多种关系的数据元素的集合
2、数据结构
数据结构分为数据的逻辑结构和数据的存储结构
数据的逻辑结构
反映数据之间的逻辑关系
分为线性结构和非线性结构
与数据的存储无关,是独立于计算机的
通常有4种结构
集合
线性结构
树形结构
图状结构