5.1 数据结构与算法的关系 教学设计（表格式）

数据结构与算法的关系教学设计 课程标准 和 教学目标 数据结构与算法的关系 教材内容： 5.1 数据结构与算法的关系 适应的课程标准： 1.3 结合生活实际，理解数据结构的概念，认识数据结构在解决问题过程中的重要作用。 1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。 教学目标： ●能结合具体程序实例，理解算法效率分析的一般方法。 ●回顾线性结构的特性，总结不同数据结构对算法效率的影响。 指向的核心素养： ●信息意识：本条目通过设置真实问题情境，引导学生发现不同的数据结构对算法效率有不同的影响，在处理实际问题能够有意识地选择合适的数据结构进行问题建模。 ●计算思维：运用简化、归约的基本思想方法，即排除掉其它无关的影响因素，从理论角度对实际程序进行算法的效率分析，对算法的运行效率进行评估、预测，并进行验证。算法与数据结构关系密切，不同的数据结构对算法的效率也有影响，考虑到实际运用场景的需要，能够选择合适的数据结构。 ●数字化实践：通过创设数字化学习环境，鼓励学生根据实际解决问题的需要，使用思维导图等数字化工具开展自主学习和协作探究，演示不同数据结构对算法的影响，提升数字化实践素养。 ●信息社会责任：能够思考、归纳出数据结构与算法在社会生活中的各项运用，它所带来的效率提升对科技发展、社会进步的重要意义。 学习环境：网络机房、算法可视化工具 建议课时：1课时 教学活动设计 教学环节 教学过程 设计意图 情境导入 导入1：在多媒体课件上展示“高斯故事”，请学生对算术求和的公式法和累加求和算法的差异之处，以对算法效率形成初步感性认识。 导入2：互联网的搜索引擎能够快速地访问与检索信息，Google做过一个试验，显示10条搜索结果的页面载入需要0.4秒，显示30条搜索结果的页面载入需要0.9秒，结果后者使得Google总的流量和收入减少了20%。Google地图上线的时候，首页大小有100KB，后来下降到70~80KB。结果，流量在第一个星期上升了10%，接下来的3个星期又再上升了25%。Amazon的统计也显示了相近的结果，首页打开时间每增加100毫秒，网站销售量会减少1%。 通过导入生活中的算法问题和计算机科学领域的算法问题，以便顺利过渡到算法“时间复杂度”、“空间复杂度”的分析。 新课教学 活动一 通过分析上述“导入1”案例，请学生比较教材中“算法一”、“算法二”及其延伸等具体程序实例。 算法一： n=int(input()) #执行1次 s=(1+n)*n/2 #执行1次 print(s) #执行1次 算法二： n=int(input()) #执行1次 s=0 #执行1次 for i in range(1,n+1): #执行n+1次 s=s+i #执行n次 print(s) #执行1次 算法二的延伸： n=int(input()) #执行1次 s=0 x=0 for i in range(1,n+1): for j in range(1,n+1): x=x+1 #执行n*n次 s=s+x print(s) #执行1次 有了对实际程序实例的对比分析后，学生对算法的时间复杂度概念有了基本的理解。这里主要侧重于理论分析，即比较不同程序的执行次数。需要注意的是，“时间复杂度”并不与程序实际运行的“时间耗费”完全等价。程序的时间耗费依赖于不同的计算机硬软件等环境因素，并且程序的运行时间往往还与测试数据的规模也有很大关系，比如排序时，小量数据在不同算法测试时可能差异几乎为零，而有一百万、一千万随机数字进行排序，那不同算法的差异就比较大了。通过教材中简单易懂的三个程序实例，搭建起学习的“脚手架”，可以让学生初步理解算法的时间复杂度分析的一般方法。通过对实际案例的对比分析，引导学生自主阅读教材内容，加深理解，从而实现知识的内化。在此基础上，教师可以引入“阶”的概念，简单介绍不同阶的时间复杂度。 小组讨论 接着引导学生分析“导入2”案例，并与教材中下列案例进行比 ... ...