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

PAGE 1 - PAGE 1 - 《数据结构与算法》课程教学大纲 课程编码： S课程名称：数据结构与算法 课程英文名称：Data Structures and Algorithms 总学时：48 讲课学时：40 实验学时：8 课外辅导学时：40 学分：3.5 开课单位：计算机科学与技术学院 授课对象：计算机科学与技术、信息安全、生物信息技术及相关专业 开课学期：2秋 先修课程：集合论与图论，高级语言程序设计 课外学时：80 主要教材及参考书： 教材：廖明宏,郭福顺,张岩,李秀坤.数据结构与算法(第4版).高等教出版社.2007. 主要参考书： 1.严蔚敏,吴伟民. 数据结构(C语言版). 清华大学出版社.2011. 2.Ellis Horawitz,Sartaj Sahni,Susan Anderson-Freed著,李建中,张岩,李治军译.Fundamentals of Data Structures in C.机械工业出版社.2006. 3. Sartaj Sahni著, 汪诗林,孙晓东. Data Structures,Algorithms,and Applications in C++.机械工业出版社.2006. 4.李秀坤,张岩,李治军,娄久.数据结构与算法实验教程.高等教育出版社.2009. 一、课程教学目的 通过本课程的学习，学生将基本掌握数据结构和算法基础知识、设计与分析的技术和方法，提高程序设计的质量；能够根据所求问题的性质，选择合理的数据结构，并对时间复杂性进行必要的控制。培养运用数据结构表示实际问题并设计有效算法解决实际问题的能力。为后续课程的学习和将来从事的研究工作打下扎实的基础。 二、教学内容及基本要求 以抽象数据型为基础，讲授数据的各种逻辑结构、在计算机中的存储结构、对数据进行的插入、查找、删除、排序、遍历等操作（运算）和这些操作（运算）在存储结构上具体实现的算法。课程的重点是基本数据结构的不同存储结构以及操作算法的实现。课程的难点是基本数据结构的不同存储结构以及操作算法的实现、算法的性能分析以及数据结构与算法的应用。 分章节描述教学内容和教学基本要求。 第1章 绪论（3学时） 教学内容：课程的基本概念和术语；课程的研究对象；抽象数据类型；算法的描述和简单的分析方法。 教学要求：（1）了解数据结构的基本概念、研究对象以及数据结构课程的发展历史，对数据结构与算法课程有一个宏观的认识；（2）掌握贯穿全书的重要概念--抽象数据型，包括其概念的定义和实现方法，初步掌握抽象技术方法；（3）了解算法、算法复杂性，掌握算法性能的评价方法；（4）了解解决问题的一般过程和算法的逐步求精方法，掌握问题求解的基本过程和方法。 第2章 线性表（9学时） 2.1 一般线性表（4学时） 教学内容：线性表的逻辑结构、各种存储结构、基本操作（算法）的实现及性能分析、不同存储结构的比较、线性表的应用等。 教学要求：（1）掌握线性表的逻辑结构，线性表的顺序存储结构和链式存储结构的描述方法；（2）熟练掌握线性表在顺序存储结构和链式存储结构的结构特点以及相关的查找、插入、删除等基本操作的实现；（3）能够从时间和空间复杂性的角度综合比较两种存储结构的不同特点；（4）能够利用线性表解决实际应用问题。 2.2 栈与队列（3学时） 教学内容：栈和队列的逻辑结构、存储结构以及基本操作的实现；栈和队列的应用。 教学要求：（1）掌握栈和队列的结构特性和描述方法；（2）熟练掌握栈和队列的基本操作的实现；（3）能够利用栈和队列解决实际应用问题。 2.3 字符串、多维数组和广义表（2学时） 教学内容：字符串的逻辑结构、存储方法和字符串匹配算法，多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏短阵的压缩存储方法及广义表的概念和性质。 教学要求：（1）掌握串的结构特性以及串的基本操作，掌握针对字符串进行操作的常用算法和模式匹配算法；（2）掌握多维数组的存储和表示方法；（3）掌握对特殊矩阵进行压缩存储时的下标变换公式；（4）了解稀疏矩阵的压缩存储表示方法及适用范围；（5）了解广义表的概念和特征。 第3章 树（10学时） 教学内容：二叉树的定义、性质、存储结构、遍历、线索化；树的定义、存储结构、遍历；树和森林与二叉树的转换；树（森林）与二叉树的应用（哈夫曼树及其应用、集合表示与等价分类、表达式求值）。 教学要求：（1）了解树型结构结点之间的层次关系；（2）掌握树和二叉树的定义及其相关的术语；（3）重点掌握二叉树的结构、性质，存储表示和四种遍历算法；（4）掌握二叉树线索化的实质及线索化的过程；（5）了解树的结构性质、存储表示方法和遍历算法；（6）掌握森林(树)与二叉树的对应关系和相互转换方法；