资源简介

(共40张PPT)
考点一　数据结构与算法效率
一、算法效率
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)二、数据结构对算法效率的影响
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 (2022 Z20名校联盟,3)下列有关数据结构的说法正确的是 (　 )
A.数组是一种适用于组织、存储涉及频繁插入与删除的数据结构
B.链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的
C.Excel软件中的撤销操作体现了队列的思想
D.树结构中,每个子节点的父节点可以有多个
解析　本题主要考查数据结构的相关知识。链表是一种适用于组织、
存储涉及频繁插入与删除的数据结构,A选项错误;Excel中的撤销操作体
现了栈的思想,C选项错误;树结构中,每个子节点的父节点只可以有一个,
D选项错误。
答案　B
1-1　下列关于算法效率分析的说法,正确的是 (　 )
A.算法复杂度是指算法控制结构的复杂程度
B.算法的时间复杂度是指算法执行的速度
C.算法的空间复杂度是指算法执行所需的时间
D.算法的时间复杂度是指算法在执行过程中基本运算的次数
答案 D
1-2　下列有关数据结构对算法效率的影响的描述,不正确的是 (　 )
A.同一个算法不一定能适用多种不同的数据结构
B.针对同一个数据结构设计不同的算法,算法的运行效率可能相同
C.使用链表存储和处理数据比使用数组效率更优
D.设计算法时,应根据实际问题选择合适的数据结构
答案 C
考向二　迭代与递归
迭代算法与递归算法的区别
1.迭代是利用变量的旧值推算出变量的一个新值;而递归算法是指一个
函数在其定义中直接或间接调用自身的一种方法,它通常把一个复杂的
问题转化为一个与原问题相似的规模较小的问题来解决,可以极大地减
少代码量,降低编程的难度。因此,迭代算法效率较高,而递归算法比较占
用空间,程序运行效率较低。
2.递归是通过函数自己调用自己,而迭代是不断地调用赋值语句;递归中
一定有迭代,但是迭代中不一定有递归,递归和迭代在大部分情况下可以
相互转换。
例2 (2022名校协作体,11)有如下Python程序段:
def　f(x):
　　if　x==1:
　　　　return 1
　　else:
　　　　return　x*f(x-1)
s=0
for i in range(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选项正确。
答案　D
2-1 (2022丽水质量监控,11)有如下Python程序段:
def s(x):
　　if x<=2:
　　　　y=x
　　else:
　　　　y=s(x-1)+s(x-2)
　　return y
a=int(input("请输入正整数:"))
result=s(a)
print(result)
运行程序,输入值为6,则输出结果为 (　 )
A.8　　B.9　　C.13　　D.14
答案 C
2-2　猴子吃桃问题:一群猴子摘了一堆桃子,不知道总数。猴子们第一天
吃了总数的一半多一个,第二天吃了剩余桃子的一半多一个,……,直到第
十天,发现只剩1个桃子了。
(1)第九天时总共有　　　 个桃子,猴子们当天吃了　　　 个桃子。
(2)设计一个递归算法,编程计算猴子总共摘了几个桃子,请在划线处填入
合适的代码。
def fun(n):
　　if　　①　 :
　　　　　return 1
　　else:
　　　　　return　　②　
答案 (1)4;3 (2)①n==10　②2*(fun(n+1)+1)
考向三　数据排序
1.冒泡排序的代码实现
对数组a进行升序排序,长度为n的数组需要排序n-1趟。
n=len(a)
for i in range(0,n-1):#排序趟数
　　for j in range(n-1,i,-1):#向左扫描,将最小值移到左端
　　if a[j]　　a[j],a[j-1]=a[j-1],a[j]
2.选择排序的代码实现
对数组a进行升序排序,长度为n的数组需要排序n-1趟。
n=len(a)
for i in range(n-1):
　　k=i
　 for j in range(i+1,n):#扫描待排序区间,寻找最小值下标
　　　if a[j]　　　　　k=j
　　　if k!=i:#如果a[i]非最小值,则将最小值交换到下标为i的位置
　　　　　a[i],a[k]=a[k],a[i]
例3 (2022 Z20名校联盟,12)某Python程序如下:
import random
n=random.randint(1,4)
a=[7,2,7,3,9,4]
for i in range(1,n):
　　for j in range(0,6-i):
　　　if a[j]　　　　a[j],a[j+1]=a[j+1],a[j]
执行该程序段后,数组a中的元素不可能为 (　 )
A.9,7,7,4,3,2 B.7,7,3,9,4,2 C.7,9,7,4,3,2 D.7,2,7,3,9,4
解析　本题主要考查冒泡排序、随机数的知识。n的范围是1~4的整数,
当n=1时,range(1,1),循环次数为0.当n=2、3、4时即循环1、2、3次的结
果分别写出,不能得到A中结果。
答案　A
3-1 (2022丽水质量监控,10)采用选择排序算法对数据序列“12,23,24,1
5,11,10”完成升序排序,则需要交换的次数为 (　 )
A.3　　B.4　　C.5　　D.6
答案 A
3-2 (2022绍兴鲁迅中学期中,11)有如下Python程序段:
n=4
a=[[j*n+i+1 for j in range(n)] for i in range(n)]
for i in range(0,n,2):
　for j in range(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和6
C.5和10　　D.9和6
答案 D
考向四　数据查找
1.顺序查找的代码实现
假设n个数据依次存储在长度为n的数组a中,查找键为key,自定义函数Seq
_search(a,key)返回数组a中首个值为key的元素下标,若找不到key,则返回
-1。
def seq_search(a,key):
　　for i in range (len(a)):
　　if a[i]= =key:
　　return i
　　　else:
　　return -1
2.二分查找的代码实现
1)假设n个递增数据依次存储在长度为n的数组a中,查找键为key,自定义
函数binary_search(a,key)返回数组a中某个值为key的元素下标,若找不到
key,则返回-1。
def binary_search(a,key):
　L,R=0,len(a)-1
　while L<=R:
　　m=(L+R)//2　　#左偏
m=(L+R+1)//2　　#右偏
if key= =a[m]:
　　return m
elif key　　R=m-1
else:
　　L=m+1
return -1
2)二分查找算法使用递归函数bsearch(a,L,R,key)也能实现,其中L和R分
别表示查找区间的左、右边界。
def bsearch(a,L,R,key):
　if L>R:
　　return -1
　m=(L+R)//2　#左偏
　if key= =a[m]:
　　return m
　elif key　　return bsearch(a,L,m-1,key)
　else:
　　return bsearch(a,m+1,R,key)
例4 (2022七彩阳光返校考,11)有如下Python程序段:
import random
a=[4,2,6,5,4,2,9,7]
k=random.randint(1,10)
i=0;j=len(a)-1;x=" "
while i<=j:
　　m=(i+j)//2
　　if k<=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
4-1 (2022 A9协作体返校考,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",False
while i <=j and flag==False:
　　m=(i+j+1)//2
　　k=k+1
　　if key==a[m]:
　　　c="Y"
　　　flag=True
　　if key>a[m]:
　　　j=m-1
　　else:
　　　i=m+1
print(c,k)
执行该程序段后,下列说法正确的是 (　 )
A.该程既能用于升序序列的查找,也能用于降序序列的查找
B.若输出k的值为2,则c的值一定为Y
C.若输入key的值为74,程序执行后变量i和j的值分别为0和4
D.若输入两位任意正整数,k的值介于1和3之间
答案 B
4-2 (2022绍兴柯桥期末,12)某二分查找算法的 Python 程序段如下:
a=[8,17,24,30,36,40,55,58,61,66]
L,R=0,9
s=[]
key=int(input("请输入要查找的数据:"))
while L <= R:
　　m=(L+R+1) // 2
　　if a[m] == key:
　　　　break
　　elif a[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]
答案 B
4-3　有如下Python程序段:
d=[3,9,1,9,6,8,9]
n=len(d)
key=int(input("please input key:"))
i=0
c=0
flag=True
s=""
while i<=n-1:
　　if key==d[i]:
　　　flag=False
　　　s=s+str(i)+","
　　i=i+1
if flag:
　　print("未找到")
else:
print("找到,索引位置为:",s[0:len(s)-1])
程序运行时,输入key的值为9,程序运行后,变量i的值为 (　 )
A.未找到 B.找到,索引位置为:1
C.找到,索引位置为:1,3 D.找到,索引位置为:1,3,6
答案 D

展开更多......

收起↑