南开大学《数据结构与算法》本科课程教学大纲Word文件下载.doc
《南开大学《数据结构与算法》本科课程教学大纲Word文件下载.doc》由会员分享，可在线阅读，更多相关《南开大学《数据结构与算法》本科课程教学大纲Word文件下载.doc（11页珍藏版）》请在冰点文库上搜索。
职称
副教授
课程组成员
赵宏，李敏，王刚，刘哲理
授课专业
理工科非计算机专业
课程类型（可多选）
■A□B□C□D□E
所需
先导
课程
计算机基础（理）
教
材
作者
名称
出版社
出版时间
赵宏，王恺
数据结构、算法与应用
上海交通大学出版社
2012
参
考
书
目
赵端阳,左伍衡
算法分析与设计—以大学生程序设计竞赛为例
清华大学出版社
严蔚敏,吴伟民
数据结构（C语言版）
2007
张铭,王腾蛟,赵海燕
高等教育出版社
2008
SartajSahni著汪诗林，孙晓东等译
数据结构、算法与应用——C++描述
机械工业出版社
2009
教学目标
详细说明学生学习课程后在知识、技能、态度等方面达到的状态，陈述应力求明确、具体，并可以观察和测量，600字以内
一、知识方面
掌握线性表、栈、队列、树、图等数据结构的基本概念、原理及相关算法；
理解直接插入排序、希尔排序、简单选择排序、冒泡排序、快速排序等常用排序算法的基本原理；
理解顺序查找、二分查找、分块查找、二叉排序树查找、哈希查找等常用查找算法的基本原理。
二、技能方面
能够应用线性表、栈、队列、树、图等数据结构将实际问题模型化，并通过选择或设计相关算法来解决实际问题；
能够应用各种数据结构的模板快速编写C++程序，通过计算机运行程序完成实际问题的求解。
三、思维方面
具备较好的计算思维能力，能够在学习和工作中自觉运用计算的思维方式更好地解决专业问题。
课程在学生培养中的地位和作用
课程开设的必要性及其在教学计划中对学生培养的作用，400字以内
一、课程开设的必要性
在解决生活或工作中的一些问题时，通常需要综合运用多种思维方式。
在科学思维的谱系中，真正具备了系统和完善的表达体系的思维模式只有三个，分别是逻辑思维、实证思维和计算思维。
大学教育中开设数学、物理和计算机等公共基础课程的主要目的就是对学生这三种思维方式的培养。
作为计算机公共基础系列课程之一，本课程对理工类学生计算思维能力的培养有着非常重要的作用和意义。
二、在教学计划中对学生培养的作用
本课程是公共计算机基础教学部针对理工类非计算机专业学生开设的一门校公共必修课。
虽然本课程的教学内容与学生的专业课程无直接联系，但通过本课程的学习，有助于培养学生的计算思维、使学生自觉运用计算的思维方式解决日常生活和专业学习中遇到的实际问题，从而进一步促进学生的专业课程学习、提高学生的专业创新能力。
主要教学手段和方法
为完成教学目标而采用的主要教学方法和手段，以及方法和手段的改革情况，600字以内
一、主要教学方法和手段
（1）案例教学
以数据结构为基础、算法设计为主线，通过大量实例讲解如何借助数据结构来描述实际问题、如何设计算法来解决实际问题，以培养学生的计算思维为教学目的。
（2）教师课堂讲授和学生自主学习相结合
通过课程教学网站为学生提供用于自主学习的教学资源，方便学生在课外灵活安排时间巩固教师课堂讲授内容及进行拓展学习。
（3）理论和实践相结合
本课程包括讲授课和上机课，在讲授课上注重讲解基本理论知识，在上机课上注重提高学生的实践能力。
（4）充分发挥学生主观能动
布置大作业，鼓励学生根据课上教师讲授内容及课外拓展学习内容自己去选择要解决的问题、设计解决问题的算法、撰写算法设计报告、编写程序实现问题求解、制作讲稿并讲解。
通过发挥学生的主观能动，激发学生对课程的兴趣，增强学生对课程内容的理解。
二、方法和手段的改革情况
（1）构建课程教学网站，并逐步丰富用于学生自主学习的课程资源。
（2）以大作业的形式激发学生的主观能动，锻炼学生自觉运用计算的思维方式解决实际问题的能力、培养学生的写作能力和讲述能力。
考核方式
明确说明考试、平时成绩（讨论、作业、测验、出勤等）、实验实践所占总成绩比重，以及考试的形式（闭卷、开卷），400字以内
本课程采用“平时测试+平时成绩+期末考核”的评价方式：
各部分的比例分别为30%，20%和50%。
其中，
平时测试：
在讲授课或上机课上组织2~3次测试，由任课教师自己安排。
平时成绩：
由任课老师评定，主要参考作业提交数量、质量、是否及时，以及理论课、上机课的出勤情况，平时上机测试等情况。
期末考核：
采用机考、闭卷形式。
课程学习要求和建议
对学生学习该课程的相关要求及学习建议，800字以内
1、正确认识本课程在本科教学计划中的地位和作用，明确本课程的学习目的。
2、积极发挥主观能动，从被动学习转为主动学习，一方面充分利用课堂时间进行课程内容的学习和实践，另一方面安排一定的课外时间进行自主学习。
3、不要局限于课堂上学习的内容，应拓展知识面，在学习基本知识的同时也要考虑如何借助本课程学习的知识更好地去解决专业学习和研究中遇到的问题。
4、多动手实践，一方面能够巩固课上所学内容，另一方面能够认识到学习过程中的一些潜在问题。
课程内容及学时分配
1.列出课程主要章节的标题，在每个标题下写出主要内容的细目及学时数。
2.各教学环节（习题、实验、课堂讨论、写作、社会调查、测验、考试）的内容和时数。
3.实验课程要详细列出每个实验的名称、内容、学时数、实验性质（验证性、综合性、设计性）、实验类别（选做、必做）和实验的分组情况等。
4.实践教学课程要写出相应的时间、地点、方式、教学内容等。
讲课/上机学时分配为26/26，剩余课时教师灵活掌握，可安排习题课、答疑课等。
课程内容
理论课时
上机课时
C++内容（模板、复习指针）
5
第1章概论
2
第2章线性表
4
第3章栈和队列
第4章数组、字符串与广义表
第5章树和二叉树
第6章图
第7章排序算法
第8章查找算法
第9章文件
第10章算法设计策略应用实例
合计
26
C++内容（模板、复习指针）（3/5）
教师讲课内容：
模板（1.5学时）、复习指针（1.5学时）
第1章概论（2/0）
数据结构基础，算法与算法分析基础
学生自学内容：
算法设计基本方法与策略基础（考试不要求）
要求：
理解数据结构和算法的基本概念，掌握算法的时间复杂度和空间复杂度分析方法，了解基本的算法设计策略。
第2章线性表（4/4）
线性表及其抽象数据类型，线性表的顺序存储结构及实现，线性表的链式存储结构及实现。
学生自学内容（教材第2.4节）：
应用实例（考试要求会应用线性表解决实际问题），循环链表和双向链表（考试不要求）。
理解线性表的基本概念和抽象数据类型；
掌握线性表的顺序存储结构和链式存储结构及其C++实现方法，能够应用线性表解决实际问题；
了解循环链表和双向链表。
第3章栈和队列（4/4）
栈及其抽象数据类型，栈的表示及实现，队列及抽象数据类型，队列的表示及实现。
学生自学内容（教材第3.5节）：
应用实例（考试要求会应用栈和队列解决实际问题）。
理解栈和队列的基本概念和抽象数据类型；
掌握栈和队列的顺序表示、链式表示及其C++实现方法，能够应用栈和队列解决实际问题。
第4章数组与字符串（0/0）
数组与矩阵、字符串，应用实例（本章内容考试都不要求）。
理解数组及数组的抽象数据类型；
掌握一维数组和二维数组的表示及实现；
了解矩阵的定义、操作、表示与实现；
了解特殊矩阵与稀疏矩阵；
能够应用数组和矩阵解决实际问题；
了解字符串及其抽象数据类型、字符串的表示及实现、字符串的模式匹配。
第5章树和二叉树（4/4）
树的基本概念，二叉树及其基本性质，二叉树的抽象数据类型和表示方式，二叉树顺序表示的实现，二叉树的遍历及常用操作，二叉树遍历的递归实现。
二叉树链式存储（考试不要求）、二叉树遍历及常用操作的C++实现（考试要求），哈夫曼树和哈夫曼码（考试不要求），树的表示法（考试不要求），树、森林与二叉树的转换（考试不要求）。
掌握树的定义、表示形式和基本术语；
掌握二叉树的定义和基本性质；
掌握二叉树的顺序表示和链式表示方法；
二叉树顺序表示的C++实现，掌握二叉树的遍历和常用操作及二叉树递归遍历算法的C++实现；
了解哈夫曼树和哈夫曼码的基本概念、哈夫曼树的构造方法及哈夫曼码的编解码方法；
了解树的双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法；
了解树、森林转换为二叉树的方法，及二叉树转换为树、森林的方法；
了解二叉树链式存储、二叉树遍历及常用操作的C++实现；
了解二叉树和树的应用；
能够应用二叉树和树解决实际问题。
第6章图（2/2）
图的基本概念及特性，图的抽象数据类型和表示方式，图的遍历。
图的C++实现（考试不要求），最小生成树和最短路径（考试不要求）。
掌握图的基本概念和应用；
掌握图的邻接矩阵表示法、邻接压缩表表示法和邻接链表表示法；
掌握图的广度优先遍历和深度优先遍历方法；
了解图的C++实现方法；
了解最小生成树和最短路径的计算方法；
能够应用图解决实际问题。
第7章排序算法（4/4）
排序算法及常见排序算法比较，插入排序，选择排序（不包括堆排序），交换排序。
堆排序和归并排序（考试要求）、箱排序和基数排序（考试不要求）。
掌握各种排序算法的适用情况；
理解直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序的基本原理，并掌握其C++实现方法；
了解箱排序和基数排序的基本原理其C++实现方法。
第8章查找算法（3/3）
查找算法及常见查找算法比较，静态查找及其实现，动态查找。
哈希查找的原理（考试要求），哈希查找的C++实现（考试不要求）。
掌握各种查找算法的适用情况；
理解顺序查找、折半查找和分块查找的基本原理，并掌握其C++实现方法；
掌握二叉排序树的生成和查找方法及其C++实现方法；
掌握哈希表、哈希函数和冲突的处理方法，了解哈希查找的C++实现方法。
第9章文件（0/0）
文件的基本概念，顺序文件，索引文件，散列文件，多关键字文件，归并排序（本章内容考试都不要求）。
了解文件的基本概念；
了解顺序文件、散列文件、多关键字文件的数据组织方式；
了解归并排序及其C++实现方法。
第10章算法设计策略及应用实例（0/0）
算法设计策略及C++程序实现（考试时会有算法类的程序题，有可能会涉及到一些算法设计策略，但不会考本章原题）。
掌握分治策略、贪心策略、动态规划策略、回溯策略和分支限界策略的基本思想、算法设计步骤及程序模式；
能够使用这些策略设计问题求解算法；
掌握应用算法设计策略求解实际问题的C++实现方法。
课程简要介绍
简要介绍课程的目标、主要授课内容、授课对象以及在学生培养中的作用，200—500字
本课程以数据结构为基础、算法设计为主线，通过大量实例讲解如何借助数据结构来描述实际问题、如何设计算法来解决实际问题，以培养学生的计算思维为教学目标。
主要授课内容包括：
各种数据结构的基本概念、原理；
借助各种数据结构的模板快速解决实际问题；
常用排序和查找算法；
应用问题的经典求解方法。
本课程是针对理工类非计算机专业学生开设的一门校公共必修课。
英文课程简要介绍
课程介绍的英文翻译版
Thiscourseprovidesthefundamentalknowledgeofdatastructureandplacesemphasisonalgorithmdesign.Throughalotofexamplestoexplainhowtousethedatastructuretodescribethepracticalproblems,howtodesignalgorithmstosolvepracticalproblems.Themainobjectiveofthiscourseistoteachcomputationalthinking（CT）skillstostudents.
Topicsinclude:
basicconceptsandprinciplesofdatastructures;
theuseofdatastructurestemplatewithapplicationsonsolvingpracticalproblems;
commonlyusedsortingandsearchingalgorithms;
classicalmethodsforsolvingapplicationproblems.
Thiscourseisageneralrequiredcoursefornon-computerstudents.Althoughthiscoursemayhavenodirectrelationswiththestudents'
majorlearning,itwillhelpstudentsimprovingtheircomputationalthinking.Asaresult,studentscanbettersolvetheproblemstheyencounteredindailylife,furtherimprovetheirlearningabilityandinnovationabilityinmajorlearning.
补充说明
修读课程的注意事项、网络资源及其他需要说明的情况，500字以内
南开大学教育在线（http:
//222.30.60.9）上提供了本课程的基本教学资源和拓展教学资源，供学生复习和自主学习时使用。
签字
日期：
学院（教学部）分管负责人意见：
签字：
（公章）
学院（教学部）学术委员会意见：
教务处意见：
负责人签字：
（公章）
升级会员 