《数据结构(2)》课程教学大纲

ADDINCNKISM.UserStyle《数据结构》课程教学大纲（学科专业类-理论课程）一、课程基本信息课程号3023S04002开课单位国际学院课程名称（中文）数据结构（英文）DataStructure课程性质必修考核类型考试课程学分3课程学时51课程类别专业核心课适用专业（类）信息管理与信息系统二、课程描述及目标（一）课程简介《数据结构》是计算机及相关专业的一门重要的专业基础课，是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术领域的核心课程，同时数据结构技术也被广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。本课程主要介绍如何合理地组织和表示数据、如何有效地存储和处理数据、如何正确地设计算法以及对算法的优劣做出分析和评价。（二）教学目标通过本课程的学习，使学生透彻理解各种常用数据结构的逻辑结构、存储结构及相关算法的实现，全面掌握处理数据的理论和方法；培养学生具备较深入的选用合适的数据结构、编写规范的高质量程序以及评价算法优劣的能力；使学生接受系统的、科学的分析问题和解决问题的训练，提高运用数据结构解决实际问题的能力，为学习后续的软件课程奠定良好的基础。课程目标1：透彻理解各种常用数据结构的逻辑结构、存储结构及相关算法的实现，全面掌握处理数据的理论和方法课程目标2：培养学生具备较深入的选用合适的数据结构、编写规范的高质量程序以及评价算法优劣的能力；课程目标3：使学生接受系统的、科学的分析问题和解决问题的训练，提高运用数据结构解决实际问题的能力，为学习后续的软件课程奠定良好的基础。三、教学方式与方法教学方式：课堂讲授为主，辅以适当的课堂提问、讨论和课堂练习。教学方法：启发式教学、探讨式教学、理论与实践相结合。四、教学重点与难点（一）教学重点从数据结构的逻辑结构、存储结构、数据的运算三个方面去掌握线性表、栈、队列、串、数组、树、图等常用的数据结构；掌握常用的各种查找方法和排序算法；能够对算法的时间复杂性和空间复杂性的进行分析。（二）教学难点逻辑结构与存储结构的关系；顺序表和链表的区别与联系；栈和队列的特点；模式匹配；矩阵的压缩存储；二叉树的性质；二叉树的非递归遍历算法；哈夫曼树的应用；图的遍历算法；最小生成树、最短路径、关键路径等图的应用及算法实现；二叉排序树、平衡二叉树和B树的建立、查找、插入和删除的方法及算法实现；哈希表的建立及性能分析；希尔排序、快速排序、堆排序和归并排序的算法实现及性能分析。五、教学内容、基本要求与学时分配序号教学内容基本要求学时教学方式对应课程目标1第1章绪论掌握数据结构中常用的基本概念和术语；理解学习数据结构的意义；了解数据结构的学习内容；掌握算法描述和分析的方法。2讲授课程目标12第2章线性表掌握线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算在相应的存储结构上的实现；理解顺序表和链表的优缺点；能够针对具体的应用问题的要求，选择合适的存储结构设计出相应的算法，解决与线性表相关的实际问题。8讲授课程目标23第3章栈和队列掌握栈和队列的逻辑结构定义及在两种存储结构上栈和队列基本运算的实现；理解栈和队列的特点，懂得在什么样的情况下使用栈或队列。4讲授课程目标24第4章串掌握串的逻辑结构、存储结构及字符串上常用的基本运算及模式匹配算法。4讲授课程目标35第5章数组和广义表掌握多维数组的逻辑结构特征及存储方式；掌握特殊矩阵和稀疏矩阵的压缩存储方法；理解广义表的概念及存储实现方法4讲授课程目标36第6章二叉树掌握二叉树的性质、二叉树的存储结构、二叉树的各种遍历算法及其应用；了解线索二叉树的构成和遍历方法；掌握哈夫曼树的建立和哈夫曼编码的方法。10讲授7第7章树和森林掌握树和森林的定义、树和森林的存储结构、树和森林与二叉树之间的相互转换、树和森林的遍历及树的应用。4讲授8第8章图掌握图的基本概念、图的存储结构、遍历算法、生成树算法；理解图的应用算法思想。14讲授9第9章查找掌握各种存储方式下的静态查找表、动态查找表和哈希表的查找方法；能够分析各种查找方法的时间性能。10讲授课程目标310第10章排序掌握各种内排序方法的基本思想、排序过程、算法实现；能够分析各种内排序方法的时间和空间性能；理解各种排序方法的适用情况，并能够根据具体要求进行选择；了解外排序的思想。8讲授课程目标4六、实验内容、基本要求与学时分配序号实验项目名称实验内容与要求学时类型对应课程目标1简单程序设计实践1.建立一个学生成绩表，人数不低于30人，完成对该表的查询、求平均分、统计各分数段的人数等基本操作；2.随机输入若干整数（不低于15个），选择任意方法对其排序并输出排序结果。2演示性课程目标12线性表的基本操作1.约瑟夫环问题问题描述：约瑟夫(Joseph)问题的一种描述是：编号为1,2,…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。2.一元多项式运算问题描述：输入并建立多项式；输出多项式；完成多项式间的加减法运算。4验证性课程目标13栈与队列的应用模拟停车场管理问题描述：设停车厂只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达的先后顺序依次排列，若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可进入;当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门后，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走。4设计性课程目标14串和矩阵的操作实现KMP算法和改进KMP算法；2设计性课程目标15树形结构的操作1.二叉树的建立与先中后序遍历的实现（根据数据结构课程内容完成即可）；2.哈夫曼编/译码问题描述：根据数据结构课程中所讲解的哈夫曼编码原理构建哈夫曼树，并根据用户的输入完成编码或译码的过程。4设计性课程目标16图形结构的操作拓扑排序和关键路径的实现（根据数据结构课程内容完成即可）。6设计性课程目标17查找实验1.实现顺序查找、折半查找等静态查找算法（根据数据结构课程内容完成即可）；2.哈希表设计问题描述：针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序6探究性课程目标1课程目标2课程目标38内排序算法的实现各种内部排序方法的比较问题描述：在教材中，各种内部排序算法（起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序）的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以得到真感受。6探究性课程目标1课程目标2课程目标3合计34注：实验要求包括必修、选修；实验类型包括“演示性”、“验证性”、“设计性”、“探究性”、“其它”等。七、学业评价和课程考核（一）考核类型：þ考试考查（二）考核方式：开卷考试þ闭卷考试课程论文课程报告其它：（三）成绩评定：考核依据建议分值（百分比）考核/评价细则对应课程目标平时考核50出勤30课程目标1作业30