数据结构与算法课程教学大纲.doc

数据结构与算法课程教学大纲课程名称：数据结构与算法/ Data Structure and Algorithm学时/学分：80学时/5学分（其中课内教学64学时，实验上机16学时）先修课程：高等数学、离散数学（可选）、高级语言程序设计适用专业：信息与计算科学开课院（系、部、室）：数学与计算机科学学院一、课程的性质和任务该课程是本专业的核心专业课程，所讨论的是数据的逻辑结构、存储方式以及相关操作的实现等问题，为学习后续专业课程打下基础。本课程的任务是：一方面训练学生理解掌握各种基本数据结构的要领，以便能够编写出各种典型算法，另一方面，培养学生应用各种典型算法解决具体应用问题的能力。二、课程内容、基本要求及学时分配（一）绪论 4学时(1)掌握计算语句频度和估算算法时间复杂度的方法；(2)掌握数据的逻辑结构和物理（存储）结构之间的关系；(3)了解抽象数据类型的定义方法。重点：数据结构的概念；估算算法时间复杂度。难点：估算算法时间复杂度。（二）线性表 10学时(1)掌握线性表的基本概念。(2)掌握线性表的两种存储结构的特点及在其上的基本操作。(3)理解同一种逻辑结构的运算在不同存储结构上实现的效率是不同的。(4)了解一元多项式的相加运算在计算机中的实现。重点：线性表的基本概念；线性表的两种存储结构的特点及在其上的基本操作。难点：线性表的两种存储结构的特点及在其上的基本操作。（三）栈和队列 4学时(1)掌握栈的特点及其基本操作；(2)掌握队列的特点和循环队列的基本操作；(3)理解递归算法与栈的关系。(4)了解栈和队列在计算机领域的应用。重点：栈与队列的特点及其基本操作。难点：循环队列；递归算法。（四）串 4学时(1)理解串的存储的特点。(2)掌握串的顺序存储结构及基本操作。(3)理解串的KMP算法。(4)了解串在文本编辑中的应用。 重点：串的顺序存储结构及基本操作。难点：串的KMP算法。（五）数组和广义表 4学时(1)掌握数组的顺序存储方法。(2)理解特殊矩阵及稀疏矩阵的压缩存储的意义及方法。(3)掌握广义表的概念。重点：数组的顺序存储方法。难点：多维数组的顺序存储。（六）树和二叉树 12学时(1)掌握树的基本概念和特点。(2)理解树结构的递归性质。(3)掌握二叉树（BT）的概念及几个性质。(4)掌握BT的遍历的原理及递归算法；(5)理解线索树。(6)掌握Huffman树的构造方法及应用。重点：二叉树（BT）的概念及几个性质；BT的遍历的原理。难点：树结构的递归性质。（七）图 10学时(1)掌握图的概念和常用的存储结构。(2)掌握图的两种遍历算法思想；(3)理解图的几种应用。重点：图的概念和常用的存储结构；图的两种遍历算法思想。难点：图的应用算法实现。 （八）查找 8学时(1)掌握顺序表和有序表的查找方法。(2)掌握二叉排序树的构造和查找方法；(3)理解B-树及B+树的特点；(4)掌握hash表构造方法，深刻理解与其他结构的表的实质性差别；重点：各种查找方法的原理。难点：各种查找方法的实现。（九）内部排序 8学时(1)掌握各种排序方法依据的原则。(2)掌握各种排序方法的时空开销及各自的特点。(3)了解排序算法的时间开销的上限的研究。重点：各种排序方法的原理。难点：各种排序方法的实现三、推荐教材和主要参考书1、推荐教材：（1）严蔚敏、吴伟民编著，数据结构（C语言），北京，清华大学出版社，1997年4月第7版。2、推荐参考书：（1） 许卓群等，数据结构，北京，高等教育出版社，1987。（2） Clifford A. Shaffer著，张铭等译，数据结构与算法分析（C+版 第二版），北京，电子工业出版社，2002.6。（3） 傅清祥等，算法与数据结构，北京，电子工业出版社，1998。（4）潘金贵等，现代计算机常用数据结构和算法，北京，南京大学出版社，1994。大纲制订者：李峰大纲审定者：吴元斌