《数据结构与算法教学教案（理论+实践）.docx》由会员分享，可在线阅读，更多相关《数据结构与算法教学教案（理论+实践）.docx（25页珍藏版）》请在课桌文档上搜索。
1、讲授章节第I讲概述授课时数2教学目的：1 .了艇数据结构课程的重要性和课程的基本要求.以及本课程涵盅的内容：2 .掌握数据结构的基本概念：3 .理解算法描述和简单的算法分析，教学内容（讲授提纲）一 .豫黄导学（线上）1 .阅读：导学通知、课程介绍、学习方法、校内SPoC使用方法、本章节知识点等2 .观看导学视软3 .论坛讨论、反馈疑难点二 .售量数学1 .介州课程工要性和戢义，以及学习目标等2 .什么是数据结构2.1 通过“中国软件和信息技术服务业现状-“排队候车.答案例介绍线性结构.去1中国软件和信息技术服务业现状年份软件业收入统计（亿元）人均创收（亿元）软件从业人员数统计（TJA）2015
2、4284874.657420164823282.358620175510389.261820186190995.0645201971768106.6673内容版峭上分鹫使出故众人累角愚放；车主TWele丢隼案,安全图1军人排队候车2.2通过早期华为坦根结构图、,族iT/案例介的材形结构图3族谱2.3通过浦速铁路网，“哥尼租七桥问”介绍图形结构图4我国“四纵四横”湍速铁跖网图5哥尼斯堡七桥向SS讨论：欧拉回路存在的充分必要条件是：(1图是连通的：(2)图中与每个顶点相连的边数(即顶点度数)必须是偶数.3,基林念和术语3.1 介绍数据(Data)、数据元南(Data1.lcmcnt,数楙项(Dat
3、aItem)、数据对象(DataObject)、抽象数据类型AbstractDataType),数据结构三个要索.3.2 课堂练习U)在数据结构中,从逻辑上可以将之分为(),【中南大学】.动态结构和静态结构B.紧凑结构和非紧凑结构C.内部结构和外部结构D,成性结构和非线性结构(2)己知我头元素为C的总院我在内存中的存储状态如下次所示.【2012全国统芍408地址元素链接地址100OHaIOIOHKXMHb100CH1008HC100011100CH=0)阶乘的算法如卜.，其时间更杂度是(【2012全国统考408】iniact(intn)if(n=i),eumI;returnn*efact(n-
4、l);A.O(l0g2n)B.O(n)C.O(nlog：n)D.0(n2)(2)下列程序段的时间H杂度()c【2014全国统考408】count=0;for(k=kkfbr(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-Z三个不相等的番数.设计一个“高效”算法,使得这三个数按从小到大蝌出.”高效”的含义是用最少的元素比较次数、元素移动次数和输出次数.(2)编程求解数组中最大连续子序列之和，井分析算法的时
5、间或杂度提示：该问啊有多种解法，应用穷举法时间女杂度较高为0(n),而时间反杂度最低能达到0(n).(3)讨论：数据的逻辑结构与存谛结构是一一对应的吗？谓举例说明.参考资料：1 .冯广慈,吴昊,文全刚.算法与数据结向(C+语古版阚|.电子工业出版社.20192 .陈守孔，胡潇琨，李玲,冯广魅,算法与数据结构考研试题耕折(第四版)M,机械工业出版社,2020讲授章节第2讲战性表、顺序去授课时数2教学目的：1 .理解北空线性结构的四个特征.2 .践性衣是虫要的践性结构，要掌握俄性表的定义。3 .靠押雄性表的操作在顺序表中的实现，教学内容（讲授提纲）一 .课防导学（线上）1 .观看导学视频2 .论坛
6、讨论、反馈疑难点二 .课依教学1 .通过中国软件和信息技术服务业现状统计表，引入戕性结构学习，总结非空战性结构的四个特征年份软件业收入绘计（亿元）人均创收亿元软件从业人员数统计万人20154284874.657420164823282.35862017551039.261820186190995.0645201971768106.66732.线性表的据会3.稣性衰的抽象数帚类量CiirBcngfh-I%1I2II4 .蛤定螃性表的现辑结构设计算法（1）遍历线性表1.（2）合并级性表1:设1.a和1.b是元素限于同数据对象且非通戒有序的两个线性表，现要求将两个戏性表合并成个新的非递减有序的雄性衣
7、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的元素按非递减有序,线性表空间足弊大。试给出一
8、种高效算法，将1.B中元素合到1.A中，使新的1.A的元素仍保持非递减有序.高效指最大限度的避免移动元素，2）【北京航空航天大学】已知长度为n的线性次A果用顺序存储结构.请写一时间复杂度为（Xn）,空间复杂度为Od）的算法，该算法IH除线性去中所有值为item的数据元素.（0（1）表示以法的辅助空间为常盘。2010全国统考408】设将n（nl）个整数存放到一维数组R中.试设计一个在时间和空间两方面都尽可能高效的匏法，将R中保存的序列循环左移P（KP5）个位置.W将R中的数据由（XO1Xl“Xn-D变换为出*：若采用仃接左移P位,空间复杂度仍为O（1）,但时间宓杂度为（XnP）.=.课后巩圆（t
9、t）课后观看习题视频，并在校内SPOC完成知识点测试。本章节的教学重点,难点：1 .I点是顺序表的定义，基本操作的实现.2 .点是高效兑法设计，例如国家2010年硕士研究生入学考试抑法时就行5种解法教学方法、教学手段：1 .城性表和顺序表的概念和类型定义30分钟2 .顺序表上基本运算的实现（30分钟）3 .顺序表算法举例（30分钟）4 .使用教具：计算机和投影仪;5 .辅助教学：雨课堂、校内SpOC、“百科园”在战考试系统、学堂在我MooC、算.法演示动ah6 .深曲现后导学视频：课中案例展开，应用蒯转课堂、项目驱动以及实践教学法：课后观石习题觇频，并在校内SPOC完成知识点在线测试，作业、讨
10、论题、思考题：1,分析在顺序存储结构下插入和删除结点时平均衢要移动多少个结点。7 .顺序表Ia与Ib非递减有序，顺序表空间足游大。试设计一种高效算法，将Ib中元素合到Ia中.使新的Ia的元素仍保持非递减有序.高效指最大眼度地避免移动元素.改为:顺序&Ia非递减有序，出非递增有序，求解该问题.参考资料：1 .冯广怒,吴昊,文全刚.算法与数据结构（Cl语言版M.电子工业出版社.20192 .陈一孔,胡潇琨,李玲.冯广慧.算法与数据结构考研试题精析（第四版）M）.机械工业出版社,2020讲授章节第3讲单链表授课时数2教学目的：1 .掌握鞋表的类型定义和基本操作的实现.2 .掌握单链表的建立方法，特别
11、是头插法和尾插法。3 .了解单箧衣的应用。教学内容（讲授提纲）二 .防导学（线上）1 .观看导学视频2 .论坛讨论、反馈疑难点二.课堂帙学1从序存储结构的优缺点，引出修良的由要性插入和删除必须大埴移动元泰：必须预先确定空间；表空间不易扩充。3 .倭表的类型定义几个概念：结点，首元结点，第一元素结点，头结点,指针，头指针头指针头:点百元结点HEB卜，I十4 .线性表的畏作在单候表中的实现（1）单椎表的初始化：（2）清空单胜衣：3）求我长：（4）遍历能表：（5）查找位序为i的元素的地址:6杳找他为Value的元素的位序：（7杳找值为ValUe的元素的前驱；（8）求某元素的后第：（9）插入元素：10
12、）删除元泰。5 .单帽表的立立方法（特别是头场法和尾插法（1）头插法；（2）尾插法，6 .算法设计举例（I）【2012全国统考408】假定采用带头结点的单链发保存用词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，ToadingWrbCing”的存储映像如下图所示，设SIrI和和2分别指向两个单词所在单链表的头结点,鞋表结点结何为（data,next）请设计一个时间上尽可能高效的算法.找出由StrI和$tr2所指的两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）.要求：a）给出口法的基本设计思想.b）根据设计思想，采用C或C+或JAVA语音描述算法，关键之处给出注样,c
13、）说明你所设计算法的时间红杂度。（2）【2009全国统考408】已知一个带有表头结点的单於表.结点结构为SataJink）,假设该椎我只给出了头指针list.在不改变胜友的前提下，请设计一个尽可能高效的算法，查找挂表中倒数第k个位置上的站点（k为正整数），若查找成功，算法输出该结点的daia域的伯，井返回1：否则.只返回0,要求：a）描述算法的基本设计思想：b）描述算法的详细实现步骤：C）根据设计思想和实现步骤.采用程序设计谱言描述律法（使用C或C+或JAvA谱=实现，关世之处请给出简要注林.三 .爆后巩固（线上）课后观百习遨视频并在校内SpoC完成知识点测试.本章节的教学重点、难点：1 .动
14、态存储（单链表）的慨念.2 .单琏表的算法设计.教学方法、教学手段：1 .鞋表的定义和基本操作的实现（45分钟）2 .胜龙生成和链友应用的算法设计（45分仲）3 ,使用教具r计算机和投影仪:4 .辅助教学：而课堂、校内SpOC、“百科园”在线考试系统.学堂在线MooC、算法演示动画：5 .课前观看呼学视频；课中案例展开，应用翎转课堂、项目题动以及实践教学法：课后观看习题觇频，并在校内SPOC完成知识点在我测试.作业、讨论题、思考题：1 .试述头指针、头结点、元素结点、百元结点的区别,说明头指针和头结点的作用.2 .分析顺序存储结构和读式存储结构的优我点，说明何时应该利用何种结构，3 .为什么在
15、单循环链表中游使用是指针，若只设头指针，插入元素的时间复杂度如何？4 .在单琏表、双链表、单循环链表中，若知道指针P指向某结点,能否删除该结点.时间双杂度如何？5 .设ha和hb分别是两个带头结点的非递减有序单接表的头指针,试设计律法,将这两个有序链去合并成，个非递增有序的单SI表。要求使用原链衣空间，表中无正处数据，改：设力“和汕分别是两个带头结点的非递减有序单链表的头指针,试设计算法，将这两个有序链表合并成个非递减行序的单於我要求使川原桂表空间.表中无重更数据.参考资料：1 .冯广慧,吴知文全刚.算法与数据结构（C+语言版Ml.电子工业Hl版社,20192 .陈守孔,胡潇混，李玲,冯广魅,
16、算法与数据结构考研试题精折（第四版M.机械工业出版社.20203 .翁惠玉,俞勇.数据结构：思想与实现.高等教育出版社M1.高等教育出版社.2018讲授章节第4讲循环法表、双链表授课时数2教学目的：1.掌握很环链2.常握循环微衣引入的背景：从任一结点开始可以访问处衣中的全部结点.衣CR循环链表，双循环链表）和Wia:表，教学内容（讲授提纲）一.谭茵导学（ttJ1 .观看导学视2 .论坛讨论、二.豫直帙学1 .比较*用2 .林单仰3 .济解两个J4 .双倭表的，为深刻的理1p-prior-ncjP-ncx（-pri（引导学生理解p-prior-no注意区分双铳5 .线性表的力凡涉及一个7同.但是
17、在插入或造表有两个指针政:）嫡反馈疑雄点良和单健表掾作的优缺点，使用范圉不倭表.指出：单循环修表往往只设尾指针4设尾指针的单循环使表合并成一个单一环倭表的例子政双倭表，展开忖论：Ct=?;H=?;双链表的特点；U=P-ncxt-prior=p;表和双循环链表是两柠钺表.作在双健表中的实现方向的指针时,如求长度.取元素，元素定位等,其算法描述和单融表基本相删除结点时.一个结点就要修改两个指针域,所以要比中魅表复杂，由于北.求前驱和后继都很方便。p-11.IIABhBgJ11r-rio1.n=9：T-yYs-Xext=p;快9A3PWE1,6,算法设计，111IIp-next-prior=p-pr
18、ior;deletep：B2J;tt*W己知一双向循环链去，从第：个结点至表尾递增有序，（设a1xan）0试编写算法，将第一个结点删除并插入表中适当位置，使整个链表述增有序。（3【2015全国统考4081用单跳表保存m个整数，节点的结构为（dataJmk）,且ktata2012全国统考408已知操作符包括一，*,黄，（和）.将中摄表达式a+b-a*（c+d）c-f）+g转换为等价的后级表达式ab+acd+cf-*-g+0j,用校来存放料时还不能确定运算次序的操作符.若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）.3 .5B.7C.8D.Il（2） 2014全国统考408翼设
19、栈初始为空,将中谈表达式ab+（c*d-e0转换为等价的后嘏表达式的过程中,当扫描到f时.栈中的元素依次是（）.A.+（*-B.+（-C./+（*-*D./+-*3 .后霰表达式求值（1）算法思想及实现（2举例：后级表达式I262O5*求他4 6.若在一个函数、过程或者数据结构定义的内部,直接（或间接）出现定义本身的应用,则称它们是递归的,或者是递打定义的.S迤归过程的应用问题的定义是递归的：f（n）=n*fOInkgtOO(nlogm)O(nlogjn0(d*(radi4fi)00(n200O(11,)0Onlogzn)Onlogm)Odf(nhxn)O(I)O(1)O(1)O(1)O(!)
20、OUog2fl)O(1)O(n)O(11dun)枪定钦定校定不稼定不检定不和定不独定稳定也定4.内部捧序小结5 .课直练习(1)2(X)9全国统考40】若数据无索序列U.12.13.7.8.9.23.4.5是采用下列排序方法之一得到的第二皑排序后的结果,则该排序算法只能是()A.起泡排序B.插入排序C.选择排序D.二路归并排序(2【2017全国统考40G下列持序方法中若将顺序存储更换为集式存谛.则算法的时间效率会修低的是().I.插入排序II.选择排序川,起泡排序IV.希尔排序V.堆排序A.仅I、HB.仅II、川C.仅Il1.IVD.仅IV、V(3)对一组数据(2,12,16,88,5.10)
21、进行排序,若前三的排序结果如下：第一随排序结果：2,12.16,5,10.88笫二超持序结果：2.12.5.10.16.88第三起排序结果:2,5,10,12,16,88期采用的排序方法可能是(),起泡排序B.希尔排序C.归并排序D.%数排序6 .算法设计举例按由大到小的顺序对-含有n个元素的数组An进行排序,利用如下改进的简单选择排序方法:第一次选出圾大者存入A0.第二次选出最小者存入Anl.第三次选出次大者存入Al,第四次选出次小者存入A(n-2).如此大小交替地选择.H到排序完毕。=.课后巩RI(tt)课后观看习题视频，并在校内SPOC完成知识点测试,本章节的教学重点、难点:归并排序的基
22、本思想、步骤、W法.教学方法、教学手段:1 .归并排序(30分钟)2 .内部排序方法的比较、小结、课堂练习(4S分钟)3 .使川敦具：计算机和投出仪4 .辅助教学；雨课堂、校内SPoC、百科园、学堂在线MOOC、算法演示动画5 .课前观百导学觇频，课中案例展开,应用翻转课堂、项目飘动以及实践教学法。课后观看习出视短，并在校内SPOC完成知识点在线测试作业、讨论密、思考咫：1 .设计排序的关键字序列为(15,21.6.30,23.6,20.17),试分别写出使用以下排序方法j趟排序后的结果。并说明做了笠少次比较,(1)直接插入排序(2)希尔排序(增量为5.2,1)(3)起泡排序(4)快速排序(5
23、)直接选择排序(6)锦标赛排序(7)堆排序(8)二路归并排序2 .讨论：你认为哪线排序算法适用于行找前K个最小元素？参考资料:1 .冯广意.吴吴,文全M算法与数据结构(CI语言版)M电子工业出版社.20192 .陈守孔，胡潇琨，李玲，冯广慈.算法与数据结构考研试题精析(第四版M.机械工业出版社,2020实验教案实验名称实验一顺序表授课时数2实验目的：1.理蟀线性交的逻辑结构特征，会定义线性表的顺序存储类型：2,熟;我顺序表的基本操作和具体的函数实现；3.熟悉多文件程序的输入、编辑、调试和运行的全过程.教学内容（讲授提纲）一 .课防（tt）1 .观看算法模拟动画，理解算法出想：2 .课前查阅资料
24、,储备背景知识,构思解决方案,确定小组分工.二 .实殴室1 .实验内容（1）顺序表的类型定义及基本运算（必做设计性/验证性）初始化IWi序去、清至顺序表、求地序表长度、判断顺序去是否为空、论历顺序表、杳找元索、插入元素、州除元泰、逆置地序表.（2学生成绩管埋系统（选做,设计性）（3）鼓励自主拟定实践训练项目选做,设计性）2 .实曲要求（I）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚伯代码保证”（2）编程环境不限，VS、DEVCPP等均可（3）小组讨论合作探究,组织讲演答辩活动三 .豫后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视领.开展自评互评本章节的教学重
25、点、难点：期序表的插入和捌除运算教学方法、教学手段：1 .使用教具：计算机和投影仪2 .辅助教学：校内SPOC、百科园算法演示动画参考资料：1 .冯广慈，吴知文全刚.算法与数据结构（C+语古版）IMl.电子工业M版社,20192 .陈守孔，胡潇混,李玲,冯广慈,算法与数据结构考研试Sfi相析（第四版）【M|,机械工业出版社.2020实验教案实验名称实验二审链表授课时数2实验目的：1.理蟀线性交的逻辑结构特征，会定义线性表的链式存储类型：2,熟悉单链表的基本操作和具体的函数实现；3.熟悉多文件程序的输入、编辑、调试和运行的全过程.教学内容（讲授提纲）一 .课防（tt）1 .观看算法模拟动画，理解
26、算法出想：2 .课前查阅资料,储备背景知识,构思解决方案,确定小组分工.二 .实殴室1 .实验内容（1）单鞋表的类型定义及基本运算（必做设计性/验证性）初始化电链去、清学单链表、求单链衣长度、判断单链去是否为空、论历单链表、杳找元索、插入元素、州除元泰、逆置单琏表、头插法创建单隆表。（2）约瑟夫环（选做，设计性）（3）请设计一个尽可能高效的算法，杳找链表中例数第k个位置上的结点峰为正整数），若杳找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。（选做,设计性）（4）鼓励自主拟定实践训练项目（选做,设计性）2 .实验要求（1）编码应遵循“数据结构与算法编程规范”,建设在程序中添加
27、“诚信代码保证”：（2）编程环境不限.VS、DEVCPP等均可：（3）小组讨论合作探究,加织讲演答辩活动。三 .售后（线上）完成代码的整合与调试，在校内SPoC平台提交报告和作品视频，开展白评互评本章节的教学重点、难点：单链表的插入、删除、逆置教学方法、教学手段：1 .使用教具：计算机和投影仪2 .情助教学：校内SpoC、百科园、算法演示动画参考资料:1,冯广收吴吴.文全刚算法与数据结构（Cl语言版）IMl.电子工业出版社.2019实验教案实验名称实验三栈与队列授课时数2实验目的：1 .理蟀栈和队列的逻辑特点，能在实际应用中正确选用2,熟练掌握栈和队列的Iwi序和链式实现方法，以及延木操作的算
28、法实现3 .会判断循环队列空和酒,会计算循环队列中元素个数教学内容（讲授提纲）一 .课防（tt）1 .观看算法模拟动画，理解算法出想2 .课前查阅资料,储备背景知识,构思解决方案,确定小组分工二 .实殴室1 .实验内容（1）栈的类型定义及基本运算（必做,设计性/验证性）实现顺序校和链栈，完成栈的舰木操作：初始化栈、检我校是否为空、清空栈、入栈、退栈、取找顶元素.（2）队列的类型定义及基本运算（必做.设计性/验证性）实现循环队列和班队列，完成队列的法本操作：初始化队列、拉杳队列是否为空、清支队列、入队、出队、取队百元素。（3）利用两个栈模拟一个队列（选做，设计性）（4）鼓励自主拟定实践训练项目选做,设计性）2 .实验要求（I）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚信代码保证”（2）编程环境不限，VS、DEVCPP等均可（3）小组讨论合作探究,组织讲演答辩活动三 .课后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视顿，开展自评互评本章节的教学重点、难点：判断循环队列空和满.带头尾指针的琏认列入队和出队时的特殊情况教学方法、教学手段：1 .使用教具：计算机和投影仪2 .辅助教学：校内SPOC、百科园、算法演示动Iui参考资料：1.冯广慈，吴昊,文全刚.算法与
