数据结构与算法教学教案（理论+实践）.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所在结点的位置p）.要求：a）给出口法的基本设计思想.b）根据设计思想，采用C或C+或JAVA语音描述算法，关键之处给出注样,c）说明你所设计算法的时间红杂度。（2）【2009全国统考408】已知一个带有表头结点的单於表.结点结构为SataJink）,假设该椎我只给出了头指针list.在不改变胜友的前提下，请设计一个尽可能高效的算法，查找挂表中倒数第k个位置上的站点（k为正整数），若查找成功，算法输出该结点的daia域的伯，井返回1：否则.只返回0,要求：a）描述算法的基本设计思想：b）描述算法的详细实现步骤：C）根据设计思想和实现步骤.采用程序设计谱言描述律法（使用C或C+或JAvA谱=实现，关世之处请给出简要注林.三 .爆后巩固（线上）课后观百习遨视频并在校内SpoC完成知识点测试.本章节的教学重点、难点：1 .动态存储（单链表）的慨念.2 .单琏表的算法设计.教学方法、教学手段：1 .鞋表的定义和基本操作的实现（45分钟）2 .胜龙生成和链友应用的算法设计（45分仲）3 ,使用教具r计算机和投影仪:4 .辅助教学：而课堂、校内SpOC、“百科园”在线考试系统.学堂在线MooC、算法演示动画：5 .课前观看呼学视频；课中案例展开，应用翎转课堂、项目题动以及实践教学法：课后观看习题觇频，并在校内SPOC完成知识点在我测试.作业、讨论题、思考题：1 .试述头指针、头结点、元素结点、百元结点的区别,说明头指针和头结点的作用.2 .分析顺序存储结构和读式存储结构的优我点，说明何时应该利用何种结构，3 .为什么在单循环链表中游使用是指针，若只设头指针，插入元素的时间复杂度如何？4 .在单琏表、双链表、单循环链表中，若知道指针P指向某结点,能否删除该结点.时间双杂度如何？5 .设ha和hb分别是两个带头结点的非递减有序单接表的头指针,试设计律法,将这两个有序链去合并成，个非递增有序的单SI表。要求使用原链衣空间，表中无正处数据，改：设力“和汕分别是两个带头结点的非递减有序单链表的头指针,试设计算法，将这两个有序链表合并成个非递减行序的单於我要求使川原桂表空间.表中无重更数据.参考资料：1 .冯广慧,吴知文全刚.算法与数据结构（C+语言版Ml.电子工业Hl版社,20192 .陈守孔,胡潇混，李玲,冯广魅,算法与数据结构考研试题精折（第四版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同.但是在插入或造表有两个指针政:）嫡反馈疑雄点良和单健表掾作的优缺点，使用范圉不倭表.指出：单循环修表往往只设尾指针4设尾指针的单循环使表合并成一个单一环倭表的例子政双倭表，展开忖论：Ct=?;H=?;双链表的特点；U=P->ncxt->prior=p;表和双循环链表是两柠钺表.作在双健表中的实现方向的指针时,如求长度.取元素，元素定位等,其算法描述和单融表基本相删除结点时.一个结点就要修改两个指针域,所以要比中魅表复杂，由于北.求前驱和后继都很方便。p-11.IIABhBgJ11r->rio1.>n=9：T-yY®s-Xext=p;快9A3PWE1,6,算法设计，111IIp->next->prior=p->prior;deletep：B2J;tt*W<5刚（1）将单循环链去改为双循环琏表。假设一个单循环琏表，其结点含有三个域pre、data,next.其中data为数据域：PrC为指针域,它的值为空指针（null）：next为指针域，它指向后维结点.请设计算法,拘此表改成双向循环链衣.（2>己知一双向循环链去，从第：个结点至表尾递增有序，（设a1<x<an）0试编写算法，将第一个结点删除并插入表中适当位置，使整个链表述增有序。（3【2015全国统考4081用单跳表保存m个整数，节点的结构为（dataJmk）,且ktata<n（n为正整数人现要求设计一个时间发杂度尽可能l效地比法，对于链去中绝对值相等的节点，仅保用第一次出现的节点而删除其余绝对值相等的节点，例如若给定的单琏表head如卜.（EDHEAD3-ffl-EB-ES-03-ffi.险后-03-EH3-I三.遇后巩国（tt±）课后观看习网视频，并在校内SPOC完成知识点测试，本章节的教学重点、难点:1 .循环链表和双陞表的概念。2 .难点是循环融表和双琏表的应用算法设计.教学方法、教学手段：1 .循环隧衣和虫链发（45分神2 .算法设计（45分钟）3 ,使用教具r计算机和投影仪：4 .辅助教学：雨课堂、校内SPOC、,百科园”在线考试系统、学堂在线MOOC、算法演示动图:5 .课前观看等学视频；课中案例展开，应刖翎转课堂、项目题动以及实践教学法：课后观看习题觇频，并在校内SPOC完成知识点在我测试.作业、讨论题、思考题：1 .设Ia是一个双向循环链表其表中元素递增有序.试写一算法插入元素X,使表中元素依然递增有序.改为：设Ia是一个双向循环於表，其表中元素递减有序.试写一算法插入元素X.使表中元素依然述诚有序，2 .设计一律法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式各自仅有奇次帘或偶次率项，并要求利用原链表中的结点空间来构造这两个链表.参考资料:1 .冯广慧，吴知文全刚.算法与数据结构（C+语古版M电子工业M版社,20192 .陈守孔.胡潇琨，李玲,冯广慈,算法与数据结构考研武题构折（第四版）M,机械工业出版社,20203 .翁惠玉,俞勇.数据结构：思想与实现.高等教育出版社IM1.高等教育出版社.2018讲授章节第5讲栈授课时数2教学目的：I埋解校和队列仍屈于线性结构.其操作是税性龙懊作的子集.是操作受限的税性表.但从数据类型的角度看，它们是和线性表大不相同的虫要抽象数据类型,2 .靠押栈的定义及操作。校是只准在一端进行插入和刷除操作的戏性衣，该端称为栈的顶端“3 .掌握栈的顺序和链式存储结构，及在这两种结构下实现栈的操作.4 .校的应用：表达式求值.教学内容（讲授提纲）*导学（线上）1 .观看导学视频2 .论坛讨论、反馈疑难点二 .课堂教学1 .栈的基本辕念：栈、校顶、栈尾，栈只在栈顶操作.2.极的抽象数据类型定义3.序机及枕的掾作在履序机中的实现4.健栈及栈的掾作在*序极中的实现5.课堂练习（1【2010全国统考408】若元素a,bc,d.e,f依次进栈，允许诳栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。A.d.c,c.b,f,aB.c.b.d.a,c,fC.b.c.a.c.f.dD.a.f.c.d.c.b（2）2OI3全国统考408】一个栈的入栈序列为1,2,3,n,其出栈序列是pl,p2.p3.pn.若p2为3,贝Up3可能取值的个数是.A.n-3B.»-2ClvID.无法确定6.枚的应用（1）过程询用（2消除递归（3）使用栈进行数制转换（4）中缴表达式的求位算术去达式中运算符（+.*1/等）的优先规则设置两个工作栈：运算符栈SI和操作数枚S2.S2存放表达式的运算结果.算法思想：I忏先置操作数技S2为空栈，冏运算符栈的栈底为表达式的起始符制优先级最低），2依次读入表达式的每个字符ch.宜至表达式结束：若Ch是操作数朋1进S2栈；若Ch是运算符，若其优先级不高于栈顶运舞符的优先娘时,则取出栈S2的栈原和次栈顶的两个元素以及枝Sl的枝顶运翼符.进行相应的运算,并将结果放入找S2中：如此下去,直至ch的优先欲高于校丁交运算符的优先级,将Ch入SI栈.三 .爆后巩固（线上）课后观看习题视频，并在校内SPOC完成知识点测试.本章节的教学重点、难点：1 .理点是栈的概念和基础知识。2 .难点：中爆表达式求值.教学方法、教学手段：1 .栈的基本概念和顺序栈（45分钟）2 .桂栈、中极表达式求色（45分钟）3 ,使用教具r计算机和投影仪:4 .辅助教学：雨课堂、校内SPOC、“百科同工学堂在线MOOC、舞法演示动痴：5 .课前观看导学税频：i果中案例展开,应用期传课堂、项目建功以及实践教学法：课后观看习题视频，并在校内SPOC完成知识点在我测试,作业、讨论题、思考题：1 .有力,个数依次进校：I、2,3、4、九在各种出栈的序列中以3、4先出的序列有哪几个。2 .铁路进行列车调度时，常.把站台设计成程式结构，岩进站的六辆列车顺序为：1，2.3.4,5.6,那么是否能上得到435612,325641,44623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何得到（即写出"进栈"或山栈”的序列）。3.设称正法和反读都相同的字符序列为“回文,例如,“abba”和“abccba”是响文“abcdc”和“ababab”则不是“51文”，试写一个算法，判别读入的一个以为结束符的字符序列姑有是“Wl参考资料：1 .冯广M.吴吴.文全刚算法与数据结构（Cl语言版M电子工业出版社.20192 .陈守孔.胡潇琨.季玲.冯广您.算法与数擀结构考研试也精折M.机械工业出版社.2020讲授章节第6讲栈的应用授课时数2教学目的：1 .掌握栈的定义的本质：1.IFO.栈是只准在一端诳行插入和捌除操作的线性表，该端称为栈的顶端，2 .掌握栈的应用：中缀表达式轿为后爆表达式，并求值“3 .掌握递归过程的应用。教学内容（讲授提纲）一课防导学（线上）1 .观看导学视频2 .论坛讨论、反馈疑难点二.课依教学本次课继续学习栈的应用。1 .中«1表达式转为后籁表达式（1）算法思想及实现（2）举例：中埃表达式12*（6/2-03转为后缀表达式（3）介绍中级衣达式转为后缴友达式的前单方法2 .谭我练习（1>2012全国统考408已知操作符包括一，*',黄，（'和）'.将中摄表达式a+b-a*（c+d）c-f）+g转换为等价的后级表达式ab+acd+cf-*-g+0j,用校来存放料时还不能确定运算次序的操作符.若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）.3 .5B.7C.8D.Il（2） 2014全国统考408翼设栈初始为空,将中谈表达式ab+（c*d-e>0转换为等价的后嘏表达式的过程中,当扫描到f时.栈中的元素依次是（）.A.+（*-B.+（-C./+（*-*D./+-*3 .后霰表达式求值（1）算法思想及实现（2>举例：后级表达式I262O5*求他4 »6.若在一个函数、过程或者数据结构定义的内部,直接（或间接）出现定义本身的应用,则称它们是递归的,或者是递打定义的.S迤归过程的应用问题的定义是递归的：f（n）=n*f<n-l）数据结构是递归的：向题的解法是递归的：HanOi塔向即6 .遇归算法的优缺点（）将f序列Rl整成大毁Je（b）66和及交畏后堆排序算法思想、手工模拟、算法实现、性旎分析、优缺点三.课后巩国（tt±）课后观看习题视频，并在校内SPOC完成知识点测试。本章节的教学重点、难点:1 .理点是各种交换排序和选择排序的基本思想、手工模拟、。法及性能分析2 .难点快速排序、堆排序.教学方法、教学手段:1 .交换排序及笄法设计举例（45分钟2 .选择排序（45分钟）3 .使用教具：计算机和投影仪4 .辅助教学：附课堂、校内SPoC、百科园、学堂在线MOOC、算法演示动画5 .课前观看导学视姣，深中案例展开，应用期转课堂、项目弱动以及实践教学法.课后观行习题视频，并在校内SPoC完成知识点在找测试作业、讨论题、思考题：1 .在堆排序、快速排序和归并排序方法中：（1）若只从存储空间考虑，则应首先选取哪种排序,其次选取哪种排序,最后选取哪种排序？（2）若只从持序结果的稳定性考虑,则应选取哪种排序方法？（3）若只从平均情况下排序最快考虑,则应选取哪种排序方法？（4）若只从最坏情况下排序必快并且要节省内存考虑，则应选取哪种排序方法？2 .判断卜面的短个结点序列是否表示一个堆，如果不足堆，请把它调整成堆。（1） 1«）.90.80.60.85.75.20,25.10.70.65.50（2） 100,70,50,20,90.75,60,25.10.85.65.803.在数组A0.n-l）中存放有n个不同的整数，其值均在I到n之间,设计算法将A中的n个数从大到小摔序后存入B0.ml数组中,要求算法的时间爱杂度为O（n）.参考资料：1 .冯广慈,吴昊,文全刚.算法与数据结构（Cl语言版）（M,电子工业由版社.20192 .陈守孔.胡潇琨,李玲,冯广恕：.算法与数据结构考研试题精析第四版）M.机械工业出版社.2020讲授章节第24讲归并持序地数排序授课时数2教学目的：1 .理解并掌握归并排序分限排序的基本思想、步舞、算法.2 .内部排序方法的比较和总结.教学内容（讲授提纲）一.瓷Ir导学（线上）1 .观看导学视领2 .论坛讨论、反馈疑难点二.僵直教学1.归并排序算法思想、手工模拟、眸法实现、初始序列：36）8011性货分析、总站优缺点6645229J'I16369第一归阪T3680)(-15166)92216r36J第二«归并:36-Y451.6680)916Y22_y3S第施9162236V-364566802餐敷押序（曲单介绍）3.内部排序方法的比较持序方法平均时间最坏情况辅助空何稳定性出图入持序折半插入排印界泡排序直按选界排序希尔排序快速排序堆排序2-归并井井基兹排序O(n2)O(P)O(n-)o(11O(nl,>OInkgtOO(nlogm)O(nlogjn>0(d*(radi4fi)0<n2>0(n2>0<n2>0<n7>O(11,)0<n2>O<nlogzn)Onlogm)O<df(nhx÷n)O(I)O(1)O(1)O(1)O(!)OUog2fl)O(1)O(n)O(11du÷n)枪定钦定校定不稼定不检定不和定不独定稳定也定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)进行排序,若前三的排序结果如下：第一随排序结果：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完成知识点测试,本章节的教学重点、难点:归并排序的基本思想、步骤、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)直接选择排序(6)锦标赛排序(7)堆排序(8)二路归并排序2 .讨论：你认为哪线排序算法适用于行找前K个最小元素？参考资料:1 .冯广意.吴吴,文全M算法与数据结构(CI语言版)M电子工业出版社.20192 .陈守孔，胡潇琨，李玲，冯广慈.算法与数据结构考研试题精析(第四版M.机械工业出版社,2020实验教案实验名称实验一顺序表授课时数2实验目的：1.理蟀线性交的逻辑结构特征，会定义线性表的顺序存储类型：2,熟;我顺序表的基本操作和具体的函数实现；3.熟悉多文件程序的输入、编辑、调试和运行的全过程.教学内容（讲授提纲）一 .课防（tt±）1 .观看算法模拟动画，理解算法出想：2 .课前查阅资料,储备背景知识,构思解决方案,确定小组分工.二 .实殴室1 .实验内容（1）顺序表的类型定义及基本运算（必做设计性/验证性）初始化IWi序去、清至顺序表、求地序表长度、判断顺序去是否为空、论历顺序表、杳找元索、插入元素、州除元泰、逆置地序表.（2学生成绩管埋系统（选做,设计性）（3）鼓励自主拟定实践训练项目选做,设计性）2 .实曲要求（I）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚伯代码保证”（2）编程环境不限，VS、DEVCPP等均可（3）小组讨论合作探究,组织讲演答辩活动三 .豫后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视领.开展自评互评本章节的教学重点、难点：期序表的插入和捌除运算教学方法、教学手段：1 .使用教具：计算机和投影仪2 .辅助教学：校内SPOC、百科园'算法演示动画参考资料：1 .冯广慈，吴知文全刚.算法与数据结构（C+语古版）IMl.电子工业M版社,20192 .陈守孔，胡潇混,李玲,冯广慈,算法与数据结构考研试Sfi相析（第四版）【M|,机械工业出版社.2020实验教案实验名称实验二审链表授课时数2实验目的：1.理蟀线性交的逻辑结构特征，会定义线性表的链式存储类型：2,熟悉单链表的基本操作和具体的函数实现；3.熟悉多文件程序的输入、编辑、调试和运行的全过程.教学内容（讲授提纲）一 .课防（tt±）1 .观看算法模拟动画，理解算法出想：2 .课前查阅资料,储备背景知识,构思解决方案,确定小组分工.二 .实殴室1 .实验内容（1）单鞋表的类型定义及基本运算（必做设计性/验证性）初始化电链去、清学单链表、求单链衣长度、判断单链去是否为空、论历单链表、杳找元索、插入元素、州除元泰、逆置单琏表、头插法创建单隆表。（2）约瑟夫环（选做，设计性）（3）请设计一个尽可能高效的算法，杳找链表中例数第k个位置上的结点峰为正整数），若杳找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。（选做,设计性）（4）鼓励自主拟定实践训练项目（选做,设计性）2 .实验要求（1）编码应遵循“数据结构与算法编程规范”,建设在程序中添加“诚信代码保证”：（2）编程环境不限.VS、DEVCPP等均可：（3）小组讨论合作探究,加织讲演答辩活动。三 .售后（线上）完成代码的整合与调试，在校内SPoC平台提交报告和作品视频，开展白评互评本章节的教学重点、难点：单链表的插入、删除、逆置教学方法、教学手段：1 .使用教具：计算机和投影仪2 .情助教学：校内SpoC、百科园、算法演示动画参考资料:1,冯广收吴吴.文全刚算法与数据结构（Cl语言版）IMl.电子工业出版社.2019实验教案实验名称实验三栈与队列授课时数2实验目的：1 .理蟀栈和队列的逻辑特点，能在实际应用中正确选用2,熟练掌握栈和队列的Iwi序和链式实现方法，以及延木操作的算法实现3 .会判断循环队列空和酒,会计算循环队列中元素个数教学内容（讲授提纲）一 .课防（tt±）1 .观看算法模拟动画，理解算法出想2 .课前查阅资料,储备背景知识,构思解决方案,确定小组分工二 .实殴室1 .实验内容（1）栈的类型定义及基本运算（必做,设计性/验证性）实现顺序校和链栈，完成栈的舰木操作：初始化栈、检我校是否为空、清空栈、入栈、退栈、取找顶元素.（2）队列的类型定义及基本运算（必做.设计性/验证性）实现循环队列和班队列，完成队列的法本操作：初始化队列、拉杳队列是否为空、清支队列、入队、出队、取队百元素。（3）利用两个栈模拟一个队列（选做，设计性）（4）鼓励自主拟定实践训练项目选做,设计性）2 .实验要求（I）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚信代码保证”（2）编程环境不限，VS、DEVCPP等均可（3）小组讨论合作探究,组织讲演答辩活动三 .课后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视顿，开展自评互评本章节的教学重点、难点：判断循环队列空和满.带头尾指针的琏认列入队和出队时的特殊情况教学方法、教学手段：1 .使用教具：计算机和投影仪2 .辅助教学：校内SPOC、百科园、算法演示动Iui参考资料：1.冯广慈，吴昊,文全刚.算法与