浙江版高中信息技术复习教学专题八数据结构与算法课件

第一部分信息技术

专题八数据结构与算法高考

技术浙江省专用考点一数据结构与算法效率一、算法效率1.衡量标准算法效率的高低可由算法的复杂度来衡量。算法复杂度又分为算法的时间复杂度和

空间复杂度,其中时间复杂度反映了算法执行所需要的时间,而空间复杂度反映了算

法执行所需要占用的存储空间。2.时间复杂度(1)一般将算法中语句的执行次数作为时间复杂度的度量标准。语句总的执行次数T

(n)是关于问题规模n的函数。所谓问题规模(也称为输入的大小)是指处理问题的大小,即用来衡量输入数据量的整数。(2)时间复杂度常用符号O表述,不包括T(n)函数的低阶项和首项系数,如

n(n-1)的量级与n2相同,其时间复杂度可表示成O(n2)。(3)推导大O阶的方法用O()来体现算法时间复杂度,称之为大O阶记法。其推导方法如下:①用常数1取代运行时间中的所有加法常数。②在修改后的运行次数函数中,只保留最高阶项。③如果最高阶项存在且不是1,那么去除与这个项相乘的常数。得到的结果就是大O

阶。例如,

n(n-1)

n2

n2(4)常见的时间复杂度耗费时间的大小关系为O(1)<O(log2n)<O(n)<O(n2)<O(n3)<O(2n)<O(n!)。二、数据结构对算法效率的影响1.数据组织成不同的结构,是为了满足不同问题的需求,便于算法对数据的操作,提高

算法处理数据的效率。2.数据结构的不同选择会影响算法的运行效率。3.通过比较时间复杂度O()来比较不同算法的效率。考点二迭代与递归一、迭代与迭代算法1.迭代是重复反馈过程的活动,其目的通常是使结果符合目标需求。2.迭代算法是利用计算机运算速度快、适合做重复性操作的特点,让计算机重复执行

一组指令(或一些步骤),这组指令(或这些步骤)每执行一次时,都会将变量从原值递推

出一个新值。二、利用迭代算法处理问题利用迭代算法处理问题需要考虑三个方面:1.确定迭代变量在能够用迭代算法处理的问题中,至少具有一个直接或间接地不断由旧值递推出新值

的变量,这个变量就是迭代变量。2.建立迭代关系式所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。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.实际应用中的数据结构设计主要考虑数据对象之间的逻辑关系,所以数据结构一般

指向的就是逻辑结构。例1

(2022Z20名校联盟,3)下列有关数据结构的说法正确的是

(

)A.数组是一种适用于组织、存储涉及频繁插入与删除的数据结构B.链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的C.Excel软件中的撤销操作体现了队列的思想D.树结构中,每个子节点的父节点可以有多个

解析

本题主要考查数据结构的相关知识。链表是一种适用于组织、存储涉及频繁插入与删除的数据结构,A选项错误;Excel中的撤销操作体现了栈的思想,C选项错

误;树结构中,每个子节点的父节点只可以有一个,D选项错误。

答案B1.(2024届嘉兴基测,10)下面有关数据结构的说法不正确的是

(

)A.在程序设计中,数据结构设计时主要考虑对象之间逻辑关系的实现B.链表结构适用于初始规模确定但在处理过程中频繁进行插入、删除操作的数据C.数组结构中采用下标访问数据,访问效率要高于链表结构D.大多数软件中都有“撤销”功能,实现此功能应采用队列结构答案

D

2.(2023浙江6月选考,12,2分)已排序的列表a有n个整型元素,现要查找出现次数最多的

值并输出。若出现次数最多的值有多个,则输出最前面的一个。实现该功能的程序段即练即清如下,方框中应填入的正确代码为

(

)c,m,v=1,1,0foriinrange(1,n):print(a[v])A.ifa[i]==a[i-1]:c+=1ifc>m:m=cv=ielse:c=1B.ifa[i]==a[i-1]:c+=1ifc>m:m=cv=ielse:c=1C.ifa[i]==a[i-1]:c+=1else:ifc>m:m=cv=i-1c=1D.ifa[i]==a[i-1]:c+=1else:ifc>m:m=cv=i-1c=1答案

A

考向二迭代与递归迭代算法与递归算法的区别1.迭代是利用变量的旧值推算出变量的一个新值;而递归算法是指一个函数在其定义

中直接或间接调用自身的一种方法,它通常把一个复杂的问题转化为一个与原问题相

似的规模较小的问题来解决,可以极大地减少代码量,降低编程的难度。因此,迭代算

法效率较高,而递归算法比较占用空间,程序运行效率较低。2.递归是通过函数自己调用自己,而迭代是不断地调用赋值语句;递归中一定有迭代,

但是迭代中不一定有递归,递归和迭代在大部分情况下可以相互转换。例2

(2022名校协作体联考,11)有如下Python程序段:deff(x):ifx==1:return1else:returnx*f(x-1)s=0foriinrange(1,6):s+=f(i)print(s)执行该程序段后,变量s的值是

(

)A.33B.34C.154D.153

解析

本题主要考查递归算法的程序的实现。从代码x*f(x-1)可知,该函数是通过递归算法实现x的阶乘。后面的循环是把1~5的阶乘进行累加,1!+2!+3!+4!+5!=1+2+6+24

+120=153,D选项正确。

答案D1.(2024届浙南名校联盟联考,10)有如下Python程序段:deff(x):ifx==1:return2else:returnf(x-1)**2y=f(3)print(y)即练即清执行该程序段后,输出的结果是

(

)A.4B.8C.16D.32答案

C

2.(2024届A9协作体返校考,9)有如下Python程序段:defpeach(n):ifn==10:return1else:return(peach(n+1)+1)*2print(peach(8))执行该程序段后,输出的结果是

(

)A.2B.6C.8D.10答案

D

考向三数据排序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=iforjinrange(i+1,n):#扫描待排序区间,寻找最小值下标ifa[j]<a[k]:k=jifk!=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中结果。

答案A1.(2024届Z20联盟联考,11)lst1和lst2都是升序排序的列表,执行如下Python程序段:result=[]i=0#用于遍历lst1j=0#用于遍历lst2whilei<len(lst1)andj<len(lst2):

#①iflst1[i]<lst2[j]:result.append(lst1[i])i+=1即练即清else:result.append(lst2[j])j+=1whilei<len(lst1):result.append(lst1[i])

#②i+=1whilej<len(lst2):result.append(lst2[j])

#③j+=1下列说法不正确的是

(

)A.程序段①执行后,result可能与lst1相同B.程序段①执行后,result可能与lst2相同C.在一次程序运行中,②处代码和③处代码可能都被执行D.程序执行后,列表result中的元素升序排序答案

C

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和7B.3和6C.5和10D.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:returnielse:return-12.二分查找的代码实现(1)假设n个递增数据依次存储在长度为n的数组a中,查找键为key,自定义函数binary_

search(a,key)返回数组a中某个值为key的元素下标,若找不到key,则返回-1。defbinary_search(a,key):L,R=0,len(a)-1whileL<=R:m=(L+R)//2#左偏m=(L+R+1)//2#右偏ifkey==a[m]:returnmelifkey<a[m]:R=m-1else:L=m+1return-1(2)二分查找算法使用递归函数bsearch(a,L,R,key)也能实现,其中L和R分别表示查找区

间的左、右边界。defbsearch(a,L,R,key):ifL>R:return-1m=(L+R)//2#左偏ifkey==a[m]:returnmelifkey<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)//2ifk<=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。

答案C例5

(2022绍兴诸暨期中,15)某二分查找算法的Python程序段如下:list1=["Carrot","Celery","Garlic","Lettuce","Mooli","Onion","Potato","Tomato"]key=list1[2]left,right=0,len(list1)-1c=0whileleft<=right:m=(left+right)//2c=c+1iflist1[m]>key:right=m-1else:left=m+1print(list1[left])程序执行后,下列说法正确的是

(

)A.变量c的值为4B.程序输出的结果为LettuceC.变量left的值为2D.变量right的值为3

解析

本题主要考查二分查找算法及Python程序实现。已知left=0,right=7,key="Garlic",第一次查找m=(left+right)//2=3,c=c+1=1,a(3)="Lettuce",判断list1[m]>key成立,执行right=m-1=2;第二次查找m=(left+right)//2=1,c=