算法、数据结构概述

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,二级高级办公培训,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,全国计算机等级考试,二级,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,）首节点无前件，尾节点无后件。,非线性结构：,不满足线性结构条件的数据结构,注意：,在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不能称为线性结构。,只有一个结点的数据结构是非线性结构,。,（重点）,基本数据结构与算法,L,o,+,（,n-1)*m,元素,n,.,元素,i,.,元素,2,元素,1,L,o,L,o,+m,L,o,+(i-1)*m,存储地址,存储内容,Loc(i)=L,o,+,（,i-1)*m,每个元素所占用的存储单元大小,(,Byte),1.3.2,顺序存储与链式存储,顺序存储,常用于线性数据结构，,将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。,三个弱点,插入或删除操作时，需移动大量元素。,长度变化较大时，需按最大空间分配。,表的容量难以扩充,（重点）,基本数据结构与算法,每个节点都由两部分组成：数据域和指针域。,数据域：,存放元素本身的数据，,指针域：,存放指针，体现,数据元素之间的逻辑联系,1.3.2,顺序存储与链式存储,1536,元素,2,1400,元素,1,1346,元素,3,元素,4,head,1345,链接存储结构特点,逻辑上相邻的节点物理上不必相邻。,最大优点：,插入、删除灵活,(,不必移动节点，仅改变节点中的指针,),。,链接存储结构,（重点）,基本数据结构与算法,1346,元素,3,1536,.,.,.,1536,元素,2,1400,.,.,.,元素,4,1346,1400,元素,1,1345,指针,：,指针域,存储内容,：,数据域,存储地址,1.3.2,顺序存储与链式存储,链式存储的地址映射表,head,指向,首元素位置,1536,元素,2,1400,元素,1,1346,元素,3,元素,4,head,1345,（重点）,每个链式结构都是以头结点（,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),算法描述,B),基本运算,C),逻辑结构,D),存储结构,通关练习,A,B,C,基本数据结构与算法,11,、数据在计算机内存中的表示是指（）,A,）数据的存储结构,B,）数据结构,C,）数据的逻辑机构,D,）数据元素间的关系,12,、,用链表表示线性表的优点是,_,。,A,、便于插入和删除操作,B,、数据元素的物理顺序与逻辑顺序相同,C,、花费的存储空间较顺序存储少,D,、便于随机存取,通关练习,A,A,