数据结构教学大纲2017年春季.docVIP

数据结构 课程教学大纲 课程基本信息（Course Information） 课程代码 （ *学时 （Credit） *学分 （Credits） *课程名称 （ （中文）数据结构 （英文）Data Structure *课程性质 （Course Type） 专业基础课 授课对象 （Target Audience） 计算机科学班 *授课语言 (Language of Instruction) 中文 *开课院系 （School） 电信学院计算机系 先修课程 （Prerequisite） 程序设计 授课教师 （Instructor） 翁惠玉 课程网址 (Course Webpage) *课程简介（Description） 本课程以数据的逻辑结构为基础，按照线性关系、树状关系、集合关系和图状关系全面介绍了的数据结构的基本内容和实现思想。主要内容包括：线性表、栈、队列和优先级队列、二叉树、散列表、排序/查找算法和图，以及它们的C++实现。对每种数据结构，都介绍了一些它们的主要应用，以帮助学生理解为什么要学数据结构以及数据结构对计算学科的重要性。 *课程简介（Description） This course is organized on the logical structures of data, and introduces the basic concepts of data structure and their implementations according to the relation of linear, tree, set and graph. Main topics include list, stack, queue and priority queue, binary tree, hash table, sort/search algorithms and graph. Their implementations in C++ will also be covered. In order to help students understand why should study data structures and how important of this course, some applications of main data structures are introduced. 课程教学大纲（course syllabus） *学习目标(Learning Outcomes) 熟练掌握各种数据结构的特点、实现方法及应用场合。 掌握类封装技术，能将数据结构封装成类。 掌握算法分析的基本知识，能分析算法的时空效率。 了解通用算法的设计思想，能设计解决简单问题的算法 *教学内容、进度安排及要求 (Class Schedule Requirements) 教学内容 学时 教学方式 作业及要求 基本要求 考查方式 绪论 4 课堂教学 了解数据结构课程的基本内容，掌握时空复杂度的概念 线性表 3 课堂教学 熟练掌握线性表的顺序实现及链接实现 栈 4 课堂教学 熟练掌握栈的顺序实现及链接实现，掌握栈的主要应用的实现 队列 2 课堂教学 熟练掌握队列的顺序实现及链接实现，掌握队列的主要应用的实现 树和二叉树 5 课堂教学 熟练掌握二叉树及基于二叉链表的树的实现，了解树的主要应用 哈夫曼树 2 课堂教学 掌握哈夫曼算法即实现，了解哈弗曼算法的应用 优先级队列 2 课堂教学 熟练掌握二叉堆的操作，掌握如何用二叉堆构建优先级队列 集合与静态查找 1 课堂教学 掌握集合的概念，熟练掌握顺序查找和二分查找 查找树 6 课堂教学 熟练掌握二叉查找树的实现，掌握AVL树的实现，了解红黑树、AA树和伸展树 哈希表 2 课堂教学 了解哈希发的基本思想，熟练掌握基于线性探测法的闭散列表以及开散列表的实现 B+树 2 课堂教学 了解外存储器的访问以及B+树的 排序 3 课堂教学 熟练掌握常用的内排序算法，了解外排序的过程 图的基本概念 2 课堂教学 掌握土的基本概念，熟练掌握邻接矩阵和邻接表的存储 图的遍历 2 课堂教学 熟练掌握DFS和BFS，了解遍历的应用 拓扑排序及关键路径 2 课堂教学 掌握拓扑排序和关键路径算法即实现，了解他们的应用 最小生成树 2 课堂教学 熟练掌握Prim算法和Kruskal算法的思想及实现 最短路径 2 课堂教学 熟练掌握Dijkstra算法和Floyed算法 通用算法 2 课堂教学 了解枚举法、贪婪法、回溯法、分治法和动态规划的基本思想及应用，掌握这些算法的经典的实例 *考核方式 (Gra