数据结构与算法效率一轮复习课件-2025-2026学年浙江省高三信息技术选择性必修一

数据结构与算法效率 1 知识过关 2 1. 数据结构与算法 (1)数据总是以一定的组织结构关系体现并存储。 (2)数据结构的设计和选择关注的是数据的逻辑结构、存储结构以及基本操作。 (3)算法的设计和选择总是依赖于数据结构。 (4)算法是编程思想,数据结构是这些思想的基础。 2. 算法效率 (1)算法效率。 算法效率的高低可由算法的复杂度来衡量。算法复杂度又分为算法的时间复杂度和空间复杂度,其中时间复杂度反映了算法执行所需要的时间,而空间复杂度反映了算法执行所需要占用的存储空间。 3 (2)时间复杂度(用大O阶表示)。 时间复杂度常用符号O表示,不包括低阶项和首项系数。时间复杂度从低到高可以分为常量阶O(1)、对数阶O(log2n)、线性阶O(n)、平方阶O(n2)等。算法的时间复杂度在很大程度上能很好地反映出算法的优劣。 (3)推导大O阶的方法。 ①用常数1取代运行时间中的所有加法常数。 ②对于修改后的运行次数函数,只保留最高阶项。 ③如果最高阶项存在且不是1,那么去除与这个项相乘的常数。 例如,算式:5n2+2n+3 ,其大O阶推导过程如下: 5n2+2n+3(用常数1取代加法常数)→5n2+2n+3(保留高阶)→5n2(去除高阶相乘常数)→n2 因此,该算式的大O阶(时间复杂度)结果为O(n2)。 一般而言,时间复杂度耗费时间的大小排序如下: 常数阶 O(1)<对数阶O(log2n)<线性阶 O(n)<线性对数阶 O(nlog2n)<平方阶 O(n2)<立方阶 O(n3)<指数阶 O(2n)…… 4 3. 数据结构对算法效率的影响 数据组织成不同的结构,是为了满足不同问题的需求,便于算法对数据结构的操作。对于不同的问题,我们可以根据问题的特性选择数组、链表、字符串、栈、队列和二叉树等数据结构来组织数据,提高算法处理数据的效率。 5 4. 算法优化 【例题】用Python编写程序,解决“百钱百鸡”问题。已知一只公鸡值五钱,一只母鸡值三钱,三只小鸡值一钱。买100只鸡共花了100钱,问:公鸡、母鸡、小鸡的数量各是多少? 算法分析:常规思路是假设i、j、k分别代表公鸡、母鸡和小鸡,结合题意可知,变量的范围分别是:i的范围是0~20,j的范围是0~33,k的范围是0~100。利用枚举算法,使用三重循环，程序如代码1所示,运行结果如下。 代码1(未经优化的三重循环结构): for i in range(21): 　　for j in range(34): 　　　　for k in range(101): 　　　　　　if i+j+k==100 and i*5+j*3+k//3==100: 　　　　　　　　print(i,j,k) 6 代码2(根据题意,将三重循环改为两重循环,结果相同,但效率显著提升): for i in range(21): 　　for j in range(34): 　　　　k=100－i－j 　　　　if i*5+j*3+k//3==100: 　　　　　　print(i,j,k) 由此可见,代码1的时间复杂度是O(n3),而代码2的时间复杂度为O(n2),算法效率大增。 7 继续优化算法,将方程i+j+k=100,以及i*5+j*3+k/3=100,进行消元(消去i),得到方程组:j=25－7*j//4;k=75+3*j//4,然后考虑变量大于等于0,且必须是整数,优化后得到的一重循环的代码3: for i in range(21): 　　j=25－7*i//4 　　k=75+3*i//4 　　if i*5+j*3+k//3==100 and j>=0 and k%3==0: 　　　　　　print(i,j,k) 可见,代码3的时间复杂度为O(n),和前面的代码相比,效率大大提高。 8 典例精选 9 【例1】 线性表一般有两种存储结构,顺序存储结构和链表存储结构。现在对这两种存储结构进行操作,关于相应操作的运行效率,下列说法中正确的是(　　) A. 读取操作时，顺序存储结构的运行效率要低于链表存储结构 B. 插入操作时，顺序存储结构的运行效率要高于链表存储结构 C. 删除操作时，顺序存储结构的运行效率要低于链表存储结构 D. 链表存储结构的各项操作运行效率均高于顺序存储结构 【解析】 删除、插入数据操作时，由于顺序存储结构需要移动大量数据,因此其运行效率要低于链表存储结构。而读取时，由于链表存储必须从头节点开始,因此顺序存储结构的运行效率要高于链表存储结构。C正确。 C 【例2】 有如下Python程序段: n=int(input()) s=0 for i in range(1,n+1): 　　s+=i print(s) 上述程序的时间复杂度为(　　) A. O(1) B. O(log2n) C. O(n) D. O(n2) 【解析】 本题算法中实现的功能是求1+2+3+…+n的和,其执行次数显然与问题规模n呈线性增长关系,因此其时间复杂度为O(n),C正确。 C 【例3】 以下两个程序段的功能相同,实现的功能是删除列表a(元素个数为n)中的重复元素(只保留一个),并将剩下的元素降序输出。 # 程序段① # 对列表a进行降序排序,代码略 i=1 while i<n:　　 　　if a[i]=a[i－1]: 　　　　for j in range(i+1,n): 　　　　　　a[j－1]=a[j] 　　　　 ;n－=1 　　i+=1 # 输出列表元素a[0]到a[n－1],代码略 # 程序段② max_num=max(a)#求出列表a中的最大值max_num b=[0]*(max_num+1) for i in range(0,n): 　　b[a[i]]+=1 : 　　if b[i]>0: 　　　　print(i,end=" ") i－=1 for i in range(max_num,0,－1) 下列关于上述两个程序段及其功能的说法,正确的是(　　) A. 同样的数据规模,两个程序段的运行时间效率一样 B. 程序段①加框处语句是否执行不受列表a原数据的影响 C. 程序段②加框处语句修改为“for i in range(1,max_num+1)”,输出结果不变 D. 在实现该功能的过程中,程序段②比程序段①需要更多的存储空间 【解析】 本题考查算法效率。程序段①时间复杂度为O(n2),程序段②时间复杂度为O(n),两个程序段的时间效率不同,A错误。程序段①中的加框处语句不能删除,否则若出现连续3个及以上的重复数字会出问题,B错误。程序段②加框处语句修改为“for i in range(1,max_num+1)”会导致最后结果升序输出,C错误。程序段②中需要预设一个长度为max_num的列表,会占用更多空间,D正确。 D 自我检测 14 1. 下列关于算法的时间复杂度的说法,错. 误. 的是 (　　) A. 如果时间复杂度为常数,那么时间复杂度为O(0) B. 仅包含顺序结构的算法的时间复杂度为O(1) C. 若算法中语句执行次数与问题规模n呈线性增大关系,则时间复杂度为O(n) D. 若算法中语句执行次数与问题规模n呈平方增大关系,则时间复杂度为O(n2) 【解析】 如果时间复杂度为常数,则其时间复杂度为O(1),A符合题意。 A 15 2. 下面程序段的时间复杂度是(　　) c = 0 n = int(input()) for i in range(1, n+1): 　　for j in range(1, i+1): 　　　　c += 1 　　print(c) A. Ο(1) B. Ο(n) C. Ο(n2) D. Ο(log2n) 【解析】 本题考查对算法时间复杂度的判断。该程序段中包含二重循环,i从1到n,每次都让j循环i次,循环体为语句“c+=1”,其执行次数为n2次。则算法中语句的执行次数与问题规模n呈平方增大关系,因此时间复杂度为O(n2),C正确。 C 16 3. 下面这段Python代码的时间复杂度是(　　) for i in range(n): 　　for j in range(n, i, －1): 　　　　if a[j] > a[j－1]: 　　　　　　a[j],a[j－1] = a[j－1],a[j－1] A. O(1) B. O(log2n) C. O(n) D. O(n2) 【解析】 由于该程序采用两重循环结构,故时间复杂度为O(n2),D正确。 D 17 必备知识练 18 1. 算法的空间复杂度是指(　　) A. 算法所处理的数据量大小的度量 B. 算法程序中语句或指令条数多少的度量 C. 算法在运行过程中临时占用存储空间大小的度量 D. 算法的输入和输出数据所占用的存储空间大小的度量 【解析】 本题考查空间复杂度的知识。算法的空间复杂度是指算法在运行过程中临时占用存储空间大小的度量,C正确。 C 19 2. 算法的时间复杂度是指(　　) A. 算法所用的程序占用空间的大小 B. 一般需要精确测量,其单位时间是秒 C. 算法的时间复杂度和空间复杂度成正比 D. 算法在计算机上运行所花费的时间,是指算法中包含简单操作的次数 【解析】 本题考查时间复杂度知识。算法在计算机上运行所花费的时间,是指算法中包含简单操作的次数,一般没必要精确计算出算法的时间复杂度,只要大致计算出相应的数量级,采用大O记法,D正确。 D 20 3. 下面这段Python代码的时间复杂度是(　　) n=100 a=50 c=a*n A. O(1) B. O(log2n) C. O(n) D. O(n2) 【解析】 本题考查程序复杂度知识。程序采用顺序结构,故时间复杂度是O(1),A正确。 A 21 4. 有如下自定义函数,其中列表a的元素按递增的顺序排列: def fun(a,x): 　　L,R=0,len(a)－1 　　while L<=R: 　　　　n=(L＋R)//2 　　　　if a[m]==x: 　　　　　　return m 　　　　elif a[m]<x: 　　　　　　L=m＋1 　　　　else: 　　　　　　R=m－1 　　　　return None 则函数fun()的算法时间复杂度是(　　) A. O(1) B. O(log2n) C. O(n) D. O(n2) 【解析】 本题考查时间复杂度的知识。二分查找的时间复杂度是O(log2n),B正确。 B 22 5. 下列关于算法效率的说法,错. 误. 的是(　　) A. 同一个问题采用不同的算法,其算法效率可能不同 B. 算法效率的高低可由算法复杂度来度量 C. 评价算法效率优劣时,只需评价时间复杂度即可 D. 数据结构的不同选择会影响算法的运行效率 【解析】 本题考查算法效率知识。评价算法效率优劣时,不仅要看评价时间复杂度,有时候还要看空间复杂度,两者都需要评估,C符合题意。 C 23 6. 下面这段Python代码的时间复杂度是(　　) import random n=int(input("请输入随机数个数n:")) d=[] for i in range(n): 　　d.append(random.randint(1,100)) print(d) key=int(input("请输入需要查找的数:")) for i in range(len(d)): 　　if key==d[i]: 　　　　print("查找成功!索引号为:",i) 　　　　break A. O(1) B. O(log2n) C. O(n) D. O(n2) 【解析】 本题考查Python程序的复杂度计算。程序采用单循环结构,故时间复杂度是O(n),C正确。 C 24 7. 下列关于数据结构的说法,正确的是(　　) A. 常见的线性关系数据结构有数组、队列、栈和树等 B. 数组和链表在操作时,其存储空间固定不变 C. 链表在访问、插入和删除元素时,算法效率比数组高 D. 栈是一种先进后出的线性表结构 【解析】 本题考查数组、链表、队列、栈和树的数据结构知识。树是非线性结构,A错误。链表的存储空间不固定,B错误。数组的访问效率高于链表,链表的插入和删除效率高于数组,C错误。 D 25 8. 下面这段Python代码的时间复杂度是(　　) s=0 for i in range(1,n＋1): 　　s＋=i print(s) A. O(1) B. O(log2n) C. O(n) D. O(n2) 【解析】 本题考查程序复杂度知识。程序采用一重循环结构,且执行次数与问题规模n呈线性增大关系,故时间复杂度是O(n),C正确。 C 26 9. 下面这段Python代码的时间复杂度是(　　) s=0;n=100 for i in range(1,n＋1): 　　for j in range(1,n＋1): 　　　　s＋=1 print(s) A. O(1) B. O(log2n) C. O(n) D. O(n2) 【解析】 本题考查程序复杂度知识。程序采用两重循环结构,且执行次数与问题规模n2呈线性增大关系,故复杂度是O(n2),D正确。 D 27 关键能力练 28 10. 有如下自定义函数: def fun(a,p,x): 　　n=len(a) 　　a.append(x) 　　for i in range(n,p,－1): 　　　　a[i]=a[i－1] 　　a[p]=x 　　return a 则函数fun()的算法时间复杂度是(　　) A. O(1) B. O(log2n) C. O(n) D. O(n2) 【解析】 本题考查程序复杂度知识。程序采用一重循环结构,且执行次数与问题规模n呈线性增大关系,故复杂度是O(n),C正确。 C 29 11. 下列关于时间复杂度之间的大小关系,正确的是(　　) A. O(1)< O(n)< O(n2)< O(log2n) B. O(1)< O(log2n)< O(n)< O(n2) C. O(log2n)< O(1)< O(n)< O(n2) D. O(n2)< O(n)< O(log2n)< O(1) 【解析】 一般而言,时间复杂度的耗时从小到大的排序如下:O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!)。B正确。 B 30 12. 某超市举办特卖活动,对n种商品进行限定打折大优惠,顾客可通过一体机输入所选商品的条形码信息,查询哪些商品能参加本次特卖。将n种商品的条形码信息存入数组a;将顾客所选商品信息存入数组b,其中b[i][0]表示某种商品的条形码信息,b[i][1]表示该种商品的名称。查询过程的Python程序部分代码如下: p = len(b) i = 0 while i < p: 　　for j in range(n): 　　　　if b[i][0]==a[j]: 　　　　　　print(b[i][1]) 　　i = i ＋ 1 31 下列说法中,错. 误. 的是(　　) A. 该程序采用了枚举算法 B. p值越大,程序运行时间越长 C. n值的大小与该程序的算法效率无关 D. 将原用数组存储的数据改用链表存储,会占用更多存储单元 【解析】 本题考查枚举算法、数据结构与算法效率等知识。本程序是一个枚举算法,A不符合题意。p的值越大则需要枚举的项越多,则需要运行的时间越长,B不符合题意。n的值越大,所需对比的数量越多,所需要的时间也越多。所以n值的大小与程序运行效率有关,C符合题意。如果数据采用链表存储,则需要增加一个存储下一个元素的指针域,因此所需要的存储空间会比数组多,D不符合题意。 C 13. 小明学习了算法后,写了以下两段代码来求斐波那契数列的第6项: 算法一 a=1;b=1 for i in range(2,6): 　　c=a＋b 　　a=b 　　b=c print(c) 算法二 def f(n): 　　if n==1 or n==2: 　　　　return 1 　　else: 　　　　return f(n－1)＋f(n－2) print(f(6)) 33 下列说法中,正确的是(　　) A. 两种算法的时间复杂度均为O(1) B. 算法一是迭代算法,算法二是递归算法,相比之下,算法二的时间效率更高 C. 执行算法二代码,f(4)共被调用了2次 D. 执行算法一代码,当i=4这一遍循环刚结束时,a的值为5 【解析】 本题考查算法阅读和算法效率问题。算法一(迭代)的时间复杂度为O(n),算法二(递归)的时间复杂度为O(2n),因此算法一的时间效率高,A、B错误。执行算法二代码, f(6)=f(5)＋f(4)=f(4)＋f(3)＋f(4)=…,由此可见f(4)被调用了2次,C正确。执行算法一代码,列出变量表:当i=4这遍循环刚结束时,a=3,D错误。 C 34 $