《数据结构实验1》课程教学大纲

ADDINCNKISM.UserStyle《数据结构实验》课程教学大纲（学科专业类-实验课程）一、课程基本信息课程号3023S04003开课单位国际学院课程名称（中文）数据结构实验（英文）DataStructureExperiment课程性质选修考核类型考查课程学分1课程学时34课程类别专业发展课程（专业核心课）适用专业（类）信息管理与信息系统二、课程描述及目标（一）课程简介《数据结构实验》课程是本专业（类）的一门专业发展课程，旨在培养数据结构分析能力。本课程主要依托数据结构理论。本课程主要包括等实验项目。（二）教学目标通过本课程的学习，使学生在《数据结构》课程学习的基础上，使用C或C++程序设计语言，通过对不同问题选用合适的数据结构，编写质量高、风格好的程序来实现有关应用算法去解决实际问题，并能够对程序进行初步测试和评价，从而使学生得到系统的、科学的分析问题和解决问题的训练，提高专业素质，为后续的软件课程奠定良好的基础。课程目标1：通过对不同问题选用合适的数据结构，编写质量高、风格好的程序来实现有关应用算法去解决实际问题课程目标2：对程序进行初步测试和评价，从而使学生得到系统的、科学的分析问题和解决问题的训练，提高专业素质，为后续的软件课程奠定良好的基础。三、教学方式与方法教学手段，教学主要在多媒体教室进行。(2)根据不同章节的特点，分别采用讲授、演示、案例分析、分组讨论、分析评价和课后作业等方法。(3)学生课堂讨论，网络教室实验。强调知识和能力两方面的平衡；特别重视个性的发展，鼓励个人潜能的开发；倡导以学生为主体的教育思想，使学生能够学会如何学习，成为学习的主人；课程以单元模块为单位，既有统一要求，又可适应个体需要；整个教学不是以最后的考试为惟一考核依据，平时的课业等也是衡量学生是否达到教学目的的主要标准，并在教学过程中结合实验情况进行指导，培养学生自主开发软件的能力。四、教学重点与难点从数据结构的存储结构、数据的运算以及程序实现三个方面去掌握线性表、栈、队列、串、数组、树、图等常用的数据结构；掌握常用的各种查找方法和排序算法；并培养对算法的时间空间复杂性的分析能力。（二）教学难点如何使用所学的数据结构知识来有效的解决实际的非数值计算问题，如何完成从算法设计到程序实现的转换，如何对自己设计的算法进行时间和空间的初步性能分析。五、实验内容、基本要求与学时分配序号实验项目名称实验内容与要求学时类型对应课程目标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课程目标1课程目标2课程目标3表现40课程目标3期末考核50课程目标1课程目标