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

资源描述

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

《南开大学《数据结构与算法》本科课程教学大纲.docx》由会员分享，可在线阅读，更多相关《南开大学《数据结构与算法》本科课程教学大纲.docx（19页珍藏版）》请在冰点文库上搜索。

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

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

课程名称

数据结构与算法

英文名称

Data Structures and Algorithms

课程编号

1030310170

学分数

总学时

讲授学时

实验、上机、习题等学

时

授课语言（单选）

■ 汉语 □英语 □双语 □其他：

成绩类型（单选）

■ 百分制 □等级制（通过/不通过）

课程负责人

王恺

职称

副教授

课程组成员

赵宏，李敏，王刚，刘哲理

授课专业

理工科非计算机专业

课程类型（可多选）

■ A □B □C □D □E

所需

先导

课程

计算机基础（理）

教

材

作者

名称

出版社

出版时间

赵宏，王恺

数据结构、算法与应用

上海交通大学出版社

2012

参

考

书

目

作者

名称

出版社

出版时间

赵端阳, 左伍

衡

算法分析与设计—以大学生程序设

计竞赛为例

清华大学出版社

2012

严蔚敏, 吴伟

民

数据结构（C 语言版）

清华大学出版社

2007

张铭, 王腾蛟,

赵海燕

数据结构与算法

高等教育出版社

2008

Sartaj Sahni

著汪诗林，

数据结构、算法与应用——C++描

述

机械工业出版社

2009

开课学院：

（公章）

南开大学本科课程教学大纲

孙晓东等译

教学目标

详细说明学生学习课程后在知识、技能、态度等方面达到的状态，陈述应

力求明确、具体，并可以观察和测量，600 字以内

一、知识方面

掌握线性表、栈、队列、树、图等数据结构的基本概念、原理及相关

算法；理解直接插入排序、希尔排序、简单选择排序、冒泡排序、快速排

序等常用排序算法的基本原理；理解顺序查找、二分查找、分块查找、二

叉排序树查找、哈希查找等常用查找算法的基本原理。

二、技能方面

能够应用线性表、栈、队列、树、图等数据结构将实际问题模型化，

并通过选择或设计相关算法来解决实际问题；能够应用各种数据结构的模

板快速编写 C++程序，通过计算机运行程序完成实际问题的求解。

三、思维方面

具备较好的计算思维能力，能够在学习和工作中自觉运用计算的思维

方式更好地解决专业问题。

课程在学生培养中的地位和作用

课程开设的必要性及其在教学计划中对学生培养的作用，400 字以内

一、课程开设的必要性

在解决生活或工作中的一些问题时，通常需要综合运用多种思维方式。

在科学思维的谱系中，真正具备了系统和完善的表达体系的思维模式只有

三个，分别是逻辑思维、实证思维和计算思维。

大学教育中开设数学、物

理和计算机等公共基础课程的主要目的就是对学生这三种思维方式的培养。

作为计算机公共基础系列课程之一，本课程对理工类学生计算思维能力的

培养有着非常重要的作用和意义。

二、在教学计划中对学生培养的作用

本课程是公共计算机基础教学部针对理工类非计算机专业学生开设的

一门校公共必修课。

虽然本课程的教学内容与学生的专业课程无直接联系，

但通过本课程的学习，有助于培养学生的计算思维、使学生自觉运用计算

的思维方式解决日常生活和专业学习中遇到的实际问题，从而进一步促进

学生的专业课程学习、提高学生的专业创新能力。

主要教学手段和方法

为完成教学目标而采用的主要教学方法和手段，以及方法和手段的改革情况，

600 字以内

一、主要教学方法和手段

（1）案例教学

以数据结构为基础、算法设计为主线，通过大量实例讲解如何借助数据

结构来描述实际问题、如何设计算法来解决实际问题，以培养学生的计算思

维为教学目的。

（2）教师课堂讲授和学生自主学习相结合

通过课程教学网站为学生提供用于自主学习的教学资源，方便学生在课

外灵活安排时间巩固教师课堂讲授内容及进行拓展学习。

（3）理论和实践相结合

本课程包括讲授课和上机课，在讲授课上注重讲解基本理论知识，在上

机课上注重提高学生的实践能力。

（4）充分发挥学生主观能动

布置大作业，鼓励学生根据课上教师讲授内容及课外拓展学习内容自己

去选择要解决的问题、设计解决问题的算法、撰写算法设计报告、编写程序

实现问题求解、制作讲稿并讲解。

通过发挥学生的主观能动，激发学生对课

程的兴趣，增强学生对课程内容的理解。

二、方法和手段的改革情况

（1）构建课程教学网站，并逐步丰富用于学生自主学习的课程资源。

（2）以大作业的形式激发学生的主观能动，锻炼学生自觉运用计算的

思维方式解决实际问题的能力、培养学生的写作能力和讲述能力。

考核方式

明确说明考试、平时成绩（讨论、作业、测验、出勤等）、实验实践所占总

成绩比重，以及考试的形式（闭卷、开卷），400 字以内

本课程采用“平时测试+平时成绩+期末考核”的评价方式：

各部分的比

例分别为 30%，20%和 50%。

其中，

平时测试：

在讲授课或上机课上组织 2~3 次测试，由任课教师自己安排。

平时成绩：

由任课老师评定，主要参考作业提交数量、质量、是否及时，

以及理论课、上机课的出勤情况，平时上机测试等情况。

期末考核：

采用机考、闭卷形式。

课程学习要求和建议

对学生学习该课程的相关要求及学习建议，800 字以内

1、正确认识本课程在本科教学计划中的地位和作用，明确本课程的学

习目的。

2、积极发挥主观能动，从被动学习转为主动学习，一方面充分利用课

堂时间进行课程内容的学习和实践，另一方面安排一定的课外时间进行自主

学习。

3、不要局限于课堂上学习的内容，应拓展知识面，在学习基本知识的

同时也要考虑如何借助本课程学习的知识更好地去解决专业学习和研究中遇

到的问题。

4、多动手实践，一方面能够巩固课上所学内容，另一方面能够认识到

学习过程中的一些潜在问题。

课程内容及学时分配

课程内容

理论课时

上机课时

C++内容（模板、复习指针）

第 1 章概论

第 2 章线性表

第 3 章栈和队列

第 4 章数组、字符串与广义表

第 5 章树和二叉树

第 6 章图

第 7 章排序算法

第 8 章查找算法

第 9 章文件

第 10 章算法设计策略应用实例

合计

1. 列出课程主要章节的标题，在每个标题下写出主要内容的细目及学时数。

2. 各教学环节（习题、实验、课堂讨论、写作、社会调查、测验、考试）

的内容和时数。

3. 实验课程要详细列出每个实验的名称、内容、学时数、实验性质（验证

性、综合性、设计性）、实验类别（选做、必做）和实验的分组情况等。

4. 实践教学课程要写出相应的时间、地点、方式、教学内容等。

讲课/上机学时分配为 26/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 字

本课程以数据结构为基础、算法设计为主线，通过大量实例讲解如何借

助数据结构来描述实际问题、如何设计算法来解决实际问题，以培养学生的

计算思维为教学目标。

主要授课内容包括：

各种数据结构的基本概念、原理；借助各种数据结

构的模板快速解决实际问题；常用排序和查找算法；应用问题的经典求解方

法。

本课程是针对理工类非计算机专业学生开设的一门校公共必修课。

虽然

本课程的教学内容与学生的专业课程无直接联系，但通过本课程的学习，有

助于培养学生的计算思维、使学生自觉运用计算的思维方式解决日常生活和

专业学习中遇到的实际问题，从而进一步促进学生的专业课程学习、提高学

生的专业创新能力。

英文课程简要介绍

课程介绍的英文翻译版

Thiscourseprovidesthefundamentalknowledgeofdata

structure and places emphasis on algorithm design. Through a lot

of examples to explain how to use the data structure to describe

thepracticalproblems,howtodesignalgorithmstosolve

practical problems. The main objective of this course is to teach

computational thinking （CT） skills to students.

Topicsinclude:

basicconceptsandprinciplesofdata

structures; the use of data structures template with applications

on solving practical problems; commonly used sorting and searching

algorithms; classical methods for solving application problems.

This course is a general required course for non-computer

students. Although this course may have no direct relations with

the students' major learning, it will help students improving

their computational thinking. As a result, students can better

solve the problems they encountered in daily life, further improve

their learning ability and innovation ability in major learning.

补充说明

修读课程的注意事项、网络资源及其他需要说明的情况，500 字以内

南开大学教育在线（http:

//222.30.60.9）上提供了本课程的基本教学

资源和拓展教学资源，供学生复习和自主学习时使用。

课程负责人

签字

日期：

学院（教学部）分管负责人意见：

签字：

（公章）

日期：

学院（教学部）学术委员会意见：

签字：

日期：

教务处意见：

负责人签字：

（公章）

日期：

展开阅读全文