《数据结构》课程教学大纲new

PAGE5《数据结构》课程教学大纲课程代码：B03203课程名称：数据结构英文名称：DataStructures课程总学时：60（其中理论课46学时，实验14学时）学分：2.5课程类别：必修课程性质：专业基础课先修课程：计算机导论、Java语言程序设计面向专业：软件技术、计算机网络技术开课单位：软件工程系一、课程的性质、地位和任务本课程是计算机程序设计的重要理论技术基础，是计算机学科的核心课程，是专业技术基础课。本课程的目的是使学生掌握数据组织、存储和运算的基本原理和方法，培养学生进行数据结构的算法设计及分析问题的能力，能够编写出正确、清晰、质量较高的程序，并且为学习后续课程打下良好的基础，在毕业后从事专业工作时能正确选择与使用数据结构；本课程的任务是从抽象数据类型的角度讨论各种基本类型的数据结构及其应用，另外还讨论了查找和排序的各种实现方法，使学生具备基本理论分析和编程能力。二、课程的教学目标（一）理论、知识方面1．掌握数据结构的基本概念，进行初步算法分析。2．掌握线性表的逻辑结构、物理结构以及常用操作的算法。3．掌握栈和队列的逻辑结构、物理结构，理解栈和队列的应用。4．了解串类型的定义、表示和实现。5．理解数组的定义、基本运算和存储结构，理解广义表的定义、术语、存储结构、基本运算，了解递归算法设计。6．掌握树的基本概念，二叉树的定义、性质和存储结构，遍历二叉树，了解线索二叉树的概念、应用，掌握赫夫曼树及应用7．掌握静态查找表的查找方法、理解动态查找表的查找方法，掌握哈希表的基本概念8．掌握常用内部排序算法（二）能力、技能方面1．培养学生的数据抽象能力。2．具备基本理论分析和编程能力。三、课程教学内容与要求第一章绪论（2学时）1.教学内容及基本要求了解数据结构的发展及所处的地位（1学时）；深刻理解数据结构的基本概念和术语；掌握算法描述及算法的评价标准（1学时）。2.重点、难点重点：数据结构的概念和术语。难点：时间复杂度的分析。第二章线性表（6学时）1.教学内容及基本要求理解线性表的概念、存储结构；深刻理解线性表的顺序存储结构的特点、类型描述，熟练掌握插入、删除、查找操作的算法实现（2学时）；熟练掌握线性表的链式存储结构的特点、类型描述，插入、删除、查找操作的算法实现（2学时）；掌握循环链表、双向链表及其基本操作的算法（2学时）。2.重点、难点重点：线性表的顺序存储和链式存储结构。难点：线性表的链式存储。第三章栈和队列（4学时）1.教学内容及基本要求理解堆栈的概念、存储结构（1学时）；熟练掌握顺序存储和链式存储两种结构下的进栈、出栈的算法（1学时）。理解队列的概念、存储结构（1学时）；熟练掌握顺序存储和链式存储两种结构下的入队、出队的算法（1学时）。2.重点、难点重点：堆栈及其操作，队列及其操作。难点：递归方法的应用，循环队列的使用。第四章串（2学时）1.教学内容及基本要求理解字符串的概念，掌握字符串的存储结构；了解字符串操作的应用。2.重点、难点重点：字符串的存储结构。难点：字符串操作的实现。第五章数组和广义表（2学时）1.教学内容及基本要求理解数组的定义、基本运算和存储结构，特殊矩阵的压缩存储（1学时）；理解广义表的定义、术语、存储结构、基本运算，递归算法设计（1学时）。2.重点、难点重点：特殊矩阵的压缩存储；广义表的定义、术语、存储结构、运算。难点：特殊矩阵的压缩存储。第六章树和二叉树（8学时）1.教学内容及基本要求理解树及二叉树的基本概念；深刻理解二叉树的定义、性质、存储结构（2学时）；熟练掌握遍历和线索二叉树的方法（2学时）；掌握哈夫曼树与哈夫曼编码（2学时）；掌握树及森林与二叉树之间的转换（2学时）。2.重点、难点重点：二叉树的遍历、线索及应用。难点：哈夫曼树的构造。第七章图（8学时）1.教学内容及基本要求理解图的概念及基本术语；掌握图的邻接矩阵和邻接表的存储结构（2学时）；熟练掌握图的深度优先遍历和广度优先遍历的方法（2学时）；了解图的遍历在实际中的应用（2学时）；了解最小生成树和最短路径（2学时）。2.重点、难点重点：图的存储结构。难点：图的遍历。第八章查找（6学时）1.教学内容及基本要求掌握顺序查找、二分查找、分块查找的方法和过程（2学时）；熟练掌握二叉排序树的定义，结点插入和删除的操作方法及二叉排序树的查找过程（2学时）；熟练掌握哈希表定义、哈希函数构造和冲突的处理方法（2学时）。2.重点、难点重点：顺序查找、二分查找、分块查找的方法。难点：二叉排序树结点的删除，哈希函数的构造。第九章排序（6学时）1.教学内容及基本要求理解排序的概念；了解各种不同排序方法的适用场合（1学时）；熟练掌握插入排序、快速排序、选择排序的算法，了解各算法的时间复杂度（3学时）；熟练掌握堆排序、归并排序、基数排序的算法，了解各算法的时间复杂度（2学时）。2.重点、难点重点：各种排序的算法思想。难点：堆排序。四、学时分配序号教学内容讲课习题课实验合计1绪论222线性表6283栈和队列4244串245数组和广义表226树和二叉树822127图82108查找6289排序62210总计=SUM(ABOVE)4441260五、大纲说明1．本课程理论总学时为46学时，为保证基本的教学质量，应当严格要求学生做好一定数量的习题，建议讲课占90％左右，习题课等占10％左右。2．在教学过程中，逐步推行多媒体教学；不断进行教学方式方法的探索，重视培养学生的自学能力。3．考核方式和成绩评定：本课程的总成绩由理论考试成绩、平时作业与实验课成绩3部分组成，按百分制计。其中：理论考试成绩占70%（理论考试成绩通过期末闭卷考试方式评定），平时作业成绩占10%（按每次作业完成情况评定），实验课成绩占20%(依实验课表现与实验报告情况评定)。理论考试为闭卷笔试，120分钟，满分100分，统考，流水作业评分。4．对外语的要求：在讲授过程中，给出各章节主要专业名词的英语单词，通过本门课程的学习，学生可接触到100个左右专业名词的英语单词。、推荐教材