南开大学《数据结构与算法》本科课程教学大纲

南开大学本科课程教学大纲开课学院：（公章）课程名称数据结构与算法英文名称DataStructuresandAlgorithms课程编号1030310170030312学分数3总学时62讲授学时32实验、上机、习题等学时30授课语言（单选）■汉语□英语□双语□其他：成绩类型（单选）■百分制□等级制（通过/不通过）课程负责人王恺职称副教授课程组成员赵宏，李敏，王刚，刘哲理授课专业理工科非计算机专业课程类型（可多选）■A□B□C□D□E所需先导课程计算机基础（理）教材作者名称出版社出版时间赵宏，王恺数据结构、算法与应用上海交通大学出版社2012参考书目作者名称出版社出版时间赵端阳,左伍衡算法分析与设计—以大学生程序设计竞赛为例清华大学出版社2012严蔚敏,吴伟民数据结构（C语言版）清华大学出版社2007张铭,王腾蛟,赵海燕数据结构与算法高等教育出版社2008SartajSahni著汪诗林，孙晓东等译数据结构、算法与应用——C++描述机械工业出版社2009教学目标详细说明学生学习课程后在知识、技能、态度等方面达到的状态，陈述应力求明确、具体，并可以观察和测量，600字以内一、知识方面掌握线性表、栈、队列、树、图等数据结构的基本概念、原理及相关算法；理解直接插入排序、希尔排序、简单选择排序、冒泡排序、快速排序等常用排序算法的基本原理；理解顺序查找、二分查找、分块查找、二叉排序树查找、哈希查找等常用查找算法的基本原理；掌握标准模板库中vector、string、set、multiset、map、multimap、deque、list、stack、queue、priority_queue等常用容器的使用方法。二、技能方面能够应用线性表、栈、队列、树、图等数据结构将实际问题模型化，并通过选择或设计相关算法来解决实际问题；能够应用标准模板库中的容器快速编写C++程序，通过计算机运行程序完成实际问题的求解。三、思维方面具备较好的计算思维能力，能够在学习和工作中自觉运用计算的思维方式更好地解决专业问题。课程在学生培养中的地位和作用课程开设的必要性及其在教学计划中对学生培养的作用，400字以内一、课程开设的必要性在解决生活或工作中的一些问题时，通常需要综合运用多种思维方式。在科学思维的谱系中，真正具备了系统和完善的表达体系的思维模式只有三个，分别是逻辑思维、实证思维和计算思维。大学教育中开设数学、物理和计算机等公共基础课程的主要目的就是对学生这三种思维方式的培养。作为计算机公共基础系列课程之一，本课程对理工类学生计算思维能力的培养有着非常重要的作用和意义。二、在教学计划中对学生培养的作用本课程是公共计算机基础教学部针对理工类非计算机专业学生开设的一门校公共必修课。虽然本课程的教学内容与学生的专业课程无直接联系，但通过本课程的学习，有助于培养学生的计算思维、使学生自觉运用计算的思维方式解决日常生活和专业学习中遇到的实际问题，从而进一步促进学生的专业课程学习、提高学生的专业创新能力。主要教学手段和方法为完成教学目标而采用的主要教学方法和手段，以及方法和手段的改革情况，600字以内一、主要教学方法和手段（1）案例教学以数据结构为基础、算法设计为主线，通过大量实例讲解如何借助数据结构来描述实际问题、如何设计算法来解决实际问题，以培养学生的计算思维为教学目的。（2）教师课堂讲授和学生自主学习相结合通过课程教学网站为学生提供用于自主学习的教学资源，方便学生在课外灵活安排时间巩固教师课堂讲授内容及进行拓展学习。（3）理论和实践相结合本课程包括讲授课和上机课，在讲授课上注重讲解基本理论知识，在上机课上注重提高学生的实践能力。（4）充分发挥学生主观能动布置大作业，鼓励学生根据课上教师讲授内容及课外拓展学习内容自己去选择要解决的问题、设计解决问题的算法、撰写算法设计报告、编写程序实现问题求解、制作讲稿并讲解。通过发挥学生的主观能动，激发学生对课程的兴趣，增强学生对课程内容的理解。二、方法和手段的改革情况（1）构建课程教学网站，并逐步丰富用于学生自主学习的课程资源。（2）以大作业的形式激发学生的主观能动，锻炼学生自觉运用计算的思维方式解决实际问题的能力、培养学生的写作能力和讲述能力。考核方式明确说明考试、平时成绩（讨论、作业、测验、出勤等）、实验实践所占总成绩比重，以及考试的形式（闭卷、开卷），400字以内本课程采用“大作业+平时成绩+期末考核”的评价方式：各部分的比例分别为20%，30%和50%。其中，大作业：学生自主选题，分析问题、选取数据结构、设计算法、编程实现、撰写报告、制作讲稿、讲解并回答教师提出的问题。平时成绩：由任课老师评定，主要参考作业提交数量、质量、是否及时，以及理论课、上机课的出勤情况，平时上机测试等情况。期末考核：采用机考、闭卷形式。课程学习要求和建议对学生学习该课程的相关要求及学习建议，800字以内1、正确认识本课程在本科教学计划中的地位和作用，明确本课程的学习目的。2、积极发挥主观能动，从被动学习转为主动学习，一方面充分利用课堂时间进行课程内容的学习和实践，另一方面安排一定的课外时间进行自主学习。3、不要局限于课堂上学习的内容，应拓展知识面，在学习基本知识的同时也要考虑如何借助本课程学习的知识更好地去解决专业学习和研究中遇到的问题。4、多动手实践，一方面能够巩固课上所学内容，另一方面能够认识到学习过程中的一些潜在问题。课程内容及学时分配列出课程主要章节的标题，在每个标题下写出主要内容的细目及学时数。各教学环节（习题、实验、课堂讨论、写作、社会调查、测验、考试）的内容和时数。实验课程要详细列出每个实验的名称、内容、学时数、实验性质（验证性、综合性、设计性）、实验类别（选做、必做）和实验的分组情况等。实践教学课程要写出相应的时间、地点、方式、教学内容等。第1部分概论教师讲授内容：数据结构基础，算法与算法分析基础学生自学内容：算法设计基本方法与策略基础要求：理解数据结构和算法的基本概念，掌握算法的时间复杂度和空间复杂度分析方法，了解基本的算法设计策略。学时：讲授2学时。第2部分线性表及基于线性表的问题求解教师讲授内容：线性表及其抽象数据类型，线性表的顺序存储结构及实现，线性表的链式存储结构及实现，vector容器、list容器和deque容器。学生自学内容：string容器、set容器、multiset容器、map容器、multimap容器、应用实例（教材第2.4节）。上机实习1顺序表的操作（2学时）（1）对于最多由100名学生的姓名和成绩信息（如王洪，90）构成的线性表，采用顺序存储结构并完成下面的问题。①统计成绩大于等于95分的人数，并输出这些学生的姓名。②删除成绩小于20分的信息。③以60分为分界线，将表中所有小于60的信息放在表的前半部分，大于60的元素放在表的后半部分。（2）有两个顺序表S1和S2，假设他们的元素值从左到右递增排列，且没有重复值。设计一个Merge函数，该函数的功能是将这两个表合并成一个元素值仍由小到大排列的顺序表S。（3）用顺序表解决选旅长的问题（有10个驴友需要选出一个负责人——旅长。大家制定了选旅长的规则：所有人围成一圈，从1到10为每个人进行编号，并设定一个数字N。然后，从编号为1的驴友开始按照编号顺序循环报数，数到N的驴友出圈，重复此过程，最后剩下那个驴友就是旅长。）上机实习2线性链表的操作（2学时）（1）对于最多由100名学生的姓名和成绩信息（王洪，90）构成的线性表建立单向链表，并完成下面的问题：①统计成绩大于等于95分的人数，并输出这些学生的姓名。②删除成绩小于20分的信息。③以60分为分界线，将表中所有小于60的信息放在表的前半部分，大于60的元素放在表的后半部分。（2）有两个带表头结点的存放整数的单向链表Link1和Link2，假设他们的元素值从左到右递增排列，且没有重复值。设计一个Merge函数，该函数的功能是将这两个单向链表合并成一个元素值仍由小到大排列的单向链表Link。（3）设计算法并测试。将单向链表中关键字的值重复的结点删除，使得链表中各结点的值均不相同。要求：理解线性表的基本概念和抽象数据类型；掌握线性表的顺序存储结构和链式存储结构；能够应用线性表解决实际问题；了解线性表的C++实现方法；了解循环链表和双向链表。学时：讲授4学时，上机4学时。第3部分栈和队列及基于栈和队列的问题求解教师讲授内容：栈及其抽象数据类型，栈的表示及实现，队列及抽象数据类型，队列的表示及实现，stack容器、queue容器和priority_queue容器。学生自学内容：应用实例（教材第3.5节）。要求：理解栈和队列的基本概念和抽象数据类型；掌握栈和队列的顺序表示、链式表示及其C++实现方法，能够应用栈和队列解决实际问题。上机实习1栈的操作（2学时）（1）用栈实现【例3-1】中将十进制数转换为其他各种进制（如二进制、八进制、十六进制）数的问题。（2）请利用已有的基本操作，实现栈元素的正序输出，并编写主函数就进行测试。主函数要求先建立一顺序栈S，若干个元素依次入栈，然后执行“Print(S);”语句，在屏幕上按输入的顺序输出栈中的元素。例如，将1、3、5、7、9、11、13、15等元素依次入栈，输出结果仍然是1、3、5、7、9、11、13、15。（3）用栈的特性来解决一个生活中的实际问题。例如，把一个字符串倒序输出。上机实习2队列的操作（2学时）（1）使用队列实现【例3-2】中的在屏幕上显示杨辉三角的问题。（2）编写程序实现利用一个队列中的元素创建一个栈的算法，将队列的头作为栈顶，队列的尾作为栈底，创建栈后队列保持不变。学时：讲授4学时，上机4学时。第4部分树和二叉树及基于树和二叉树的问题求解教师讲授内容：树的基本概念，二叉树及其基本性质，二叉树的抽象数据类型和表示方式，二叉树顺序表示的实现，二叉树的遍历及常用操作，二叉树遍历的递归实现。学生自学内容：二叉树链式存储、二叉树遍历及常用操作的C++实现，哈夫曼树和哈夫曼码，树的表示法，树、森林与二叉树的转换。要求：掌握树的定义、表示形式和基本术语；掌握二叉树的定义和基本性质；掌握二叉树的顺序表示和链式表示方法；二叉树顺序表示的C++实现，掌握二叉树的遍历和常用操作及二叉树递归遍历算法的C++实现；了解哈夫曼树和哈夫曼码的基本概念、哈夫曼树的构造方法及哈夫曼码的编解码方法；了解树的双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法；了解树、森林转换为二叉树的方法，及二叉树转换为树、森林的方法；了解二叉树链式存储、二叉树遍历及常用操作的C++实现；了解二叉树和树的应用；能够应用二叉树和树解决实际问题。上机实习1二叉树的操作（2学时）（1）构建一棵链式表示的二叉树，其中每一结点保存一个整数，且任一结点中的整数值大于其左子树各结点中的整数值、小于其右子树各结点中的整数值。假设将值为43、56、37、28、17、39、22、70的各结点依次插入到二叉树中，插入完毕后采用中序遍历方式输出二叉树中每一结点的整数值。（2）构建一棵链式表示的二叉树，其中每一结点保存一名学生信息（包括学号、姓名和成绩），且任一结点中学生的学号大于其左子树各结点中学生的学号、小于其右子树各结点中学生的学号。假设将以下六名学生信息依次插入到二叉树中：("1102030","李刚",65)、("1102035","王涛",92)、("1102041","吴明",73)、("1102023","马洪",85)、("1102033","赵冰",90)、("1102045","陈立",88)，插入完毕后分别在二叉树中查找学号为1102033和1102037的结点，若查找成功则将结点中保存的学生信息输出，否则输出“查找失败！”。上机实习2哈夫曼树和哈夫曼码（2学时）（1）假设要编码的字符集为{A,B,C,D,E,F}，各字符的出现次数为{20,5,13,8,23,3}，构造一棵哈夫曼树。（2）利用第1题中构造的哈夫曼树，得到字符串“FACE”的哈夫曼编码，再将编码结果输入到哈夫曼树中，得到解码结果“FACE”。学时：讲授4学时，上机4学时。第5部分图及基于图的问题求解教师讲授内容：图的基本概念及特性，图的抽象数据类型和表示方式，图的遍历。学生自学内容：图的C++实现，最小生成树和最短路径。要求：掌握图的基本概念和应用；掌握图的邻接矩阵表示法、邻接压缩表表示法和邻接链表表示法；掌握图的广度优先遍历和深度优先遍历方法；掌握最小生成树和最短路径的计算方法；能够应用图解决实际问题；了解图的C++实现方法。上机实习图的操作（4学时）（1）实现【例5-1】，城市之间修建高速公路的工程造价如图5-4（a）所示。（2）实现【例5-2】，从一个地方到另一个地方的里程数如图5-4（b）所示。（3）构建一个人际关系网：假设有李刚、王涛、吴明、马洪、赵冰、陈立6个人，其中(李刚,王涛)、(李刚,马洪)、（李刚,赵冰）、（王涛,赵冰）、（吴明,马洪）、（马洪,陈立）是朋友关系。请编程实现该人际关系网，并按关系远近输出与吴明有直接或间接关系的人（如马洪是吴明的朋友；陈立、李刚是马洪的朋友，即吴明的朋友的朋友；王涛、赵冰是李刚的朋友，即吴明的朋友的朋友的朋友）。学时：讲授4学时，上机4学时。第6部分排序算法教师讲授内容：排序算法及常见排序算法比较，插入排序，选择排序（堆排序不讲），交换排序（快速排序只讲原理、不讲实现）。学生自学内容：堆排序、快速排序的C++实现、归并排序、箱排序和基数排序的C++实现。要求：掌握各种排序算法的适用情况；理解直接插入排序、希尔排序、简单选择排序和冒泡排序的基本原理，并掌握其C++实现方法；理解快速排序的基本原理，并了解其C++实现方法；了解堆排序、归并排序、箱排序和基数排序的基本原理其C++实现方法。上机实习插入排序、选择排序和交换排序（3学时）假设有以下6名学生的信息（包括学号、姓名和成绩）：("1102030","李刚",65)、("1102035","王涛",92)、("1102041","吴明",73)、("1102023","马洪",85)、("1102033","赵冰",90)、("1102045","陈立",88)。分别用冒泡排序算法、希尔排序算法和快速排序算法，按学号从低到高对学生信息进行排序并将排序结果输出。学时：讲授3学时，上机3学时。第7部分查找算法教师讲授内容：查找算法及常见查找算法比较，静态查找及其实现，动态查找（只讲原理、不讲实现）。学生自学内容：动态查找的C++实现，哈希查找及其C++实现。要求：掌握各种查找算法的适用情况；理解顺序查找、折半查找和分块查找的基本原理，并掌握其C++实现方法；掌握二叉排序树的生成和查找方法，并了解其C++实现方法；掌握哈希表、哈希函数和冲突的处理方法，了解哈希查找的C++实现方法。上机实习1静态查找（1学时）假设有以下6名学生的信息（包括学号、姓名和成绩）：("1102023","马洪",85)、("1102030","李刚",65)、("1102033","赵冰",90)、("1102035","王涛",92)、("1102041","吴明",73)、("1102045","陈立",88)。分别用顺序查找算法和折半查找算法，按学号对学生信息进行查找。上机实习2动态查找和哈希查找（2学时）假设有以下6名学生的信息（包括学号、姓名和成绩）：("1102030","李刚",65)、("1102035","王涛",92)、("1102041","吴明",73)、("1102023","马洪",85)、("1102033","赵冰",90)、("1102045","陈立",88)。分别用二叉排序树查找算法按姓名对学生信息进行查找和哈希算法、用哈希算法，按学号对学生信息进行查找。学时：讲授3学时，上机3学时。第8部分经典实例教师讲授内容：分治策略，贪心策略，动态规划策略，回溯策略，分支限界策略。学生自学内容：使用各种算法设计策略解决实际问题的应用实例。要求：掌握分治策略、贪心策略、动态规划策略、回溯策略和分支限界策略的基本思想、算法设计步骤及程序模式；能够使用这些策略设计问题求解算法；了解应用算法设计策略求解实际问题的C++实现方法。上机实习《数据结构与算法》课程大作业（8学时）3~7人一组，上机课上每组学生派一名代表按PPT讲稿讲解所求解的问题和具体求解算法（讲解时间在4~6分钟），讲解后教师或其他学生向该组中的每名学生问1~3个问题，根据回答情况给每名学生打不同的分数。评分标准如下：评分项评分内容分值选题（5分）选题难易程度5文档（10分）是否按时提交（第12周及之前提交给满分，每晚一周扣1分，最晚不得超过第14周）3问题描述是否清楚2求解算法描述是否清楚3文档（包括Word文档和PPT讲稿）是否规范2讲解（5分）讲解是否清楚2回答问题是否正确3学时：讲授8学时，上机8学时。课程简要介绍简要介绍课程的目标、主要授课内容、授课对象以及在学生培养中的作用，200—500字本课程以数据结构为基础、算法设计为主线，通过大量实例讲解如何借助数据结构来描述实际问题、如何设计算法来解决实际问题，以培养学生的计算思维为教学目标。主要授课内容包括：各种数据结构的基本概念、原理；标准模板库的使用方法，借助标准模板库快速解决实际问题；常用排序和查找算法；应用问题的经典求解方法。本课程是针对理工类非计算机专业学生开设的一门校公共必修课。虽然本课程的教学内容与学生的专业课程无直接联系，但通过本课程的学习，有助于培养学生的计算思维、使学生自觉运用计算的思维方式解决日常生活和专业学习中遇到的实际问题，从而进一步促进学生的专业课程学习、提高学生的专业创新能力。英文课程简要介绍课程介绍的英文翻译版Thiscourseprovidesthefundamentalknowledgeofdatastructureandplacesemphasisonalgorithmdesign.Throughalotofexamplestoexplainhowtousethedatastructuretodescribethepracticalproblems,howtodesignalgorithmstosolvepracticalproblems.Themainobjectiveofthiscourseistoteachco