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

上传人:王** 文档编号:1394569 上传时间:2024-07-05 格式:DOCX 页数:25 大小:198.99KB
下载 相关 举报
数据结构与算法教学教案(理论+实践).docx_第1页
第1页 / 共25页
数据结构与算法教学教案(理论+实践).docx_第2页
第2页 / 共25页
数据结构与算法教学教案(理论+实践).docx_第3页
第3页 / 共25页
数据结构与算法教学教案(理论+实践).docx_第4页
第4页 / 共25页
数据结构与算法教学教案(理论+实践).docx_第5页
第5页 / 共25页
数据结构与算法教学教案(理论+实践).docx_第6页
第6页 / 共25页
数据结构与算法教学教案(理论+实践).docx_第7页
第7页 / 共25页
数据结构与算法教学教案(理论+实践).docx_第8页
第8页 / 共25页
数据结构与算法教学教案(理论+实践).docx_第9页
第9页 / 共25页
数据结构与算法教学教案(理论+实践).docx_第10页
第10页 / 共25页
亲,该文档总共25页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《数据结构与算法教学教案(理论+实践).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)删除元泰。5 .单帽表的立立方法(特别是头场法和尾插法(1)头插法;(2)尾插法,6 .算法设计举例(I)【2012全国统考408】假定采用带头结点的单链发保存用词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间。例如,ToadingWrbCing”的存储映像如下图所示,设SIrI和和2分别指向两个单词所在单链表的头结点,鞋表结点结何为(data,next)请设计一个时间上尽可能高效的算法.找出由StrI和$tr2所指的两个链表共同后缀的起始位置(如图中字符i所在结点

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!