数据结构与算法教学大纲

《数据结构与算法教学大纲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中山大学信息科学与技术学院计算机科学系《《《数据结构与算法》》》课程教学大纲》课程教学大纲课程名称：数据结构类别：专业必修课授课对象：本科生总学时：54学时+36学时实验适用专业：计算机科学与技术/网络工程/开课学期：第四学期信息安全编写人员：蔡国扬，高集荣，审核人员：王若梅编写日期：2006年2月乔海燕修订人员：审核人员：修订日期：一、教学目的数据结构与算法是计算机科学教育中的一门核心课程。数据结构与算法主要讨论在应用计算机解决问题时，如何有效地组织数据、表示数据和处理数据，以及如何设计正确的算法和评价算法的效率。课程介绍常见的数据结构及其应用，常用的数据处理技术和算法，以及算法效率估算

2、的基本技术。通过本课程的学习，学生应该掌握常用的数据结构，掌握合理地组织数据结构和表示数据的方法，掌握有效地处理数据的方法，掌握评价算法性能的基本方法。通过本课程的训练，进一步提高学生的数据抽象能力；提高学生设计高质量程序的能力。本课程也为学生学习操作系统、编译原理和数据库等后续课程奠定基础。二、教学内容选择原则数据结构与算法主要包括下列内容：1．常用数据结构的ADT及其实现，包括栈、队列、向量和串，二叉树，树和图等；2．常用检索、索引和排序方法，包括线性表、散列表、倒排文件、B树等常见的检索和索引技术，插入排序、Shell排序、堆排序、快速排序、基数排序等常用的各种排序算法及其时间和空间

3、开销；3．常用解决问题策略，包括分治法（Divideandconquer），递归(Recursion)，回溯(Backtracking)，贪心法(Greedy)等。以上内容也是数据结构的经典内容，是多数数据结构教材的核心内容。第六部分所列的参考教材都不失为较好的选择。其中有些教材在讲解算法时使用了伪代码，以使学生专注于结构与算法本身的掌握，而不会淹没于特定语言实现的复杂细节中，如推荐教材1；有的教材使用了C++代码，其优点是使学生进一步掌握了现代程序设计思想，如C++的数据封装，多态和继承等，如推荐教材5。有的教材使用了较新的数据组织概念，如推荐教材3使用了STL（StandardTemp

4、lateLibrary）的Container和Iterator等概念。推荐教材5是英文教材。学生在开始阅读英文教材时可能会感到有些不适，如生词较多，阅读速度慢，理解不深等。阅读英文教材需要有一个过程，教师应该给学生以充分的鼓励。经过两三周时间，多数学生会适应使用英文教材。三、教学基本要求数据结构与算法的讲授应该注重理论和实践相结合。理论课程每周三学时，实验课每周两学时。理论课程以讲授为主，鼓励课堂讨论,建议采用多媒体教学方式。根据每章内容，建议每周布置一定量的书面作业，使学生更好地掌握课程中讲授的基本概念和基本方法。书面作业不要求上机操作。实践课程以学生在实验室完成上机作业为主。上机作业分

5、两部分：基本部分要求学生能够自己动手完成基本数据结构的实现，要求在实验课上完成；综合部分训练学生综合应用所学知识的能力，根据课程内容，由六至七个较大的实验构成，可以在课后完成。综合实验由2-3个人构成的小组协作完成，并通过协作训练学生的交流与合作意识。实验内容强调培养学生动手解决实际问题能力，并培养学生养成良好的编程习惯，如代码的可读性，完整性，健壮性，实用性和正确性等。其中基本数据结构的实现，如棧和队列，查找和排序等的实现，可以要求学生通过与STL相应数据结构的比较编写自动随机测试程序，检查自己的实现是否存在错误。同时，在讲常用解数据结构和算法时，应该结合STL的相应部分，使学生学会使用

6、已有的数据结构与算法。四、先修课程与后续课程1、先修课程：本课程的先修课程包括：(1).程序设计(2).离散数学2、后续课程：本课程的后续课程包括：(1).操作系统(2).编译原理等。五、教学内容与学时分配1、绪论（4学时）1.1数据结构的概念从解决实际问题过程中组织数据，存储数据和实现数据上的操作出发，介绍数据的逻辑结构，存储结构和数据上的操作等概念。1.2抽象数据类型介绍数据类型和抽象数据类型的概念，以及抽象数据类型的表示和实现。1.3算法与算法分析介绍算法的概念和算法的基本特性；介绍算法设计的基本要求；引入算法的时间复杂度和空间复杂度的概念，平均时间复杂度和最坏情况复杂度，复杂度的大

7、O和大Θ表示法；介绍估算复杂度的基本方法。2、栈、队列和线性表及其应用（6学时）2.1栈的ADT定义，栈的连续实现和链表实现，栈的应用举例2.2队列的ADT定义，队列的连续实现和链表实现，队列应用举例2.3线性表的ADT定义，线性表的连续实现和链表实现，连续实现与链表实现特点之比较本章介绍常用的数据结构ADT及其不同的实现方法。通过这部分的学习，学生应该基本掌握ADT的概念及其ADT的实现方法，理解从实际问题到ADT定义