数据结构课程知识体系和教学实践课件省名师优质课赛课获奖课件市赛课百校联赛优质课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,北京大学信息学院,版权所有，转载或翻印必究 Page,北京大学信息学院 版权所有，转载或翻印必究 Page *,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。不能作为科学依据。,数据结构课程知识体系和教学实践,张 铭,北京大学信息科学与技术学院,208月,1/34,内容提要,一、知识体系,二、教学实践,三、教学案例,2/34,北京大学信息学院 版权全部，转载或翻印必究 Page 2,一、知识体系,1.数据定义,2.算法效率问题,3.抽象数据类型,3/34,北京大学信息学院 版权全部，转载或翻印必究 Page 3,1.数据结构定义,数据逻辑结构,数据存放结构,数据运算,4/34,北京大学信息学院 版权全部，转载或翻印必究 Page 4,常见逻辑关系,线性结构,树形结构,图结构,文件结构,图,树,二叉树,线性表,5/34,北京大学信息学院 版权全部，转载或翻印必究 Page 5,常见存放方法,次序方法,链接方法,索引方法（线性、树形）,散列方法,6/34,北京大学信息学院 版权全部，转载或翻印必究 Page 6,运算,建立、去除数据结构,插入一个新数据元素,删除、修改某个数据元素,排序,检索,7/34,北京大学信息学院 版权全部，转载或翻印必究 Page 7,一、知识体系,1.数据定义,2.算法效率问题,3.抽象数据类型,8/34,北京大学信息学院 版权全部，转载或翻印必究 Page 8,算法效率基本问题权衡,对于给定一类问题,算法需要多少存放空间和时间？,最好算法最坏情况是什么？,平均来说，算法运行好到何种程度？,算法普通化到何种程度？,什么情况下，最好算法是什么？,算法分析技术,9/34,北京大学信息学院 版权全部，转载或翻印必究 Page 9,一、知识体系,1.数据定义,2.算法效率问题,3.抽象数据类型,10/34,北京大学信息学院 版权全部，转载或翻印必究 Page 10,抽象数据类型ADT,抽象数据类型是定义了一组运算数学模型,把数据结构存放与实现细节剥离,在适当抽象层次上考虑程序结构和算法,封装和信息隐蔽,11/34,北京大学信息学院 版权全部，转载或翻印必究 Page 11,二、教学实践,1.教学目,2.教材编写,3.教学策略,12/34,北京大学信息学院 版权全部，转载或翻印必究 Page 12,数据结构课程主要内容,理论,算法数学基础,算法时间和空间度量,抽象,排序、检索等主要问题类有效算法,主要数据结构技术,设计,算法选择、实现和测试,13/34,北京大学信息学院 版权全部，转载或翻印必究 Page 13,教学目,“数据结构算法程序”,把数据结构和算法理论与编程实践相结合,能够在实际工程实践中灵活地给予应用,培养数据抽象能力,提升程序设计质量,14/34,北京大学信息学院 版权全部，转载或翻印必究 Page 14,二、教学实践,1.教学目,2.教材编写,3.教学策略,15/34,北京大学信息学院 版权全部，转载或翻印必究 Page 15,教材编写,许卓群、杨冬青、唐世渭、张铭，数据结构与算法，高等教育出版社，7月。ISBN 7-04-014616-9。,张铭、赵海燕、王腾蛟，数据结构与算法学习指导与习题解析，高等教育出版社，9月。ISBN 7-04-017829-X。,16/34,北京大学信息学院 版权全部，转载或翻印必究 Page 16,数据结构与算法,C+模板,抽象数据类型ADT),第1章概论,数据结构定义,抽象数据类型,基本算法分析技术,第2-6章,从逻辑结构角度系统地介绍各种基本数据结构,线性表、字符串、二叉树、树和图,17/34,北京大学信息学院 版权全部，转载或翻印必究 Page 17,第7章 内排序,第8章 文件与外排序,第9章 检索,第10章 索引,第11章 高级线性结构,第12章 高级树形结构,Patricia树、伸展树，k-d树、PR四分树、R*树,18/34,北京大学信息学院 版权全部，转载或翻印必究 Page 18,数据结构与算法学习指导与习题详解,第1-12章，涵盖了主教材基本内容,主教材主要数据结构和算法知识点、学习重点和难点,习题详解第13章上机汇报,ACM竞赛：穷举、回溯、分治、搜索、DP,实习汇报要求和样例,第14章为考试题及其解答,秋季学期期中、期末考题和答案,1999-年北大硕士入学考试,19/34,北京大学信息学院 版权全部，转载或翻印必究 Page 19,习题详解,212道习题、53道上机题,题意分析、边界处理提醒,经典解法（算法描述）,算法代价分析,经典错误,170道新习题，40道新上机题,20/34,北京大学信息学院 版权全部，转载或翻印必究 Page 20,二、教学实践,1.教学目,2.教材编写,3.教学策略,21/34,北京大学信息学院 版权全部，转载或翻印必究 Page 21,（1）启发式教学,数学特征,抽象数据类型,不一样存放方法,不一样存放方法可能算法,结合算法分析来讨论各种存放方法和算法利弊，摒弃不宜方法,22/34,北京大学信息学院 版权全部，转载或翻印必究 Page 22,（2）引进新理论技术,“搜索引擎”中数据结构技术,图搜索,排序,索引技术,23/34,北京大学信息学院 版权全部，转载或翻印必究 Page 23,（3）加强实践步骤训练,数据结构与算法，3学分/周3课时,每七天布置6道书面作业或小程序实习,数据结构与算法实习，2学分/周2课时,一个学期8道ACM竞赛题,6道综合上机实习题,上机实习时间，120小时/学生,24/34,北京大学信息学院 版权全部，转载或翻印必究 Page 24,（4）新教育技术,建立了高质量课程网站,50多小时rm（全程录像）,标准C+模板编写可执行源程序代码,9209代码总行数，非注释行7498,习题和上机题及其参考答案,BBS讨论版(7月28日数据),2244名注册会员，653个问题，1863回帖,助教讲答,25/34,北京大学信息学院 版权全部，转载或翻印必究 Page 25,26/34,北京大学信息学院 版权全部，转载或翻印必究 Page 26,每章内容,概述、前测,知识点详解,动画,习题解、新习题,电子教案,pdf、视频,扩展资源,参考网站、论文、讲义,27/34,北京大学信息学院 版权全部，转载或翻印必究 Page 27,5）严格要求，教书育人,每一届都布置全新作业,“老实代码”,助教严格检验,28/34,北京大学信息学院 版权全部，转载或翻印必究 Page 28,教学实施,1.教师面授重点难点讲解（30%）,2.学生利用网络课件和网络资源自学（40%）,3.课后作业和小组协作（课上和课下）（20%）,4.助教网络答疑和网络讨论（10%）,5.重点难点时间放在网络自学及教师面授讲解上。,29/34,北京大学信息学院 版权全部，转载或翻印必究 Page 29,主课教学评价,1.平时(书面作业、课堂测试)：20%,2.上机实习(+实习汇报)：15%,3.期中考试：20%,4.期末考试：40%,5.考勤和态度：5%30/34,北京大学信息学院 版权全部，转载或翻印必究 Page 30,实习课教学评价,平时(考勤+开卷随堂测试课堂表现)占30%,上机题（源程序实习汇报）70%,31/34,北京大学信息学院 版权全部，转载或翻印必究 Page 31,1线性表；,2二叉树,；3树；4图；5散列与检索；,6排序,；,7索引,；8高级数据结构。,学生对知识点认识,32/34,北京大学信息学院 版权全部，转载或翻印必究 Page 32,学生评定,专业内容游刃有余、知识拓展广,课堂效率高、实例丰富,学生实践机会多,课程增加了知识和能力,动手以及思索能力得到很大锻炼,33/34,北京大学信息学院 版权全部，转载或翻印必究 Page 33,谢谢！,教学案例 vs 案例教学,版权全部，转载或翻印必究 Page 34,