《数据结构与算法》课程教学大纲

1、数据结构与算法课程教学大纲课程编码： SC03100110课程名称：数据结构与算法课程英文名称：Data Structures and Algorithms总学时：48 讲课学时：40 实验学时：8 课外辅导学时：40学分：3.5开课单位：计算机科学与技术学院授课对象：计算机科学与技术、信息安全、生物信息技术及相关专业开课学期：2秋先修课程：集合论与图论，高级语言程序设计课外学时：80主要教材及参考书：教材：廖明宏,郭福顺,张岩,李秀坤.数据结构与算法(第4版).高等教出版社.2007.主要参考书：1.严蔚敏,吴伟民. 数据结构(C语言版). 清华大学出版社.2011. 2.Ellis Hor

2、awitz,Sartaj Sahni,Susan Anderson-Freed著,李建中,张岩,李治军译.Fundamentals of Data Structures in C.机械工业出版社.2006.3. HYPERLINK /s/?key1=%a3%a8%c3%c0%a3%a9Sartaj+Sahni t _blank Sartaj Sahni著, HYPERLINK /s/?key1=%cd%f4%ca%ab%c1%d6+%cb%ef%cf%fe%b6%ab&zyandor=and t _blank 汪诗林,孙晓东. HYPERLINK /exec/obidos/tg/detail/

3、-/0929306325/qid=1105684999/sr=1-1/ref=sr_1_1/102-6921192-4712132?v=glance&s=books t _blank Data Structures,Algorithms,and Applications in C+.机械工业出版社.2006.4.李秀坤,张岩,李治军,娄久.数据结构与算法实验教程.高等教育出版社.2009.一、课程教学目的通过本课程的学习，学生将基本掌握数据结构和算法基础知识、设计与分析的技术和方法，提高程序设计的质量；能够根据所求问题的性质，选择合理的数据结构，并对时间复杂性进行必要的控制。培养运用数据结构表

4、示实际问题并设计有效算法解决实际问题的能力。为后续课程的学习和将来从事的研究工作打下扎实的基础。二、教学内容及基本要求以抽象数据型为基础，讲授数据的各种逻辑结构、在计算机中的存储结构、对数据进行的插入、查找、删除、排序、遍历等操作（运算）和这些操作（运算）在存储结构上具体实现的算法。课程的重点是基本数据结构的不同存储结构以及操作算法的实现。课程的难点是基本数据结构的不同存储结构以及操作算法的实现、算法的性能分析以及数据结构与算法的应用。分章节描述教学内容和教学基本要求。 第1章 绪论（3学时）教学内容：课程的基本概念和术语；课程的研究对象；抽象数据类型；算法的描述和简单的分析方法。教学要求：（

5、1）了解数据结构的基本概念、研究对象以及数据结构课程的发展历史，对数据结构与算法课程有一个宏观的认识；（2）掌握贯穿全书的重要概念-抽象数据型，包括其概念的定义和实现方法，初步掌握抽象技术方法；（3）了解算法、算法复杂性，掌握算法性能的评价方法；（4）了解解决问题的一般过程和算法的逐步求精方法，掌握问题求解的基本过程和方法。第2章 线性表（9学时）2.1 一般线性表（4学时）教学内容：线性表的逻辑结构、各种存储结构、基本操作（算法）的实现及性能分析、不同存储结构的比较、线性表的应用等。教学要求：（1）掌握线性表的逻辑结构，线性表的顺序存储结构和链式存储结构的描述方法；（2）熟练掌握线性表在顺序

6、存储结构和链式存储结构的结构特点以及相关的查找、插入、删除等基本操作的实现；（3）能够从时间和空间复杂性的角度综合比较两种存储结构的不同特点；（4）能够利用线性表解决实际应用问题。2.2 栈与队列（3学时）教学内容：栈和队列的逻辑结构、存储结构以及基本操作的实现；栈和队列的应用。教学要求：（1）掌握栈和队列的结构特性和描述方法；（2）熟练掌握栈和队列的基本操作的实现；（3）能够利用栈和队列解决实际应用问题。2.3 字符串、多维数组和广义表（2学时）教学内容：字符串的逻辑结构、存储方法和字符串匹配算法，多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏短阵的压缩存储方法及广义表的概念和性质。教学

7、要求：（1）掌握串的结构特性以及串的基本操作，掌握针对字符串进行操作的常用算法和模式匹配算法；（2）掌握多维数组的存储和表示方法；（3）掌握对特殊矩阵进行压缩存储时的下标变换公式；（4）了解稀疏矩阵的压缩存储表示方法及适用范围；（5）了解广义表的概念和特征。第3章 树（10学时）教学内容：二叉树的定义、性质、存储结构、遍历、线索化；树的定义、存储结构、遍历；树和森林与二叉树的转换；树（森林）与二叉树的应用（哈夫曼树及其应用、集合表示与等价分类、表达式求值）。教学要求：（1）了解树型结构结点之间的层次关系；（2）掌握树和二叉树的定义及其相关的术语；（3）重点掌握二叉树的结构、性质，存储表示和四种

8、遍历算法；（4）掌握二叉树线索化的实质及线索化的过程；（5）了解树的结构性质、存储表示方法和遍历算法；（6）掌握森林(树)与二叉树的对应关系和相互转换方法；（7）了解树型结构的应用，重点掌握哈夫曼树的概念和构造方法，哈夫曼编码和译码的原理及实现方法。第4章 图（8学时）教学内容：图的概念和相关术语、图的常用存储结构、两种搜索算法与连通性，图的应用算法，包括：最小生成树算法、拓扑排序算法、关键路径算法、最短路径算法等。教学要求：（1）了解图的定义及相关的术语，掌握图的逻辑结构及其特点；（2）了解图的存储方法，重点掌握图的邻接矩阵和邻接表存储结构；（3）掌握图的遍历方法，重点掌握图的遍历算法的实现

9、；（4）了解图型结构的应用，重点掌握最小生成树算法、最短路径算法、拓扑排序和关键路径算法的基本思想、算法原理和实现过程。第5章 查找（6学时）教学内容：在线性表、树结构和散列结构上进行查找的基本思想和方法、查找算法的实现以及各种查找方法的时间性能；基于关键字查找与基于关键字散列地址查找的本质区别。教学要求：（1）了解不同数据结构上的查找方法；（2）掌握各种查找结构的性质、在静态和动态环境下的查找算法的设计思想和实现方法；（3）掌握各种查找方法的时间性能(平均查找长度)的分析方法；（4）能够根据具体情况选择适合的方法解决实际问题。第6章 排序（4学时）教学内容：气泡排序、插入排序、希尔排序、选择

10、排序、快速排序、堆排序、归并排序、基数排序等排序方法的基本思想、排序过程、算法实现、时间和空间性能，各种排序方法的比较和选择。教学要求：（1）掌握排序的基本概念和常用术语；（2）熟练掌握插入排序与希尔排序；气泡排序与快速排序、选择排序与堆排序、归并排序和基数排序的基本思想、算法原理、排序过程和算法实现；（3）掌握各种排序算法的性能及其分析方法，以及各种排序方法的比较和选择等。第7章（选讲） 文件与外部排序（2学时）教学内容：存储在外存上的数据结构(即文件)的有关概念、各种文件的特点、组织方法及查询和更新操作等；外部排序的基本思想、过程和方法，与内排序的比较等。教学要求：（1）掌握文件的相关概念

11、；文件的各种组织方法及特点；查询、更新操作及其算法；（2）掌握外部排序的一般过程，熟练掌握适合外存特点的归并排序的相关技术。三、其它教学环节（一）课程辅导环节（40学时）课程课堂教学10周，每周安排一次（4学时）辅导答疑， 共40学时课外辅导。（二）课外自学环节（80学时）按课程授课学时1：2配备课外复习和自习学时，共80学时。（三）课内实验（8学时） 具体要求见实验教学大纲。四、考试权重 课程总成绩由三部分组成：期末考试成绩占总成绩的70%，实验成绩占总成绩的20%，作业成绩占总成绩的10%。大纲撰写人：张岩 大纲审核人：李秀坤数据结构与算法实验教学大纲开课实验室：计算机软件实验中心课程名称

12、：数据结构与算法实验学时：8面向专业：计算机科学与技术专业、信息安全专业、生物信息技术专业课程总学时：48课程编号：SC03100110实验类别：技术基础课一、实验教学的指导思想和教学目的指导思想：“数据结构与算法”是计算机科学与技术专业软件系列课程的基础理论课，也是软件技术核心基础课，主要训练信息在计算机中的组织和表示方法，实验着眼于基础知识和实际应用的有机结合，是在理性指导下的实践，逐步培养和提高学生的专业修养和专业素质。教学目的：使学生学会如何把课堂上学到的数据结构与算法的基础知识用于解决实际问题，培养软件工作者所需要的实践能力。另一方面，能使课堂上学到的知识变活，达到深化理解和灵活掌握

13、教学内容的目的。训练学生进行复杂程序设计的技能和培养良好程序设计的风格。二、实验教学的基本要求1通过线性表、树、图等基本的抽象数据型的数据结构和重要算法的实验，使学生更好地掌握和巩固数据结构与算法的基本理论知识。2能够灵活运用基本的数据结构和算法，结合对实际问题的分析和抽象的思维方法以及软件设计的一般过程和方法，达到为实际问题设计数据结构与和算法，并能用高级语言编程、调试，验证其正确性。三、实验教材及参考书1.数据结构与算法，廖明宏等，高等教育出版社，2007。2.数据结构与算法实践教程，李秀坤等，高等教育出版社，2009。四、实验考核1实验成绩在期末考试总成绩中体现，占总成绩20%。2必须按要求完成规定数量的实验，缺一次实验不准许考试。对于完成实验的质和量都特别优秀的给予加分奖励，并记入期末总成绩。3实验之前，要求做好实验准备工作，包括对问题的分析、逻辑设计和物理设计。实验过程中完成编码、调试和测试等工作。实验后，完成对实验的总结工作，包括对设计的调整、实验过程