中国海洋大学数据结构与算法课程大纲理论课程-中国海洋大学信息.DOC

中国海洋大学 数据结构与算法 课程大纲（理论课程） 英文名称 Data Structure and Algorithm 【开课单位】信息科学与工程学院计算机系 【课程模块】 学科基础 【课程编号】 【课程类别】 必修 【学时数 】 80 （理论 64 实践 16 ） 【学分数 】 4.5 一、课程描述 本课程大纲根据2011年本科人才培养方案进行修订或制定。 教学对象 计算机系二年级学生 （二）教学目标及修读要求 1、教学目标 《数据结构》是计算机专业的核心基础课程，它主要介绍数据在计算机系统中的存贮结构、访问策略及计算等。通过本课程的学习，希望能够达到如下目标： 明确数据、数据结构、算法与算法分析的基本概念，充分体会数据结构及其运算在计算机领域中的重要性。 使学生能熟练的掌握数据的几种基本逻辑结构、物理表示、运算及其实现方法。 通过简单有效的的算法分析，学会分析和比较算法的性能、理解算法分析的含义、掌握算法分析的基本方法。 为后继课程（编译原理、操作系统、数据库、算法分析与设计等）的学习打好基础。 通过各种实例的讲解，剖析及上机实习，提高复杂算法的设计能力。为今后从事计算机科学以及非数值方面的理论研究和实际应用工作打下坚实的理论与实践基础。 2、修读要求 《数据结构》是计算机科学与技术专业的核心课程之一，在该专业的本科教学中起着举足轻重的作用。该课程上承计算机概论与程序设计基础，下启算法分析与设计和计算复杂性理论，同时是操作系统、软件工程、数据库概论、编译技术、人工智能、计算机图形学等专业课程的必修先行课。 学生在选修本课程前应该学会至少一种高级程序设计语言，并对图论有所熟悉。 （三）先修课程 高级程序设计语言、图论 二、教学内容 （一）第1章 绪论 1、主要内容：数据、数据类型、数据结构、算法、算法分析、数据结构的发展及与其他课程的联系，有关描述算法所使用的语言的说明。 2、教学要求：掌握数据、数据类型、数据结构、算法、算法分析，理解有关描述算法所使用的语言的说明，了解数据结构的发展及与其他课程的联系。 3、重点、难点： 重点是数据结构及算法的基本概念、算法的分析方法及问题求解的一般步骤。 难点是评价算法的标准及分析方法。 4、其它教学环节：无 （二）第2章 线性表 1、主要内容：线性表的定义及基本运算，线性表的顺序存储方式和链式存储方式的表示和实现及性能分析，一元多项式的表示及相加。 2、教学要求：掌握线性表的逻辑结构和两种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。理解一元多项式的表示和实现的算法描述及分析。 3、重点、难点： 重点是线性表的定义、线性表的顺序存储和链式存储的特点；顺序表的基本运算（插入、删除、查找）算法和算法分析；单链表的基本运算（插入、删除、查找）算法及算法分析。 难点是链表概念的建立、结点、指针和结点的指针之间的关系；不同的链表（是否加头结点、设尾指针、循环、单向、双向等）适用的场合。 4、其它教学环节：编程实现一元多项式运算器 （三）第3章 栈和队列 1、主要内容：栈和队列的定义、栈和队列的顺序表示与实现、栈和队列的链式表示与实现、栈和队列的应用。 栈和队列的定义、栈和队列的顺序表示与实现、栈和队列的链式表示与实现 3、重点、难点： 重点栈和队列的特点、工作原理、存储方法及基本操作的实现。 难点利用栈和队列解决实际问题以及递归的原理与应用。 （四）第4章 串 1、主要内容：串的类型定义、表示和实现，串的模式匹配算法、串操作的应用举例。 2、教学要求：掌握串的类型定义、表示和实现，串的模式匹配的一种改进算法。理解串操作的应用举例。了解串的其它模式匹配算法。 3、重点、难点： 重点是串的基本概念和基本运算、串的三种存储结构及基本运算的算法实现。 难点是串的模式匹配算法。 4、其它教学环节：无 （五）第5章 数组和广义表 1、主要内容：数组的定义，数组的顺序表示和实现，矩阵的压缩存储：特殊矩阵、稀疏矩阵，广义表的定义，广义表的存储结构，广义表的递归算法。 2、教学要求：掌握数组的定义，数组的顺序表示和实现，稀疏矩阵的压缩存储及运算的实现，广义表的定义，广义表的存储结构。理解广义表的递归算法。了解特殊矩阵的压缩存储。 3、重点、难点： 重点是数组的两种存储表示方法，稀疏矩阵的两类压缩存储方法的特点和适用范围，特殊矩阵的压缩存储方法，稀疏矩阵的三元组表示及各种运算等，广义表的定义、存储结构及相关算法实现。 难点是稀疏矩阵的三