2023年数据结构教学大纲.docx

《2023年数据结构教学大纲.docx》由会员分享，可在线阅读，更多相关《2023年数据结构教学大纲.docx（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、2023年数据结构教学大纲 第一篇：数据结构教学大纲 数据结构与算法教学大纲 课程编号：030816 适用专业：教化技术学 总学时数：64 学 分：4 编制单位：茂名学院理学院教化与信息技术系 编制时间：2023年6月20日 一、课程地位、性质和任务 数据结构与算法课程是计算机相关学科专业的基础课程中的一门重要的核心课程。通过本课程的教学，使学生知道求解非数值类问题的基本模型表、树、图，模型的特点和适用场合，能够根据问题设计和选择好的算法，为学习后续的操作系统、编译原理和软件工程等专业课程，设计应用程序打下基础。 本课程以提高学生的计算机应用实力和综合素养为目标，通过课程教学，为学生构建数据结

2、构与算法方面的学问体系，使学生一方面能够根据问题选择合适的数据结构，设计高效的算法，提高程序设计实力，另一方面，在工程应用中，具有甄别好算法的实力，也就是要从建模、解模和综合等三个方面，提高学生的程序设计实力。 二、与其他课程的关系 先修课：程序设计基础、离散数学、计算机组成原理、计算机文化基础 三、教学内容、课时支配和基本要求 一教学部分 第1章 绪论2学时1.1什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析算法及其设计的要求，算法效率的度量，算法的存储空间需求1.5 问题求解 基本要求： 了解：抽象数据类型，算法设计方法与算法分析。 驾驭：

3、数据与数据结构、算法的基本概念；问题求解的方法与步骤 重点：数据结构和算法的概念，算法的描述形式和评价方法，问题求解的一般步骤 难点：评价算法的标准和评价方法，最坏状况和平均状况的区分。 第2章 线性表8学时2.1 线性表的类型定义 2.2 线性表的依次表示和实现 2.3 线性表的链式表示和实现线性链表，循环链表，双向链表2.4 一元多项式的表示及相加 基本要求： 了解：两种存储结构依次存储结构和链式存储结构及一元多项式的表示及相加。 驾驭：要求娴熟驾驭处理线性表的各种算法。为后继章节的学习打基础。重点：各种算法。难点：链表的理解。 第3章 栈与队列4学时 3.1 栈定义，栈的表示和实现 3.

4、2 栈的应用举例数制转换，括号匹配的检验，行编辑程序，迷宫求解，表达式求值 3.3 栈与递归的实现 3.4 队列及其实现定义，链队列，循环队列3.5 *离散事务模拟 教学要求：娴熟驾驭栈和队列的特性和在不同存储结构前提下的算法实现。栈和队列是表最基本和重要的数据结构，是数据结构课程的基础。 基本要求： 了解： 栈和队列的定义及其实现。 驾驭： 娴熟驾驭栈和队列的特性和在不同存储结构前提下的算法实现。重点： 栈和队列的算法实现。难点： 栈和队列的算法实现。 第4章 串2学时4.1 串类型的定义 4.2 串的表示和实现定长依次存储，堆支配存储，串的块链存储4.3 串的模式匹配算法求子串位置的定位函

5、数，模式匹配的一种改良算法4.4 串操作应用举例文本编辑，建立词索引表 基本要求： 了解：串的基本概念及主要操作和运算。驾驭：驾驭串的基本概念和运算。重点：主要操作和运算。难点：模式匹配及串的应用。 第5章 数组2学时5.1 数组的定义 5.2 数组的依次表示和实现 5.3 矩阵的压缩存储特殊矩阵，稀疏矩阵5.4 广义表的定义 5.5 广义表的存储结构 5.6 m元多项式的表示 5.7 广义表的递归算法求广义表的深度，复制广义表，建立广义表的存储结构 基本要求： 了解：了解作为抽象数据类型的数组和C语言的数组。相识到数组可以作为依次存储结构用于依次表、字符串和稀疏矩阵的实现。也可以接受链式存储

6、结构。 驾驭：驾驭基本概念和算法。重点：算法。 难点：广义表的递归算法。 第6章 树与二叉树15学时6.1 树的定义和基本术语 6.2 二叉树二叉树的定义，二叉树的性质，二叉树的存储结构6.3 遍历二叉树和线索二叉树遍历二叉树，线索二叉树 6.4 树和森林树的存储结构，森林与二叉树的转换，树和森林的遍历6.5 树与等价问题 6.6 赫夫曼树及其应用最优二叉树赫夫曼树，赫夫曼编码6.7 回溯法与树的遍历 6.8 树的计数 基本要求： 了解：理解树与森林的定义与术语。 驾驭：娴熟驾驭二叉树性质和遍历算法，驾驭树与森林的孩子兄弟存储表示和遍历。驾驭哈夫曼树构造的方法和算法。重点： 树的存储结构和遍历

7、算法。难点：哈夫曼树构造的方法和算法 第7章 图11学时7.1 图的定义和术语 7.2 图的存储结构数组表示法，邻接表，十字链表，邻接多重表7.3 图的遍历深度优先搜寻，广度优先搜寻 7.4 图的连通性问题无向图的连通重量和生成树，有向图的强连通重量，最小生成树，关节点和重连通重量 7.5 有向无环图及其应用拓扑排序，关键路径 7.6 最短路径从某个源点到其余各项点的最短路径，每一对顶点之间的最短路径基本要求： 了解：图的基本概念和相关术语。 驾驭：图的两种主要存储结构及遍历算法。驾驭最小生成树、最短路径和活动网算法的思想。 重点：图的两种主要存储结构及遍历算法。难点：图的遍历算法，最短路径算

8、法。 第8章 查找8学时 9.1 静态查找表依次表，有序表，静态树表，索引依次表9.2 动态查找表二叉排序树和平衡二叉树，B_树和B+树，键树9.3 哈希表定义，构造方法，处理冲突的方法，查找及其分析 基本要求： 了解： 各种查找法的基本概念及实现的基本思想。 驾驭：娴熟驾驭搜寻结构的折半查找、二叉搜寻树、平衡二叉树主要搜寻算法。驾驭哈希表查找算法。重点：各种算法的基本思想及实现。难点：哈希表查找算法。 第9章 内部排序8学时10.1 概述 10.2 插入排序干脆插入，其他插入，希尔10.3 交换排序冒泡排序、快速排序10.4 选择排序简洁，树形，堆10.5 归并排序 10.6 基数排序多关键

9、字，链式10.7 排序算法分析 基本要求： 了解：基数排序，排序算法分析方法 驾驭：排序的基本概念，插入排序，交换排序，选择排序，归并排序重点：内部排序算法 难点：基数排序多关键字，链式 第10章 *外部排序2学时11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换-选择排序 11.5 最正确归并树 基本要求： 了解：外部排序的基本概念和相关术语。 驾驭：基本驾驭外排算法的基本思想，不同排序方法的比较。重点：外部排序算法 难点：多路平衡归并的实现 第11章 算法设计的一般方法2学时 1重点 1有效算法的概念，问题固有难度的概念； 2递归法；分治法；平

10、衡原则；贪心法；动态规划的基本原理；3搜寻-回溯法的基本原理和本质.2难点 1问题固有难度的概念； 2递归分治法的效率分析写出时间耗费的递推式，并求解；3动态规划法中的状态转移方程确实定。 二试验、实习部分 课程支配五个类别的试验，试验时数为12课时，其中： 试验 一、线性链表及运算 2课时 试验 二、栈和队列 2课时 试验 三、树和二叉树 4课时 试验 四、图及其应用 2课时 试验 五、查找与排序 2课时 四、课程考核方式 闭卷考试70%、平常作业与试验30% 五、建议教材和教学参考书 参考教材： 1、数据结构C语言描述高等教化出版社 耿国华主编 2、数据结构C语言版清华高校出版社 严蔚敏，

11、吴伟民编者 3、数据结构题集C语言版清华高校出版社 严蔚敏，吴伟民编者 4、数据结构算法实现及解析其次版西安电子科技高校出版社 高一凡 六、说明 1、因课时支配少，教学内容多。建议接受多媒体教学。 2、由于本课程内容较多，在实际教学中可根据大纲内容，进行适当调整。 其次篇：数据结构教学大纲(参考) 数据结构 Data Structure 课程代码： 学 时 数：64讲课50 试验14 研讨0 实习实践1周 学 分 数： 3、4 课程类别：学科基础课 开课学期：4 主讲老师： 编写日期： 2023年7月1日 一、课程性质和目的课程性质：数据结构A是计算机科学与技术、数字媒体艺术、信息管理与信息系

12、统专业的一门重要学科基础课，是必修课。 教学目的：通过本课程的学习，一方面，使学生学会分析探讨计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的规律结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培育学生的数据抽象实力和程序设计的实力。 二、课程教学内容、学时支配和课程教学基本要求 1.绪论理论2学时 教学内容： (1)数据结构的一些基本概念：数据、数据元素、数据的规律结构、物理结构等。(2)抽象数据类型的表示和实现。(3)算法的概念和特性。 (4)算法时间困难度和空间困难度的分析。基本要求： 驾驭数据结构的基本

13、概念，了解抽象数据类型，驾驭算法时间困难度和空间困难度的分析方法。 2.线性表理论8学时，试验4学时 教学内容： (1)线性表的类型定义。(2)线性表的依次表示和实现。(3)线性表的链式表示和实现。 (4)线性表的应用，包括无序表和有序表的合并、多项式的加法运算等。基本要求： 理解线性表的规律结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是依次存储结构依次表和链式存储结构链表。娴熟驾驭这两类存储结构的描述方法，驾驭链表中的头结点、头指针和首元结点的区分及循环链表、双向链表的特点等。驾驭依次表的查找、插入和删除算法，驾驭链表的查找、插入和删除算法。能够从时间和空

14、间困难度的角度比较两种存储结构的不同特点及其适用场合。驾驭无序表和有序表的合并算法，了解多项式的加法运算。 试验： 试验内容：单链表的基本操作。试验要求：以单链表形式创建一个学生表或图书表，并能实现相关的查找、插入和删除等算法。3.栈和队列理论6学时，试验4学时 教学内容： (1)栈的类型定义，栈的依次存储和链接存储的表示和实现。(2)栈的应用举例，如迷宫求解和表达式求值。 (3)栈与递归的实现，递归程序转换为非递归程序的方法。 (4)队列的类型，队列的依次存储(循环队)和链接存储的表示和实现。(5)队列的应用举例，如打印杨晖三角形，模拟汽车加油站等问题。基本要求： 驾驭栈和队列的特点，并能在

15、相应的应用问题中正确选用。娴熟驾驭栈的依次栈和链栈的进栈出栈算法，特别应留意栈满和栈空的条件。驾驭利用栈实现表达式求值的算法，了解迷宫求解算法。理解递归算法执行过程中栈的状态转变过程，了解将递归程序转换为非递归程序的方法。娴熟驾驭循环队列和链队列的进队出队算法，特别是循环队列中队头与队尾指针的转变状况。了解队列的应用。 试验： 试验内容：栈的应用。试验要求：借助栈来解决某些实际应用问题，如表达式求值、迷宫问题等。 4.串、数组和广义表理论2学时 教学内容： (1)串的表示和实现，包括依次存储和链式存储表示。古典的模式匹配算法。(2)数组的存储方法。 (3)特殊矩阵和稀疏矩阵的压缩存储，稀疏矩阵

16、的转置运算。(4)广义表的规律结构和存储结构。基本要求： 了解串的依次存储结构和堆存储结构。驾驭串的古典的模式匹配算法。驾驭数组的地址计算方法。了解稀疏矩阵的两种压缩存储方法的特点和适用范围。了解广义表的结构特点及其存储方法。5.树和二叉树理论8学时，试验2学时 教学内容： (1)二叉树的定义和术语，二叉树的性质，特殊的二叉树。(2)二叉树的存储结构，依次存储和二叉链表。 (3)二叉树的的前序、中序、后序、层次遍历方法。线索化二叉树。(4)树和森林的定义，树的存储，树、森林与二叉树的转换。(5)树的应用，哈夫曼树及哈夫曼编码。基本要求： 了解树和森林的概念，包括树的定义、树的术语。驾驭二叉树的

17、概念、性质及二叉树的表示。娴熟驾驭二叉树的遍历算法，并且能灵敏运用遍历算法实现二叉树的其他操作。驾驭线索化二叉树的特性及找寻某结点的前驱和后继的方法。了解树的存储、树和森林与二叉树的转换方法。驾驭哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径长度的计算。 试验： 试验内容：二叉树的基本算法。试验要求：利用二叉链表方法建立二叉树，实现二叉树的前、中、后序三种遍历算法，并运用遍历算法实现二叉树的其他操作，如计算二叉树结点个数、叶子结点个数、二叉树的高度等。6.图理论8学时，试验2学时 教学内容： (1)图的定义和术语。 (2)图的存储结构两种存储结构：邻接矩阵和邻接表表示法。(3)图的两种遍历

18、策略：深度优先搜寻和广度优先搜寻。(4)构造最小生成树的两种算法：普里姆算法和克鲁斯卡尔算法。(5)拓扑排序和关键路径。 (6)两类求最短路径问题的算法，迪杰斯特拉算法和弗洛伊德算法。基本要求： 驾驭图的基本概念及相关术语和性质，驾驭图的邻接矩阵和邻接表表示法，了解实际问题的求解效率与接受何种存储结构和算法有亲热联系。娴熟驾驭图的两种搜寻路径的遍历：深度优先搜寻和广度优先搜寻的算法。驾驭构造最小生成树的两种算法及拓扑排序算法的思想，驾驭迪杰斯特拉算法。了解关键路径的概念和求解方法，了解弗洛伊德算法。 试验： 试验内容：图的建立和搜寻。试验要求：运用邻接矩阵或邻接表表示法存储一个图，实现图的深度

19、优先搜寻和广度优先搜寻的算法。7.查找理论6学时 教学内容：(1)查找的基本概念，平均查找长度。(2)基于线性表的查找：依次查找、折半查找。 (3)基于树表的查找：二叉排序树、平衡二叉树、B-树和B+树。 (4)散列表：散列表的基本概念，散列函数的构造方法、处理冲突的方法、散列表的查找与分析。 基本要求： 娴熟驾驭依次表和有序表的查找方法及其实现，驾驭二叉排序树的插入和查找算法及其实现，了解平衡二叉树、B-树和B+树的各种操作。娴熟驾驭散列表的构造方法、处理冲突的方法，深刻理散列表与其他结构的表的实质性的差异，了解各种散列函数的特点。驾驭描述折半查找过程的判定树的构造方法，以及按定义计算各种查

20、找方法在等概率状况下查找胜利时的平均查找长度。 8.排序理论8学时，试验2学时 教学内容： (1)排序的基本概念，包括正序，逆序，稳定性，排序方法的分类。(2)插入排序：干脆插入排序、折半插入排序和希尔排序。(3)交换排序：冒泡排序和快速排序。(4)选择排序：简洁选择排序和堆排序。(5)归并排序：2-路归并排序。 (6)基数排序：多关键字的排序和链数基数排序。 (7)排序算法分析：各种排序算法的比较和移动次数，时间困难度和空间困难度的分析。基本要求： 明确排序的基本概念，排序方法的分类。深刻理解排序算法的过程、特点及其根据的原则，并能加以灵敏应用。驾驭各种排序方法的时间和空间困难度的分析方法。

21、能从关键字间的比较次数和移动次数分析算法的平均状况和最坏状况的时间性能。理解排序方法“稳定或“不稳定的含义，弄清楚在什么状况下要求应用的排序方法必需是稳定的。快速排序、堆排序和归并排序等高效排序方法是本章的学习重点和难点。 试验： 试验内容：综合性试验。试验要求：选取一个合适的数据结构存储数据，能对数据进行插入、删除，用不同查找算法进行查找、用不同的排序算法进行排序等。9.实习1周 教学内容： (1)设计准备：理解实习任务，明确相关算法，搜集可用资源，熟识实习环境。(2)方案设计：完成设计目标、设计路途确实定，并进行模块设计和任务分工。(3)代码编写：各模块代码编写，模块测试。(4)代码测试：

22、模块组装，整体测试。(5)设计报告：完成设计文档，制作设计报告。基本要求： 能将数据结构课程中所学的基本学问融会贯穿，综合运用所学的学问解决相关的实际问题，能够把所学学问包括算法和结构在计算机上用编程语言加以实现，并且能够根据实际需求创建自己的数据结构和实现自己的算法。 本课程的教学环节包括：课堂讲授、试验、实习、作业、答疑、小测验等。其中，课堂讲授以老师讲授为主，授课时将电子教案和板书相结合，充分发挥各自的优点。接受启发式教学，激励学生自学，培育学生的自学实力，以“少而精为原则，精选教学内容，调动学生学习的主观能动性。试验针对相应单元所学的内容，能够实行合适的数据结构和算法解决有关问题。试验

23、重点培育学生的动手实力。实习针对较为困难的应用问题，能够综合运用所学的各种数据结构进行算法设计和实现，留意学生数据抽象实力和算法设计实力的培育。 三、本课程与其它课程的联系和分工 本课程的先修课为程序设计基础和离散数学，本课程可以C/C+或Java语言作为算法描述和上机实践的工具。同时，本课程又是软件开发与设计等方面课程的基础，如数据库、操作系统、编译原理、软件工程等课程。 四、本课程的考核方式 期末考试接受笔试形式，考试题型为：选择、填空、推断、应用题和算法设计题。总评成果由平常成果和期末成果组成，其中平常成果占30%-40%，期末考试占70%-60%。 课程实习的成果由平常成果和实习作业两

24、部分组成，其中平常成果占30%，实习作业占70%。 五、建议教材与教学参考书 建议教材： 1.严蔚敏，李冬梅，吴伟民数据结构C语言版北京：人民邮电出版社 2.严蔚敏主编数据结构C语言版北京：清华高校出版社 3.殷人昆主编数据结构用面对对象方法与C+描述北京：清华高校出版社 建议教学参考书： 1.Bruno R.Preiss著，胡广斌，王崧等译数据结构与算法面对对象的C+设计模式北京：电子工业出版社 2.殷人昆主编数据结构与习题解析用面对对象方法与C+描述北京：清华高校出版社 六、课程简介 数据结构是一门专业基础课，是学习其他软件开发与设计等方面课程的基础。主要内容包括：线性表、栈和队列、串、数

25、组和广义表、树、图、查找算法和排序算法。数据结构探讨数据的组织方式，内容丰富、学习量大，隐含在各部分内容中的方法和技术多，旨在让学生驾驭计算机软件系统所必需的数据结构的算法。要求学生驾驭贯穿全课程的动态链表存储结构，驾驭算法设计的动态性和抽象性。要求学生学会分析探讨计算机加工的数据对象的特征，以便在实际应用中选择适当的数据结构、存储结构和相应算法，初步驾驭算法的时间与空间性能分析技巧，并培育困难程序设计的技能。 执笔人： 审核人： 教学院长： 院学术委员会： 院长： 第三篇：数据结构教学大纲 中心广播电视高校“开放教化试点计算机科学与技术专业本科 数据结构课程教学大纲 第一部分 大纲说明 一、

26、课程的性质和任务 数据结构是计算机科学与技术专业本科生的一门必修课程。本课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：数组、链接表、栈和队列、递归、树与森林、图、堆与优先级队列、集合与搜寻结构、排序、索引与散列结构等。课程接受面对对象的观点探讨数据结构技术，并以兼有面对过程和面对对象双重特色的C+语言作为算法的描述工具，强化数据结构基本学问和面对对象程序设计基本实力的双基训练。为后续计算机专业课程的学习打下坚实的基础。 二、先修课要求 面对对象程序设计、计算机数学(离散数学)。 三、课程的教学基本要求 1、驾驭重要数据结构的概念、运用方法及实现技术； 2、学会做简洁的算法分析

27、，包括算法的时间代价和空间代价。 四、教学方法和教学形式建议 电视授课为主，结合面授辅导、面授或电子邮件答疑，进行必要的上机试验。 五、课程教学要求的层次 1、娴熟驾驭：要求学生能够全面、深化理解和娴熟驾驭所学内容，并能够用其学问分析、设计和解答相关的应用问题。 2、驾驭：要求学生能够较好地理解和驾驭，并且能够做简洁的分析。 3、了解：要求学生能够一般地了解的所学内容。 六、课程试验 试验内容和要求由省级电大作出具体规定，从2023年春起先按该课程试验教材规定进行。 其次部分 多种媒体教材一体化总体设计初步方案 一、学时支配 课程教学总学时数为 72学时，4学分，其中讲授学时48，试验24 教

28、 学 内 容 讲授学时 试验学时 一、数据结构基本概念及算法分析 3学时 2学时 二、数组 3学时 2学时 三、链表 3学时 3学时 四、栈和队列 3学时 2学时 五、递归 3学时 2学时 六、树与森林 9学时 4学时 七、集合与搜寻 5学时 2学时 八、图 7学时 4学时 九、排序 7学时 3学时 十、索引与散列结构 5学时 二、教学环节 1、电视教学 本课程是计算机专业基础课，内容多且带有确定的抽象性，学习起来有确定难度。为保证教学效果，实行电视集中授课方式。聘请有阅历的老师担当主讲老师，尽可能利用多种媒体进行教学，使学生能够很快驾驭课程的主要学问和解决问题的方法。 2、面授辅导或答疑 本

29、课程教学过程中，面授辅导和答疑是必不行少的教学环节。各地方电大应聘请有阅历、认真负责的老师任教，以习题课、专题探讨或答疑的方式，对课程中的重要概念和典型问题的解决方法进行总结和深化探讨，稳固和加深课堂内学到的学问。面授辅导或答疑支配两周一次为宜。必要时可接受电子邮件方式干脆与主讲老师联系进行答疑。 3、自学与练习 自学是获得学问的重要手段。老师讲课只是起到抛砖引玉的作用，关键还在于学生的自学。为到达自学的效果，除读懂教科书中所讲内容外，还需大量做题。其目的是要通过做题弄懂、加深对概念的理解，提高程序设计，解决问题的实力。为此，支配确定的试验上机学时。要求学生珍惜试验机时，真正做到学有所获。 学

30、生在上机做试验前，应事先将程序、调试数据、上机操作依次准备好，并提前运用这些调试数据人工执行过。目的是提高上机的效率和胜利率，严禁抄袭或拷贝他人的成果，自觉培育科学、严谨的作风。 除学校供应的时间外，要求课外学生利用自己可能拥有的计算机条件，完成更多的练习，不通过大量的实践，实力和学问水平得不到有效得提高。 4、考试 考试是对学生驾驭学问水平的检验。本着多练多考的原则，各地方电大可以再平常多做一些小考。要求考试内容紧扣大纲要求，既要能够检验学生的驾驭状况，又要表达水平。因此，不要出难题、怪题，但也不要过于简洁，适当有一些编程题。 课程考试具体规定请参看该课程考核说明。 第三部分 教学内容和教学

31、要求 一、数据结构基本概念及简洁的算法分析 3学时 1、教学内容： 什么是数据结构 抽象数据类型及面对对象概念：数据类型；数据抽象与抽象数据类型；面对对象的概念；用于描述数据结构的语言 数据结构的抽象层次 算法定义 性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间困难度度量；时间困难度度量；时间困难度的渐进表示法；渐进的空间困难度 2、教学要求： 了解：什么是数据、数据对象、数据元素、数据结构、数据的规律结构与物理结构、规律结构与物理结构间的关系 了解：什么是数据类型、抽象数据类型、数据抽象和信息隐藏原则。了解什么是面对对象 了解：算法的定义、算法的特性、算法的时间代价、算

32、法的空间代价 驾驭：用C+语言描述算法的方法，能够运用C+语言编写程序 二、数组 3学时 1、教学内容： 作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组；数组的依次存储方式 依次表：依次表的定义和特点；依次表的类定义；依次表的查找、插入和删除；运用依次表的事例 字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配 2、教学要求： 了解：线性表的规律结构特性，以及线性表的两种存储实现方式 了解：作为抽象数据类型的数组的定义，数组的按行依次存储与按列依次存储 娴熟驾驭：依次表的定义与实现，包括搜寻、插入、删除算法的实现及其平均比较次数的计算，驾驭应用依次表作为集合的

33、简洁操作 了解：稀疏矩阵的定义及其数组实现 娴熟驾驭：字符串的定义及实现 三、链表 3学时 1、教学内容： 单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；静态链表 循环链表：循环链表的类定义；用循环链表解约瑟夫问题； 多项式及其相加：多项式的类定义；多项式的加法 双向链表 2、教学要求： 了解：链表与数组一样，是一种实现级结构。有动态链表和静态链表之分 了解：链表有单链表、循环单链表、双向链表之分 了解：单链表的结构、特点 驾驭：单链表的类定义、构造函数、单链表的插入与删除算法 了解：带表头结点的单链表的优点和类定义及相应操作的实现 娴熟

34、驾驭：用模板定义的单链表类 了解：循环链表的特点，循环链表的类定义，以及用循环链表解决问题的方法 驾驭：双向链表的特点，双向链表的类定义及相关操作的实现，用双向链表解决问题的方法。 四、栈和队列 3学时 1、教学内容： 栈：栈的抽象数据类型；栈的依次存储表示；栈的链接存储表示 表达式求值：中缀表达式求值；中缀表示到后缀表示的转换 队列 ：队列的抽象数据类型；队列的依次存储表示；队列的链接存储表示；队列的应用举例 优先级队列：优先级队列的定义；优先级队列的存储表示 2、教学要求： 娴熟驾驭：栈的定义、特性和栈的抽象数据类型，栈的依次表示、链表表示以及相应操作的实现。特别留意栈空和栈满的条件 了解

35、：在表达式计算时栈是如何运用的，重点了解用后缀表示计算表达式及中缀表示改后缀表示的方法和算法思路 娴熟驾驭：队列的定义、特性和队列的抽象数据类型，队列的依次表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针的转变状况 驾驭：优先级队列的定义、特性和优先级队列的抽象数据类型，优先级队列的插入与删除算法 五、递归 3学时 1、教学内容： 递归的概念：递归问题的求解 递归过程与递归工作栈：单向递归和尾递归的迭代实现；一般递归问题利用栈实现非递归解法 广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广义表的访问算法；广义表的递归算法 2、教学要求： 驾驭：递归的概念。包括

36、什么是递归，有那些种类的递归，递归问题的递归求解方法 驾驭：递归过程的机制与利用递归工作栈实现递归的方法 了解：迷宫问题的递归求解思路及如何利用栈实现迷宫问题的非递归解法 驾驭：利用递归解决问题的分治法和回溯法 驾驭：广义表的定义及其实现方法 驾驭：广义表的递归算法 六、树与森林 9学时 1、教学内容： 树和森林的概念：树的定义；树的术语；树的抽象数据类型 二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型 二叉树的表示：依次表示；二叉链表表示 遍历二叉树：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例；二叉树的计数 线索化二叉树：线索；中序线索化二叉树 堆：堆的定义；堆的建立；堆的

37、插入与删除；堆的调整算法 树与森林：树的存储表示；森林与二叉树的转换；遍历树；遍历森林 霍夫曼树：路径长度；霍夫曼树；霍夫曼编码 2、教学要求： 了解：树和森林的概念。包括树的定义、树的术语、树的抽象数据类型 驾驭：二叉树的概念、性质及二叉树的表示 娴熟驾驭：二叉树的遍历方法 驾驭：线索化二叉树的特性及找寻某结点的前驱和后继的方法 娴熟驾驭：堆的定义，堆的建立、堆的插入与删除、堆的向上和向下调整等算法以及用来实现优先级队列的方法 驾驭：树与森林的实现，重点在用二叉树实现 驾驭：森林与二叉树的转换；树的遍历算法 驾驭：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法 驾驭：霍夫曼树的实现方法、

38、构造霍夫曼编码的方法及带权路径长度的计算 七、集合与搜寻 5学时 1、教学内容： 集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用位向量实现集合抽象据类型；用有序链表实现集合的抽象数据类型 并查集：并查集的定义；并查集的实现 简洁的搜寻结构：搜寻的概念；静态搜寻结构；依次搜寻；基于有序依次表的依次搜寻和折半搜寻 二叉搜寻树：二叉搜寻树的定义；二叉搜寻树上的搜寻；二叉搜寻树的插入；二叉搜寻树的删除 AVL树：AVL树定义；平衡化旋转；AVL树的插入和删除；AVL树高度 2、教学要求： 驾驭：集合的基本概念及其表示方法，包括位数组及有序链表的表示及其相关操作的实现算法 驾驭：利用并查集实

39、现集合的方法 娴熟驾驭：静态搜寻表的依次搜寻和折半搜寻算法及其性能分析方法 娴熟驾驭：二叉搜寻树的表示、搜寻、插入、删除算法及其性能分析方法 驾驭：AVL树的平衡化旋转、构造、插入、删除时的调整方法及其性能分析 八、图 7学时 1、教学内容： 图的基本概念：图的基本概念；图的抽象数据类型 图的存储表示：邻接矩阵；邻接表；邻接多重表 图的遍历与连通性：深度优先搜寻；广度优先搜寻；连通重量；关节点与重连通重量 最小生成树：kruskul算法；prim算法 单源最短路径问题：dijkstra算法 活动网络：AOV网络与拓扑排序；AOE网络与关键路径 2、教学要求： 理解：图的基本概念和图的抽象数据类

40、型 驾驭：图的3种存储表示：邻接矩阵、邻接表和邻接多重表。对于前两种，要求驾驭典型操作，如构造、求根、找第一个邻接顶点、找下一个邻接顶点等操作的实现算法 娴熟驾驭：图的两种遍历算法与求解连通性问题的方法。包括深度优先搜寻和广度优先搜寻算法、求连通重量的方法(不要求算法) 理解：求解关节点及构造重连通图的方法(不要求算法) 驾驭：构造最小生成树的Prim算法和Kruskal算法，要求理解算法 理解：如何用Dijkstra方法求解单源最短路径问题(不要求算法) 娴熟驾驭：活动网络的拓扑排序算法 驾驭：求解关键路径的方法 九、排序 7学时 1、教学内容： 概述 插入排序：干脆插入排序；折半插入排序；

41、链表插入排序；希尔排序 交换排序：起泡排序；快速排序 选择排序：干脆选择排序；锦标赛排序；堆排序 归并排序：归并；迭代的归并排序算法；递归的链表归并排序 基数排序：多关键码排序；链式基数排序 外排序：外排序的基本过程；k路平衡归并；初始归并段的生成；最正确归并树 2、教学要求： 驾驭：排序的基本概念和性能分析方法 驾驭：插入排序、交换排序、选择排序、归并排序等内排序的方法及其性能分析方法 了解：基数排序方法及其性能分析方法 驾驭：多路平衡归并等外排序方法及败者树构造方法 驾驭：生成初始归并段及败者树构造方法 驾驭：最正确归并树的建立方法 十、索引与散列结构 5学时 1、教学内容： 静态索引结构：线性索引；倒排索引；m路静态查找树 动态索引结构：动态的m路查找树；B树的定义；B树的插入；B树的删除；B+树 散列：散列表与散列方法；散列函数；处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析 2、教学要求： 娴熟驾驭：静态索引结构，包括线性索引、倒排索引、静态索引树的搜寻和构造方法 娴熟驾驭：动态索引结构，包括B树、B+树的搜寻和构造方法 娴熟驾驭：散列法，包括散列函数的构造、解决冲突的方法 第四篇：数据结构课程教学大