《大学数据结构的教学方法探讨课件》由会员分享，可在线阅读，更多相关《大学数据结构的教学方法探讨课件（66页珍藏版）》请在金锄头文库上搜索。
1、数据结构教学方法探讨 - 兴趣、实践、研究1大学数据结构的教学方法探讨第一部分（第一部分（20分钟）分钟）lWeiss原版教材简介原版教材简介l教学内容与讲授提示教学内容与讲授提示l辅助教材：辅助教材：Sartaj Sahni 教材教材2大学数据结构的教学方法探讨第二部分（第二部分（40分钟）分钟）l数据结构基础数据结构基础 综合性课程设计的作用综合性课程设计的作用l存在问题及解决思路存在问题及解决思路 l课程设计的课程设计的l内容选择内容选择l实施方法实施方法l激励手段激励手段 l相关文档、辅助教材、配套相关文档、辅助教材、配套MOOC3大学数据结构的教学方法探讨第三部分（第三部分（30分钟
2、）分钟）l研究型教学的探索研究型教学的探索l高级数据结构与算法分析部分高级数据结构与算法分析部分l知识点分割知识点分割l课堂研讨环节设计课堂研讨环节设计l实验环节设计实验环节设计l课程总体评分方法课程总体评分方法4大学数据结构的教学方法探讨第四部分（第四部分（30分钟）分钟）l Programming Ability Test (PAT)l Programming Teaching Assistant (PTA)5大学数据结构的教学方法探讨第一部分（第一部分（20分钟）分钟）lWeiss原版教材简介原版教材简介l教学内容与讲授提示教学内容与讲授提示l辅助教材：辅助教材：Sartaj Sahni
3、 教材教材6大学数据结构的教学方法探讨Weiss原版教材简介原版教材简介lMark Allen Weiss在数据结构与算法分析方面卓有建树，在数据结构与算法分析方面卓有建树，他在此方面的著作尤其畅销，并受到广泛好评。他的他在此方面的著作尤其畅销，并受到广泛好评。他的 Data Structures and Algorithm Analysis 曾被评为曾被评为2020世世纪最佳的纪最佳的3030部计算机著作之一，本书是此书的部计算机著作之一，本书是此书的C语言版。语言版。他在数据结构与算法分析方面的系列著作他在数据结构与算法分析方面的系列著作（Pascal, Ada, C, C+）已被国际上已
4、被国际上500500余所大学用做教材。余所大学用做教材。l普林斯顿大学计算机科学博士，师从普林斯顿大学计算机科学博士，师从Robert Sedgewick。现任美国佛罗里达国际大学现任美国佛罗里达国际大学(FIU)计算机学院教授，曾计算机学院教授，曾获得洲优秀教师奖和校优秀研究奖。获得洲优秀教师奖和校优秀研究奖。7大学数据结构的教学方法探讨Weiss原版教材简介原版教材简介l改编内容改编内容1.1.第第1 1章中的数学基础概念回顾被删除；章中的数学基础概念回顾被删除；2.Hashing（原版第（原版第5章）章）被移到被移到Sorting（原（原版第版第7章）章）之后，并且在介绍之后，并且在介绍
5、hashing 之前之前增加增加 interpolation search 的介绍，以说明的介绍，以说明搜索的时间下限可以如何突破；搜索的时间下限可以如何突破；3.3.第第3.23.2节加入稀疏矩阵表示法（考研内容）节加入稀疏矩阵表示法（考研内容）作为作为multilist的应用例子；的应用例子；8大学数据结构的教学方法探讨Weiss原版教材简介原版教材简介l改编内容改编内容4.4.第第4 4章中关于树的遍历的介绍，原版比较分章中关于树的遍历的介绍，原版比较分散，现集中到第散，现集中到第4.2.34.2.3节，并且增加了二叉节，并且增加了二叉线索树（考研内容）；线索树（考研内容）；5.5.第第
6、6.86.8节增加了节增加了table sort，详细介绍对大结，详细介绍对大结构体进行物理移动排序的方法；构体进行物理移动排序的方法；6.6.第第6 6章增加了对桶排序和基数排序的详细论章增加了对桶排序和基数排序的详细论述（原版只在第述（原版只在第3.23.2节简单举了桶排序作为节简单举了桶排序作为链表的应用例子）。链表的应用例子）。9大学数据结构的教学方法探讨第一部分（第一部分（20分钟）分钟）lWeiss原版教材简介原版教材简介l教学内容与讲授提示教学内容与讲授提示l辅助教材：辅助教材：Sartaj Sahni 教材教材10大学数据结构的教学方法探讨教学内容与讲授提示教学内容与讲授提示知
7、识模块知识模块内容内容学时学时算法复杂度基算法复杂度基本概念本概念1. Algorithm analysis （算法分析）（算法分析）3+1数据结构模块数据结构模块（表、树）（表、树）2. ADT, List, Stack, Queue （抽象数据结构（抽象数据结构概念，表、堆栈、队列的表达和应用）概念，表、堆栈、队列的表达和应用）4+13. Binary Tree, Search Tree, Tree traversals （基本树结构：二叉树、二叉搜索树的（基本树结构：二叉树、二叉搜索树的表达和应用、表达和应用、树的遍历树的遍历）4+24. AVL Tree, Splay tree, B+
8、tree （高级树结（高级树结构：平衡树、伸展树、构：平衡树、伸展树、B+树的表达和应树的表达和应用）用）4+411大学数据结构的教学方法探讨教学内容与讲授提示教学内容与讲授提示知识模块知识模块内容内容学时学时基本算法模基本算法模块（分类、块（分类、查找、排序）查找、排序）5. Binary Heap, Application of priority Queues, d-heaps, Leftist Heap, Skew Heap，Binomial Queue （堆结构：优先队列应用、（堆结构：优先队列应用、d-堆、堆、左斜堆、斜堆、二项式队列左斜堆、斜堆、二项式队列）3+14+26. Ins
9、ertion Sort, Shellsort, Heapsort, Merge Sort, Quick Sort, Table Sort, Bucket Sort（排序算法：插入、希尔、堆排序、归并、（排序算法：插入、希尔、堆排序、归并、快排、表排序、桶排序）快排、表排序、桶排序）4+47. Hash Function, Separate Chaining, Open Addressing, Rehashing （哈希函数、哈希（哈希函数、哈希算法的表达和应用）算法的表达和应用）4+28. Equivalence Relation, Union Algorithm, Path Compress
10、ion （等价关系和算法）（等价关系和算法）2+112大学数据结构的教学方法探讨教学内容与讲授提示教学内容与讲授提示知识模块知识模块内容内容学时学时数据结构模块数据结构模块（图）（图）9. Graph Definitions, Topological Sort, Shortest-path Algorithm, Network Flow Problem, Minimum Spanning Tree, Depth-first Search, NP-completeness （图：拓扑分类、最短路径、网络流、（图：拓扑分类、最短路径、网络流、最小生成树、深度优先搜索、最小生成树、深度优先搜索、NP
11、完全问完全问题题）8+41+2经典算法模块经典算法模块10. Greedy Algorithms, Divide and Conquer, Dynamic Programming, Backtracking Algorithm （经典算法：贪心法、分治法、（经典算法：贪心法、分治法、动态规划法、回溯法）动态规划法、回溯法）7+813大学数据结构的教学方法探讨教学内容与讲授提示教学内容与讲授提示l数据结构基础（数据结构基础（32+1632+16学时）学时）l8 8周周（4 4节理论课节理论课 + 2+ 2节实验课）节实验课）/ /周周l高级数据结构与算法分析（高级数据结构与算法分析（16+161
12、6+16学时）学时）l8 8周周（2 2节理论课节理论课 + 2+ 2节实验课）节实验课）/ /周周14大学数据结构的教学方法探讨教学内容与讲授提示教学内容与讲授提示l难点难点l培养学生数据结构培养学生数据结构应用应用的能力：学生如何用基本数的能力：学生如何用基本数据结构类型来对现实世界问题的非结构化数据进行据结构类型来对现实世界问题的非结构化数据进行有效规划。有效规划。l培养学生进行算法培养学生进行算法选择选择的能力：对现实世界的问题的能力：对现实世界的问题规划之后的算法选择，以及根据算法调整数据结构。规划之后的算法选择，以及根据算法调整数据结构。15大学数据结构的教学方法探讨教学内容与讲授
13、提示教学内容与讲授提示l讲授方法提示讲授方法提示l兴趣兴趣 引子的重要性引子的重要性l乐学乐学 兴趣是最好的老师兴趣是最好的老师l每章第一句话：为什么要学？每章第一句话：为什么要学？l问题驱动，从常识性思考开始问题驱动，从常识性思考开始l每章结尾：解决一个有趣的问题每章结尾：解决一个有趣的问题 使学生清楚每一种数据结构和算法存在的使学生清楚每一种数据结构和算法存在的价值价值16大学数据结构的教学方法探讨教学内容与讲授提示教学内容与讲授提示l讲授方法提示讲授方法提示l贯彻案例教学为主线，注重研讨式、启发式贯彻案例教学为主线，注重研讨式、启发式教学，鼓励学生采取多种不同方案尝试解决教学，鼓励学生采
14、取多种不同方案尝试解决同一问题同一问题l加强综合性实验项目的训练，全面锻炼学生加强综合性实验项目的训练，全面锻炼学生的算法设计与实现能力、测试能力、组织文的算法设计与实现能力、测试能力、组织文档能力、以及团队合作能力档能力、以及团队合作能力17大学数据结构的教学方法探讨第一部分（第一部分（20分钟）分钟）lWeiss原版教材简介原版教材简介l教学内容与讲授提示教学内容与讲授提示l辅助教材：辅助教材：Sartaj Sahni 教材教材18大学数据结构的教学方法探讨辅助教材：辅助教材：Sartaj Sahni 教材教材l浙大教材浙大教材1978-02： Fundamentals of Data S
15、tructures in C (78-92:PASCAL) Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed l数据结构、算法与应用数据结构、算法与应用C+语言描述语言描述 （原书第（原书第2版）版）Sartaj Sahni l800多道练习题和多道练习题和50多个应用实例多个应用实例19大学数据结构的教学方法探讨第二部分（第二部分（40分钟）分钟）l数据结构基础数据结构基础 综合性课程设计的作用综合性课程设计的作用l存在问题及解决思路存在问题及解决思路 l课程设计的课程设计的l内容选择内容选择l实施方法实施方法l激励手段激励手段 l相关文档
16、、辅助教材、配套相关文档、辅助教材、配套MOOC20大学数据结构的教学方法探讨存在问题及解决思路存在问题及解决思路l问题问题 在传统的课程教学中，往往采用在传统的课程教学中，往往采用一般性实验一般性实验作为课程实践的作为课程实践的主要内容，即布置针对本次课堂教学内容的小型练习题，让学生主要内容，即布置针对本次课堂教学内容的小型练习题，让学生独立完成程序设计与实现。这样的实践主要存在两方面问题：独立完成程序设计与实现。这样的实践主要存在两方面问题：l练习题所需要用到的知识点就是课堂教学刚讲授过的内容，学练习题所需要用到的知识点就是课堂教学刚讲授过的内容，学生只要直接拿来用就可以，不需要自己去考虑
17、各种可能的解决生只要直接拿来用就可以，不需要自己去考虑各种可能的解决方案并找到最合适的方法。这种实践是方案并找到最合适的方法。这种实践是验证性验证性的，比较简单直的，比较简单直接，学生受到的锻炼相对较少。接，学生受到的锻炼相对较少。l学生独立完成小型程序，虽然可以在一定程度上锻炼编程能力，学生独立完成小型程序，虽然可以在一定程度上锻炼编程能力，但这个但这个锻炼的层次和涉及面都比较窄锻炼的层次和涉及面都比较窄。现代软件开发的规模，。现代软件开发的规模，使得团队合作在大多数情况下成为必须。而且部分数据结构只使得团队合作在大多数情况下成为必须。而且部分数据结构只有在处理大规模输入的复杂问题时才能体现
18、出优势，编写小型有在处理大规模输入的复杂问题时才能体现出优势，编写小型程序很难使学生真正认识到该数据结构存在的意义。程序很难使学生真正认识到该数据结构存在的意义。21大学数据结构的教学方法探讨存在问题及解决思路存在问题及解决思路l解决解决l课程设计题目覆盖的课程设计题目覆盖的知识点应尽可能避免单一知识点应尽可能避免单一，要采用，要采用启启发式发式的设计思路，引导学生围绕课程设计目标，通过查找的设计思路，引导学生围绕课程设计目标，通过查找与分析有关参考资料，进行探究式的学习，激发创造的意与分析有关参考资料，进行探究式的学习，激发创造的意识和能力。所以，在题目设计和实施中，不应该只是识和能力。所以
19、，在题目设计和实施中，不应该只是“手手把手把手”地教，要给学生留出发挥想像力和创造力的空间；地教，要给学生留出发挥想像力和创造力的空间；l题目的题目的规模应充分大规模应充分大，并且努力使学生对规范性的软件开，并且努力使学生对规范性的软件开发有初步体验，在一定程度上使得学生的工程化能力和团发有初步体验，在一定程度上使得学生的工程化能力和团队合作能力得到锻炼。队合作能力得到锻炼。l而上述两方面的考虑若要取得真正好的效果，还必须有一而上述两方面的考虑若要取得真正好的效果，还必须有一套行之有效的套行之有效的激励机制激励机制，既可以公平地判定每个学生作为，既可以公平地判定每个学生作为个体的能力，又可以鼓
20、励团队精神，同时还可以鼓励学生个体的能力，又可以鼓励团队精神，同时还可以鼓励学生开拓创新思维，主动进行研究性学习。开拓创新思维，主动进行研究性学习。 22大学数据结构的教学方法探讨第二部分（第二部分（40分钟）分钟）l数据结构基础数据结构基础 综合性课程设计的作用综合性课程设计的作用l存在问题及解决思路存在问题及解决思路 l课程设计的课程设计的l内容选择内容选择l实施方法实施方法l激励手段激励手段 l相关文档、辅助教材、配套相关文档、辅助教材、配套MOOC23大学数据结构的教学方法探讨课程设计的内容选择课程设计的内容选择l题目应避免涉及单一知识点；题目应避免涉及单一知识点；l为锻炼学生进行研究
21、性学习的能力，可设为锻炼学生进行研究性学习的能力，可设计算法效率分析比较类型的题目；计算法效率分析比较类型的题目；l采用启发式教学思路，设计有多种解法的采用启发式教学思路，设计有多种解法的题目，可以给学生留出发挥想像力和创造题目，可以给学生留出发挥想像力和创造力的空间，锻炼学生灵活运用知识分析问力的空间，锻炼学生灵活运用知识分析问题和解决问题的能力。题和解决问题的能力。24大学数据结构的教学方法探讨课程设计的内容选择课程设计的内容选择l题目集（题目集（1 1）lPerformance Measurement (Print integers)lThe Worlds Richest People
22、（各种排序的组合）（各种排序的组合）lHashing （拓扑排序、哈希映射）（拓扑排序、哈希映射）lBonus: Waiting in Line （队列模拟）（队列模拟）lBonus: Attack of Panda （3种解，并查集最佳）种解，并查集最佳）25大学数据结构的教学方法探讨课程设计的内容选择课程设计的内容选择l题目集（题目集（2 2）lPerformance Measurement (MAXIMUM SUBMATRIX SUM )lBinary Search Tree （不同输入顺序）（不同输入顺序）lAttack of Panda （3种解，并查集最佳）种解，并查集最佳）lBo
23、nus: Sort Poems （大数据结构排序）（大数据结构排序）lBonus: Universal Travel Sites （网络流、哈希）（网络流、哈希）26大学数据结构的教学方法探讨课程设计的内容选择课程设计的内容选择l题目集（题目集（3 3）lPerformance Measurement (XN )lHarry Potters Exam （最短路径应用）（最短路径应用）lSort Poems （大数据结构排序）（大数据结构排序） lBonus: Lineal Tree （树的建立与遍历）（树的建立与遍历）lBonus: Utopia （求树结点的最低公共祖先）（求树结点的最低公共
24、祖先）27大学数据结构的教学方法探讨课程设计的内容选择课程设计的内容选择l题目集（题目集（4 4）lPerformance Measurement (search )lCounting Leaves （树的建立与遍历）（树的建立与遍历）lBattle Over Cities （连通集、关节点、最小生成树）（连通集、关节点、最小生成树）lBonus: Binary Search Tree （不同输入顺序）（不同输入顺序）lBonus: Hashing （拓扑排序、哈希映射）（拓扑排序、哈希映射）28大学数据结构的教学方法探讨课程设计的实施方法课程设计的实施方法l将学生分成三人小组，分工负责程序编
25、写、测试以将学生分成三人小组，分工负责程序编写、测试以及实验报告撰写工作；及实验报告撰写工作；l一份完整的实验报告至少应包含以下四部分内容：一份完整的实验报告至少应包含以下四部分内容：l（一）实验内容简介（一）实验内容简介l（二）算法说明（二）算法说明l（三）测试结果（三）测试结果l（四）分析与探讨（四）分析与探讨l附录：源代码附录：源代码l独立性声明独立性声明29大学数据结构的教学方法探讨课程设计的激励手段课程设计的激励手段l程序员、测试员、文档员的工作难度不同，其工作的分数程序员、测试员、文档员的工作难度不同，其工作的分数分配也应不同。例如我们采用分配也应不同。例如我们采用50:30:20
26、50:30:20的分配制度，这样的分配制度，这样只有在三个课程设计中将三种角色分别体验一遍，才有可只有在三个课程设计中将三种角色分别体验一遍，才有可能得到满分能得到满分100100；l应对应对“分析与探讨分析与探讨”部分特别关注，及时发现并鼓励学生部分特别关注，及时发现并鼓励学生的创新思维；的创新思维；l由于每个学生的能力水平不同，应使组内每个人的成绩相由于每个学生的能力水平不同，应使组内每个人的成绩相对独立，不依赖于其他组员的表现而得分；对独立，不依赖于其他组员的表现而得分；l只有三项工作都完美的组，才会获得特别表扬（红人榜）。只有三项工作都完美的组，才会获得特别表扬（红人榜）。这时学生会在
27、完成了自己工作的情况下，对队友提供一定这时学生会在完成了自己工作的情况下，对队友提供一定帮助，以获得团队的荣誉。帮助，以获得团队的荣誉。 30大学数据结构的教学方法探讨第二部分（第二部分（40分钟）分钟）l数据结构基础数据结构基础 综合性课程设计的作用综合性课程设计的作用l存在问题及解决思路存在问题及解决思路 l课程设计的课程设计的l内容选择内容选择l实施方法实施方法l激励手段激励手段 l相关文档、辅助教材、配套相关文档、辅助教材、配套MOOC31大学数据结构的教学方法探讨相关文档及辅助教材相关文档及辅助教材l实验报告要求实验报告要求；学生报告样例学生报告样例l对一本院校推荐辅助教材：对一本院
28、校推荐辅助教材：何钦铭、冯雁、陈越，何钦铭、冯雁、陈越，数据结构课程设计数据结构课程设计l8 8个案例详解：个案例详解：表达式求值（栈）、文件目录结构显示表达式求值（栈）、文件目录结构显示（树遍历）、拯救（树遍历）、拯救007007（最短路）、迷宫（最短路）、迷宫（DFS, BFSDFS, BFS）、）、快速排序分析、插队买票（快速排序分析、插队买票（hash+hash+队列）、搜索算法分析、队列）、搜索算法分析、任务调度（贪心）任务调度（贪心）l8 8个案例习题：个案例习题：搜索树分析、检查网络（并查集）、宇搜索树分析、检查网络（并查集）、宇宙旅行（网络流）、室内布线（最小生成树）、最小套圈
29、宙旅行（网络流）、室内布线（最小生成树）、最小套圈（分治）、商店购物（动态规划）、熊猫烧香（多解）、（分治）、商店购物（动态规划）、熊猫烧香（多解）、神秘国度的爱情故事（自己推导解法）神秘国度的爱情故事（自己推导解法）l光盘光盘32大学数据结构的教学方法探讨相关文档及辅助教材相关文档及辅助教材l教材：教材：数据结构数据结构l定位：定位：面向二、三本学生面向二、三本学生l问题驱动：每章以问题开篇、以实际案例结束，由问题驱动：每章以问题开篇、以实际案例结束，由浅渐深，提供丰富的应用案例及解决方案浅渐深，提供丰富的应用案例及解决方案l例例1 1：银行排队问题：银行排队问题 单窗口单窗口-多窗口单队列
30、多窗口单队列-带带VIPVIP窗口的单队列窗口的单队列-多窗口多队列多窗口多队列-带夹塞的队带夹塞的队列列l例例2 2：畅通工程问题：畅通工程问题 修多少条路能畅通修多少条路能畅通 -最低最低成本问题成本问题-局部最低成本问题局部最低成本问题33大学数据结构的教学方法探讨相关文档及辅助教材相关文档及辅助教材l教材：实验辅助教材教材：实验辅助教材数据结构学习数据结构学习与实验指导与实验指导l设计了设计了2727道实验案例，每题给出详细的测试数据、道实验案例，每题给出详细的测试数据、解答和源代码，帮助读者从实际应用的角度更好地解答和源代码，帮助读者从实际应用的角度更好地理解知识点理解知识点 l设计
31、了设计了3838道实验项目，大部分是实验案例的延伸和道实验项目，大部分是实验案例的延伸和提高，可以在实验案例已经提供的解答程序基础上提高，可以在实验案例已经提供的解答程序基础上完成。每题给出详细的测试数据和解题提示完成。每题给出详细的测试数据和解题提示34大学数据结构的教学方法探讨配套配套MOOC课程课程l2014年年12月月1日日“中中国大学国大学MOOC”上线上线 33000+l2015年年3月月1日日“云课云课堂堂”上线上线 20000+l2015年年9月月1日日“中国中国大学大学MOOC”即将再次即将再次上线上线按照自己的初衷使用教按照自己的初衷使用教材，为教材用户提供材，为教材用户提
32、供实实际教学全过程际教学全过程的参考的参考35大学数据结构的教学方法探讨第三部分（第三部分（30分钟）分钟）l研究型教学的探索研究型教学的探索l高级数据结构与算法分析部分高级数据结构与算法分析部分l知识点分割知识点分割l课堂研讨环节设计课堂研讨环节设计l实验环节设计实验环节设计l课程总体评分方法课程总体评分方法36大学数据结构的教学方法探讨研究型教学的探索研究型教学的探索l存在问题存在问题l科学研究的一般方法科学研究的一般方法l研究型课程教学模式研究型课程教学模式l学生收获学生收获l浙江大学计算机学院浙江大学计算机学院“精研课程精研课程”37大学数据结构的教学方法探讨研究型教学的探索研究型教学
33、的探索l存在问题存在问题以以知识的传授为为核核心心，重重点点关关注注教教师师讲了什么关关注注学学生生应该学什么关关心心学学生生究究竟竟学到了什么针针对对探探索索和和批批判判这这两两个个关关键键因因素素，培培养养学学生生主主动动获获取取知知识识、进进一一步步综综合合已已有有的的知知识识去去创创造造新新知知识识的的能能力力关注点基本上局限于关注点基本上局限于知识点本身，教学过程中便不可避本身，教学过程中便不可避免地存在着免地存在着灌输的痕迹的痕迹38大学数据结构的教学方法探讨研究型教学的探索研究型教学的探索l科学研究的一般方法科学研究的一般方法1.提出问题提出问题2.回顾已经存在的解决方案回顾已经
34、存在的解决方案3.发现现有方法的不足发现现有方法的不足4.设计更有效的方法设计更有效的方法5.验证有效性验证有效性39大学数据结构的教学方法探讨研究型教学的探索研究型教学的探索l研究型课程教学模式研究型课程教学模式1.为什么我们需要知道？引出要解决的问题。为什么我们需要知道？引出要解决的问题。2.我们学过的知识能否解决这个问题？回顾知我们学过的知识能否解决这个问题？回顾知识点，分析长短。识点，分析长短。3.什么是当前的瓶颈？什么是当前的瓶颈？4.我们该怎么办？我们该怎么办？5.验证一下：真的像书上声称得那么好吗？验证一下：真的像书上声称得那么好吗？不断提问、提问、再提问不断提问、提问、再提问4
35、0大学数据结构的教学方法探讨研究型教学的探索研究型教学的探索l学生收获学生收获l知识：什么叫知识：什么叫“做研究做研究”？有什么基本套路？有什么基本套路？l能力：查找资料，质疑，发现缺陷，解决问能力：查找资料，质疑，发现缺陷，解决问题，撰写报告、演讲。题，撰写报告、演讲。l素质：科学严谨的态度，创新意识的萌芽。素质：科学严谨的态度，创新意识的萌芽。41大学数据结构的教学方法探讨研究型教学的探索研究型教学的探索l浙江大学计算机学院浙江大学计算机学院“精研课程精研课程”l教学内容：教学内容：体现体现“精、深、通精、深、通”的内容设计原则。立项偏重于的内容设计原则。立项偏重于大三开设的专业方向性研究
36、型选修课，少量优秀的研究型专业大三开设的专业方向性研究型选修课，少量优秀的研究型专业基础课也适当考虑。基础课也适当考虑。教学大纲中设计有研究探索性主题。教学大纲中设计有研究探索性主题。l教学方法：教学方法：与传统方法中与传统方法中“满堂灌满堂灌”和只重考试结果的弊端相和只重考试结果的弊端相对应，精研课程的教学应体现三个重点：对应，精研课程的教学应体现三个重点：重对主动探索的引导；重对主动探索的引导；重对学习过程的指导；重课堂内外的互动。重对学习过程的指导；重课堂内外的互动。l考核方法：考核方法：设置多环节过程考核，全面评价学生能力，期末考设置多环节过程考核，全面评价学生能力，期末考试占总评的比
37、例一般不超过试占总评的比例一般不超过50%50%。特别。特别有具体措施鼓励学生到有具体措施鼓励学生到课并积极参与讨论课并积极参与讨论（例如：设计课堂报告、主动提问、抢答、（例如：设计课堂报告、主动提问、抢答、讨论、测验等环节的得分占总评的讨论、测验等环节的得分占总评的30%30%或更高）。或更高）。l教学规模：教学规模：精研课程原则上要求精研课程原则上要求每班规模为每班规模为10-5010-50人人，若有分，若有分组考核的项目，则每组规模原则上不超过组考核的项目，则每组规模原则上不超过3 3人。人。42大学数据结构的教学方法探讨第三部分（第三部分（30分钟）分钟）l研究型教学的探索研究型教学的
38、探索l高级数据结构与算法分析部分高级数据结构与算法分析部分l知识点分割知识点分割l课堂研讨环节设计课堂研讨环节设计l实验环节设计实验环节设计l课程总体评分方法课程总体评分方法43大学数据结构的教学方法探讨知识点分割知识点分割知识点知识点必须由必须由教师讲教师讲可以由可以由学生讲学生讲 高级数据结构与算法高级数据结构与算法是是数据结构基础数据结构基础的后续课程，主要包括的后续课程，主要包括“排序树排序树”、“优先队优先队列列”、“NP问题问题”、“经典算法经典算法”四部分内容。四部分内容。44大学数据结构的教学方法探讨知识点分割知识点分割知知识模模块课堂内容堂内容课时安排安排课外研究内容外研究内
39、容排序排序树AVL Tree, Splay Tree, B+ Tree, Inverted 4+42-d tree, B-tree, Trie优先先队列列Leftist Heap, Skew Heap,Binomial Queue4+2Fibonacci Heaps,Amortized AnalysisNP问题NP-Completeness1+2Karps 21 NP-complete problems经典算法典算法Greedy Algorithm;Divide and Conquer;Backtracking;Dynamic Programming7+8Applications45大学数据结
40、构的教学方法探讨课堂研讨环节设计课堂研讨环节设计l比较难的比较难的1414个问题由学生在课堂上分组讨个问题由学生在课堂上分组讨论，论，5-105-10分钟后提交答案并记分；分钟后提交答案并记分；l比较简单的问题（一般是引导性问题）由比较简单的问题（一般是引导性问题）由学生独立抢答，每次回答或者主动提问均学生独立抢答，每次回答或者主动提问均记入课堂讨论得分。记入课堂讨论得分。l目的在于敦促学生做好课前预习，鼓励学目的在于敦促学生做好课前预习，鼓励学生参与教学的积极性，活跃课堂气氛。生参与教学的积极性，活跃课堂气氛。46大学数据结构的教学方法探讨实验环节设计实验环节设计l除了布置小型作业外，还将除
41、了布置小型作业外，还将“课外研究内容课外研究内容”设计成设计成5 5道研究型大作业，由学生分组完成。每道研究型大作业，由学生分组完成。每次次3 3组必做（于是每班分组必做（于是每班分1515组），其他组选做；组），其他组选做；l学生需要根据题目要求，自行查找资料、归纳学生需要根据题目要求，自行查找资料、归纳总结知识点、动手做实验进行验证等，最后提总结知识点、动手做实验进行验证等，最后提交一份研究报告，并在交一份研究报告，并在2 2周后的课堂上做周后的课堂上做10-1510-15分钟的汇报演讲；分钟的汇报演讲；l每组进行课堂演讲的人选由教师在现场抽签决每组进行课堂演讲的人选由教师在现场抽签决定，
42、该演讲人的得分即为全组演讲得分，不参定，该演讲人的得分即为全组演讲得分，不参加抽签者得加抽签者得0 0分；分；47大学数据结构的教学方法探讨实验环节设计实验环节设计l必做组满分为必做组满分为2020（report） + 3+ 3（PPT）+ 7+ 7（报告）；选做组得分为（报告）；选做组得分为report/10/10，作为，作为Bonus（于是总评最高加分（于是总评最高加分8 8。但即使总评超出。但即使总评超出100100分的学生，只要任何一项考察项得分不完美，分的学生，只要任何一项考察项得分不完美，总评都是总评都是9999封顶）。封顶）。l目的在于引导学生产生做科学研究的兴趣，充目的在于引导
43、学生产生做科学研究的兴趣，充分锻炼学生自主学习与钻研的能力、撰写科学分锻炼学生自主学习与钻研的能力、撰写科学研究报告的能力、口头表达能力、以及团队合研究报告的能力、口头表达能力、以及团队合作与沟通能力等。作与沟通能力等。48大学数据结构的教学方法探讨课程总体评分方法课程总体评分方法Research Project(30)Discussions(14)Homework(5)Q&A(0.5 each)Total 50Final Exam (50)讲讲1做做2考考349大学数据结构的教学方法探讨第四部分（第四部分（30分钟）分钟）l Programming Ability Test (PAT)l P
44、rogramming Teaching Assistant (PTA)50大学数据结构的教学方法探讨l标准化编程能力测试：效果检验标准化编程能力测试：效果检验 Programming Ability Test 2011年年8月创立月创立IT业的业的TOEFLProgramming Ability Test (PAT)5151大学数据结构的教学方法探讨PAT初衷初衷l学生学习缺少动力学生学习缺少动力l大中型企业招聘条件中歧视性潜规则：大中型企业招聘条件中歧视性潜规则：非非985、211不看不看5252大学数据结构的教学方法探讨PAT初衷初衷l教学缺少实践环节教学缺少实践环节l应付计算机等级考试：
45、纸上谈兵应付计算机等级考试：纸上谈兵l后果：后果：l考研复试考研复试A+B测试题，测试题，30分钟有数十人分钟有数十人0分，分，部分无法通过编译部分无法通过编译l标准化上机考试标准化上机考试3小时数十人小时数十人0分，部分考生无分，部分考生无1题能通过编译题能通过编译l中小企业新员工培训，要从基础编程能力开始中小企业新员工培训，要从基础编程能力开始5353大学数据结构的教学方法探讨Programming Ability Test (PAT)l标准化编程能力测试：公平的就业机会标准化编程能力测试：公平的就业机会l联盟企业：联盟企业：91家家 划定免笔试划定免笔试分数线分数线，收到数据包后会收到数
46、据包后会主动联系主动联系考生考生 Google中国中国 Microsoft 华为华为 雅虎雅虎 网易雷火游戏部网易雷火游戏部 百度百度 腾讯腾讯 网易有道网易有道 道富科技道富科技 北京小米科技北京小米科技 大众点评大众点评 摩根士丹利摩根士丹利 上海微创软件有限公司上海微创软件有限公司 杭州华三通信技术有限公司杭州华三通信技术有限公司 甲骨文亚洲研发中心甲骨文亚洲研发中心 华硕科技华硕科技 阿里巴巴阿里巴巴-B2B技术部技术部/百年技术大学百年技术大学 淘宝（中国）淘宝（中国） eBay中国研发中心中国研发中心 诺基亚西门子诺基亚西门子 奇虎奇虎360 5454大学数据结构的教学方法探讨Pr
47、ogramming Ability Test (PAT)lGoogle: 甲级前甲级前15名、顶级前名、顶级前20名且名且80分以上，分以上，2年有效，可以年有效，可以免除笔试，直接进入面试阶段免除笔试，直接进入面试阶段l证书证书2年内有效，年内有效，T-50、A-80、B-100，优先面试，优先面试l证书证书2年内有效，年内有效，T-20、A-50、B-80，可免笔试并优先录取，可免笔试并优先录取l甲级成绩甲级成绩70分乙级分乙级90分可以免除笔试直接进入面试分可以免除笔试直接进入面试l甲级甲级60分、乙级分、乙级80分，直接面试分，直接面试l本科生乙级本科生乙级60分以上、硕士生甲级分以上
48、、硕士生甲级60分以上，可免除笔试分以上，可免除笔试l乙级乙级80分及以上，可获得实习和工作机会分及以上，可获得实习和工作机会l有有PAT证书就免笔试证书就免笔试l55大学数据结构的教学方法探讨没有所谓的没有所谓的985、211门槛！门槛！一次考试相当于通过一次考试相当于通过N家公司的笔试！家公司的笔试！56Programming Ability Test (PAT)56大学数据结构的教学方法探讨Programming Ability Test (PAT)l2014年年4月月10日：浙江大学研究生院正式批准日：浙江大学研究生院正式批准了计算机学院与软件学院了计算机学院与软件学院关于研究生复试中
49、关于研究生复试中上机考试改革的申请报告上机考试改革的申请报告，同意自，同意自2015年硕年硕士研究生招生启动相关改革，士研究生招生启动相关改革，以以PAT（甲级）（甲级）一年内的成绩作为上机复试成绩一年内的成绩作为上机复试成绩 今年浙今年浙大计算机大计算机+软件复试软件复试228人，有人，有63人提交了人提交了PAT(A)的证书，直接进入面试的证书，直接进入面试l中国大学中国大学MOOC: 凭凭PAT成绩获取优秀证书成绩获取优秀证书5757大学数据结构的教学方法探讨PAT的影响力的影响力l联盟院校联盟院校30所，覆盖所，覆盖18省省/直辖市，直辖市，25城市，提城市，提供供8000多座多座位位
50、l考生来源国考生来源国内外内外360余校余校及部分在职及部分在职全国高等学校教学研究中心全国高等学校教学研究中心合合 作作 运运 营营58大学数据结构的教学方法探讨PAT考试系统考试系统（http:/ ）l特点特点l与各个与各个OJ相比，更注重系统安全性相比，更注重系统安全性l支持万人级别并发支持万人级别并发l题库偏基础入门，结合课程或教材的题库有知识点题库偏基础入门，结合课程或教材的题库有知识点分类分类l分分case计分，题目难度由题目分数体现计分，题目难度由题目分数体现l缺点缺点l可支持的题目类型单一可支持的题目类型单一l为安全性牺牲了教师用户的使用方便性为安全性牺牲了教师用户的使用方便性
51、l l适合：正式编程类考试适合：正式编程类考试适合：正式编程类考试适合：正式编程类考试5959大学数据结构的教学方法探讨第四部分（第四部分（30分钟）分钟）l Programming Ability Test (PAT)l Programming Teaching Assistant (PTA)60大学数据结构的教学方法探讨Programming Teaching Assistant (PTA)6161大学数据结构的教学方法探讨Programming Teaching Assistant (PTA)l支持支持5种题目类型：编程、函数填空、程序填种题目类型：编程、函数填空、程序填空、选择、判断空
52、、选择、判断l教师可自由建设题库、练习集、考试，教师可自由建设题库、练习集、考试，并与并与所有用户共享所有用户共享l题目作者可根据自己创建题目被他人引用的题目作者可根据自己创建题目被他人引用的数量，数量，获得报酬获得报酬l以学校或企业为单位租用系统服务以学校或企业为单位租用系统服务l同时支撑高等教育出版社计算机类教材的附同时支撑高等教育出版社计算机类教材的附加资源加资源6262大学数据结构的教学方法探讨6363大学数据结构的教学方法探讨64大学数据结构的教学方法探讨计划上线时间：计划上线时间：2015年年8月月支持课程支持课程5门：门：C程序设计、程序设计、C+程序设计、程序设计、Java程序设计、程序设计、数据结构与算法、数值分析数据结构与算法、数值分析判断判断100+题、选择题、选择200+题、程序填空题、程序填空10+题、函数题、函数60+题、编程题、编程400+题题目前有目前有11所高校老师注册试用所高校老师注册试用（秋学期开学正式可用，第一学期（秋学期开学正式可用，第一学期免费免费试用）试用）65大学数据结构的教学方法探讨66大学数据结构的教学方法探讨
