数据结构_教学大纲（理论）.docx

《数据结构_教学大纲（理论）.docx》由会员分享，可在线阅读，更多相关《数据结构_教学大纲（理论）.docx（7页珍藏版）》请在第一文库网上搜索。

1、【课程编号】数据结构（理论）（-）基本信息中文课程名称：数据结构（理论）英文课程名称：DataStrUetUre（TheoryCourse）课程编号：学分：4学时：64适用专业：计算机科学与技术、人工智能、数据科学与大数据技术先修课程：高级语言程序设计开课系（教研部）：计算机科学技术系执笔：审核：课程简介：“数据结构”是计算机学科本科教学计划中的骨干基础课程，对学生基本的计算机问题求解能力的培养具有重要意义。作为一门必修课程，该课程既是对以往课程的深入和扩展，也是为将来更加深入地学习其他专业课程打下基础。课程中所学的排序问题的算法以及基本的线性表、树、图等数据结构，是计算机学科的基本功。散列表

2、等高级数据结构，也是数据库、操作系统、编译原理、计算机网络等后续课程的基础。（二）课程目标“数据结构”是计算机科学与技术专业、人工智能、数据科学与大数据技术等专业的一门学科基础课，在培养学生创造性思维、综合设计能力、软件工程实践能力以及解决实际问题能力等方面占有重要地位。通过本课程的学习，使学生掌握如何根据问题的需求合理地组织数据，在计算机中有效地存储数据和处理数据，并初步了解算法的设计和分析。课程目标对学生的能力要求如下：（1）能够掌握线性表、树、图等基本数据结构的逻辑关系、存储结构及基本算法，掌握查找和排序算法，具备解决复杂工程问题的算法理论基础。（支撑毕业要求1.3）（2）在学习和理解基

3、本数据结构特性、基本算法的基础上，能够运用这些知识对工程问题进行分析、建模和求解。（支撑毕业要求2.2）（3）能够通过算法设计过程的分析、时间与空间复杂度的分析，论证解决方案的合理性。（支撑毕业要求4.3)课程目标对毕业要求的支撑关系如下表所示。毕业要求毕业要求指标点课程目标支撑1工程知识1.3具备能够运用于解决计算机领域复杂工程问题的计算机专业知识。课程目标1M2.问题分析2.2针对计算机领域的复杂工程中所涉及到的问题，能够基于数学、工程科学和本专业基本原理对问题进行描述、抽象、并建立数学模型。课程目标2H4.研究4.3能够正确整理和分析实验数据，对结果进行解释和评价得到有效结论。课程目标3

4、H(=)教学内容与课程目标的关系序号教学内容教学要求推荐学时教学方式对应的课程目标11概论(1)数据结构的基本概念。(2)数据的逻辑结构、存储结构以及二者之间的关系。(3)抽象数据类型的形式化描述。(4)算法设计的要求。(5)算法的时间免杂度分析。(1)深入了解数据结构的基本概念，为本课程后续章节奠定基础。学会定义数据结构和抽象数据类型。学会分析算法的时间复杂度和空间复杂度。4讲授课程目标1课程目标322线性表及其顺序存储(1)线性表的逻辑结构定义。(2)线性表的顺序存储结构及其基本操作的实现。(3)顺序表基本操作的时间性能分析。(4)栈和队列的操作特性。(5)栈的顺序表示、队列的顺序表示，及

5、其基本操作的实现。(6)栈在函数调用中所起的作用，栈的典型应用算法，例：括号匹配的检验、表达式求值等。(1)熟练掌握线性表的顺序存储结构的表示及其基本操作的实现。能对上述操作的时间复杂度和空间复杂进行分析。学会用线性表解决实际问题，并对所编写算法的时间复杂度和空间复杂进行分析。(4)熟练掌握栈和队列的特点及适用场合。(5)熟练掌握栈的顺序表示、队列的顺序表示，会应用它6讲授课程目标1课程目标2课程目标3们的基本操作设计算法，并分析其时间复杂度和空间复杂度。33线性表的链式存储(1)线性表的链式存储结构及其基本操作的实现。(2)单链表基本操作的时间性能分析。(3)顺序表和单链表的比较，适用场合。

6、(4)栈、队列的链式表示，及其基本操作的实现。(1)熟练掌握线性表的链式存储结构的表示及其基本操作的实现。能对上述操作的时间复杂度和空间复杂进行分析。(3)熟练掌握栈、队列的链式表示，会应用它们的基本操作设计算法，并分析其时间复杂度和空间复杂度。6讲授课程目标1课程目标2课程目标344串(1)串的抽象数据类型定义及其基本运算。(2)串的模式匹配算法。(1)使用串基本操作构造与串相关的算法，解决简单的应用问题。2讲授课程目标1课程目标255数组(1)数组的寻址方法。(2)二维数组的顺序存储结构。(3)特殊矩阵(对称矩阵、上/下三角矩阵)、稀疏矩阵的压缩存储方法。(4)稀疏矩阵的三元组表示。(5)

7、稀疏矩阵的快速转置算法。(1)熟练掌握多维数组的逻辑结构特征及其存储方式。熟练掌握特殊矩阵和稀疏矩阵的压缩存储方法。(3)熟练掌握稀疏矩阵的快速转置算法。(4)综合利用线性结构的特性和所学算法，解决较复杂的工程问题。4讲授课程目标1课程目标2课程目标366递归(1)递归算法的思想，递归程序的执行过程分析。(2)递归程序到非递归程序转换的方法(3)递归算法时间性能分析。(1)深入理解递归算法的执行原理。了解递归算法转化为非递归算法的常用方法。4讲授课程目标1课程目标2课程目标377树和二叉树(1)二叉树的性质。(2)二叉树和树的存储表示。(1)熟练掌握树与二叉树的抽象数据类型定义和实现。熟练掌握

8、二叉树的遍历6讲授课程目标1课程目标2课程目标3(3)二叉树的递归、非递归遍历算法的实现及应用。(4)穿线二叉树。(5)树、森林与二叉树的转换关系。与穿线二叉树。(3)熟练掌握树、森林与二叉树的关系。88图(1)图的邻接矩阵和邻接表存储结构。图的深度和广度优先遍历算法。(3)图的典型应用：最小生成树、拓扑排序、最短路径、关键路径。(1)熟练掌握图的两种存储结构的表示及其基本操作的实现。能利用图的深度优先遍历、广度优先遍历解决简单的应用问题。12讲授课程目标1课程目标2课程目标399查找顺序表的查找。(2)有序表的查找。(3)索引顺序表。(4)二叉排序树。(5)哈夫曼树及应用。(6)散列表的构造

9、与查找。(1)深入理解查找的相关概念。各种查找技术的实现及分析。(3)熟练掌握哈夫曼树及其应用。熟练掌握散列表的构造与查找。8讲授课程目标1课程目标2课程目标31010排序(1)各种内部排序算法的基本思想。各种内部排序算法的执行过程。(3)各种内部排序算法的设计。(4)各种排序算法的时间复杂度、空间复杂度和稳定性的比较。(1)了解排序的定义和各种排序方法的特点。熟悉各种排序方法的基本思想及其算法。掌握各种排序方法的时间复杂度分析方法，能从“排序码的比较次数”、“数据元素的移动次数”分析排序算法的平均情况和最坏情况的时间性能。(4)理解排序方法稳定或不稳定的含义，弄清楚在什么情况下要求应用的排序

10、方法必须是稳定的。8讲授课程目标1课程目标2课程目标3（四）教学方法课程以培养学生计算思维能力和问题求解为主线，从问题抽象、数据抽象和算法抽象的角度来组织数据结构与算法的设计，指导学生建立数学模型，使用不同的数据结构、不同的算法分别去解决问题，最后去探讨各种数据结构和算法的优缺点，同时让学生学会如何根据实际问题来取舍数据结构和算法，并且在时间复杂度和空间复杂度之间进行平衡。通过学习，使学生能够提高利用计算机解决实际问题的能力。在教学方法上，主要有如下举措：（I）采用课堂教学、实验教学、网络协作教学三位一体的教学模式，充分利用信息技术手段提升课程教学质量，培养学生问题求解能力。（2）理论与实践并

11、重，理论教学坚持基础优先、问题驱动的教学方法，通过启发式、案例式、实证型、研究型教学法提升教学质量，培养学生计算思维能力。（五）考核方式及成绩评定1 .评价主体教师为主，主要依据是学习表现、平时作业、期末考试。2 .考核方式课程考核以检验课程目标的达成度为手段，进而评价学生学习成果的达成度。考核的环节包括平时成绩、期末考试，总评成绩以百分计，满分IOO分，各考核环节所占分值可根据具体情况进行微调，建议值及考核细则如下：（1）平时成绩（50分）主要考查学生对各章节知识点的复习、理解和掌握程度。考查学生应用所学知识及先进工具解决教育系统的分析问题和解决问题能力、合理性分析能力。教师根据作业完成情况

12、评分。（2）期末考试（50分）卷面总分100分，以卷面成绩乘以其在总评成绩中所占的比例计入总评成绩。主要考核各种数据结构的逻辑结构、物理结构、特性、算法及其分析。考试题型可以有：选择题、填空题、应用题、算法分析题、算法设计题等。其中，建议1对应课程目标1的试题分数占总分的30-40%,题型以选择题、填空题、应用题为主。II.对应课程目标2的试题分数占总分的40-50斩题型以解答题、应用题、算法分析题、算法设计题为主。H1对应课程目标3的试题分数占总分的10-20%,题型以选择题、算法分析题、算法设计题为主。3.课程目标达成评价课程目标考核内容评价方式学习表现和平时作业(50%)期末考试(50%

13、)分目标总分课程目标1能够掌握线性表、树、图等基本数据结构的逻辑关系、存储结构及基本算法，掌握查找和排序算法，具备解决复杂工程问题的算法理论基础。学习表现平时作业期末考试30%40%35课程目标2在学习和理解基本数据结构特性、基本算法的基础上，能够运用这些知识对工程问题进行分析、建模和求解。学习表现平时作业期末考试50%50%50课程目标3能够通过算法设计过程的分析、时间与空间复杂度的分析，论证解决方案的合理性。学习表现平时作业期末考试20%10%15课程目标达成度评价包括课程分目标达成度评价和课程总目标达成度评价，具体计算方法如下:、里阳今日广大出席-总评成绩中支撑该课程目标相关考核环节平均

14、得分之和味桂分日称1成度=总评成绩中支撑该课程目标相关考核环节目标总分(六)评分标准课程目标评分标准90-10075-8960-740-59优良中/及格不及格课程目标1深入掌握线性表、树、图等基本数据结构的逻辑关系、存储结构及基本算法，以及查找和排序算法，完全具备解决复杂工程问题较好掌握线性表、树、图等基本数据结构的逻辑关系、存储结构及基本算法，以及查找和排序算法，具备解决复杂工程问题的算一般掌握线性表、树、图等基本数据结构的逻辑关系、存储结构及基本算法，以及查找和排序算法，基本具备解决复杂工程问题未能掌握线性表、树、图等基本数据结构的逻辑关系、存储结构及基本算法，以及查找和排序算法，不具备解决复杂工程问题的的算法理论基础。法理论基础。的算法理论基础。算法理论基础。课程目标2深入理解数据结构特性和基本算法，完全能够运用这些知识对工程问题进行分析、建模和求解。较好理解数据结构特性和基本算法，能够运用这些知识对工程问题进行分析、建模和求解。一般理解数据结构特性和基本算法，基本能够运用这些知识对工程问题进行分析、建模和求解。未能理解数据结构特性和基本算法，不能运用这些知识对工程问题进行分析、建模和求解。课程目标3能够熟练通过算法