数据结构实验-课程教学大纲

ADDINCNKISM.UserStyle《数据结构实验》课程教学大纲（实验课程）一、课程基本信息课程号1223S00067开课单位课程名称（中文）数据结构实验（英文）DataStructurePractice课程性质必修考核类型考查课程学分1课程学时34课程类别学科基础课程（学科核心课）适用专业（类）生物信息学二、课程描述及目标（一）课程简介数据结构是生物信息专业的专业核心课程，它是介于数学、计算机硬件和计算机软件三者之间的一门重要核心课程，其内容不仅是一般程序设计(特别是非数值性程序设计)的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。本课程的目的是使学生掌握数据组织、存储和运算的基本原理和方法，培养学生进行数据结构算法设计并提高分析问题和解决问题的能力，尤其是能够经过分析得出问题的较优解决方法，从而编写出正确且质量较高的程序，为学习后续课程打下良好的基础，如：数据库技术基础、生物信息方面软件的设计与开发、动态网站的设计与开发等等，并且在从事专业工作时能够正确选择和使用数据结构相应算法，提高生物信息方面的数据检索与处理效率。（二）教学目标许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。选择了数据结构，算法也随之确定，系统构造的关键因素是数据结构而不是算法。此种洞见导致了许多软件设计方法和程序设计语言的出现。所以，本课程的任务是从抽象数据类型的角度讨论各种基本类型的数据结构及其应用，使学生具备基本理论分析和编程能力。课程目标1：使学生掌握结构体指针的用法；掌握算法的特征和评价标准；掌握线性结构中的顺序表、链表、栈和队列的基本运算；掌握树形结构中的二叉树的性质与基本运算；掌握图状结构的遍历与基本应用；了解查找与排序的基本算法；课程目标2：使学生具有进行数据结构算法设计以及分析问题的能力，能够得出问题的较优解决方法，并编写出正确、质量较高的程序；课程目标3：使学生能够在从事专业工作时正确选择和使用数据结构，从而提高数据检索与处理的效率。三、课程目标对毕业要求的支撑关系毕业要求指标点课程目标1-3：掌握比较扎实的数学和物理、化学方面的基础理论知识,具有计算机及信息科学等方面的基础知识；课程目标12-2：具有综合运用所掌握的理论知识和技能，从事生物技术及其相关领域科学研究的能力；课程目标2课程目标32-5：具有一定的计算机和信息技术应用能力。课程目标13-3：具备良好的专业素质，受到严格的科学思维训练，有求实创新的精神、批判性思维和可持续发展理念；课程目标2课程目标3四、教学方式与方法通过大量的实验促使学生掌握数据结构相应知识。五、教学重点与难点（一）教学重点算法的特征与评价标准、线性结构、树形结构、图状结构、查找、排序。（二）教学难点线性链表、树形结构、图状结构、二叉排序树、堆排序。六、实验内容、基本要求与学时分配序号实验项目名称实验内容与要求学时类型对应课程目标1C语言指针、结构体实验必修内容：计算i!+(i-1)!的值并存入数组；计算多项式前n项之和。要求：掌握指针和结构体的用法2验证性课程目标12必修顺序表的插入与逆置内容：将x插入到顺序表的适当位置上，以保持该表的有序性；对顺序表实现就地逆置；要求：掌握顺序表的插入和逆置算法2验证性课程目标13必修单链表的插入与删除内容：在有头结点的单链表结构上实现线性表操作Insert；删除单链表中所有值相同的多余元素；要求：掌握单链表的插入与删除算法2验证性课程目标14必修多项式的合并内容：将两个多项式LP1和LP2合并，并释放空间；要求：掌握链表的遍历2设计性课程目标1课程目标25必修单向循环链表删除前驱结点内容：在链表中删除指针s所指结点的前驱结点；要求：掌握循环链表的用法2验证性课程目标16选修车厢调度问题内容：火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度；要求：掌握栈的插入与删除算法2设计性课程目标1课程目标2课程目标37必修逆波兰式内容：将求中缀表达式（由个位整数与+-*/()组成）转逆波兰式；要求：掌握表达式的运算过程2设计性课程目标18选修模拟患者去医院看病过程内容：模拟患者去医院看病过程：先排队等候，再看病；要求：掌握队列的用法2设计性课程目标1课程目标2课程目标39必修串的应用内容：串求逆的递推算法；从串s中删除所有和串t相同的子串；要求：掌握串的相关算法2设计性课程目标110必修数组的应用内容：设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法；要求：掌握表达式的运算过程2设计性课程目标1课程目标2课程目标311必修二叉链表内容：由完全二叉树的顺序存储建立该二叉树的二叉链表；要求：掌握二叉链表的建立2综合性课程目标1课程目标212必修二叉树的遍历内容：求二叉树先序序列中第k个位置结点的值；求距离a,b两个结点最近的共同祖先的算法；要求：掌握二叉树的遍历算法3综合性课程目标1课程目标213必修图的遍历内容：基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径；要求：掌握图的遍历过程2综合性课程目标1课程目标214选修图的应用：最小生成树内容：以邻接矩阵存储并用普里姆算法求其最小生成树；要求：掌握最小生成树算法3综合性课程目标1课程目标2课程目标315选修查找内容：由给定数组data中的值建立二叉排序树算法；要求：了解查找中的二叉排序树。2验证性课程目标1课程目标2课程目标316必修排序内容：随机生成50个数，分别用直接插入排序、简单选择排序、冒泡排序、快速排序进行增序排序；要求：了解顺序表的排序过程2验证性课程目标1课程目标2课程目标3合计=SUM(ABOVE)34七、学业评价和课程考核（一）考核类型：考试考查（二）考核方式：实验报告实验作品其它：上机测试（填写具体考核方式）（三）成绩评定：考核依据建议分值（百分比）考核/评价细则对应课程目标过程考核50考勤10考勤情况，课堂表现课程目标1作业25正确性、时效性、完成度课程目标1-2测试15MOOC测试，正确性、时效性课程目标1-2期末考核50上机测试，正确性、时效性课程目标1-3八、课程目标达成评价课程目标的实际达成效果计算方式如下，达成值越高，教学效果越好。课程目标达成度毕业要求指标点达成度九、教材与教学参考书（一）教材《数据结构（C语言版）》，严蔚敏等，清华大学出版社，2018.6，第2版。（二）教学参考书《数据结构