《数据构造课程教学大纲.docx》由会员分享，可在线阅读，更多相关《数据构造课程教学大纲.docx（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据构造课程教学大纲（数据构造）教学大纲课程性质专业必修课课程名称数据构造课程编号*04069适用专业计算机科学与技术/软件工程开课学期第3学期总学时64理论50学分数4实践14一、课程性质与目的数据构造课程属于专业必修课。通过本课程数据构造的学习，学生应实现如下目的：1.知识目的：本课程主要讲述线性表、栈、队列、字符串、数组、树、二叉树、图、查找表、内部排序等常用数据构造的基本概念、操作及其典型应用例子。通过本课程的学习，应使学生把握数据构造的概念及不同的存储构造、把握一些典型算法原理和方法，且能够在不同存储构造上实现编程，同时，对于算法设计的方式和技巧也有所体会。2.能力目的1独立获取知识
2、的能力逐步把握科学的学习方法，不断地扩展知识面，加强独立考虑的能力，更新知识构造；2科学观察和思维的能力运用数据构造的基本理论，熟悉各种基本数据构造及其操作，学会根据实际问题要求来选择数据构造。3分析问题和解决问题的能力学会利用数据构造原理分析实际问题，提高发现问题与解决问题的能力。对部分优秀的学生，培养其在知名程序设计在线评测系统如POJ等中求解实际问题的能力。4务实精神通过数据构造理论课程教学，培养学生严谨务实的科学态度和刻苦钻研的作风。5实践能力通过学习，有意识地培养学生编写高质量、高效率程序的能力和风格。3.素质目的：使学生具备一定的计算思维，热爱算法设计和程序实现，面对实际问题能转换
3、为计算机能够求解的经过并选择适宜的数据构造，设计出在时间和空间上具备一定高效率的程序，培养学生学习算法设计与实现的细心和耐心，培养学生坚定不移，攀登技术高峰的优秀品质。让部分优秀的学生热爱上湖南省大学生程序设计竞赛，体会ACM程序设计竞赛的魅力。二、课程教学基本要求课程前应该认真预习，十分是前导课程相关知识体系;课中应该认真听课，介入教学经过中的互动、回答问题及联络实际编程;课后积极做好温习、认真完成作业及课程设计相关实践教学的环节。作业应具备一定实用性的数据构造和算法实现为主，对部分优秀学生，引入一定量的知名程序设计在线评测系统如POJ等中与数据构造相关的题目进行编程并在线提交验证正确性与时
4、间、空间效率。三、教学内容与学时分配课程教学内容与学时分配序号教学模块主要教学内容学时1课程导论什么叫数据构造，数据的逻辑构造与存储构造的概念1课时数据类型与抽象数据类型算法的定义、算法复杂度课程的用处、学习要求与建议，考核方式讲明2线性表线性表的概念和特点，线性表的逻辑构造定义、各种存储结构的描绘方法和ADT定义4课时线性表的顺序表示和实现线性表的链式表示和实现双向链表和循环链表简介3栈和队列栈的概念和特点，栈的逻辑构造定义、各种存储构造的描绘方法和ADT定义6课时栈的顺序表示和实现栈的链式表示和实现队列的概念和特点，队列的逻辑构造定义、各种存储构造的描绘方法和ADT定义队列的顺序表示和实现
5、队列的链式表示和实现4数组和字符串数组的定义、顺序表示和实现2课时矩阵的压缩存储：特殊矩阵；稀疏矩阵字符串的概念和特点及ADT定义字符串的形式匹配算法KMP算法选讲5树和二叉树树的概念和特点，树的逻辑构造定义、各种存储构造的描绘方法和ADT定义11课时树的先根遍历、后根遍历、层次遍历的特点和实现二叉树的定义、性质和存储构造二叉树的遍历：先序遍历、中序遍历、后序遍历、层次遍历的特点和实现树、森林与二叉树的转换；树和森林的遍历；Huffman树的创立与Huffman编码的算法及实现树与等价问题并查集字典树Trie树6图和网图的定义、特点和相关术语13课时图的数据构造表示：邻接矩阵、邻接表、边集数组
6、等图的遍历：深度优先搜索；广度优先搜索欧拉道路/回路、汉密尔顿/回路的概念，以及判定欧拉道路/回路的Fluery算法选讲关节点和重连通问题及寻找连通图的关节点的Targan算法选讲最小生成树的概念及MST性质、寻找连通图的最小生成树的Prim和Kruskal算法有向无环图的拓扑排序问题及其算法有向无环图的关键途径问题及其算法非负边权值图的最短途径问题1：单源点最短途径问题及Dijsktra算法的原理和实现非负边权值图的最短途径问题2：每一对顶点之间的最短途径问题及Floyed算法简介选讲带负边权值图的最短途径问题：SPFA算法及其实现7查找线性表的查找技术：无序线性表的顺序查找、已序线性表的二
7、分查找6课时二叉排序树的概念，在二叉排序树中查找、插入结点、删除结点的算法实现二叉平衡树的概念和相关算法简介B-树和B+树简介选讲Hash散列技术：Hash表的查找与冲突解决方法8内排序内排序的概念、排序的稳定性7课时插入排序：直接插入排序、折半插入排序、希尔排序的原理与实现；交换排序：冒泡排序、快速排序的原理与实现；选择排序：简单项选择择排序、堆排序的原理与实现；归并排序的原理与实现；分配排序：桶排序的原理与实现；基数排序简介选讲各种内部排序方法的比拟注：1.课后作业布置应引入程序设计在线评测系统如POJ等中的数据构造相关题目，对于计算思维和代码编写能力较强的学生，应鼓励其在程序设计在线评测
8、系统如POJ等中多做题目并提交验证；2.对于标注“选讲的内容，当班级整体基础和接受能力较差时，能够不在课堂讲授，也不纳入考试范围，但应在课后组织班上计算思维和接受能力较强的学生学习选讲内容。课内实验教学内容与学时分配序号实验项目名称内容摘要实验学时实验类型开出要求1线性表线性表中元素的查找、插入、删除，把握vector容器和list容器的使用。可参考北京大学算法与程序设计在线评测系统题目POJ1208TheBlocksProblem文档视界2022/0e936934a31614791711cc7931b765ce05087a82pnazq1pyk0z.html/problem?id=1208，
9、编写代码并在线提交验证明验结果。可以由老师选择OJ系统中其他线性表相关的题目。1验证性必做2栈通过表达式求值把握栈中元素的入栈、出栈、获取栈顶元素的操作，把握stack容器的使用。可参考北京大学算法与程序设计在线评测系统题目POJ2106BooleanExpressions文档视界2022/0e936934a31614791711cc7931b765ce05087a82pnazq1pyk0z.html/problem?id=2106，编写代码并在线提交验证明验结果。可以由老师选择OJ系统中其他栈相关的题目。2验证性必做3队列把握队列中元素的入队、出队、获取队首和队尾元素的操作，把握queue容
10、器和deque容器的使用。可参考北京大学算法与程序设计在线评测系统题目POJ2259TeamQueue文档视界2022/0e936934a31614791711cc7931b765ce05087a82pnazq1pyk0z.html/problem?id=2259，编写代码并在线提交验证明验结果。可以由老师选择OJ系统中其他队列相关的题目。1验证性必做4二叉树二叉树的创立和遍历。可参考北京大学算法与程序设计在线评测系统题目POJ1577FallingLeaves文档视界2022/0e936934a31614791711cc7931b765ce05087a82pnazq1pyk0z.html/p
11、roblem?id=1577，编写代码并在线提交验证明验结果。可以由老师选择OJ系统中其他二叉树的题目。1验证性必做5Huffman树与Huffman编码根据给定的叶子结点的权值，创立Huffman树，并对每个叶子结点进行Huffman编码。可参考北京大学算法与程序设计在线评测系统题目POJ1521Entropy文档视界2022/0e936934a31614791711cc7931b765ce05087a82pnazq1pyk0z.html/problem?id=1521，编写代码并在线提交验证明验结果。可以由老师选择OJ系统中其他Huffman树相关的题目。2验证性必做6最小生成树分别使用P
12、rim算法或Kruscal算法，找出给定的无向连通图的最小生成树并计算最小生成树的每一条边上的权值之和。可参考北京大学算法与程序设计在线评测系统题目POJ2485Highways文档视界2022/0e936934a31614791711cc7931b765ce05087a82pnazq1pyk0z.html/problem?id=2485，编写代码并在线提交验证明验结果。可以由老师选择OJ系统中其他最小生成树的题目。2验证性必做7最短路径使用Dikjstra算法或SPFA算法，在给定的不带负权边的图中，计算从给定顶点出发到其余各个顶点的最短途径的长度。可参考北京大学算法与程序设计在线评测系统题
13、目POJ2502Subway题文档视界2022/0e936934a31614791711cc7931b765ce05087a82pnazq1pyk0z.html/problem?id=2502，编写代码并在线提交验证明验结果。可以由老师选择OJ系统中其他最短途径相关的题目。2验证性必做8树表查找在二叉排序树或二叉平衡树中实现结点的查找，以及结点的动态添加和删除，把握set/multiset容器和map/multimap容器的使用。可参考北京大学算法与程序设计在线评测系统题目POJ2021RelativeRelatives文档视界2022/0e936934a31614791711cc7931b7
14、65ce05087a82pnazq1pyk0z.html/problem?id=2021，编写代码并在线提交验证明验结果。可以由老师选择OJ系统中其他树表查找相关的题目。1验证性必做9Hash表查找创立一个Hash表，并在Hash表中查找元素和添加元素，对Hash冲突进行处理。可参考北京大学算法与程序设计在线评测系统题目POJ3349Snowflake1验证性必做SnowSnowflakes题文档视界2022/0e936934a31614791711cc7931b765ce05087a82pnazq1pyk0z.html/problem?id=3349，编写代码并在线提交验证明验结果。可以由老
15、师选择OJ系统中其他Hash技术相关的题目。10堆排序通过大根堆或小根堆把握堆排序的实现和应用，掌握priority_queue容器的使用。可参考北京大学算法与程序设计在线评测系统题目POJ2567CodetheTree文档视界2022/0e936934a31614791711cc7931b765ce05087a82pnazq1pyk0z.html/problem?id=2567，编写代码并在线提交验证明验结果。可以由老师选择OJ系统中其他堆排序相关的题目。1验证性必做注：1.“实验类型主要分为演示性、验证性、综合性和设计性实验。2.“开出要求可分为必修或选修二种形式。四、教学方法与手段本课程
16、主要采用课堂讲授+上机指导为主，并辅以案例教学、启发式教学，分组讨论，多媒体课件，观看相关视频演示、引入程序设计在线评测系统做相关习题并在线验证结果、引入企业程序员招聘中与数据构造有关的题目作为案例等多种教学方法。对于重要的思想、原理、重点和难点在课堂上予以讲授；布置需要上机操作的练习；建立有效的考核机制催促、监管学生的学习成效。五、考核方式及成绩评定细则考核方式：1.期末考试：闭卷、笔试，考试时间不应少于100分钟，但也不应超过120分钟，成绩评定采用计分制满分100分；题型采用选择题、填空题、判定题、简答题、算法设计、算法实现题等多种形式组成卷面分，满分100分，60分及格。2.实践环节：
17、见实验教学信息部分本课程总成绩评定：1.综合成绩评定采用计分制，满分100分，60分及格。综合考核成绩平常成绩0.3期末考试成绩0.7。2.平常成绩包含出勤、作业/实验组成，按100分制计分。出勤占总平常成绩的40%，以每周点名次数为根据，作业/实验占总平常成绩60%。卷面分评分标准：成绩按实际成绩录入。等级等级描绘优秀10090分字迹工整、卷面整洁，90%以上的试题解答正确良好8980分字迹工整、卷面整洁，80%以上的试题解答正确中等7970分字迹较工整、卷面较整洁，70%以上的试题解答正确及格6960分字迹基本工整、卷面基本整洁，60%以上的试题解答正确不及格60下面字迹模糊、卷面书写零乱
18、；超过40%的试题解答不正确作业/实验布置应引入程序设计在线评测系统如POJ等中的数据构造相关题目，尽量让学生提交源代码电子版，评阅成绩的标准根据相关规定，成绩一般可分为优秀、良好、中、及格、不及格五个等级，评分细则如下：等级等级描绘优秀10090分学习态度认真端正，独立完成作业/实验，代码运行结果正确、算法与数据构造设计合理、时间效率和空间效率高效、代码构造优良、可读性和可维护性强、根据正确格式进行输入或者输出、提交作业按时按质按量。良好8980分学习态度认真端正，独立完成作业/实验或者对教师和同学依靠很少，代码运行结果正确、算法与数据构造设计合理、时间效率和空间效率高效、但代码构造不够优良
19、、可读性和可维护性不强、或者没能根据指定的格式进行输入和输出，或者提交作业略有拖延。中等7970分学习态度较为端正，独立性弱，在教师和同学的屡次指导和帮助下才完成作业/实验，代码运行结果正确、算法与数据构造设计合理、时间效率和空间效率高效、但代码构造不够优良、可读性和可维护性不强，并且没能根据指定的格式进行输入和输出，或者提交作业有一定拖延。及格6960分学习态度一般，对教师和同学的依靠很大，只能勉强看懂教师或同学的代码照着做，代码运行结果正确，但效率不高，代码构造不合理、可读性糟糕、没能根据指定的格式进行输入和输出，或者提交作业拖延现象严重。不及格60下面学习态度很不端正，代码出现编译错误、
20、算法与数据构造设计不合理或无法体现和理性、时间效率和空间效率达不到要求或无法验证、源代码构造混乱、可读性和可维护性很差，或者明显抄袭，无法回答教师针对作业的提问。情况严重者可计0分。六、教材与参考资料推荐教材：（数据构造C语言版），严蔚敏、吴伟民编著，清华大学出版社，2021.参考资料1（数据构造与算法分析新视角），周幸妮、任智源、马彦卓、樊凯编著，电子工业出版社，2021.2（挑战程序设计竞赛2算法和数据构造），日渡部有隆编著，支鹏浩翻译，人民邮电出版社，2021.3（数据构造编程实验：大学程序设计课程与竞赛训练教材第2版），吴永辉、王建德编著，机械工业出版社，2021.4（算法竞赛宝典3基础数据构造），张新华编著，清华大学出版社，2021.5（数据构造STL版），王晓东、陈道蓄编著，清华大学出版社，2020.6（数据构造算法与解析STL版），高一凡编著，清华大学出版社，2021.7（数据构造C+语言版第3版），邓俊辉编著，清华大学出版社，2021.8（程序员代码面试指南：IT名企算法与数据构造题目最优解），左程云编著，电子工业出版社，2021.9（图解数据构造第2版），胡昭民编著，清华大学出版社，2021.大纲执笔人：邹竞系教研室审核人：学院部审定人：