还剩7页未读,继续阅读
文本内容:
数据结构与算法实践
一、课程概况所属专业软件工程开课单位数学计算机科学学院课程类型专业实践课程课程代码07414310开课学期4学分
1.5学时51核心课程否拟使用教材徐慧.数据结构与算法实验实践教程[M].清华大学出版社,
2012.国内(外)现有教材
1.齐悦等著.数据结构、算法与应用[M].清华大学出版社,
2015.
2.李文书.数据结构与算法应用实践教程(第2版)[M].北京大学出版社,
2015.学习参考资料
1.严蔚敏、吴伟民著.数据结构(C语言版)[M].北京清华大学出版社,
2007.
2.宁正元等著.数据结构习题解析与上机实验指导[M].北京中国水利水电出版社,200().
二、课程描述数据结构是计算机科学的算法理论基础和软件设计的技术基础,是计算机专业的核心课程本课程实验采用实验教学和学生实验相结合方式,使学生掌握数据结构的基本原理和编程方法达到提高学生分析问题和解决问题的能力的目的通过实验环节,学生应学会和掌握本课程的基本和重点知识;理解数据结构的基本概念和基本原理,深刻理解逻辑结构、物理结构、算法设计之间的关系,掌握分析问题,建立模型,运用程序进行问题求解的方法本课程是一门实践性极强的程序设计课程,旨在培养学生的实际动手能力,加强学生创新思维能力的培养
三、课程目标数据结构与算法实践课程将覆盖计算机软件实现中的大部分算法,并具有一定的深度和广度,使学生对计算机常用算法有一个全盘的了解;通过此课的学习,学生应该具有针对所给的问题设计和实现高效算法的能力通过上机实验,将使学生熟悉、掌握课堂教学中所学的大部分算法同时,上机实习是对学生在软件设计方面的综合训练,包括问题分析,总体结构设计,用户界面设计,程序设计基本技能和技巧等,以培养良好的编程风格和科学作风通过理论联系实际,以最终提高学生动手操作的能力以及分析问题的能力
四、教学要求本课程由15组设计性实验和2组综合性大实验构成,每次实验课,授课教师将对学生的相关基础知识进行传授,并对实验的基本要求进行分析讲解,指导学生做好实验方案设计、实验提交等工作对学生分组设计实现某个简单系统以完成综合性作业学生应熟悉遵守实验室管理相关规章制度,按时完成各项实验工作参与实践课程教学活动不迟到、不早退,无正当理由不请假,上课认真听讲,不做任何与实践课堂教学无关事宜,不使用手机,积极与授课教师进行实践互动实验完成后做好撰写实验报告提交工作,并对最后的综合实验做好系统的演示或者讲解工作
五、考核方式及要求为实现课程教学目标,本门课程考核采用平时成绩、实验考核与综合实验相结合的方式进行平时成绩用于考察学生考勤、参与课程教学的行为表现,占课程总成绩的30%;实验考核主要用于检验学生对于实验原理与实验完成情况,占课程总成绩的40%;综合实验考核为教师出题和学生自主选题相结合完成某项系统,根据系统功能、代码完成情况、实验报告撰写情况与答辩结果进行评分,占课程总成绩的30%o
六、课程内容实践一数据结构算法设计基础(授课时间第四学期第一周)教学目标数据结构的基本概念和术语、抽象数据类型的表示与实现、算法设计的要求、时间复杂度的概念以及部分算法的时间效率主要内容数据结构与算法绪论、算法的时间效率分析、选择排序、快速排序、堆排序等排序算法分析比较、汉诺塔递归算法分析比较学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践二顺序表及其应用(授课时间第四学期第二周)教学目标理解线性表的顺序表示和实现,顺序表的存储结构,掌握顺序表的基本操作;利用顺序表实现有关问题的求解主要内容线性表的类型定义、顺序表示和实现、顺序表的基本操作;设计算法实现约瑟夫问题、并编程实现有序表的合并问题学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践三链表及其应用(授课时间第四学期第三周)教学目标掌握单链表的表示和实现,单链表的存储结构,掌握单链表的基本操作;利用链表实现有关问题的求解理解并掌握双链表、循环单链表、循环双链表的基本操作,编程实现相关问题的求解主要内容单链表、双链表、循环单链表、循环双链表的类型定义及基本操作;设计算法实现多项式的求和、和求导问题,实现集合并、交、差运算问题学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践四栈及其应用(授课时间第四学期第四周)教学目标理解栈的概念和基本要素,掌握顺序栈和链栈的存储与基本运算的算法,利用栈实现相关问题的求解主要内容顺序栈和链栈的存储结构与基本操作;利用栈实现数制转换;设计算法解决表达式求值问题、掌握设计回溯算法的基本技巧并结合栈用于8皇后问题的求解;编程实现、设计算法求解迷宫问题、顺序栈的公用问题学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践五队列及其应用(授课时间第四学期第五周)教学目标理解队列的概念和基本要素,掌握顺序环形队列和链式队列的存储与基本运算的算法,利用队列实现相关问题的求解主要内容顺序环形队列和链式队列的存储结构与基本操作;利用链式队列编写程序模拟病人到医院看病,排队看医生的情况;以栈模拟停车场,以队列模拟车场外的候车场,编程实现停车场的模拟;设计链表表示轮渡,队列存储到达渡口的车,设计算法实现轮渡的模拟学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践六串及其应用(授课时间第四学期第六周)教学目标理解串的概念和基本要素•,掌握顺序串、链串的基本操作;掌握串的模式匹配的各种算法,利用串实现相关问题的求解主要内容顺序串和链串的存储结构与基本操作;Brute_Force算法、Boyer_Moore算法、kmp算法实现串的模式匹配设计算法进行病毒感染检测,编程实现最长连续相同字符、字符串加密、计数的模式匹配学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践七数组、广义表及其应用(授课时间第四学期第七周)教学目标理解数组、广义表的概念和基本要素,掌握数组、广义表的存储结构和基本运算;实现矩阵的压缩存储,广义表的递归算法;利用数组和广义表实现相关问题的求解主要内容数组的定义、顺序表示和基本运算的实现、矩阵的压缩存储;广义表的定义、存储结构和基本运算、递归算法求广义表深度;设计算法实现存储格式转换问题、矩阵求解魔方问题、两个对称矩阵之和与乘积问题学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践八树及其应用(授课时间第四学期第八周)教学目标理解树、二叉树的定义和基本术语;掌握二叉树的存储结构和基本运算、二又树的各种遍历算法;利用二又树实现相关问题的求解主要内容二叉树的存储结构和基本操作;先序遍历、中序遍历、后序遍历算法的分析比较;设计算法实现二叉树中从根结点到叶子结点的路径、叶子结点个数的计算、由遍历构造二叉树、二叉树任一结点的特征计算学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践九树及其应用(授课时间第四学期第九周)教学目标掌握线索二叉树的算法、树与森林、赫夫曼树及其应用、回溯法与树的遍历;解决一些相关的综合问题主要内容实现中序线索化二叉树的算法、树和森林的遍历算法、利用赫夫曼算法构造赫夫曼树;设计算法实现电文的编码和译码、家族关系查询系统学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践十图及其应用(授课时间第四学期第十周)教学目标掌握图的定义和基本术语、图的存储结构和基本操作、图的遍历利用图解决一些相关问题主要内容图的存储结构数组表示法、邻接表、十字链表、邻接多重表存储图的分析比较、邻接矩阵和邻接表的转化;深度优先遍历、广度优先遍历算法的实现与比较;有向图的路径问题学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践■•一图及其应用(授课时间第四学期第十一周)教学目标掌握图的连通性问题、有向无环图及其应用、最短路径的算法主要内容克鲁斯卡尔算法、普利姆算法的实现;编程实现拓扑排序的序列、求关键路径、关键活动的算法;设计算法求从某个源点到其余各顶点的最短路径和每一对顶点之间的最短路径学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践十二图及其应用(授课时间第四学期第十二周)教学目标利用图解决一些综合性问题主要内容假设以一个带权有向图表示某一区域的公交线路网,图中顶点代表一些区域中的重要站点,弧代表己有的公交路线,弧上的权表示该路线上的票价(或者所需时间),设计一个交通指南系统,指导前来咨询者以最低的票价或最少的时间从区域中的某一站点到达另一站点学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践十三查找及其应用(授课时间第四学期第十三周)教学目标掌握静态查找表、二叉排序树、哈希表及其应用,并利用查找解决一些相关问题主要内容顺序表、有序表的查找算法,二叉排序树查找算法的验证,设计哈希表的创建、查找、元素插入等算法并验证,顺序查找与折半查找的性能比较、线性散列与链式散列的性能比较学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践十四排序及其应用(授课时间第四学期第十四周)教学目标掌握各种内部排序的特点和算法主要内容直接实现插入排序、冒泡排序、选择排序、快速排序、希尔排序、堆排序等6种内部排序算法,比较各算法的比较次数和移动次数学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践十五排序及其应用(授课时间第四学期第十五周)教学目标利用排序解决一些相关问题主要内容修改冒泡排序算法以实现双向冒泡排序;用单链表作为待排序数据的存储结构,在其上实现直接插入排序算法;学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践十六综合实验(授课时间第四学期第十六周)教学目标设计算法实现有关数据结构的综合问题主要内容设计算法、编程实现通讯录管理系统主要涉及线性表的基本操作、查找操作、排序操作、索引表的创建与使用;根据通讯录的操作情况,通讯录的记录可选择顺序表或链表;若提供多种有序显示,如按姓名、关系等通过建立索引表来实现;建立索引表,可按关键字排序,可以对原记录按关键字建立二叉排序树学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验实践十七综合实验(授课时间第四学期第十七周)教学目标设计算法实现有关数据结构的综合问题主要内容校园导游问题,为某校内生活、购物、参观的人们提供行走线路查询、选择、景点介绍的帮助;设计校园游览图,景点不少于6个、设计全景图的显示方式、设计图的存储结构、文件读入或键盘方式输入图的顶点信息和边信息,在内存中创建图;由于景点浏览时不通过遍历获取信息,考虑将景点与景点信息分开存储,道路标志与道路的其他信息分开存储,运用图的存储、遍历、Dijkstra.Floyd算法学时3学时教学方法演示法/讲授/现场指导实验类型设计型实验、综合性实验
七、课程内容调整说明。