《数据结构B》教学大纲 课程名称（中文/英文）：数据结构(Data Structure) 课程编号：5201010 学分：4学分 学时：总学时80讲授学时48实验16其它16 开设学期：第2学期 授课对象：信息管理与信息系统专业本科生 课程级别：市级重点建设课程，上海海洋大学精品课程 课程负责人：袁红春 一、课程性质与目的 数据结构是信息类专业的一门综合性的专业基础课。数据结构的研究不仅涉及到计算机 硬件的研究范围，而且和计算机软件的研究有密切的关系，无论是编译程序还是操作系统， 都涉及到数据元素在存储器中的分配问题。可以认为数据结构是介于数学、计算机硬件和计 算机软件三者之间的一门核心课程。在计算机科学中，数据结构不仅是一般程序设计的基础。 而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要 基础。因此，数据结构课程在计算机学科中具有举足轻重的作用。 二、课程简介 本课程主要讲授软件设计中经常遇到的线性表、栈、队列、串、数组、树和二叉树、图 等典型数据结构的逻辑结构、存储结构和操作的实现方法，以及递归算法设计方法和各种典 型排序和查找算法的设计方法。通过本课程的学习，要求学生学会分析、研究计算机加工的 数据对象特性，以便选择适当的数据结构以及相应的算法，并初步掌握算法的时间分析和空 间分析技巧，从而为学习后续计算机类课程打下坚实的理论基础。 三、教学内容 第1章数据结构概念 主要讲述数据结构的基本概念和术语及算法和算法分析。（理论：2学时） 第2章线性表 主要讲述线性表的定义和特点，顺序表、单链表、循环链表和双向链表的类定义及相关 操作实现。（理论：6学时，上机：2学时，其它：2学时） 第3章栈和队列
21 《数据结构 B》教学大纲 课程名称（中文/英文）：数据结构（Data Structure） 课程编号：5201010 学 分：4 学分 学 时：总学时 80 讲授学时 48 实验 16 其它 16 开设学期： 第 2 学期 授课对象：信息管理与信息系统专业本科生 课程级别：市级重点建设课程, 上海海洋大学精品课程 课程负责人：袁红春 一、课程性质与目的 数据结构是信息类专业的一门综合性的专业基础课。数据结构的研究不仅涉及到计算机 硬件的研究范围，而且和计算机软件的研究有密切的关系，无论是编译程序还是操作系统， 都涉及到数据元素在存储器中的分配问题。可以认为数据结构是介于数学、计算机硬件和计 算机软件三者之间的一门核心课程。在计算机科学中，数据结构不仅是一般程序设计的基础， 而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要 基础。因此，数据结构课程在计算机学科中具有举足轻重的作用。 二、课程简介 本课程主要讲授软件设计中经常遇到的线性表、栈、队列、串、数组、树和二叉树、图 等典型数据结构的逻辑结构、存储结构和操作的实现方法，以及递归算法设计方法和各种典 型排序和查找算法的设计方法。通过本课程的学习，要求学生学会分析、研究计算机加工的 数据对象特性，以便选择适当的数据结构以及相应的算法，并初步掌握算法的时间分析和空 间分析技巧，从而为学习后续计算机类课程打下坚实的理论基础。 三、教学内容 第 1 章 数据结构概念 主要讲述数据结构的基本概念和术语及算法和算法分析。（理论:2 学时） 第 2 章 线性表 主要讲述线性表的定义和特点，顺序表、单链表、循环链表和双向链表的类定义及相关 操作实现。（理论:6 学时,上机:2 学时,其它:2 学时） 第 3 章 栈和队列
主要讲述抽象数据类型栈和队列的顺式和链式表示，及其类定义及相关操作实现。（理 论：4学时，上机：2学时，其它：2学时) 第4章数组、串与广义表 主要讲述一维数组与多维数组、特殊矩阵、稀疏矩阵、字符串、广义表的概念、表示 操作及其存储结构的实现。（理论：4学时，上机：2学时，其它：2学时） 第5章树与二叉树 主要讲述树和森林的概念，二叉树、树和森林的逻辑结构和存储结构及其遍历算法，赫 夫曼树及其应用。（理论：6学时，上机：2学时，其它：2学时） 第6章集合与字典 主要讲述集合及其表示、并查集与等价类、字典、跳表、散列。（理论：4学时，上机：2 学时，其它：2学时) 第7章搜索结构 主要讲述静态搜索表、二叉搜索树、最优二叉搜索树、AL树伸展树和红黑树。 (理论：4学时，上机：2学时，其它：2学时) 第8章图 主嬰讲述图的基本概念、图的存储表示、图的遍历和连通性、最小生成树、最短路径和 活动网络。（理论：8学时，上机：2学时，其它：2学时） 第9章排序 主要讲述插入排序、交换排序、选择排序、归并排序和基数排序等各种内部排序的方法 及实现。（理论：6学时，上机：2学时，其它：2学时） 第10章文件、外部排序与搜索 主要讲述主存储器和外存储器、文件组织、外排序、多级索引结构、可扩充散列 和Trie树。(4学时) 四、教学基本要求 教师在课堂上应对数据结构的基本概念、软件设计中经常遇到的线性表、栈、队列、串、 数组、树与森林、图等典型数据结构的逻辑结构、存储结构和操作的实现方法，以及递归算 法、各种典型排序和查找算法进行必要的讲授，并详细讲授每章的重点、难点内容：讲授中 应注意理论联系实际，通过必要的案例展示、讨论，启迪学生的思维，加深学生对有关概念。 理论等内容的理解，并应采用多媒体辅助教学，加大课堂授课的知识含量。 22
22 主要讲述抽象数据类型栈和队列的顺式和链式表示，及其类定义及相关操作实现。 （理 论:4 学时,上机:2 学时,其它:2 学时） 第 4 章 数组、串与广义表 主要讲述一维数组与多维数组、特殊矩阵、稀疏矩阵、字符串、广义表的概念、表示、 操作及其存储结构的实现。（理论:4 学时,上机:2 学时,其它:2 学时） 第 5 章 树与二叉树 主要讲述树和森林的概念，二叉树、树和森林的逻辑结构和存储结构及其遍历算法，赫 夫曼树及其应用。（理论:6 学时,上机:2 学时,其它:2 学时） 第 6 章 集合与字典 主要讲述集合及其表示、并查集与等价类、字典、跳表、散列。（理论:4 学时,上机:2 学时,其它:2 学时） 第 7 章 搜索结构 主要讲述静态搜索表、二叉搜索树、最优二叉搜索树、AVL 树伸展树和红黑树。 （理论:4 学时,上机:2 学时,其它:2 学时） 第 8 章 图 主要讲述图的基本概念、图的存储表示、图的遍历和连通性、最小生成树、最短路径和 活动网络。（理论:8 学时,上机:2 学时,其它:2 学时） 第 9 章 排序 主要讲述插入排序、交换排序、选择排序、归并排序和基数排序等各种内部排序的方法 及实现。（理论:6 学时,上机:2 学时,其它:2 学时） 第 10 章 文件、外部排序与搜索 主要讲述主存储器和外存储器、文件组织、外排序、多级索引结构、可扩充散列 和 Trie 树。（4 学时） 四、教学基本要求 教师在课堂上应对数据结构的基本概念、软件设计中经常遇到的线性表、栈、队列、串、 数组、树与森林、图等典型数据结构的逻辑结构、存储结构和操作的实现方法，以及递归算 法、各种典型排序和查找算法进行必要的讲授，并详细讲授每章的重点、难点内容；讲授中 应注意理论联系实际，通过必要的案例展示、讨论，启迪学生的思维，加深学生对有关概念、 理论等内容的理解，并应采用多媒体辅助教学，加大课堂授课的知识含量
五、教学方法 从面向21世纪信息类专业人才培养需求出发，以培养创新精神和提高实践能力为目 标，改变课程内容繁、难、偏、旧和偏重书本知识的现状。为此本课程采用多种教学方法， 充分发挥学生学习的潜能和积极性。 ()以问题驱动提高学生学习兴趣 数据结构理论是从解决实际问题中产生、总结并提高的，那么它也必然以解决更多实际 问题为其归宿，所以数据结构的理论学习和解决实际问题是紧密结合的。例如，栈的应用： 火车调度问题；哈夫曼树的应用：电文编码：图的应用：工程或网络通讯造价问题等。这些 程序的实现不仅有助于数据结构课程的学习，更主要的是通过这些程序的实现，大大提高了 学生编程能力和解决实际问题的能力。 (2)以启发式教学培养创新能力 创新思维是培养学生创造力的基础，是学生进行创新活动的前提。在教学中有意识地培 养学生的创新思维能力，可以提高学生理论联系实际的能力、发现问题以及灵活独特地解决 问题的能力。因此，要从实际教学内容出发，适当引入难易适中的实例分析，采用启发式教 学方法，强调把教学内容设置到复杂的、有意义的实际问题环境中，让学生通过解决实际问 题，来理解和掌握隐含于问题背后的知识，提高解决问题的能力，从而提高创新思维能力。 (③)以灵活的教学方式培养学生的自主学习能力 在教学形式上有以教师为主体的集中课堂教学形式，还有适合学生自学方式的分组学习 形式或自主实验时间。通过教师留讨论题目，学生按项目小组通过查阅文献探究相关知识， 并在课堂上进行互相交流。教师引导学生利用己有的知识、经验建构新的相关知识。以此激 发学生的学习潜能，进而取得良好的教学效果。既可以起到教师的主导作用，也可以满足学 生个性化学习的需求与肯定学生个别的表现。提高了学生的自主学习能力。 六、参考教材和阅读书目 参考教材： 殷人昆编著，数据结构（用面向对象方法与C+语言描述）（第二版），清华大学出版社 2010年。 阅读书目： 1.严蔚敏，吴伟民编若，《数据结构》，出版社：清华大学出版社，2004年 2.严蔚敏，吴伟民编著，《数据结构题集(C语言版)》，清华大学出版社，1999年 3.徐孝凯，殷人昆编若，《数据结构实验》，中央广播电视大学出版社，2003年 23
23 五、教学方法 从面向 21 世纪信息类专业人才培养需求出发，以培养创新精神和提高实践能力为目 标，改变课程内容繁、难、偏、旧和偏重书本知识的现状。为此本课程采用多种教学方法， 充分发挥学生学习的潜能和积极性。 (1) 以问题驱动提高学生学习兴趣 数据结构理论是从解决实际问题中产生、总结并提高的，那么它也必然以解决更多实际 问题为其归宿，所以数据结构的理论学习和解决实际问题是紧密结合的。例如，栈的应用： 火车调度问题; 哈夫曼树的应用：电文编码；图的应用：工程或网络通讯造价问题等。这些 程序的实现不仅有助于数据结构课程的学习, 更主要的是通过这些程序的实现, 大大提高了 学生编程能力和解决实际问题的能力。 (2) 以启发式教学培养创新能力 创新思维是培养学生创造力的基础，是学生进行创新活动的前提。在教学中有意识地培 养学生的创新思维能力，可以提高学生理论联系实际的能力、发现问题以及灵活独特地解决 问题的能力。因此，要从实际教学内容出发，适当引入难易适中的实例分析，采用启发式教 学方法，强调把教学内容设置到复杂的、有意义的实际问题环境中，让学生通过解决实际问 题，来理解和掌握隐含于问题背后的知识，提高解决问题的能力，从而提高创新思维能力。 (3) 以灵活的教学方式培养学生的自主学习能力 在教学形式上有以教师为主体的集中课堂教学形式，还有适合学生自学方式的分组学习 形式或自主实验时间。通过教师留讨论题目，学生按项目小组通过查阅文献探究相关知识， 并在课堂上进行互相交流。教师引导学生利用已有的知识、经验建构新的相关知识。以此激 发学生的学习潜能，进而取得良好的教学效果。既可以起到教师的主导作用，也可以满足学 生个性化学习的需求与肯定学生个别的表现。提高了学生的自主学习能力。 六、参考教材和阅读书目 参考教材： 殷人昆编著，数据结构(用面向对象方法与 C++语言描述)（第二版），清华大学出版社， 2010 年。 阅读书目： 1. 严蔚敏, 吴伟民编著, 《数据结构》, 出版社: 清华大学出版社, 2004 年. 2. 严蔚敏, 吴伟民编著, 《数据结构题集(C 语言版) 》, 清华大学出版社, 1999 年. 3. 徐孝凯, 殷人昆编著, 《数据结构实验》, 中央广播电视大学出版社, 2003 年
4.股人昆，徐孝凯编若。《数据结构习题解析》，清华大学出版社，2002年 七、本课程与其它课程的联系与分工 本课程是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及 其它系统程序和大型应用程序的重要基础，各章应重点讲授各种数据结构的基本概念、逻辑 结构、物理结构和算法实现。 主撰人：袁红春 审核人：袁红春 分管教学院长：沙荣方 2011年9月23日 《算法设计与分析B》教学大纲 课程名称（中文/英文）：算法设计与分析(Design and Analysis of Algorithms) 课程编号：5201012 学分：2学分 学时：总学时32，讲授学时24，上机学时8 开设学期：第6学期 授课对象：信息管理与信息系统专业本科生 课程级别：信息管理与信息系统专业教有高地建设课程 课程负责人：袁红春 教学团队：袁红春，李净，王令群 一、课程性质与目的 算法设计与分析B是信息管理与信息系统专业的学科选修课。本课程的学习目的如下： 一方面需要学习求解计算领域中典型问题的各种有效算法，在遇到问题时能灵活地应用所学 握的方法技巧：另一方面还要学习设计新算法和分析算法性能的方法，当没有现成可用的算 法时，能够创造出有效的问题求解方法。 二、课程简介 本课程主要讲授以下内容：算法基本概念、算法的复杂度、算法设计与分析步骤：递归
24 4. 殷人昆, 徐孝凯编著, 《数据结构习题解析》, 清华大学出版社, 2002 年 七、本课程与其它课程的联系与分工 本课程是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及 其它系统程序和大型应用程序的重要基础，各章应重点讲授各种数据结构的基本概念、逻辑 结构、物理结构和算法实现。 主撰人：袁红春 审核人：袁红春 分管教学院长：沙荣方 2011 年 9 月 23 日 《算法设计与分析 B》教学大纲 课程名称（中文/英文）： 算法设计与分析（Design and Analysis of Algorithms） 课程编号：5201012 学 分：2 学分 学 时：总学时 32 ， 讲授学时 24， 上机学时 8 开设学期： 第 6 学期 授课对象：信息管理与信息系统专业本科生 课程级别： 信息管理与信息系统专业教育高地建设课程 课程负责人：袁红春 教学团队：袁红春，李净，王令群 一、课程性质与目的 算法设计与分析 B 是信息管理与信息系统专业的学科选修课。本课程的学习目的如下： 一方面需要学习求解计算领域中典型问题的各种有效算法，在遇到问题时能灵活地应用所掌 握的方法技巧；另一方面还要学习设计新算法和分析算法性能的方法，当没有现成可用的算 法时，能够创造出有效的问题求解方法。 二、课程简介 本课程主要讲授以下内容：算法基本概念、算法的复杂度、算法设计与分析步骤；递归
技术概念、递归方程的建立与求解、递归消除：分治法概念及其典型应用案例：贪心法概念 及其典型应用案例：动态规划概念及其典型应用案例：回湖法概念及其典型应用案例：分支 限界法概念及其典型应用案例：概率算法概念及四种典型的概率算法：NP问画概念、P类 与P类问题、P完全问题：近似算法等。通过学习，使学生了解典型的算法设计策略，掌 握基本的算法设计和分析方法，为编写高质量的程序打下基础。 三、教学内容 第一章算法橛述（理论2学时） 对分析算法的抽象表示、算法渐进复杂度以及如何对算法进行设计与分析作简要的阐 述。 第二章递归技术(4学时) 主要内容：递归技术概述，aoi塔问题，递归方程的建立与求解，递归消除。 学习要求：掌握递归的概念，学会用递归方法解决实际问题，熟练掌握递归算法的复杂 度（时间和空间）分析方法。 第三章分治法（理论2学时，上机2学时） 主要内容：分治法概述，二分检索技术，找第K小元素，分治乘法，棋盘覆盖，分治合 并排序，分治快速排序。 学习要求：掌握利用分治策略设计算法，解决实际问题，学会分治算法的复杂度分析。 第四章贪心法（理论2学时，上机2学时） 主要内容：贪心算法概述，背包问题，磁带存储，作业调度，启发式算法。 学习要求：掌挥利用贪心算法解决问题的基本思想，会用某高级语言编写贪心算法解决 问题的程序，并能对算法的复杂度、可靠性进行分析。 第五章动态规划（理论2学时，上机2学时） 主要内容：动态规划的概述，最短路径，0/1背包问题，多矩阵乘积，TSP问题，资源 分配。 学习要求：掌握利用动态规划方法解决问题的基本思想，会用某高级语言编写动态规划 解决问题的程序，并能对算法的复杂度进行分析。 第六章回湖法（理论2学时，上机2学时） 主要内容：回溯法概述，一皇后问题，图的m着色问题，批处理作业调度问题。 学习要求：掌握利用回溯法解决问题的基本思想，会用某高级语言编写回溯法解决问题 的程序，并能准确地分析回潮法的效率及稳定性。 25
25 技术概念、递归方程的建立与求解、递归消除；分治法概念及其典型应用案例；贪心法概念 及其典型应用案例；动态规划概念及其典型应用案例；回溯法概念及其典型应用案例；分支 限界法概念及其典型应用案例；概率算法概念及四种典型的概率算法；NP 问题概念、P 类 与 NP 类问题、NP 完全问题；近似算法等。通过学习, 使学生了解典型的算法设计策略, 掌 握基本的算法设计和分析方法, 为编写高质量的程序打下基础。 三、教学内容 第一章 算法概述（理论 2 学时） 对分析算法的抽象表示、算法渐进复杂度以及如何对算法进行设计与分析作简要的阐 述。 第二章 递归技术（4 学时） 主要内容：递归技术概述，Hanoi 塔问题，递归方程的建立与求解，递归消除。 学习要求：掌握递归的概念，学会用递归方法解决实际问题，熟练掌握递归算法的复杂 度（时间和空间）分析方法。 第三章 分治法（理论 2 学时，上机 2 学时） 主要内容：分治法概述，二分检索技术，找第 K 小元素，分治乘法，棋盘覆盖，分治合 并排序，分治快速排序。 学习要求：掌握利用分治策略设计算法，解决实际问题，学会分治算法的复杂度分析。 第四章 贪心法（理论 2 学时，上机 2 学时） 主要内容：贪心算法概述，背包问题，磁带存储，作业调度，启发式算法。 学习要求：掌握利用贪心算法解决问题的基本思想，会用某高级语言编写贪心算法解决 问题的程序，并能对算法的复杂度、可靠性进行分析。 第五章 动态规划（理论 2 学时，上机 2 学时） 主要内容：动态规划的概述，最短路径，0/1 背包问题，多矩阵乘积，TSP 问题，资源 分配。 学习要求：掌握利用动态规划方法解决问题的基本思想，会用某高级语言编写动态规划 解决问题的程序，并能对算法的复杂度进行分析。 第六章 回溯法（理论 2 学时，上机 2 学时） 主要内容：回溯法概述，n-皇后问题，图的 m 着色问题，批处理作业调度问题。 学习要求：掌握利用回溯法解决问题的基本思想，会用某高级语言编写回溯法解决问题 的程序，并能准确地分析回溯法的效率及稳定性