5.1数据结构与算法效率 学案 - 浙教版2019 高中 信息技术 选修1 学案

5.1数据结构与算法效率 导学案 学科 高中信息技术 教材版本 浙教版2019选修1 课题 5.1数据结构与算法效率 一、【学习目标】 1.理解数据结构与算法的关系。（重点）（学科核心素养：信息意识、计算思维） 2.认识算法效率高低的主要的两个方面：时间复杂度与空间复杂度，及这两个方面的表示与计算。（难点）（学科核心素养：信息意识、计算思维） 3.逐步自觉将算法的效率应用在算法程序设计中，根据问题选择合适的数据结构，提高算法效率。（学科核心素养：信息意识） 二、【自主探究】 任务一：学生自主学习课本，完成下列题目： 1.算法效率的高低可由 来度量。算法复杂度又分为算法的 和 ，其中时间复杂度反映了 所需要的时间，而空间复杂度反映了算法执行所需要占用的 。 2.算法的 反映了程序执行时间随问题规模增长而增长的量级，在很大程度上能很好地反映出算法的优劣。 任务二： def ct(n): s=0 while n>0: s+=n%2 n//=2 return s n=int(input("输入一个正整数：") ans=ct(n) print(ans) 请回答下列问题： （1）程序运行后，输入整数23,自定义函数ct(n)中语句“s+=n%2”执行的次数是 。 （2）该算法的时间复杂度为 (单选，填字母：A.O(n)/B.O(log₂n))。 任务三：小华规划自驾游路线，出发地为杭州，目的地为北京，途径地为上海、苏州、南京、济南、石家庄。用数组来实现其更改过程。 0数组a 1 2 3 4 5 6 杭州 上海 苏州 南京 济南 石家庄 北京 (1)小华想要查询第5个到达的城市，如何编程实现 时间复杂度为 。 (2)小华计划有变决定直接从上海出发，不从杭州出发，如何编程实现?时间复杂度为 。 a=["杭州","上海","苏州","南京","济南","石家庄","北京"] n=ien(a) q=0 for i in range(q,n-1): a. pop() print(a) 任务四：比较数组和链表两种不同的数据结构对算法的影响并填写表格。 3、 课后练习题 1.算法的时间复杂度反映了程序执行时间与什么因素的关系？( ) A.算法的编写风格 B.输入数据的具体值 C.问题规模 D.程序员的编程技巧 2.某算法的时间复杂度为O(n²),表明该算法的（ ） A.问题规模是n² B.执行时间等于n² C.问题规模与n²成正比 D.执行次数与n²呈线性增大关系 3. 某Python 程序如下： i=1 k=0 n=int(input()) while i<=n: k+=2*i i+=1 该算法的时间复杂度是（ ） A.O(1) B.O(n) C.O(n²) D.0(log₂n) 4. 某 Python 程序如下： n=int(input("n=") ansl=ans2=0 fori in range(0,n,2): for j in range(n): ansl=ans1+2 ans2=ans2+2*ans1 print("ansl=",ans1,"ans2=",ans2) 该算法的时间复杂度是 ( ) A.O(1) B.O(n) C.O(n²) D.O(2") 5. 某 Python 程序如下： def f(n): if n<=2: return n else: return f(n- 1)*n x=int(input("x=") print(f(x)) 该算法的时间复杂度是 A.O(n) B.O(n²) C.O(n!) D.O(nlog₂n) 课后练习答案 1 2 3 4 5 C D B C A 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 $$