信息技术选修1 数据与数据结构5.1 数据结构与算法的关系完美版ppt课件

课程标准

和

教学目标

数据结构与算法的关系

教材内容： 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”案例，请学生比较教材中“算法一”、“算法二”及其延伸等具体程序实例。

算法一：

算法二：

算法二的延伸：

有了对实际程序实例的对比分析后，学生对算法的时间复杂度概念有了基本的理解。这里主要侧重于理论分析，即比较不同程序的执行次数。需要注意的是，“时间复杂度”并不与程序实际运行的“时间耗费”完全等价。程序的时间耗费依赖于不同的计算机硬软件等环境因素，并且程序的运行时间往往还与测试数据的规模也有很大关系，比如排序时，小量数据在不同算法测试时可能差异几乎为零，而有一百万、一千万随机数字进行排序，那不同算法的差异就比较大了。通过教材中简单易懂的三个程序实例，搭建起学习的“脚手架”，可以让学生初步理解算法的时间复杂度分析的一般方法。通过对实际案例的对比分析，引导学生自主阅读教材内容，加深理解，从而实现知识的内化。在此基础上，教师可以引入“阶”的概念，简单介绍不同阶的时间复杂度。

小组讨论

接着引导学生分析“导入2”案例，并与教材中下列案例进行比较分析：

          天气预报程序必须在指定时间前完成气象指数的计算。如果不能按时计算出预报结果，这个算法就毫无价值。

          数字相机的人脸识别程序，必须在几分之一秒内完成工作。过慢的算法会带来糟糕的用户体验，照相机的制造商不可能采用。

算法效率对实际生活产生非常大的影响，对算法效率分析可以从两个维度展开：“时间复杂度”即算法的时间耗费，“空间复杂度”即算法的空间耗费。在此基础上，可以设问：“举例说明算法时间复杂度与空间复杂度存在怎样的关系？”引导学生回忆前面所学知识，教师可以提供如下案例：某程序需要判断某年是不是闰年，每次给一个年份，都要通过计算得到是否是闰年的结果。如果这种计算比较频繁的话，还有另一个办法就是，事先建立一个有2050个元素的数组（年数略比现实多一点），然后把所有的年份按下标的数字对应，如果是闰年，此数组项的值就是1，如果不是值为0。这样，所谓的判断某一年是否是闰年，就变成了查找这个数组的某一项的值是多少的问题。假设输入数据规模为n，这时算法的时间复杂度降为O(1)，但是空间耗费变大了，需要存储2050个0或1。这就是典型的“以空间换时间”的算法。

新课教学

活动二

问题导学：以我们曾经学习过的数组和链表为例，试回忆元素访问、插入、删除方面的效率差异，并完成下列表格。

教师可以快速展示数组、链表中插入新元素之后的基本操作过程，或者引导学生使用相应的信息工具直观呈现二者操作的算法效率差异

引自教材 图2.1.5 数组中插入新数据的过程

引自教材 图2.2.3 单向链表中插入新结点过程

通过对以前所学知识的总结与归纳、提升，可以立足于“最近发展区”，通过旧知构建新知，实现抽象概念建立的平滑过渡，培养学生数据结构与算法关系密切相关的意识。本任务可以看成是任务一在本任务中的自然延伸。学生在回顾数组、链表中元素访问、插入、删除的操作时，可以利用相关信息工具进行直观演示即可，并不需要代码具体实现，从而可以保证课堂效率。

拓展学习

有人认为现代计算机的运行速度足够快了，已经没有必要研究算法的效率了，通过导入2中的案例，你有什么体会？

可以让学生自主学习和分组讨论。

教师总结：大数据时代对算法的效率要求更高了，而不是可有可无。

帮助学生建立起算法效率分析的一般方法，并能与数据结构联系起来。

课堂小结

1. 算法效率分析的一般方法，时间复杂度的基本概念；

2. 数据结构与算法的紧密关系；

3. 合理评估算法效率的重要性。

概念学习需要先从生活实例出发，通过分析实例，培养学生对概念的感性认识，为深刻理解概念提供事实基础；有了事实基础和体验过程，还需要对知识进行归纳和总结，纳入原有知识结构，实现知识的升华。

作业布置

所有学生都应当完成本节课的1个问题与讨论和2个思考与练习。

教学设计思路

本课内容分配1课时完成，内容为数据结构与算法的关系。本节内容可在回忆、梳理本书前四章内容的基础上进行归纳、提升，相关概念在本章后续学习中进一步深化。本节第一部分通过“算法一”、“算法二”及其延伸等具体程序实例，介绍算法效率分析中的时间复杂度分析方法。第二部分则从学生已经熟悉的线性结构出发，简要分析数组与链表在元素访问、插入、删除方面的效率差异，体现出数据结构与算法效率之间的紧密关系。

首先，要让学生对“时间复杂度”的概念建立初步认识，可以举一些学生比较熟悉的生活实例，或者熟悉的故事。教材中的示例程序“算法一”、“算法二”即可引用伟大数学家高斯小学时的故事展开。算法不同的实现方式，导致解决问题的效率上差异。

其次，在对“时间复杂度”有一定认识的基础上，可以对“算法二”进行延伸，引导学生分析程序中的时间复杂度与数据规模的关系，进而引出不同“阶”的时间复杂度。

再次，解决同一个问题，因为算法设计、数据结构选择的不同导致算法效率特别是运行时间上的差异。在课前准备一些与算法效率相关的程序实例，在课堂上老师可以结合这些实例，直观呈现程序运行时间上的差异结果。

本节在全章中起到提纲挈领的作用，教学中既要注重基本概念的理解和掌握，又要关注兴趣的形成。数据结构、逻辑结构、存储结构、算法效率、时间复杂度、空间复杂度这些知识比较抽象，应避免单一的概念讲解，立足学生最近发展区，充分挖掘前面四章的铺垫、展现学生熟悉的算法实例（项目），结合这些实例的剖析，使学生从抽象到具体地理解数据结构与算法的紧密联系，算法效率的一般分析方法，如教材中有关线性结构中数组与链表之间区别的问题与讨论。在学生掌握时间复杂度的基础上，让学生主动探究空间复杂度的度量问题，此时可结合教材的“空间复杂度度量”问题与讨论。

针对

核心素养培养的

设计考虑

信息意识、信息社会责任：本条目通过设置真实问题情境，引导学生发现不同的数据结构对算法效率有不同的影响，在处理实际问题能够有意识地选择合适的数据结构进行问题建模。本节课在导入时选择了两个案例，第一个案例简单易懂，贴近学生的学习实际，可以方便迁移到新知。第二个案例涉及到的算法比较复杂，尽管有的学生可能有所了解，但不宜展开多讲。教师引导总结提升到理论层次的方式，目的是培养学生重视算法效率，并选择合适的数据结构。能够思考、归纳出数据结构与算法在社会生活中的各项运用，它所带来的效率提升对科技发展、社会进步的重要意义。

计算思维：实际生活场景中如搜索引擎、智能地图、自动驾驶的算法非常复杂，也难以进行详细、具体、全面的分析，需要运用简化、归约的基本思想方法，即排除掉其它无关的影响因素，从理论角度对实际程序进行算法的效率分析，对算法的运行效率进行评估、预测，并进行验证。通过导入的案例一，即三个简单的小程序即可阐明算法复杂度的基本概念。

数字化学习与创新：通过创设数字化学习环境，鼓励学生根据实际解决问题的需要，使用思维导图等数字化工具开展自主学习和协作探究，演示不同数据结构对算法的影响，提升数字化实践素养。本节在任务二中，主要是总结线性结构中各种基本操作基础上，进一步提炼升华旧知，回顾数组、链表操作的过程中，鼓励学生根据实际解决问题的需要，恰当选择信息工具，不需要实现代码，仅演示相应操作即可，以达到提高效率的目的。