16专题八　数据结构与算法

第一部分信息技术专题八数据结构与算法高考技术某省市专用考点清单考向清单目录考点一

数据结构与算法效率考点二

迭代与递归考点三

数据排序考点四数据查找考向一

数据结构与算法效率考向二

迭代与递归考向三

数据排序考向四

数据查找考点一数据结构与算法效率一、算法效率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.树结构中,每个子节点的父节点可以有多个B解析

本题主要考查数据结构的相关知识。链表是一种适用于组织、存储涉及频繁

插入与删除的数据结构,A选项错误;Excel中的撤销操作体现了栈的思想,C选项错误;树

结构中,每个子节点的父节点只可以有一个,D选项错误。1.(2024嘉兴基测,10)下面有关数据结构的说法不正确的是

(

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

本题考查数组、链表、栈、队列等基础数据结构的相关知识。软件中“撤

销”功能的实现可以通过一个栈来存储操作的历史记录,当用户进行操作时,将其添加

到栈中,当用户想要撤销操作时,从栈中取出最近的操作并撤销。2.(2023浙江6月选考,12,2分)已排序的列表a有n个整型元素,现要查找出现次数最多的

值并输出。若出现次数最多的值有多个,则输出最前面的一个。实现该功能的程序段

如下,方框中应填入的正确代码为

(

)A解析

本题考查基本算法和数据结构的应用等知识。由于列表a为有序列表,即有“值

相同的数都是相邻的”这一逻辑关系,因此计算每个数的出现次数。可以通过检查相

邻两个数进行统计。观察程序段和选项中的代码可知:变量v为出现次数最多的值在列

表a中的索引,变量c为当前数值的出现次数,变量m统计次数中的最大值。其算法思想

是:若相邻两个数相等,则计数器c加1,否则应该将c变为初值1,首先可以排除选项B,因

为该选项中else分支不符合逻辑。选项CD都存在缺陷,当最多的一组相同的数出现在

列表的最后时,均不能准确统计结果。例如a=[2,3,3,3,4,4,4,4,4]。此时输出值为3,而正

确结果为4。选项A逻辑结构合理,可以完成各种情况的统计任务。考向二迭代与递归迭代算法与递归算法的区别1.迭代是利用变量的旧值推算出变量的一个新值;而递归算法是指一个函数在其定义

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

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

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

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

(2025届湖衢某省市质量检测,10)定义如下函数:deff(x,y,flag):ifflag==False:returnx*y//f(x,y,notflag)ifx==y:returnxelifx<y:returnf(x,y-x,flag)

else:returnf(x-y,y,flag)执行语句w=f(6,9,False)后,w的值为(

)A.18B.9C.6D.3A解析

本题考查递归算法相关知识。由代码可知,函数f的调用过程如下:f(6,9,False)→

6*9//f(6,9,True)→6*9//f(6,3,True)→6*9//f(3,3,True)→6*9//3=18,因此输出结果为18,故

选A。1.(2024浙南名校联盟联考,10)有如下Python程序段:deff(x):ifx==1:return2else:returnf(x-1)**2y=f(3)print(y)针对训练执行该程序段后,输出的结果是

(

)A.4B.8C.16D.32C解析

本题考查递归的相关知识。由程序可得,f(3)=f(2)**2→(f(1)**2)**2→(2**2)**2

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

(

)DA.2B.6C.8D.10解析

本题考查递归的相关知识。递过程:peach(8)=(peach(9)+1)*2;peach(9)=(peach(10)+1)*2。归过程:peach(9)=(1+1)*2=4;peach(8)=(4+1)*2=10。考向三数据排序典例3

(2025届浙南名校联盟联考,10)有如下Python程序段:k=random.randint(2,4)foriinrange(1,k):forjinrange(i,0,-1):ifa[j]<a[j-1]:a[j],a[j-1]=a[j-1],a[j]若a为[14,11,2,1,20,16],运行该程序段后,a的结果不可能是

(

)A.[11,14,2,1,20,16]B.[2,11,14,1,20,16]DC.[1,2,11,14,20,16]D.[1,2,11,14,16,20]解析

本题程序代码采用的是非常规的冒泡交换方式。k的值决定了排序的趟数,其取

值分别是2、3、4:当k=2时,排序1趟,前2个有序,后面的数据无变化,对应到选项A;当k=3时,排序2趟,前3个有序,后面的数据无变化,对应到选项B;当k=4时,排序3趟,前4个有序,后面的数据无变化,对应到选项C;选项D不可能。1.(2024Z20联盟联考,11)lst1和lst2都是升序排序的列表,执行如下Python程序段:result=[]i=0#用于遍历lst1j=0#用于遍历lst2whilei<len(lst1)andj<len(lst2):

#①iflst1[i]<lst2[j]:result.append(lst1[i])针对训练i+=1else: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解析

本题考查两个升序数组的归并排序。lst1,lst2都是升序数组,①处while循环完成两个数据都有数据时的归并,结果添加到re-

sult,其中一个数组读完即退出第1个while循环,后面②处循环处理lst1没读完的情况,③

处循环处理lst2没读完的情况。若lst1所有数值均小于lst2,则A说法正确;同理,若lst2所

有数值均小于lst1,则B说法正确;合并后的数组为升序,D说法正确。①处while循环退

出条件是有一个数组已经读完,故C说法错误。2.(2024新阵地联盟联考,12)某对分查找算法的Python程序段如下:fromrandomimportrandinta=[8,12,15,18,18,25,25,35,47]i=0;j=8key=randint(8,48)whilei<=j:m=(i+j)//2ifkey<=a[m]:j=m-1else:i=m+1print(i)该程序执行完成后输出值为3,以下说法错误的是

(

)A.key值可能是16到18的整数B.该程序中m=(i+j)//2被执行4次C.该程序可实现查找第一个大于等于key值的位置D.若key<=a[m]改为key<a[m],且key=25,则程序执行后i值为6D解析

本题考查随机数及二分查找知识。该程序执行完成后输出值为3,可以推断a[2]

<key<=a[3],故选项A正确。若key值是16到18之间,查找共进行4次,因此m=(i+j)//2被执

行4次,故选项B正确。由于key<=a[m]时调整j,因此循环结束后的i是第一个大于等于

key值的位置,因此选项C正确。选项D错误,修改key<=a[m]为key<a[m],且key=25时,执

行后i的值应该是7,即数值35所在的下标。考向四数据查找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

(2025届湖衢某省市质量检测,11)某二分查找算法的Python程序段如下:keyt=5,0i,j=0,len(d)-1whilei<=j:t+=1m=(i+j)//2ifkey==d[m]:breakelifkey<d[m]:j=m-1else:i=m+1当d为[2,4,5,6,7,8,9]时,在d中插入一个元素x,维持d为一个非降序序列,在元素x插入前

后分别运行程序段,若变t的值相同,则增加的元素x可能是

(

)A.2B.3C.4D.6D解析

本题考查二分查找算法相关知识。由代码可知,key的值是5,当d为[2,4,5,6,7,8,9]

时,模拟二分查找需要3次循环,找到key=5后程序退出,因t=3。而在d中插入一个元

素x,维持d为一个非降序序列,在元素x插入前后分别运行程序段,需要变t的值相

同。只有当插入的x大于key时,二分查找的次数才可能保持不变。因为若插入5前面,

则二分查找中