《数据结构》课程标准韶关学院计算机科学系2004年12月《数据结构》课程标准一、课程概述"数据结构"是计算机学科的算法理论基础和软件设计的技术基础，主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。它不仅是计算机学科各专业的核心课程，而且已成为其它理工科专业的热门选修课。本标准的编写依据是2002级专业教学计划，适用于计算机系计算机科学与技术专业（本科）。其它专业及其它教学层次参照本标准执行，执行时，由任课教师根据教学计划安排的实际学时作适当调整。二、课程目标从课程性质上讲，《数据结构》是一门计算机专业技术基础课。通过本课程的教学，达到的教学目标是：1．知道《数据结构》这门学科的性质、地位和独立价值。知道这门学科的研究范围、分析框架、研究方法、学科进展和未来方向。2．理解这门学科的基本概念、主要结构类型和算法，尤其是数据结构的三要素、存储结构的实现和算法的评价策略。3．学会分析研究计算机加工的数据的结构特性，以便为实际应用问题所涉及到的数据选择适当的逻辑结构、存储结构及其算法。4．逐步理解算法的时间分析和空间分析的技术。5．培养数据抽象能力；训练复杂程序设计的技能；要求编写的程序结构清楚和正确易读，养成良好程序设计习惯。三、教学内容和教学要求本课程的知识与技能要求分为知道、理解、掌握、学会四个层次。这四个层次的一般涵义表述如下：知道--是指对本课程涉及的一般知识的认知。理解--是指对本课程涉及到的概念、主要结构类型和算法的说明和解释。掌握--是指运用已理解的概念和算法解决实际问题的一般方法。学会--是指能模仿或在教师指导下独立地完成较复杂程序设计。教学内容和要求表中的"√"号表示教学知识和技能的教学要求层次。1．绪论（讲授8学时）教学内容教学要求知道理解掌握学会1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析√√√√2．线性表（讲授6学时）教学内容教学要求知道理解掌握学会2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示及相加√√√√3．栈和队列（讲授6学时）教学内容教学要求知道理解掌握学会3.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列√√√√4．串（讲授4学时）教学内容教学要求知道理解掌握学会4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法4.4串操作应用举例√√√√5．数组和广义表（讲授4学时）教学内容教学要求知道理解掌握学会5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的概念√√√√6．树和二叉树（讲授10学时）教学内容教学要求知道理解掌握学会6.1树的定义和基本术语6.2二叉树6.3遍历二叉树6.4线索二叉树6.5树和森林6.6赫夫曼树及其应用√√√√√√7．图（讲授12学时）教学内容教学要求知道理解掌握学会7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4拓扑排序7.5关键路径7.6最短路径√√√√√√8．查找（讲授6学时）教学内容教学要求知道理解掌握学会8.1静态查找表8.2动态查找表8.3哈希表√√√9．内部排序（讲授12学时）教学内容教学要求知道理解掌握学会9.1概述9.2计数排序9.3插入排序9.4折半排序9.5冒泡排序9.6快速排序9.7选择排序9.8树排序9.9堆排序9.10归并排序9.11基数排序9.12各种内部排序方法的比较讨论√√√√√√√√√√√√10．外部排序（讲授2学时）教学内容教学要求知道理解掌握学会10.1外部信息的存取10.2外部排序的方法√√11．文件（讲授2学时）教学内容教学要求知道理解掌握学会11.1文件的基本概念11.2文件的组织√√四、课程实施（一）课时安排与教学建议课程学时：90(授课72/实验18)。具体安排如下：主要内容课时建议教与学的方法建议按90课时计按50课时计1绪论66由案例讲解2线性表63讲解与多媒体演示相结合3栈和队列63讲解与多媒体演示相结合4串44讲解与多媒体演示相结合、阅读指导5数组和广义表44讲解与多媒体演示相结合、阅读指导6树和二叉树88讲解与多媒体演示相结合、讨论7图126讲解与多媒体演示相结合8查找66讲解与多媒体演示相结合、阅读指导9内部排序126讲解与多媒体演示相结合、