数据结构与算法的关系教学设计高中信息技术新浙教版选修1数据与数据结构

数据结构与算法的关系教学设计数据结构与算法的关系教材内容数据结构与算法的关系

5.1适应的课程标准结合生活实际，理解数据结构的概念，认识数据结构在解决问题过程中的重要作用

1.3通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系

1.7教学目标指向的核心素养•能结合具体程序实例，理解算法效率分析的•信息意识本条目通过设置真实问题情境，引导学一般方法生发现不同的数据结构对算法效率有不同的影响，在•回顾线性结构的特性，总结不同数据结构对处理实际问题能够有意识地选择合适的数据结构进行算法效率的影响问题建模・计算思维运用简化、归约的基本思想方法，即排除掉其它无关的影响因素，从理论角度对实际程序进课程标准和教学目标行算法的效率分析，对算法的运行效率进行评估、预测，并进行验证算法与数据结构关系密切，不同的数据结构对算法的效率也有影响，考虑到实际运用场景的需要，能够选择合适的数据结构・数字化实践通过创设数字化学习环境，鼓励学生根据实际解决问题的需要，使用思维导图等数字化工具开展自主学习和协作探究，演示不同数据结构对算法的影响，提升数字化实践素养・信息社会责任能够思考、归纳出数据结构与算法在社会生活中的各项运用，它所带来的效率提升对科技发展、社会进步的重要意义学习环境网络机房、算法可视化工具建议课时课时1教学环节教学过程设计意图通过导入生活中的算法问题和计算机科学领情境导入导入1:在多媒体课件上展示“高斯故事”，请学生对算术域的算法问题，以便顺利过渡到算法“时间复求和的公式法和累加求和算法的差异之处，以对算法效率杂度”、“空间复杂度”的分析形成初步感性认识教学活动设导入2互联网的搜索引擎能够快速地访问与检索信息，计Google做过一个试验，显示10条搜索结果的页面载入需要

0.4秒,显示30条搜索结果的页面载入需要

0.9秒，结果后者使得Google总的流量和收入减少了20%o Google地图上线的时候,首页大小有100KB,后来下降到70~80KB结果，流量在第一个星期上升了10%,接下来的3个星期又再上升了25%Amazon的统计也显示了相近的结果，首页打开时间O每增加100毫秒，网站销售量会减少1%Ox=x+l#执行n*n次通过分析上述“导入1”案例，请学生比较教材中“算法新课教学s=s+x一”、“算法二”及其延伸等具体程序实例活动一算法一print s#执行1次有了对实际程序实例的对比分析后，学n=int input#执行1次生对算法的时间复杂度概念有了基本的理解这里主要侧重于理论分析，s=l+n*n/2#执行1次即比较不同程序的执行次数需要注print s#执行1次意的是，“时间复杂度”并不与程序算法二:实际运行的“时间耗费”完全等价程序的时间耗费依赖于不同的计算机n=int input#执行1次硬软件等环境因素，并且程序的运行s=0#执行1次时间往往还与测试数据的规模也有很大关系，比如排序时，小量数据在不同for iin range1,n+1#执行n+1次算法测试时可能差异几乎为零，而有一s=s+i#执行n次百万、一千万随机数字进行排序，那print s#执行1次不同算法的差异就比较大了通过教材中简单易懂的三个程序实例，搭建算法二的延伸起学习的“脚手架”，可以让学生初n=int input#执行1次步理解算法的时间复杂度分析的一般方法通过对实际案例的对比分析，s=0引导学生自主阅读教材内容，加深理x=0解，从而实现知识的内化在此基础上，教师可以引入“阶”的概念，简单介for iin range1,n+1:绍不同阶的时间复杂度for jin range1,n+1:接着引导学生分析“导入2”案例，并与教材中下列案例算法效率对实际生活产生非常大的影响，对小组讨论进行比较分析算法效率分析可以从两个维度展开“时间•天气预报程序必须在指定时间前完成气象指数的计复杂度”即算法的时间耗费，“空间复杂算如果不能按时计算出预报结果，这个算法就毫无价值度”即算法的空间耗费在此基础上，可以•数字相机的人脸识别程序，必须在几分之一秒内完成设问“举例说明算法时间复杂度与空间复工作过慢的算法会带来糟糕的用户体验，照相机的制造杂度存在怎样的关系？”引导学生回忆前面商不可能采用所学知识，教师可以提供如下案例某程序需要判断某年是不是闰年，每次给一个年份，都要通过计算得到是否是闰年的结果如果这种计算比较频繁的话，还有另一个办法就是，事先建立一个有2050个元素的数组年数略比现实多一点，然后把所有的年份按下标的数字对应，如果是闰年，此数组项的值就是1,如果不是值为0o这样，所谓的判断某一年是否是闰年,就变成了查找这个数组的某一项的值是多少的问题假设输入数据规模为n,这时算法的时间复杂度降为01,但是空间耗费变大了，需要存储2050个0或1这就是典型的“以空间换时间”的算法问题导学以我们曾经学习过的数组和链表为例，试回忆通过对以前所学知识的总结与归纳、提升,可新课教学元素访问、插入、删除方面的效率差异，并完成下列表格以立足于“最近发展区”，通过旧知构建新活动二知，实现抽象概念建立的平滑过渡，培养学生数据结构与算法关系密切相关的意数组链表识本任务可以看成是任务一在本任务中的应适合数据规模确不需要预先分配自然延伸学生在回顾数组、链表中元素访用定且在处理过程存储空间，结点个问、插入、删除的操作时，可以利用相关信场中保持数据规模数不受限制息工具进行直观演示即可，并不需要代码具景稳定的问题体实现，从而可以保证课堂效率组用一段连续的存由结点构成，每个织储单元来依次存结点中包含数据结储数组元素区域和指针区域，构相邻结点间通过指针链接操访问数据访问访问需要从头结作效率较高点开始寻找特时间复杂度时间复杂度性插入或删除需插入或删除只要要移动大量数组找出某个结点位元素置，可以方便操作时间复杂度时间复杂度教师可以快速展示数组、链表中插入新元素之后的基本操作过程，或者引导学生使用相应的信息工具直观呈现二者操作的算法效率差异引自教材图数组中插入新数据的过程

2.

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

2.

2.3有人认为现代计算机的运行速度足够快了，已经没有必要拓展学习可以让学生自主学习和分组讨论研究算法的效率了，通过导入2中的案例，你有什么体会？教师总结大数据时代对算法的效率要求更图了，而不是口」有口J无帮助学生建立起算法效率分析的一般方法，并能与数据结构联系起来

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

2.数据结构与算法的紧密关系；概念学习需要先从生活实例出发，通过分析实

3.合理评估算法效率的重要性例，培养学生对概念的感性认识，为深刻理解概念提供事实基础；有了事实基础和体验过程，还需要对知识进行归纳和总结，纳入原有知识结构，实现知识的升华所有学生都应当完成本节课的1个问题与讨论和2个思考与作业布置练习本课内容分配1课时完成，内容为数据结构与算法的关系本节内容可在回忆、梳理本书前四章内容的基础上进行归纳、提升，相关概念在本章后续学习中进一步深化本节第一部分通过“算法一”、“算法二”及其延伸等具体程序实例，介绍算法效率分析中的时间复杂度分析方法第二部分则从学生已经熟悉的线性结构出发，简要分析数组与链表在元素访问、插入、删除方面的效率差异，体现出数据结构与算法效率之间的紧密关系首先，要让学生对“时间复杂度”的概念建立初步认识，可以举一些学生比较熟悉的生活实例，或者熟悉的故事教材中的示例程序“算法一”、“算法一”即可引用伟大数学家高斯小学时的故事展开算法不同的实现方式，导致解决问题的效率上差异其次，在对“时间复杂度”有一定认识的基础上，可以对“算法二”进行延伸，引导学生分析程序中的时间复杂度与教学设计思数据规模的关系，进而引出不同“阶”的时间复杂度路再次，解决同一个问题，因为算法设计、数据结构选择的不同导致算法效率特别是运行时间上的差异在课前准备一些与算法效率相关的程序实例，在课堂上老帅可以结合这些实例，直观呈现程序运行时间上的差异结果本节在全章中起到提纲挈领的作用，教学中既要注重基本概念的理解和掌握，又要关注兴趣的形成数据结构、逻辑结构、存储结构、算法效率、时间复杂度、空间复杂度这些知识比较抽象，应避免单一的概念讲解，立足学生最近发展区，充分挖掘前面四章的铺垫、展现学生熟悉的算法实例（项目），结合这些实例的剖析，使学生从抽象到具体地理解数据结构与算法的紧密联系，算法效率的一般分析方法，如教材中有关线性结构中数组与链表之间区别的问题与讨论在学生掌握时间复杂度的基础上，让学生主动探究空间复杂度的度量问题，此时可结合教材的“空间复杂度度量”问题与讨论信息意识、信息社会责任本条目通过设置真实问题情境，引导学生发现不同的数据结构对算法效率有不同的影响，在处理实际问题能够有意识地选择合适的数据结构进行问题建模本节课在导入时选择了两个案例，第一个案例简单易懂，贴近学生的学习实际，可以方便迁移到新知第二个案例涉及到的算法比较复杂，尽管有的学生可能有所了解.，但不宜展开多讲教师引导总结提升到理论层次的方式，目的是培养学生重视算法效率，并选择合适的数据结构能够思考、归纳出针对核心素数据结构与算法在社会生活中的各项运用，它所带来的效率提升对科技发展、社会进步的重要意义日算思维实际生活养培养的设场景中如搜索引擎、智能地图、自动驾驶的算法非常复杂，也难以进行详细、具体、全面的分析，需要运用简化、归约的计考虑基本思想方法，即排除掉其它无关的影响因素，从理论角度对实际程序进行算法的效率分析，对算法的运行效率进行评估、预测，并进行验证通过导入的案例一，即三个简单的小程序即可阐明算法复杂度的基本概念数字化学习与创新通过创设数字化学习环境，鼓励学生根据实际解决问题的需要，使用思维导图等数字化工具开展自主学习和协作探究，演示不同数据结构对算法的影响，提升数字化实践素养本节在任务一中，主要是总结线性结构中各种基本操作基础上，进一步提炼升华旧知，回顾数组、链表操作的过程中，鼓励学生根据实际解决问题的需要,恰当选择信息工具，不需要实现代码，仅演示相应操作即可，以达到提高效率的目的。