1、第 1章 基本数据结构与算法 主讲：曾庆尚 烟台大学文经学院电子系 NoImag e二级 ACCESS 数据库基础知识 NoImag e本章的重要性 2007年 4月 -2010年 9月共 8次计算机等级考试 涉及到本章内容的题目有 40题，平均每次接近 10分，因此本章还是很重要的。 本章在考试中只涉及笔试题目，上机不考。 NoImag e二级 ACCESS 数据访问页 NoImag e关键考点 顺序存储与链式存储的基本概念 栈、队列的基本概念与基本操作 循环队列元素个数的计算 算法时间、空间复杂度的概念 几种查找与排序的比较次数 二叉树的遍历 二叉树结点个数的计算 NoImag e基本数据
2、结构与算法 NoImag e本章主要内容 算法 数据结构 数据结构研究的主要内容 基本概念和术语 数据结构类型 线性结构和非线性结构 顺序存储与链式存储 线性表 栈和队列 线性链表 树与二叉树 查找和排序 图 NoImag e基本数据结构与算法 NoImag e1.1 算法 算法的基本概念 算法：解题方案的准确而完整的描述。 算法的基本特征： 是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。 算法不等于程序，程序不可能优于算法。 基本特性 可行性 ：根据实际问题设计的算法，执行得到满意结果 确定性 ：每一步骤必须有明确定义，不允许有多义性。 有穷性
3、：算法必须能在有限的时间内做完。 拥有足够的情报 ：输入和输出，方可执行。 NoImag e基本数据结构与算法 NoImag e1.1 算法 算法的基本要素 1.算法中对数据的运算和操作 算术运算：、 、 等 逻辑运算： 、 =、 =、 !=等 关系运算： and、 or、 not等 数据传输： w、 r等 2.算法的控制结构 算法中各操作之间的执行顺序 描述算法的工具通常有传统流程图、 N-S结构化流程图、算法描述语言等 算法可以用 顺序、选择、循环 三种基本机构组合而成。 NoImag e基本数据结构与算法 NoImag e1.1 算法 算法设计基本方法 （ 1）列举法： 根据问题，列举所
4、有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 （ 2）归纳法： 通过列举少量的特殊情况，经过分析，最后找出一般的关系。 （ 3）递推： 是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。 （ 4）递归： 将问题逐层分解的过程。 （ 5）减半递推技术： “ 减半 ” ，是指将问题规模减半，而问题性质不变； “ 递推 ” ，是指重复 “ 减半 ” 过程。 （ 6）回溯法： 分析问题，找出一个解决总线索，然后沿着这个线索逐步试探。 NoImag e基本数据结构与算法 NoImag e1.1 算法 算法的复杂度：时间复杂度、空间复杂度 （ P5） 算法的时间复杂度
5、 算法时间复杂度是指执行算法所需要的 计算工作量 。 工作量用算法所执行的 基本运算次数 来度量，而算法所执行的基本运算次数是问题规模的函数，即 算法的工作量 =f(n) 算法空间复杂度 算法空间复杂度是指执行这个算法所需要的 内存空间 。 存储空间包括： 算法程序所占的空间、 输入数据所占的空间、 算法执行过程中所需要的额外空间。 NoImag e基本数据结构与算法 NoImag e3.2.1 数据结构研究的主要内容 当今计算机应用的特点 所处理的数据量大且具有一定的关系； 对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。 应用举例 1 学籍档案管理 假设一个学籍档案管
6、理系统应包含如下表所示的学生信息。 学生基本情况学 号 姓 名 性 别 出生年月.9 9 0 7 0 1 0 1 李 军 男 80 12 .9 9 0 7 0 1 0 2 王颜霞 女 81 2 .9 9 0 7 0 1 0 3 孙 涛 男 80 9 .9 9 0 7 0 1 0 4 单晓宏 男 81 3 . . . . .NoImag e基本数据结构与算法 NoImag e特点 每个学生的信息占据一行，所有学生的信息 按学号顺序 依次排列构成一张表格； 表中每个学生的信息依据学号的大小存在着一种 前后关系 . 对它的操作通常是 插入 某个学生的信息， 删除 某个学生的信息， 更新 某个学生的信息，按条件 检索 某个学生的信息等等。 数据结构研究的主要内容
