2024新高考浙江版高中信息技术专题八 数据结构与算法知识点归纳讲解PPT

专题八数据结构与算法考点一　数据结构与算法效率一、算法效率1.衡量标准算法效率的高低可由算法的复杂度来衡量。算法复杂度又分为算法的时间复杂度和空间复杂度,其中时间复杂度反映了算法执行所需要的时间,而空间复杂度反映了算法执行所需要占用的存储空间。2.时间复杂度1)一般将算法中语句的执行次数作为时间复杂度的度量标准。语句总的执行次数T(n)是关于问题规模n的函数。所谓问题规模(也称为输入的大小)是指处理问题的大小,即用来衡量输入数据量的整数。考点清单2)时间复杂度常用符号O 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 述,不包括T(n)函数的低阶项和首项系数,如 n(n-1)的量级与n2相同,其时间复杂度可表示成O(n2)。3)推导大O阶的方法用O()来体现算法时间复杂度,称之为大O阶记法。其推导方法如下:①用常数1取代运行时间中的所有加法常数。②在修改后的运行次数函数中,只保留最高阶项。③如果最高阶项存在且不是1,那么去除与这个项相乘的常数。得到的结果就是大O阶。例如, n(n-1)  n2 n24)常见的时间复杂度耗费时间的大小关系为O(1)<O(log2n)<O(n)<O(n2)<O(n3)<O(2n)<O(n!)。二、数据结构对算法效率的影响1.数据组织成不同的结构,是为了满足不同问题的需求,便于算法对数据的操作,提高算法处理数据的效率。2.数据结构的不同选择会影响算法的运行效率。3.通过比较时间复杂度O()来比较不同算法的效率。考点二　迭代与递归一、迭代与迭代算法1.迭代是重复反馈过程的活动,其目的通常是使结果符合目标需求。2.迭代算法是利用计算机运算速度快、适合做重复性操作的特点,让计算机重复执行一组指令(或一些步骤),这组指令(或这些步骤)每执行一次时,都会将变量从原值递推出一个新值。二、利用迭代算法处理问题利用迭代算法处理问题需要考虑三个方面:1.确定迭代变量:在能够用迭代算法处理的问题中,至少具有一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。2.建立迭代关系式:所谓迭代关系式,指如何从变量的前一个值推出其下一个值的 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 (或关系)。3.控制迭代过程:迭代过程在经过若干次重复执行以后要能结束,因此,要设定迭代结束的条件。三、递归的概念与特性1.概念:大问题的解决中嵌套着与原问题相似的规模较小的问题,这种解决问题的方式在计算机科学中称为递归,通过函数自己调用自己来实现,即一个函数在其定义中直接或间接调用自身的一种方法。2.递归的特性:通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归往往能使函数的定义和算法的描述简洁且易于理解,极大地减少了程序代码量。3.能采用递归描述的算法的特征为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解中方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法。当递归到达某个边界,如问题规模缩减为0或1时,能直接得解。4.利用递归算法解决问题的关键步骤①抽象建立递归模型,确定递归公式。②确定临界条件(即递归结束条件)。考点三　数据排序一、排序1.概念排序就是整理数据的序列,使其中元素按照某个值的递增(或递减)的次序重新排列的操作。在排序的过程中,数据元素的值保持不变,但其在序列中的顺序可能会改变。2.存储方式待排序数据的存储一般有数组和链表两种方式,利用数组存储数据,在排序时需要对数据本身进行物理重排,可能需要移动数据的位置,而利用链表存储数据,无须移动数据,仅需修改指针即可。二、冒泡排序1.冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整,让较大的数“下沉(上冒)”,较小的数“上冒(下沉)”的一种排序技术。2.算法效率:对于n个元素的数组,共需要n-1趟,第一趟的比较次数为n-1,第二趟的比较次数为n-2,以此类推,最后一趟的比较只需1次。共需比较(n-1)+(n-2)+…+1= 次。其时间复杂度为O(n2)。三、选择排序算法1)在参加排序的数组的所有元素中找出最小(或最大)的数据,使它与第一个元素(左端)中的数据相互交换位置。然后在余下的元素中找出最小(或最大)的数据,与第二个元素中的数据交换位置。以此类推,直到所有元素成为一个有序的序列。2)对长度为n的数组,每一趟排序过程都会扫描待排序区域的所有元素,将最小(或最大)值交换到最左端,直至只剩下1个元素为止,总共排序n-1趟,比较的次数为 ,时间复杂度为O(n2)。考点四　数据查找一、查找查找又称检索,计算机根据所给条件查找出满足条件的对象,即在存储的一批数据内寻找出一个特定的数据,或者确认在该批数据内是否存在这样的数据。若没有找到满足条件的对象,则返回特定值,表明查找失败;若查找到满足条件的对象,则表明查找成功。二、顺序查找1.概念顺序查找又称线性查找,从顺序表的一端开始,依次将每个元素的关键字与给定值key(查找键)进行比较。若某个元素的关键字等于key,则表明查找成功;若所有元素都比较完毕仍找不到,则表明查找失败。2.优缺点顺序查找的优点是算法简单,容易实现,且对存放数据的表结构无任何要求,不管数据是否有序,均可使用,缺点是查找效率低,当数据量较大时不宜采用。三、二分查找1.概念二分查找又称折半查找,对分查找。二分查找首先将查找键与有序数组内处于中间位置的元素进行比较,如果中间位置上的元素与查找键不同,根据数组元素的有序性,就可以确定在数组的前半部分还是后半部分继续查找;在新确定的范围内,继续按上述方法进行查找,直到获得最终结果。2.二分查找是一种效率很高的查找方法,要求被查找的数据序列必须是有序的,最多进行⌊log2n」+1次比较。考向一　数据结构与算法效率数据结构1.数据结构指的是数据之间的相互关系,即数据的组织形式。1)数据元素之间的逻辑关系,也称为数据的逻辑关系。2)数据元素及其关系在计算机存储器内的表示,也称为数据的存储结构或物理结构。3)数据的运算,即对数据施加的操作。2.实际应用中的数据结构 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 主要考虑数据对象之间的逻辑关系,所以数据结构一般指向的就是逻辑结构。考向突破例1    (2022Z20名校联盟,3)下列有关数据结构的说法正确的是 (　    )A.数组是一种适用于组织、存储涉及频繁插入与删除的数据结构B.链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的C.Excel软件中的撤销操作体现了队列的思想D.树结构中,每个子节点的父节点可以有多个解析　本题主要考查数据结构的相关知识。链表是一种适用于组织、存储涉及频繁插入与删除的数据结构,A选项错误;Excel中的撤销操作体现了栈的思想,C选项错误;树结构中,每个子节点的父节点只可以有一个,D选项错误。 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 　B1-1　下列关于算法效率 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 的说法,正确的是 (　    )A.算法复杂度是指算法控制结构的复杂程度B.算法的时间复杂度是指算法执行的速度C.算法的空间复杂度是指算法执行所需的时间D.算法的时间复杂度是指算法在执行过程中基本运算的次数答案    D1-2　下列有关数据结构对算法效率的影响的描述,不正确的是 (　    )A.同一个算法不一定能适用多种不同的数据结构B.针对同一个数据结构设计不同的算法,算法的运行效率可能相同C.使用链表存储和处理数据比使用数组效率更优D.设计算法时,应根据实际问题选择合适的数据结构答案    C考向二　迭代与递归迭代算法与递归算法的区别1.迭代是利用变量的旧值推算出变量的一个新值;而递归算法是指一个函数在其定义中直接或间接调用自身的一种方法,它通常把一个复杂的问题转化为一个与原问题相似的规模较小的问题来解决,可以极大地减少代码量,降低编程的难度。因此,迭代算法效率较高,而递归算法比较占用空间,程序运行效率较低。2.递归是通过函数自己调用自己,而迭代是不断地调用赋值语句;递归中一定有迭代,但是迭代中不一定有递归,递归和迭代在大部分情况下可以相互转换。例2    (2022名校协作体,11)有如下Python程序段:def　f(x):　　if　x==1:　　　　return1　　else:　　　　return　x*f(x-1)s=0foriinrange(1,6):　　s+=f(i)print(s)执行该程序段后,变量s的值是 (　    )A.33　　B.34　　C.154　　D.153解析　本题主要考查递归算法的程序的实现。从代码x*f(x-1)可知,该函数是通过递归算法实现x的阶乘。后面的循环是把1~5的阶乘进行累加,1!+2!+3!+4!+5!=1+2+6+24+120=153,D选项正确。答案　D2-1    (2022丽水质量监控,11)有如下Python程序段:defs(x):　　ifx<=2:　　　　y=x　　else:　　　　y=s(x-1)+s(x-2)　　returnya=int(input("请输入正整数:"))result=s(a)print(result)运行程序,输入值为6,则输出结果为 (　    )A.8　　B.9　　C.13　　D.14答案    C2-2　猴子吃桃问题:一群猴子摘了一堆桃子,不知道总数。猴子们第一天吃了总数的一半多一个,第二天吃了剩余桃子的一半多一个,……,直到第十天,发现只剩1个桃子了。(1)第九天时总共有　　　    个桃子,猴子们当天吃了　　　    个桃子。(2)设计一个递归算法,编程计算猴子总共摘了几个桃子,请在划线处填入合适的代码。deffun(n):　　if　　①　    :　　　　　return1　　else:　　　　　return　　②　    答案    (1)4;3    (2)①n==10　②2*(fun(n+1)+1)考向三　数据排序1.冒泡排序的代码实现对数组a进行升序排序,长度为n的数组需要排序n-1趟。n=len(a)foriinrange(0,n-1):#排序趟数　　forjinrange(n-1,i,-1):#向左扫描,将最小值移到左端　　ifa[j]<a[j-1]:　　a[j],a[j-1]=a[j-1],a[j]2.选择排序的代码实现对数组a进行升序排序,长度为n的数组需要排序n-1趟。n=len(a)foriinrange(n-1):　　k=i　forjinrange(i+1,n):#扫描待排序区间,寻找最小值下标　　　ifa[j]<a[k]:　　　　　k=j　　　ifk!=i:#如果a[i]非最小值,则将最小值交换到下标为i的位置　　　　　a[i],a[k]=a[k],a[i]例3    (2022Z20名校联盟,12)某Python程序如下:importrandomn=random.randint(1,4)a=[7,2,7,3,9,4]foriinrange(1,n):　　forjinrange(0,6-i):　　　ifa[j]<a[j+1]:　　　　a[j],a[j+1]=a[j+1],a[j]执行该程序段后,数组a中的元素不可能为 (　    )A.9,7,7,4,3,2B.7,7,3,9,4,2C.7,9,7,4,3,2D.7,2,7,3,9,4解析　本题主要考查冒泡排序、随机数的知识。n的范围是1~4的整数,当n=1时,range(1,1),循环次数为0.当n=2、3、4时即循环1、2、3次的结果分别写出,不能得到A中结果。答案　A3-1    (2022丽水质量监控,10)采用选择排序算法对数据序列“12,23,24,15,11,10”完成升序排序,则需要交换的次数为 (　    )A.3　　B.4　　C.5　　D.6答案    A3-2    (2022绍兴鲁迅中学期中,11)有如下Python程序段:n=4a=[[j*n+i+1forjinrange(n)]foriinrange(n)]foriinrange(0,n,2):　forjinrange(n//2):　　a[i][j],a[i][n-j-1]=a[i][n-j-1],a[i][j]则程序执行后,a[0][1]和a[1][1]的值分别为(　    )A.2和7　　B.3和6C.5和10　　D.9和6答案    D考向四　数据查找1.顺序查找的代码实现假设n个数据依次存储在长度为n的数组a中,查找键为key,自定义函数Seq_search(a,key)返回数组a中首个值为key的元素下标,若找不到key,则返回-1。defseq_search(a,key):　　foriinrange(len(a)):　　ifa[i]==key:　　returni　　　else:　　return-12.二分查找的代码实现1)假设n个递增数据依次存储在长度为n的数组a中,查找键为key,自定义函数binary_search(a,key)返回数组a中某个值为key的元素下标,若找不到key,则返回-1。defbinary_search(a,key):　L,R=0,len(a)-1　whileL<=R:　　m=(L+R)//2　　#左偏m=(L+R+1)//2　　#右偏ifkey==a[m]:　　returnmelifkey<a[m]:　　R=m-1else:　　L=m+1return-12)二分查找算法使用递归函数bsearch(a,L,R,key)也能实现,其中L和R分别表示查找区间的左、右边界。defbsearch(a,L,R,key):　ifL>R:　　return-1　m=(L+R)//2　#左偏　ifkey==a[m]:　　returnm　elifkey<a[m]:　　returnbsearch(a,L,m-1,key)　else:　　returnbsearch(a,m+1,R,key)例4    (2022七彩阳光返校考,11)有如下Python程序段:importrandoma=[4,2,6,5,4,2,9,7]k=random.randint(1,10)i=0;j=len(a)-1;x=""whilei<=j:　　m=(i+j)//2　　ifk<=a[m]:　　　　j=m-1;x=x+"L"　　else:　　　　i=m+1;x=x+"R"print(x)执行该程序段后,输出的结果不可能出现的是 (　    )A."LLL"　　B."LRL"　　C."RLR"　　D."RRRR"解析　本题主要考查二分查找算法。输入k的值在1~10的整数,m的第一个值为3,则对应列表a中元素5,所以把[1,10]分成[1,5]和[6,10]两段。最终分成四段[1,2]、[3,5]、[6,9]、[10,10]分别对应四种不同的s的值"LLL","LRL","RRL","RRRR",所以不可能出现的是RLR.答案　C4-1    (2022A9协作体返校考,11)有如下Python程序段:a=[99,85,74,68,53,42,34,27,20,13]key=int(input("请输入一个整数:"))i,j,k,c,flag=0,9,0,"N",Falsewhilei<=jandflag==False:　　m=(i+j+1)//2　　k=k+1　　ifkey==a[m]:　　　c="Y"　　　flag=True　　ifkey>a[m]:　　　j=m-1　　else:　　　i=m+1print(c,k)执行该程序段后,下列说法正确的是 (　    )A.该程既能用于升序序列的查找,也能用于降序序列的查找B.若输出k的值为2,则c的值一定为YC.若输入key的值为74,程序执行后变量i和j的值分别为0和4D.若输入两位任意正整数,k的值介于1和3之间答案    B4-2    (2022绍兴柯桥期末,12)某二分查找算法的Python程序段如下:a=[8,17,24,30,36,40,55,58,61,66]L,R=0,9s=[]key=int(input("请输入要查找的数据:"))whileL<=R:　　m=(L+R+1)//2　　ifa[m]==key:　　　　break　　elifa[m]>key:　　　　R=m-1　　else:　　　　L=m+1　　s.append(a[m])print(s)执行该程序段,当输入的值为30时,程序输出的结果是 (　    )A.[40,24]　　B.[40,24,36]C.[24,36]　　D.[36,17,24]答案    B4-3　有如下Python程序段:d=[3,9,1,9,6,8,9]n=len(d)key=int(input("pleaseinputkey:"))i=0c=0flag=Trues=""whilei<=n-1:　　ifkey==d[i]:　　　flag=False　　　s=s+str(i)+","　　i=i+1ifflag:　　print("未找到")else:print("找到,索引位置为:",s[0:len(s)-1])程序运行时,输入key的值为9,程序运行后,变量i的值为 (　    )A.未找到B.找到,索引位置为:1C.找到,索引位置为:1,3D.找到,索引位置为:1,3,6答案    D