主要介绍递归的定义，执行过程及常见问题的递归程序分析与设计方法。要求学生掌握 递归设计的方法并能给出常规问题的递归算法。 分治与平衡 通过介绍向题解决的分治思想，给出几个典型问题的分治设计思想，包括合并排序、快 速排序、归并排序、堆排序等 集合运算 介绍集合的概念及其计算机上的实现，包括集合上的基本操作、二叉检索、最优二叉检 索树等。 算法设计技术 是本课程的重点章节，通过对典型问题的分析给出分析和解决算法问题的常规方法，这 些方法包括：分治法、贪心法、动态规划、分枝限界法、回溯法等。要求学生掌握各种方的 思想和设计方法，掌握各种方法中的典型案例算法的设计与分析。 五、教学方法 本课程涉及了常见算法分析方法和算法设计技术，比较抽象且难懂。建议采用案例教学 并结合演示让学生理解和掌握各种算法设计方法，通过课堂讨论、课后作业，加强学生对各 种算法设计方法的掌握。 考核主要考察学生应用算法设计方法来解决具体问题的能力，建议由算法设计与实现 (程序设计)、期末考试和出勤三部分构成，分别占20%、70%和10%。算法设计与实现部 分共可在平时课程教学过程中完成。 教师除课堂教学外，可利用网络教学平台，电子郎件等方法收缴作业和答疑。 六、参考教材和阅读书目 1.计算机算法设计与分析王晓东电子工业出版社出版2007年 2.算法设计与分析曹新谱湖南科学技术出版社1984年 3.算法设计与分析朱洪等上海科学技术文献出版社1989年 4.算法设计与分析周培德 机械工业出版社 1996年 七、本课程与其它课程的联系与分工 本课程先修课程：程序设计语言、数据结构、高等数学、概率论。 主撰人：骆解民
36 主要介绍递归的定义，执行过程及常见问题的递归程序分析与设计方法。要求学生掌握 递归设计的方法并能给出常规问题的递归算法。 分治与平衡 通过介绍问题解决的分治思想，给出几个典型问题的分治设计思想，包括合并排序、快 速排序、归并排序、堆排序等 集合运算 介绍集合的概念及其计算机上的实现，包括集合上的基本操作、二叉检索、最优二叉检 索树等。 算法设计技术 是本课程的重点章节，通过对典型问题的分析给出分析和解决算法问题的常规方法，这 些方法包括：分治法、贪心法、动态规划、分枝限界法、回溯法等。要求学生掌握各种方的 思想和设计方法，掌握各种方法中的典型案例算法的设计与分析。 五、教学方法 本课程涉及了常见算法分析方法和算法设计技术，比较抽象且难懂。建议采用案例教学 并结合演示让学生理解和掌握各种算法设计方法，通过课堂讨论、课后作业，加强学生对各 种算法设计方法的掌握。 考核主要考察学生应用算法设计方法来解决具体问题的能力，建议由算法设计与实现 （程序设计）、期末考试和出勤三部分构成，分别占 20% 、70%和 10%。算法设计与实现部 分共可在平时课程教学过程中完成。 教师除课堂教学外，可利用网络教学平台，电子邮件等方法收缴作业和答疑。 六、参考教材和阅读书目 1. 计算机算法设计与分析 王晓东 电子工业出版社出版 2007 年 2. 算法设计与分析 曹新谱 湖南科学技术出版社 1984 年 3. 算法设计与分析 朱洪等 上海科学技术文献出版社 1989 年 4. 算法设计与分析 周培德 机械工业出版社 1996 年 七、本课程与其它课程的联系与分工 本课程先修课程：程序设计语言、数据结构、高等数学、概率论。 主撰人：骆解民
审核人：骆解民 分管教学院长：沙荣方 2011年8月20日 《数据结构》教学大纲 课程名称（中文/英文）：数据结构(Data Structure 课程编号：5201030 学分：4学分 学时：总学时80讲授学时64实验学时16 开设学期：第3学期 授课对象：本科生 课程级别： 课程负责人：张书台 一、课程性质与目的 数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核 心课程，是高级程序设计语言、编译原理、操作系统、数据库、人工智能等课程的基础。同 时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。数 据结构课程集中讨论软件开发过程中的设计阶段、同时设计编码和分析阶段的若干基本问 题。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。 教学要求： 1.掌握各种数据结构的特点及实现方法和适用范围 2.培养学生阅读、分析和设计算法的能力 3.进行必要的分析设计基木技能训练 4.掌握常规设计方法和技巧 二、课程简介 本课程是空间信息与数字技术专业基础课。“数据结构”是计算机专业的核心课程，是 从事计算机软件开发和应用人员必备的专业基础。随着计算机的日益普及，“数据结构”课 程也在不断地发展。从面向对象的概念、对象类设计的风格和数据结构的层次开始，从线性 结构到非线性结构，从简单到复杂，深入地讨论了各种数据结构内在的逻辑关系及其在计算
37 审核人：骆解民 分管教学院长：沙荣方 2011 年 8 月 20 日 《数据结构》教学大纲 课程名称（中文/英文）：数据结构（Data Structure） 课程编号：5201030 学 分：4 学分 学 时：总学时 80 讲授学时 64 实验学时 16 开设学期： 第 3 学期 授课对象：本科生 课程级别： 课程负责人：张书台 一、课程性质与目的 数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核 心课程，是高级程序设计语言、编译原理、操作系统、数据库、人工智能等课程的基础。同 时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。数 据结构课程集中讨论软件开发过程中的设计阶段、同时设计编码和分析阶段的若干基本问 题。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。 教学要求： 1. 掌握各种数据结构的特点及实现方法和适用范围 2. 培养学生阅读、分析和设计算法的能力 3. 进行必要的分析设计基本技能训练 4. 掌握常规设计方法和技巧 二、课程简介 本课程是空间信息与数字技术专业基础课。“数据结构”是计算机专业的核心课程，是 从事计算机软件开发和应用人员必备的专业基础。随着计算机的日益普及，“数据结构”课 程也在不断地发展。从面向对象的概念、对象类设计的风格和数据结构的层次开始，从线性 结构到非线性结构，从简单到复杂，深入地讨论了各种数据结构内在的逻辑关系及其在计算
机中的实现方式和使用。主要讲解数据结构和算法设计与分析的基本知识，各种基本数据结 构的定义，存储结构、相应的算法以及应用，掌握基本的数据结构与算法的关系。培养计算 机专业的学生结合实际应用，设计有效的算法和数据结构的能力，数据结构的内容包括抽象、 实现和评价三个层次，从数据表示和数据处理上看有五个基本组成“要素”分别是逻辑结构 存储结构、基本运算、算法及不同数据结构的比较与算法分析。通过学习，使学生初步具备 分析问题、解决问题的能力，养成良好的程序设计风格，积聚和提高基本的分析设计能力。 为后续课程的学习打下坚实的基础。 三、教学内容 第一章数据结构概论(6学时) 主要内容：C+的预备知识，数据结构的概念，抽象形式，ADT的C+类，算法的定义 和算法性能分析与度量。 学习要求：掌握基本的C+的知识，理解概念包括：数据、数据对象和数据源书，数据 结构，数据类型，数据抽象，数据抽象类型，数据结构的抽象层次，面向对象，对象与类的 关系，类的继承关系，对象间的消息通信等。算法的五个特性，如何评价算法的性能 自学：C+基础知识 讨论：线性结构与非线性结构：面向对象，算法分析 第二章线性表(4学时) 主要内容：线性表，线性表的存储形式，顺序表，单链表，循环链表，以及单链表的应 用。 学习要求：线性表的特点，单链表的定义，相应操作的实现，单链表和双向循环链表的 异同，热练掌握单链表的操作。 自学：单链表的应用 讨论：线性结构与内存结构 第三章栈和队列(6学时) 主要内容：栈和队列，优先级队列，双端队列，递归 学习要求：熟练掌握栈和队列的特点以及操作，了解递归的概念。 自学：栈的应用，队列的应用 讨论：栈和队列的差异 第四章数组串和广义表(6学时) 38
38 机中的实现方式和使用。主要讲解数据结构和算法设计与分析的基本知识，各种基本数据结 构的定义，存储结构、相应的算法以及应用，掌握基本的数据结构与算法的关系。培养计算 机专业的学生结合实际应用，设计有效的算法和数据结构的能力。数据结构的内容包括抽象、 实现和评价三个层次，从数据表示和数据处理上看有五个基本组成“要素”分别是逻辑结构， 存储结构、基本运算、算法及不同数据结构的比较与算法分析。通过学习，使学生初步具备 分析问题、解决问题的能力，养成良好的程序设计风格，积聚和提高基本的分析设计能力。 为 后续课程的学习打下坚实的基础。 三、教学内容 第一章 数据结构概论（6 学时） 主要内容：C++的预备知识，数据结构的概念，抽象形式，ADT 的 C++类,算法的定义 和算法性能分析与度量。 学习要求：掌握基本的 C++的知识，理解概念包括：数据、数据对象和数据源书，数据 结构，数据类型，数据抽象，数据抽象类型，数据结构的抽象层次，面向对象，对象与类的 关系，类的继承关系，对象间的消息通信等。算法的五个特性，如何评价算法的性能。 自学：C++基础知识 讨论：线性结构与非线性结构；面向对象，算法分析 第二章 线性表（4 学时） 主要内容：线性表，线性表的存储形式，顺序表，单链表，循环链表，以及单链表的应 用。 学习要求：线性表的特点，单链表的定义，相应操作的实现，单链表和双向循环链表的 异同，熟练掌握单链表的操作。 自学：单链表的应用 讨论：线性结构与内存结构 第三章 栈和队列（6 学时） 主要内容：栈和队列，优先级队列，双端队列，递归 学习要求：熟练掌握栈和队列的特点以及操作，了解递归的概念。 自学：栈的应用，队列的应用 讨论：栈和队列的差异 第四章 数组串和广义表（6 学时）
主要内容：数组，特殊矩阵，稀疏矩阵，字符串和广义表 学习要求：熟练掌握数组，特殊矩阵和稀疏矩阵的数据存储形式，掌握存储地址的计算。 了解广义表和字符串的概念和存储形式。 自学：字符串的匹配 讨论：多维数组和稀疏矩阵、特殊矩阵的存储形式，广义表的表示 第五章树(8学时) 主要内容：树，二叉树，二叉树的遍历，线索二叉树，树和森林 学习要求：树的定义，数的抽象数据类型，二叉树的定义，二叉树的性质，二叉树的抽 象数据类型，存储表示。掌握二叉树的遍历。对于线索化二叉树，要求理解什么是线索。掌 握堆的定义及其实现方法。最后掌握Huffman树的实现方法和Huffman编码。树和森林的 转换，树的存储表示。 自学：堆的应用，最优判定树 讨论：二叉树的遍历，二叉树的生成 第六章集合和字典(6学时) 主要内容：集合和字典，跳表，散列 学习要求：理解集合及其表示方法，并查集的实现方法。掌握散列函数和散列方法 自学：跳表的应用，并查集的应用 讨论：二叉树的遍历，二叉树的生成 第七章搜索结构(8学时) 主要内容：静态搜索结构，二叉搜索树，AVL树，伸展树和红黑树 学习要求：掌握静态搜索结构，二叉搜索树的概念，插入和删除算法以及性能分析， AVL树的概念，AVL数的插入、删除以及平衡化的旋转，了解伸展树和红黑树的概念 自学：红黑树的插入和删除 讨论：二叉搜索树的应用 第八章图(8学时) 主要内容：图的概念，图的存储结构，图的遍历以及最小生成树，最短路径和AOV.AOE 网络 学习要求：掌握图的概念，图的存储结构，图的深度优先和广度优先遍历，最小生成树 的生成方法。最短路径算法以及AOV,AOE网络。 自学：任意权值的单源最短路径，所有定点之间的最短路径，重连通分量 39
39 主要内容：数组，特殊矩阵，稀疏矩阵，字符串和广义表 学习要求：熟练掌握数组，特殊矩阵和稀疏矩阵的数据存储形式，掌握存储地址的计算。 了解广义表和字符串的概念和存储形式。 自学：字符串的匹配 讨论：多维数组和稀疏矩阵、特殊矩阵的存储形式，广义表的表示 第五章 树（8 学时） 主要内容：树，二叉树，二叉树的遍历，线索二叉树，树和森林 学习要求：树的定义，数的抽象数据类型，二叉树的定义，二叉树的性质，二叉树的抽 象数据类型，存储表示。掌握二叉树的遍历。对于线索化二叉树，要求理解什么是线索。掌 握堆的定义及其实现方法。最后掌握 Huffman 树的实现方法和 Huffman 编码。树和森林的 转换，树的存储表示。 自学：堆的应用，最优判定树 讨论：二叉树的遍历，二叉树的生成 第六章 集合和字典（6 学时） 主要内容：集合和字典，跳表，散列 学习要求：理解集合及其表示方法，并查集的实现方法。掌握散列函数和散列方法 自学：跳表的应用，并查集的应用 讨论：二叉树的遍历，二叉树的生成 第七章 搜索结构（8 学时） 主要内容：静态搜索结构，二叉搜索树，AVL 树，伸展树和红黑树 学习要求：掌握静态搜索结构，二叉搜索树的概念，插入和删除算法以及性能分析， AVL 树的概念，AVL 数的插入、删除以及平衡化的旋转，了解伸展树和红黑树的概念 自学：红黑树的插入和删除 讨论：二叉搜索树的应用 第八章 图（8 学时） 主要内容：图的概念，图的存储结构，图的遍历以及最小生成树，最短路径和 AOV,AOE 网络 学习要求：掌握图的概念，图的存储结构，图的深度优先和广度优先遍历，最小生成树 的生成方法。最短路径算法以及 AOV，AOE 网络。 自学：任意权值的单源最短路径，所有定点之间的最短路径，重连通分量
讨论：最小生成树的应用 第九章排序(8学时) 主要内容：排序的概念，插入排序，快速排序，选择排序，归并排序，基于链表的排序 算法，分配排序 学习要求：掌握排序的概念，插入排序，快速排序，选择排序，归并排序，基于链表的 排序算法，分配排序的算法，以及性能。 自学：链表插入排序，链表归并排序 讨论：排序的应用 第十章文件、外部排序和瘦索(4学时) 主要内容：主存储和外存储器、文件组织、外排序、多级索引结构，可扩充的散列，Trs 学习要求：掌据主存储和外存储器、文件组织、外排序。 自学：多级索引结构，可扩充的散列，Ties 实验教学内容概况： 木课程实验大纲是面向计算机相关专业学生开设的《数据结构》实验课计划指导大纲 是依据《数据结构》课程教学计划指导大纲编制。 计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算 机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是 数据结构课程中学习和研究的内容。由于数据结构的原理和算法较抽象，而该课程一般在本 科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得较为困难。 数据结构实验课程着眼于数据结构原理和应用的结合点，使读者学会如何将书上学到的知识 用于解决实际问题，培养软件工作需要的动手能力：另一方面，能使书上的知识变“活”， 起到深化理解和灵活掌握教学内容的目的。 本实验课程主要结合数据结构课程的教学大纲的相应内容，设计了7个实验（包括验证 型、综合型、设计型实验)，力求提高学生的动手能力，做到理论和实践相结合。使学生在 实验过程中进一步掌握典型数据结构的逻辑结构、存储结构及算法的程序实现，并训练问题 的综合分析能力和编程能力，形成良好的编程风格，为后续课程的学习奠定坚实的理论和实 践基础。 为了提高学生的动手能力，我们为《数据结构》安排了课程设计（见教学大纲的《课程 设计1》)，在教学结束后的期末集中一个星期进行，分组选题，教师指导，这样就可以将
40 讨论：最小生成树的应用 第九章 排序（8 学时） 主要内容：排序的概念，插入排序，快速排序，选择排序，归并排序，基于链表的排序 算法，分配排序 学习要求：掌握排序的概念，插入排序，快速排序，选择排序，归并排序，基于链表的 排序算法，分配排序的算法，以及性能。 自学：链表插入排序，链表归并排序 讨论：排序的应用 第十章 文件、外部排序和搜索（4 学时） 主要内容：主存储和外存储器、文件组织、外排序、多级索引结构，可扩充的散列，Tries 学习要求：掌握主存储和外存储器、文件组织、外排序。 自学：多级索引结构，可扩充的散列，Tries 实验教学内容概况： 本课程实验大纲是面向计算机相关专业学生开设的《数据结构》实验课计划指导大纲， 是依据《数据结构》课程教学计划指导大纲编制。 计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算 机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是 数据结构课程中学习和研究的内容。由于数据结构的原理和算法较抽象，而该课程一般在本 科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得较为困难。 数据结构实验课程着眼于数据结构原理和应用的结合点，使读者学会如何将书上学到的知识 用于解决实际问题，培养软件工作需要的动手能力；另一方面，能使书上的知识变“活”， 起到深化理解和灵活掌握教学内容的目的。 本实验课程主要结合数据结构课程的教学大纲的相应内容，设计了 7 个实验（包括验证 型、综合型、设计型实验），力求提高学生的动手能力，做到理论和实践相结合。使学生在 实验过程中进一步掌握典型数据结构的逻辑结构、存储结构及算法的程序实现，并训练问题 的综合分析能力和编程能力，形成良好的编程风格，为后续课程的学习奠定坚实的理论和实 践基础。 为了提高学生的动手能力，我们为《数据结构》安排了课程设计（见教学大纲的《课程 设计 I》），在教学结束后的期末集中一个星期进行，分组选题，教师指导，这样就可以将一