二级access2003与公共基础常识教程 第十一章 数据结构与算法2[指南].ppt

全国计算机等级考试二级公共基础知识;基本要求 ;一、 基本数据结构与算法(8-10 分）;二、 程序设计基础（2-4分）;三、 软件工程基础（6-8分）;四、数据库设计基础(8-10分);考试方式;学习方法;本章重点;;结构化程序算法的特性如下： （1）可行性算法中的操作能够用已经实现的基本运算执行有限次来实现。 （2）确定性算法中的每一步都有确切的含义。 （3）有穷性一个算法（对任何合法的输入）在执行有穷步后能够结束，并且在有限的时间内完成。 （4）拥有足够的情报当算法拥有足够的情报，此算法才是有效的。;1.1.2 算法的基本要素 1、对数据对象的运算和操作 算术运算：加减乘除等 逻辑运算：与或非 关系运算：大于、小于、大于等于、小于等于 数据传输：赋值、输入、输出等 2、算法的控制结构 算法中各操作之间的执行顺序 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言或者自然语言等 一个算法一般可以用顺序、选择、循环三种基本机构组合而成。;1.1.3 算法设计基本方法 列举法：根据提出的问题，列举所有可能情况，用问题中给定的条件检验哪些需要，哪些不需要 归纳法：列举少量的特殊情况，找出一般关系 递推：从已知条件出发，逐次推出所要求的各种中间结果和最终结果 递归：解决复杂问题时，一般总是将问题逐层分解，最后归结为一些最简单的问题。这种问题并没有对问题进行求解，二知识当解决了最后哪些简单问题后，再按原来犯戒的逆过程进行综合。（分为直接递归和间接递归） 减半递推技术 回溯法（如迷宫）;1.2 算法复杂度;1.2.2 算法的空间复杂度 一般是指执行这个算法所需要的内存空间 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需要的附加存储空间 一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。;例题讲解;6.在计算机中，算法是指 A) 加工方法 B) 解题方案的准确而完整的描述 C) 排序方法 D) 查询方法 7.算法分析的???的是 A) 找出数据结构的合理性 B) 找出算法中输入和输出之间的关系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改进 8.算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 【 】 。;1.2 数据结构;1.2.1 数据结构研究的主要内容;应用举例1——学籍档案管理 假设一个学籍档案管理系统应包含如下表1-1所示的学生信息。;特点： 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格； 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。 ;图 1-1 3个对象的全排列过程;特点： 在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构； 对它的操作有：建立树形结构，输出最低层结点内容等等。 应用举例3——制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表1-2所示：;曼炬链逼古扰梦映拿很霖悸棵冗猖箱恍床浦纷泄旺瓜犊嘱行蜀荔省建让焦二级Access2003与公共基础知识教程 第十一章 数据结构与算法2二级Access2003与公共基础知识教程 第十一章 数据结构与算法2;课程先后关系的图形描形式：;特点： 课程之间的先后关系用图结构描述； 通过实施创建图结构，按要求将图结构中的顶点进行线性排序。 结论： 数据结构主要研究以下三个方面的问题： 数据的逻辑结构：用来描述数据元素之间的逻辑关系。 数据的存储结构：用来描述数据元素及数据元素之间的关系在存储器中的存储形式。 *重点提示： 同一逻辑结构的数据可以采用不同存储结构，但会影响数据处理效率。 数据的运算：即对数据元素施加的操作。 ;整数(1,2)、实数(1.1,1.2) 字符串(Beijing)、 图形、声音。;1.2.2 基本概念和术语;如何将0,1,2,3,4,5,6,7,8,9这10个数存放在 计算机中能最快地达到你所需要的目的？ 从大到小排列：9,8,7,6,5,4,3,2,1,0 无序排列：5,4,6,9,8,7,2,3,1,0 ;对数据结构中的结点进行 操作处理 (插入、删除、修改、查找、排序);数据元素(