算法、数据结构概述.ppt

全国计算机等级考试 二级MS-Office培训讲义,公共基础知识 （四个部分选择题-10分） 记忆为主，理解推导为辅 （多做多看资料！）,一、基本数据结构与算法 重点：记忆，理解。 对于基本存储结构、基本数据结构、排序和查找的算法的特点、意义、分类进行比较记忆。 而对于栈、循环队列、二叉树结点个数和结点遍历方法要求能理解并计算和推导。,【熟记】算法的概念、4个特征 【理解】算法的复杂度2种,1.1 算法,基本数据结构与算法,1.1 算法,算法的基本概念 （重点） 算法：解题方案的准确而完整的描述。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。算法不等于程序，程序不可能优于算法。 基本特性 可行性：根据实际问题设计的算法，执行得到满意结果 确定性：每一步骤必须有明确定义，不允许有多义性。 有穷性：算法必须能在有限的时间内做完。 拥有足够的情报: 输入和输出必须拥有足够的情报：方可执行。,求圆面积算法： 第一，输入圆半径r 第二，确定求圆面积公式:s=pi*r2 第三，确定圆周律：pi=3.14 第四，计算圆面积 第五，输出面积结果s,基本数据结构与算法,1.1 算法,算法的复杂度：时间复杂度、空间复杂度（重点） 算法的时间复杂度 算法时间复杂度是指执行算法所需要的计算工作量。 工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即 算法的工作量=f(n) 算法空间复杂度 算法空间复杂度是指执行这个算法所需要的内存空间。 存储空间包括：算法程序所占的空间、 输入数据所占的空间、算法执行过程中所需要的额外空间。,基本数据结构与算法,通关练习,1.下列叙述中正确的是（ ）。 A.算法的效率只与问题规模有关，与存储结构无关。 B.算法的时间复杂度是指执行算法所需的计算工作量。 C.数据的逻辑结构与存储结构是一一对应的。 D.算法的时间复杂度与空间复杂度一定相关。 2.算法的时间复杂度取决于（ ）。 A.问题的规模 B.问题的困难度 C.待处理的数据的初始状态 D.A和C 3在下列选项中，哪个不是一个算法一般应该具有的基本特征_。 A、确定性 B、可行性 C、无穷性 D、拥有足够的情报,B,D,C,基本数据结构与算法,通关练习,4下面叙述正确的是_。 A、算法的执行效率与数据的存储结构无关 B、算法的空间复杂度是指算法程序中指令（或语句）的条数 C、算法的有穷性是指算法必须能在执行有限个步骤之后终止 D、以上三种描述都不对 5算法的时间复杂度是指_。 A、算法的执行时间 B、算法所处理的数据量 C、算法程序中的语句或指令条数 D、算法在执行过程中所需要的基本运算次数,C,D,基本数据结构与算法,通关练习,6算法的空间复杂度是指_。 A、算法在执行过程中所需要的计算机存储空间 B、算法所处理的数据量 C、算法程序中的语句或指令条数 D、算法在执行过程中所需要的临时工作单元数 7. 算法的有穷性是指_。 A、算法程序的运行时间是有限的 B、算法程序所处理的数据量是有限的 C、算法程序的长度是有限的 D、算法只能被有限的用户使用,A,A,基本数据结构与算法,通关练习,8算法分析的目的是_。 A、找出数据结构的合理性 B、找出算法中输入和输出之间的关系 C、分析算法的易懂性和可靠性 D、分析算法的效率以求改进 9下列叙述中正确的是_。 A、一个算法的空间复杂度大，则其时间复杂度也必定大 B、一个算法的空间复杂度大，则其时间复杂度必定小 C、一个算法的时间复杂度大，则其空间复杂度必定小 D、上述三种说法都不对,D,分析算法的目的是要: 降低算法的时间复杂度和空间复杂度，提高算法的执行效率。,D,基本数据结构与算法,通关练习,4算法一般都可以用哪几种控制结构组合而成_。 A、循环、分支、递归 B、顺序、循环、嵌套 C、循环、递归、选择 D、顺序、选择、循环,D,算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。,基本数据结构与算法,数据结构主要研究以下三个方面的问题：重点掌握 数据的逻辑结构：数据集合中各元素的信息，及元素之间所固有的逻辑关系（前后件关系） 数据的存储结构：各数据元素在计算机中的存储关系 对各种数据结构进行的运算 主要目的是为了提高数据处理的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。,1.2 数据结构研究的主要内容,基本数据结构与算法,数据元素(Data Element):是数据的基本单位，即数据集合中的个体。 有时一个数据元素可由若干数据项(Data Item)组成。数据项是数据的最小单位。,数据元素亦称节点或记录。,1.2.1 基本概念和术语,（重点）,数据结构是相互有关联的数据元素的集合。 （重点）,基本数据结构与算法,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面,1.3 数据结构类型,（重点）,C 索引存储（了解）,基本数据结构与算法,1.3.1 线性结构和非线性结构,线性结构条件 （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 （3）首节点无前件，尾节点无后件。 非线性结构：不满足线性结构条件的数据结构 注意：在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不能称为线性结构。只有一个结点的数据结构是非线性结构。,（重点）,基本数据结构与算法,1.3.2 顺序存储与链式存储,顺序存储 常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。 三个弱点 插入或删除操作时，需移动大量元素。 长度变化较大时，需按最大空间分配。 表的容量难以扩充,（重点）,基本数据结构与算法,每个节点都由两部分组成：数据域和指针域。 数据域：存放元素本身的数据， 指针域：存放指针，体现数据元素之间的逻辑联系,1.3.2 顺序存储与链式存储,链接存储结构特点 逻辑上相邻的节点物理上不必相邻。 最大优点：插入、删除灵活(不必移动节点，仅改变节点中的指针)。,链接存储结构,（重点）,基本数据结构与算法,1.3.2 顺序存储与链式存储,链式存储的地址映射表,head指向,首元素位置,（重点）,每个链式结构都是以头结点（head）开始， 以尾结点指针域存放0或null表示链表的结束。,基本数据结构与算法,1、链表不具有的特点是（ ） A)不必事先估计存储空间 B)插入删除不需要移动元素 C)可随机访问任一元素 D)所需空间与线性表长度成正比 2、数据结构中，与所使用的计算机无关的是数据的（ ） A) 存储结构 B) 物理结构 C) 逻辑结构 D) 物理和存储结构 3、根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成（ ） A) 动态结构和静态结构 B) 紧凑结构和非紧凑结构 C) 线性结构和非线性结构 D) 内部结构和外部结构 4、数据处理的最小单位是（ ） A) 数据 B) 数据元素 C) 数据项 D) 数据结构,通关练习,C,C,C,C,基本数据结构与算法,5、下列叙述中，错误的是（ ） A) 数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占空间不一定是连续的 D) 一种数据的逻辑结构可以有多种存储结构 6、线性表的顺序存储结构和线性表的链式存储结构分别是（ ) A) 顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的存储结构 7、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及（ ） A) 数据的存储结构 B) 计算方法 C) 数据映象 D) 逻辑存储,通关练习,B,B,A,基本数据结构与算法,8、下列叙述中正确的是（ ） A）程序执行的效率与数据的存储结构密切相关 B）程序执行的效率只取决于程序的控制结构 C）程序执行的效率只取决于所处理的数据量 D）以上都不对 9、数据的存储结构是指（ ） A）数据所占的存储空间 B）数据的逻辑结构在计算机中的表示 C）数据在计算机中的顺序存储方式 D）存储在外存中的数据 10、数据（ ）包括集合、线性结构、树形结构和图4种类型。 A) 算法