《DS第一章绪论》PPT课件

第一章绪论,考纲要求考纲中没有这一章考纲分析建议考生复习时复习这一章，因为把握这一章有助于对整个课程知识的理解。本章主要掌握DS和算法的基本概念，其出题形式主要为选择题。关于DS的深刻理解有可能出小分值的综合应用题。由于分值有限，算法时间复杂度的分析一般不会以综合应用题的形式单独出题，通常会结合算法设计题来分析，由于DS课程要求掌握初步的算法分析技术，因此，算法分析题不会太难。,基本知识点：数据结构和算法的概念重点：数据结构的定义、逻辑结构、存储结构和数据运算三方面的概念及相互关系难点：分析算法的时间复杂度,第一章绪论,DS的基本概念,考核知识点数据：是信息的载体。数据元素（也称为结点）：是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项：是构成数据元素的不可分割的最小单位。数据对象：是具有相同性质的数据元素的集合，是数据的子集。（在不产生混淆的情况下，将数据对象简称为数据）。数据结构()DataStructure=(D,R)，其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结构（物理结构）。,DS的基本概念,考核知识点数据的逻辑结构()是指数据元素之间逻辑关系的整体。根据数据元素之间逻辑关系的不同，数据结构分为四类：1)集合：数据元素之间就是“属于同一个集合”，除此之外，无任何关系；2)线性结构：一对一；3)树结构：一对多的层次关系；4)图结构：多对多的任意关系。树和图结构也称为非线性结构。,DS的基本概念,考核知识点7.数据的存储结构()又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺序存储结构和链接存储结构。顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示；链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。存储结构除了存储数据元素之外，还必须存储数据元素之间的逻辑关系。,DS的基本概念,考核知识点抽象数据类型ADT()抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。它提供了使用和实现两个不同的视图，实现了封装和信息隐藏。,典型题解析,1.假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承（如图），则表示该遗产继承关系的最合适的DS应该是（）。A.树B.图C.线性表D.集合解答：B,典型题解析,2.计算机所处理的数据一般具有某种内在联系，这是指（）。A.数据和数据之间存在某种联系B.元素和元素之间存在某种联系C.元素内部具有某种结构D.数据项和数据项之间存在某种联系解答：B分析：数据结构是指相互之间存在一定关系的数据元素的集合，数据元素是讨论数据结构时涉及的最小数据单位，元素内部各数据项一般不予考虑。,典型题解析,3.在链接存储结构中，要求（）。A.每个结点占用一片连续的存储区域B.所有结点占用一片连续的存储区域C.结点的最后一个域是指针类型D.每个结点有多少个后继就设有多少个指针解答：A分析：结点作为存取操作的独立单位，需要占用连续的存储区域，但不要求结点中各组成部分（域）的顺序。,典型题解析,4.下列说法中不正确的是（）。A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小单位C.数据可由若干个数据项构成D.数据元素可由若干个数据项构成解答：C分析：数据是由若干个数据元素构成，数据元素是由若干个数据项构成。,典型题解析,5.可以用（）、数据关系和基本操作定义一个完整的抽象数据类型。A.数据元素B.数据对象C.原子类型D.存储结构解答：B分析：ADT的三要素为：数据对象、数据关系、基本操作。,典型题解析（应用题）,1.试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解答：数据结构是指相互之间存在一定关系的数据元素的集合，抽象数据类型是指一个数据结构以及定义在该结构上的一个操作，程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称。抽象数据类型可以看成是对数据类型的一种抽象。在高级程序设计语言中，基本数据类型隐含着数据结构和定义在该结构上的操作的统一。例如C+中的整型就是整数的数学含义与算术运算的统一体，只是由于这些基本数据类型中的数据结构的具体表示、基本操作和具体实现都很规范，可以通过系统内置而隐藏起来。,典型题解析（应用题）,2.说明数据的逻辑结构和存储结构之间的关系。解答：数据的逻辑结构和存储结构是密切相关的两个方面。数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式。数据的存储结构属于具体实现的视图，是面向计算机的，其基本目标是将数据及其逻辑关系存储到计算机的内存中。一般来说，一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。,典型题解析（应用题）,3.抽象数据类型的主要特点是什么？数据类型和抽象数据类型的关系如何？使用抽象数据类型的主要好处是什么？解答：抽象数据类型是指一个数据结构及定义在该结构上的一组操作。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的逻辑特性不变就不影响它的外部使用。数据类型是高级语言中的一个概念，它是一个值的集合和一组操作的集合，如C语言中的整型、实型和字符型等。实际上数据类型是厂家已经实现了的数据结构。抽象数据类型可以理解为对数据类型的进一步抽象，抽象数据类型不局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自定义的数据类型。抽象数据类型是提供了使用和实现两个不同的视图，实现了封装和信息隐藏。抽象数据类型的定义部分只包含数据的逻辑特性和基本操作的集合，一方面，使用者依据这些定义来使用抽象数据类型，即通过操作集合对该抽象数据类型进行各种处理；另一方面，抽象数据类型的实现者依据这些定义来完成该抽象数据类型的具体实现，包括存储结构的设计和基本操作的实现。,算法和算法分析,考核知识点1.算法的定义（）说明：通常一个问题可以有多种算法，一个给定算法解决一个特定的问题。2.算法的特性（）输入、输出、有穷性、确定性、可行性3.算法的描述方法（）常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等，其中伪代码被称为算法语言，是比较合适的描述算法的方法。说明：伪代码的书写形式没有严格的规定，只是要求了解任何一种现代程序设计语言的人都能够很好的理解。,算法和算法分析,考核知识点4.算法的时间复杂度（）算法的渐近时间复杂度（简称时间复杂度）考察当问题规模充分大时，算法中基本语句的执行次数在渐近意义上的阶，通常用大O记号表示。问题规模是指输入量的多少。基本语句是执行次数与整个算法的执行次数成正比的语句。常用的算法时间复杂度由小到大依次为：clog2nnnlog2nn2n32n3nn!说明：撇开与计算机软硬件有关的因素，影响算法时间代价的最主要因素是问题规模。,算法和算法分析,考核知识点5.算法的空间复杂度（）算法的空间复杂度是指在算法的执行过程中需要的辅助空间数量。辅助空间是除算法本身和输入输出数据所占据的空间之外，算法在运行过程中临时开辟的存储空间。算法的空间复杂度表示为：S(n)=O(g(n)表示随着问题规模n的增大，算法运行所需存储量的增长率与函数g(n)的增长率相同。,算法和算法分析典型题解析,选择题：主要考察算法的基本概念，要求深刻理解算法、算法的特性、算法与程序的关系，掌握算法时间性能的度量方法、基本语句执行次数的计算、时间复杂度的分析等有关内容。,算法和算法分析典型题解析,选择题1：下面（）不是算法应具备的特性。A.有穷性B.确切性C.高效性D.可行性解答：C分析：高效性是好算法应具备的特性。,算法和算法分析典型题解析,选择题2：算法必须具备输入、输出和（）等特性。A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、稳定性和有穷性D.易读性、稳定性和健壮性解答：B分析：可移植性、可扩充性、易读性、稳定性和健壮性都是好算法应该具备的特性。,算法和算法分析典型题解析,选择题3：当输入非法错误时，一个“好”的算法会进行适当处理，而不会产生难以理解的输出结果，这称为算法的（）。A.可读性B.健壮性C.正确性D.有穷性解答：B分析：健壮性也称鲁棒性，是指算法对非法输入的抵抗能力，即对于错误的输入，算法应能识别并做出处理，而不是产生错误动作或陷入瘫痪。,算法和算法分析典型题解析,选择题4：算法分析的目的是（），算法分析的两个主要方面是（）。A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和文档性E.空间性能和时间性能F.正确性和简明性G.可读性和文档性H.数据复杂性和程序复杂性解答：C,E分析：数据结构的合理性需要从多方面进行权衡；算法中输入和输出的关系是由问题本身决定的，一般和算法无关。,算法和算法分析典型题解析,选择题5：算法的时间复杂度与（）有关。A.问题规模B.待处理数据的初态C.算法的易读性D.A和B解答：D分析：有时算法本身比较复杂但是时间性能较好，例如快速排序算法比较复杂，但快速排序是目前在平均情况下最快的排序方法；算法的时间复杂度不仅取决于问题规模，还与处理数据的初态有关，例如对n个元素组成的序列进行排序，如果初始排列不同则排序的时间性能有很大的差别。,算法和算法分析典型题解析,选择题6：某算法的时间复杂度是O(n2)，表明该算法（）。A.问题规模是n2B.执行时间等于n2C.执行时间与n2成正比D.问题规模与n2成正比解答：C分析：算法的时间复杂度是O(n2)，问题规模可能是n（例如对n个元素进行排序），也可能是n2（例如对n*n的方阵进行转置），也有其他可能，因此，从时间复杂度不能确定问题规模；算法的时间复杂度是O(n2)表明算法的执行时间T(n)=c*n2(C为常数).,算法和算法分析典型题解析,选择题7：下面说法错误的是（）。1)算法原地工作的含义是指不需要任何额外的辅助空间2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法3)所谓的时间复杂度是指最坏情况下，估算算法执行时间的一个上界4)同一个算法，实现语言的级别越高，执行效率就越低A.1)B.1),2)C.1),4)D.3)解答：B分析：算法原地（也称就地）工作是指算法的空间复杂度为O(1)，例如直接插入排序算法需要一个用于交换的临时单元；说法2)考虑在时间上的性能，此时需要考虑两个复杂度的系数，例如复杂度为O(n)的算法其系数为100,算法复杂度为O(2n)的算法的系数为1，这两个函数曲线就有一个交叉点，如果仅就时间复杂度而言，复杂度O(n)的算法优于复杂度为O(2n)的算法；时间复杂度需要考虑最坏情况下，算法执行时间的一个上界；说法4)中“实现语言的级别”指的是机器语言、汇编语言和高级语言。,算法和算法分析典型题解析,选择题8：设某算法完成对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+500，则该算法的时间复杂度是A.O(1)B.O(n)C.O(nlog2n)D.O(nlog2n+n)解答：C分析：算法的时间复杂度可以忽略所有低次幂和最高次幂的系数。,算法和算法分析典型题解析,选择题9：假设时间复杂度为O(n2)的算法在有200个元素的数组上运行需要3.1ms，则在有400个元素的数组上运行需要（）ms?A.3.1B.6.2C.12.4D.9.61解答：C分析：运行时间为：3.1*(400/200)2=12.4ms。,算法和算法分析典型题解析,选择题10：下列程序段加下划线的语句执行（）次?for(m=0,i=1;i=n;i+)for(j=1;j=2*i;j+)m=m+1;A.n2B.3nC.n(n+1)D.n3解答：C分析：外层循环执行n次，内层循环执行2,4,6,2n次，共执行(2+4+6+2n)=n(n+1)次。,如何估算算法的时间复杂度,算法主要由程序的控制结构（顺序，分支，循环）和原操作（必须的操作）构成，算法的时间主要取决于两者。算法控制结构原操作,固有数据类型的操作,如何估算算法的时间复杂度,算法的执行时间原操作(i)的执行次数原操作(i)的执行时间算法的执行时间和原操作执行次数之和成正比具体而言：从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。,或者说算法中基本操作重复执行的次数是问题规模n的某个函数f(n),语句的频度（FrequencyCount),+x;s=0;,时间复杂度,for(j=1;j=n;+j)+x;s+=x;,语句的频度（FrequencyCount):重复执行的次数。此算法中的语句的频度为1，时间复杂度为O(1)。为常量阶,语句的频度为n，时间复杂度为O(n)。为线性阶,时间复杂度,for(j=1;j=n;+j)for(k=1;k=n;+k)+x;s+=x;,语句频度为nn，时间复杂度为O(n2)。为平方阶,时间复杂度,for(j=1;j=n;+j)for(k=1;k=j;+k)+x;s+=x;语句频度：,为近似于n2，所以时间复杂度仍为O(n2)。,时间复杂度只考虑量级就可以了。,时间复杂度,s=0;for(j=1;j=n;j*=2)for(k=1;k=n;+k)s+;语句频度为：,时间复杂度为：O(nlog2n),x表示不小于x的最小整数，即向上取整，如6.1=7,算法和算法分析典型题解析,应用题1：已知如下程序段：FORi:=ndownto1do语句1BEGINx:=x+1;语句2FORj:=ndowntoido语句3y:=y+1;语句4END;语句1执行的频度为：n+1语句2执行的频度为：n语句3执行的频度为：2+3+4+(n+1)=n*(2+n+1)/2=n(3+n)/2语句4执行的频度为：1+2+3+n=n(n+1)/2,算法和算法分析典型题解析,应用题2：分析以下各程序段，并用大O记号表示其执行时间。i=1;k=0;while(in-1)k=k+10*i);i+;,基本语句是k=k+10*i；共执行了n-2次，所以T(n)=O(n),算法和算法分析典型题解析,应用题2：分析以下各程序段，并用大O记号表示其执行时间。2)i=1;k=0;dok=k+10*i);i+;while(i=n),基本语句是k=k+10*i；共执行了n次，所以T(n)=O(n),算法和算法分析典型题解析,应用题2：分析以下各程序段，并用大O记号表示其执行时间。3)i=1;j=0;while(i+jj)j+;elsei+;,分析条件语句，每循环一次，i+j整体加1，共循环n次，所以T(n)=O(n),算法和算法分析典型题解析,应用题2：分析以下各程序段，并用大O记号表示其执行时间。4)y=0;while(y+1)*(y+1)=n)y=y+1;,设循环体共执行了T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即(T(n)+1)2=n所以：T(n)=O(n1/2),算法和算法分析典型题解析,应用题2：分析以下各程序段，并用大O记号表示其执行时间。5)for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x+;,x+是基本语句，所以,算法和算法分析典型题解析,应用题2：分析以下各程序段，并用大O记号表示其执行时间。6)for(i=0;in;i+)for(j=0;jm;j+)aij=0;,aij=0是基本语句，执行了m*n次，所以T(m,n)=O(m*n),算法和算法分析典型题解析,应用题3：分析以下算法的时间复杂度。voidfunc(intn)inti=0,s=0;while(sn)i+;s=s+i;,解答：对于while语句，设执行的次数为m，i从0开始递增1，直到m-1为止，有：s=0+1+2+m-1=m(m-1)/2,并满足：s=m(m-1)/2n，则有，所以，该算法的时间复杂度为：,算法和算法分析典型题解析,应用题4：设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。intm=0,i,j;for(i=1;i=n;i+)for(j=2*i;j=n;j+)m+;,算法和算法分析典型题解析,应用题5：分析以下算法的时间复杂度。voidfunc(intn)inti=1,k=100;while(in)k+;i+=2;,解答：设while循环语句执行的次数为m，i从1开始每次递增2，最后取值为1+2m，有：i=1+2mn,即m(n-1)/2=O(n)所以，该算法的时间复杂度为：O(n),算法和算法分析典型题解析,应用题6：下面程序段中带下划线的语句的执行次数的数量级是（）。i=1；WHILE(in2,则算法A2好于算法A1.,算法和算法分析典型题解析,应用题12：度量一个算法的执行时间通常有几种方法？各有何优缺点？解答：通常有两种方法：事后统计和事前分析。事后统计方法的优点是比较精确，缺点是必须根据算法编写相应的程序，而且所得的时间依赖于计算机的软硬件环境，有时候容易掩盖算法本身的优劣。事前分析方法的优点是不必运行程序就可以从复杂度角度比较算法的优劣，缺点是不够精确，当一个算法比另一个算法稍好一些时不易判断。,挑战题解析,综合应用题：主要考查难度较大的算法时间性能分析、有关深层次理解DS的综合问题。,Hanoi塔算法,voidHanoi(intn,charx,chary,charz)if(n