资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,北京大学信息学院,版权所有，转载或翻印必究 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,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
