数据结构与算法教学教案（理论+实践）.docx

讲授章节第I讲概述授课时数2教学目的：1 .了艇数据结构课程的重要性和课程的基本要求.以及本课程涵盅的内容：2 .掌握数据结构的基本概念：3 .理解算法描述和简单的算法分析，教学内容（讲授提纲）一 .豫黄导学（线上）1 .阅读：导学通知、课程介绍、学习方法、校内SPoC使用方法、本章节知识点等2 .观看导学视软3 .论坛讨论、反馈疑难点二 .售量数学1 .介州课程工要性和戢义，以及学习目标等2 .什么是数据结构2.1 通过“中国软件和信息技术服务业现状-“排队候车.答案例介绍线性结构.去1中国软件和信息技术服务业现状年份软件业收入统计（亿元）人均创收（亿元）软件从业人员数统计（TJA）20154284874.657420164823282.358620175510389.261820186190995.0645201971768106.6673内容版峭上分鹫使出故众人累角愚放；车主TWel¾e丢隼案,安全图1军人排队候车2.2通过早期华为坦根结构图"、,族iT/案例介的材形结构图3族谱2.3通过浦速铁路网，“哥尼租七桥问”介绍图形结构图4我国“四纵四横”湍速铁跖网图5哥尼斯堡七桥向SS讨论：欧拉回路存在的充分必要条件是：(1>图是连通的：(2)图中与每个顶点相连的边数(即顶点度数)必须是偶数.3,基林念和术语3.1 介绍数据(Data)、数据元南(Data1.lcmcnt>,数楙项(DataItem)、数据对象(DataObject)、抽象数据类型<AbstractDataType),数据结构三个要索.3.2 课堂练习U)在数据结构中,从逻辑上可以将之分为(),【中南大学】.动态结构和静态结构B.紧凑结构和非紧凑结构C.内部结构和外部结构D,成性结构和非线性结构(2)己知我头元素为C的总院我在内存中的存储状态如下次所示.【2012全国统芍408地址元素链接地址100OHaIOIOHKXMHb100CH1008HC100011100CH<NU1.1.IOIOHeI004H1()I4H现将f放于1014H处并插入到单链表中,若f在龙辑上位a和e之间,则a,e,f的链接地址”依次是().A.I()I()H,1OI4H.IWMHB.I()IOH,KXMH.IOHHC.!0!4H.IOlOH.1004HD.10!4H.IO(MH.IOlOH4,算法和售法分析4介绍算法的定义、特性、设计要求及籁法效率的衡设方法，4.2 "百钱买百鸡”问卷讨轮转,我国古代数学冢张丘建在MW经3一书中皆提出过著名的百钱买百利问迤，小坦讨论“百钱买百鸡”算法思路，开展翻转课堂活动，最后教师总结算法的重要性，4.3 引导学生归纳总结各种常见阶数时间发杂度4.4 课堂练习(I)求整数n(n>=0)阶乘的算法如卜.，其时间更杂度是(>【2012全国统考408】iniact(intn)if(n<=i),e<umI;returnn*efact(n-l);A.O(l0g2n)B.O(n)C.O(nlog：n)D.0(n2)(2)下列程序段的时间H杂度()c【2014全国统考408】count=0;for(k=kk<=n:kte=2>fbr(j=I;j<=n;j÷=l)counif；A.O(log211)B.O(n)C,O(nlog：n)D,0(n2)(3)下列函数的时间复杂度()，(2017全国统考408】intlunc(intn)(inti=().sum=():WhiHsum<n)sum+=+i;returni;).O(log211)B.CHn'C.O(n)D.O(nlog21)三,课后巩固(tt±)课后观看习超视翔并在校内SPoC完成知识点测试.本章节的教学重点、难点：1 .点是数据结构的嘱本概会2 .难点是时间发杂度的分析教学方法、教学手段：1 .介绍数据结构与算法概念和术语(45分钟)2 .算法分析和举例(45分钟)3 ,使用载具：计骈机和投影仪;4 .辅助教学：雨课堂、校内SpOC、“百科园”、学堂在线MOOC、算法演示动画：5 .课前现存导学视频：课中案例展开应用翻转课堂、项目驱动以及实践教学法：课后观若习题视叙，井在校内SPoC完成知识点在线测试.作业、讨论题、思考题：说明：所有作业和实脸无纸化，提交至网络教学平台：测船使用“百科园”考试系统，(1)课后作业：已知给入X.>-Z三个不相等的番数.设计一个“高效”算法,使得这三个数按从小到大蝌出.”高效”的含义是用最少的元素比较次数、元素移动次数和输出次数.(2)编程求解数组中最大连续子序列之和，井分析算法的时间或杂度提示：该问啊有多种解法，应用穷举法时间女杂度较高为0(n'),而时间反杂度最低能达到0(n).(3)讨论：数据的逻辑结构与存谛结构是一一对应的吗？谓举例说明.参考资料：1 .冯广慈,吴昊,文全刚.算法与数据结向(C+语古版阚|.电子工业出版社.20192 .陈守孔，胡潇琨，李玲,冯广魅,算法与数据结构考研试题耕折(第四版)M,机械工业出版社,2020讲授章节第2讲战性表、顺序去授课时数2教学目的：1 .理解北空线性结构的四个特征.2 .践性衣是虫要的践性结构，要掌握俄性表的定义。3 .靠押雄性表的操作在顺序表中的实现，教学内容（讲授提纲）一 .课防导学（线上）1 .观看导学视频2 .论坛讨论、反馈疑难点二 .课依教学1 .通过中国软件和信息技术服务业现状统计表，引入戕性结构学习，总结非空战性结构的四个特征年份软件业收入绘计（亿元）人均创收亿元软件从业人员数统计万人20154284874.657420164823282.3586201755103«9.261820186190995.0645201971768106.66732.线性表的据会3.稣性衰的抽象数帚类量CiirBcngfh-I%«1I»2II4 .蛤定螃性表的现辑结构设计算法（1）遍历线性表1.（2）合并级性表1:设1.a和1.b是元素限于同数据对象且非通戒有序的两个线性表，现要求将两个戏性表合并成个新的非递减有序的雄性衣1.eo（3）合弁线性表2:设1.a和1.b是元素属于同数据对象的两个线性非，试将线性表1.b合并到我性去1.a中.要求1.b中元素和1.a中元素相同的不再合并。要分析为什么和（3的时复杂度分别是0（m*n）和O（m+n）.5 .线性表的序表示及类型定义6 .序表上基本运算的实现<1）构造一个空序表：（2）拷贝构造函数：（3）遍历顺序表：4查找元素：（5）求前驱和后继：（6）插入运匏：（7删除运算：（8）逆置运算：（9）扩大表空间：虫点分析在插入和删除操作中的时间更杂度，7 .算法设计举例1顺序结构线性表1.A与IB的结点关造字为整数.1.A与1.B的元素按非递减有序,线性表空间足弊大。试给出一种高效算法，将1.B中元素合到1.A中，使新的1.A的元素仍保持非递减有序.高效指最大限度的避免移动元素，<2）【北京航空航天大学】已知长度为n的线性次A果用顺序存储结构.请写一时间复杂度为（Xn）,空间复杂度为Od）的算法，该算法IH除线性去中所有值为item的数据元素.（0（1）表示以法的辅助空间为常盘。<3>2010全国统考408】设将n（n>l）个整数存放到一维数组R中.试设计一个在时间和空间两方面都尽可能高效的匏法，将R中保存的序列循环左移P（KP5）个位置.W将R中的数据由（XO1Xl“Xn-D变换为<Xp.Xp+l.Xn0.X.l）.要求:a）给出算法的基本设计思想,b）采用C或Cl或JAVA语言描述蚱法C）说明算法的时间更杂度和空间复杂度.d>出*：若采用仃接左移P位,空间复杂度仍为O（1）,但时间宓杂度为（XnP）.=.课后巩圆（tt±）课后观看习题视频，并在校内SPOC完成知识点测试。本章节的教学重点,难点：1 .I点是顺序表的定义，基本操作的实现.2 .点是高效兑法设计，例如国家2010年硕士研究生入学考试抑法时就行5种解法教学方法、教学手段：1 .城性表和顺序表的概念和类型定义30分钟2 .顺序表上基本运算的实现（30分钟）3 .顺序表算法举例（30分钟）4 .使用教具：计算机和投影仪;5 .辅助教学：雨课堂、校内SpOC、“百科园”在战考试系统、学堂在我MooC、算.法演示动ah6 .深曲现后导学视频：课中案例展开，应用蒯转课堂、项目驱动以及实践教学法：课后观石习题觇频，并在校内SPOC完成知识点在线测试，作业、讨论题、思考题：1,分析在顺序存储结构下插入和删除结点时平均衢要移动多少个结点。7 .顺序表Ia与Ib非递减有序，顺序表空间足游大。试设计一种高效算法，将Ib中元素合到Ia中.使新的Ia的元素仍保持非递减有序.高效指最大眼度地避免移动元素.改为:顺序&Ia非递减有序，出非递增有序，求解该问题.参考资料：1 .冯广怒,吴昊,文全刚.算法与数据结构（Cl语言版M.电子工业出版社.20192 .陈一孔,胡潇琨,李玲.冯广慧.算法与数据结构考研试题精析（第四版）M）.机械工业出版社,2020讲授章节第3讲单链表授课时数2教学目的：1 .掌握鞋表的类型定义和基本操作的实现.2 .掌握单链表的建立方法，特别是头插法和尾插法。3 .了解单箧衣的应用。教学内容（讲授提纲）二 .防导学（线上）1 .观看导学视频2 .论坛讨论、反馈疑难点二.课堂帙学1从序存储结构的优缺点，引出修良的由要性插入和删除必须大埴移动元泰：必须预先确定空间；表空间不易扩充。3 .倭表的类型定义几个概念：结点，首元结点，第一元素结点，头结点,指针，头指针头指针头:点百元结点HEB卜，I十4 .线性表的畏作在单候表中的实现（1）单椎表的初始化：（2）清空单胜衣：3）求我长：（4）遍历能表：（5）查找位序为i的元素的地址:6杳找他为Value的元素的位序：（7杳找值为ValUe的元素的前驱；（8）求某元素的后第：（9）插入元素：10）删除元泰。5 .单帽表的立立方法（特别是头场法和尾插法（1）头插法；（2）尾插法，6 .算法设计举例（I）【2012全国统考408】假定采用带头结点的单链发保存用词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，Toading'WrbCing”的存储映像如下图所示，设SIrI和和2分别指向两个单词所在单链表的头结点,鞋表结点结何为（data,next）请设计一个时间上尽可能高效的算法.找出由StrI和$tr2所指的两个链表共同后缀的起始位置（如图中字符i所在结点