10 公共基础1-数据结构与算法(精品·公开课件).ppt

公共基础 数据结构与算法 1 算法的基本概念 算法是解题方案的准确而完整的描述，它不等于程序，也不等于计算方法 算法可以使用语言、图形、程序（VBA语言、c语言）描述 2 算法的基本特征 A.可行性：能得到满意结果 B.确定性：没有多义性 C.有穷性：算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止 D.拥有足够的情报：输入足够数据 1.1 算法 3 算法复杂度：评价算法的执行效率，度量一个算法的好坏 时间复杂度： 执行算法需要的工作量，即执行运算的次数。 不是执行的时间，不是指令（语句）的条数。 空间复杂度 算法执行过程所需要的内存空间 算法的空间复杂度与时间复杂度没有直接联系，即无关 1.1算法 算法概念练习 1、问题处理方案的正确而完整的描述称为：( )2005.4 2、算法的有穷性是指： ( )····2008.04-5 A 算法程序的运行时间是有限的 B 算法程序处理的数据量是有限的 C 算法程序的长度是有限的 D 算法只能被有限的用户使用 3、算法的空间复杂度是指：( )···2009.09-4 A）算法在执行过程中所需要的计算机存储空间 B）算法所处理的数据量 C）算法程序中的语句或指令条数 D）算法在执行过程中所需要的临时工作单元数 算法概念练习 4、算法的时间复杂度是指：( )···2010.03-2 A 算法的执行时间 B 算法所处理的数据量 C 算法程序中的语句或指令条数 D 算法在执行过程中的所需要的基本运算次数 5、判断：随着算法的空间复杂度的增大，时间复杂度也跟着增大（true/false） 6、算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 （ ） 1.2 数据结构的基本概念 1 数据结构研究的主要内容 A 数据的逻辑结构：反映数据之间的逻辑关系的结构。 B 数据的存储结构：逻辑结构在计算机的存储形式。 C 对各种数据结构进行的运算 2．研究数据结构目的 提高数据处理的速度···时间复杂度 尽量节省在数据处理过程中所占用的计算机存储空间 ···空间复杂度 注：不同的数据结构直接影响算法的执行效率 1.2 数据结构的基本概念 3 数据逻辑结构的定义 数据结构是指相互有关联的数据元素的集合 数据元素：每一个需要处理的对象都可以抽象为数据元素； 数据结构中，用前后件关系来描述数据元素之间的关系。 所以一个数据结构应包含两方面的信息：表示数据元素的信息；表示各数据元素之间的前后件关系（逻辑关系） 春夏秋冬是四个数据元素， 根据一年四季的顺序关系， 则“春”是“夏”的前件， 而“夏”是“春”的后件·· 4、数据的逻辑结构 对数据元素之间的逻辑关系的描述； 只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关； 一种逻辑结构可以采用多种存储结构； 5、数据的存储结构（数据的物理结构） 数据的逻辑结构在计算机存储空间中的存放形式； 一种逻辑结构可以采用多种存储结构，采用不同的存储结构，对数据处理的效率是不同的； 常见的存储结构有顺序、链接、索引 1.2 数据结构的基本概念 6、数据结构的图形表示 1.2 数据结构的基本概念 春夏秋冬是四个数据元素， 根据一年四季的顺序关系， 则“春”是“夏”的前件， 而“夏”是“春”的后件·· 数据元素用方框表示，前后件关系用有向线段表示 7、线性结构与非线性结构 根据数据逻辑结构中各数据元素之间前后件关系的复杂程度，分为：线性结构与非线性结构 线性结构（线性表）：满足 a.有且只有一个根结点（没有前件的结点），b.每个结点最多有一个前件，也最多有一个后件。 非线性结构：不是线性结构。 如果一个数据结构中一个数据元素都没有，就称为空的数据结构，线性结构和非线性结构都可以是空的数据结构 1.2 数据结构的基本概念 线性结构 非线性结构 数据结构基本概念练习 数据的存储结构是指（）···· 2005.4-1 A) 存储在外存中的数据  B) 数据所占的存储空间量 C) 数据在计算机中的顺序存储方式 D) 数据的逻辑结构在计算机中的表示     下列叙述中正确的是（）····· 2005.9-4 　A）一个逻辑数据结构只能有一种存储结构 　B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 　C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 　D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 数据结构基本概念练习 数据的逻辑结构在计算机存储空间中的存放形式成为数据的（ ） 下列叙述中正确的是 ····2007.4-1 A） 算法的效率只与问题的规模有关,而与数据的存储结构无关. B）算法的时间复杂度是指执行算法所需要的计算工作