1、数据结构与算法教学大纲课程编号：10140013英文名称：Data Structure and Algorithm学 分：3.5(3+0.5)学 时：64(48+16)课程类别：专业平台课程 授课对象：信息与计算科学专业学生教学单位：工学院计算机科学技术学科修读学期：第 3 学期一、教学任务基本的算法理论，分析问题的方法，数据的逻辑结构，数据的存储结构以及基于这些结构上的算法，数据组织和处理技术，基于数据结构的分析和解决问题的方法，算法实现和程序设计技能的训练。本课程是信息与计算科学专业重要的专业理论与技术基础课，通过该课程的学习，使学生具备一定的软件技术知识和技能，初步具备从现实问题抽象到信
2、息范畴再到计算机中数据组织和处理的转换，实现解决问题的一定的较综合的能力；为学生的专业素质和分析及解决问题的能力奠定一定的基础。二、教学目标1专业知识方面：明确本课程对用计算机解决实际问题的作用；明确把现实问题通过计算机来解决的过程和方法；掌握对计算机加工的数据对象特性的分析方法，掌握线性结构、树结构、图结构等结构的特性；掌握基本的查找和排序方法。2专业能力方面：能根据实际问题选择合适的数据逻辑结构和存储结构，并在相应存储结构的基础上掌握对这些数据对象的操作技术。初步具备选用合适的存储结构的组织数据方法，初步具备对部分结构编写算法的能力；初步具备算法评价的能力。3综合能力方面：初步具备通过对现
3、实世界中问题的分析，能把处理对象的数据和关系抽象到信息世界里的结构模型，然后把结构模型组织到计算机里，从而在这基础上编制有一定综合性的算法，实现问题求解的能力。 三、教学内容理论：（一）基本概念1明确本课程研究的对象、内容和过程，明确本课程在专业人才培养中的地位、任务和作用。2明确数据、数据对象、数据的逻辑结构、存储结构、算法的概念以及它们之间的联系，了解抽象数据类型。3明确算法与数据结构的关系、描述算法的方法，掌握基本的算法分析方法。重点：数据结构，数据关系、算法时间复杂度分析。难点：算法时间复杂度分析。自学内容：抽象数据类型(4 学时)。（二）线性结构1明确线性表的概念，了解抽象数据类型定
4、义；明确顺序表和链表的概念和结构特征，掌握顺序表和链表的定义和组织形式；掌握线性表的顺序存储结构和链式存储结构，掌握单链表的实现方法和算法，并能初步应用线性结构。了解循环链表、双向链表。2明确栈的概念和结构特点，了解栈的抽象数据类型定义，掌握顺序存储和链式存储结构栈的基本操作方法及算法；能初步应用栈结构。3明确队列的概念和结构特点，了解队列的抽象数据类型定义，掌握顺序存储结构和链式存储结构队列的基本操作方法及算法；能初步应用队列结构。4明确数组的概念、数组的顺序存储的特点；掌握顺序存储数组的存储地址计算方法；掌握特殊矩阵和压缩矩阵的存储方法和存储地址计算方法。5明确广义表的概念，掌握求广义表的
5、表头、表尾、长度和深度方法。重点：线性表顺序存储结构、链式存储结构及其基本操作方法和算法；栈的特点及入栈、出栈等基本操作方法，栈在顺序存储结构、链式存储结构上的基本操作及算法；队列的特点及入队、出队等基本操作方法，队列在顺序存储结构、链式存储结构上的基本操作算法；计算数组的存储地址；特殊矩阵和压缩矩阵的存储方法；求广义表的表头、表尾、长度、深度。难点：线性结构的算法及初步应用；栈的基本算法及应用，循环队列的基本算法及初步应用。自主学习内容：了解线性结构的抽象数据类型，明确串的概念和抽象数据类型定义，掌握串的基本算法，串的初步应用(6 学时)。 （三）树结构1 明确树的基本概念；明确树的各种存储
6、结构；明确二叉树的概念；掌握二叉树的顺序存储表示和链式存储表示方法；掌握二叉树的性质，掌握二叉树遍历方法；掌握二叉树前序、中序遍历的递归和非递归算法；掌握二叉树后序遍历的递归算法；掌握二叉树的初步应用算法；明确线索二叉树的概念；掌握前序、中序、后序线索化二叉树的方法。2 树、森林与二叉树的转换及遍历方法。3明确哈夫曼树和哈夫曼编码的概念，掌握哈夫曼树和哈夫曼编码的构造方法及含权路径长度的计算，了解哈夫曼树的应用。重点：二叉树的的存储结构；二叉树的性质；二叉树的前序、中序、后序遍历方法及其算法；二叉树的初步应用算法；构造哈夫曼树和哈夫曼编码的方法；森林与二叉树之间的转换方法。难点：二叉树的前序、
7、中序、后序遍历的算法；二叉树的初步应用算法；构造哈夫曼树的算法和构造哈夫曼编码的方法。自主学习内容：明确二叉树抽象数据类型；掌握树、森林与二叉树的转换方法；掌握树与森林的常用遍历方法(4 学时)。（四）图结构1 明确图的基本概念；掌握图的邻接矩阵存储和邻接表存储的方法与算法。2明确图的遍历的概念；掌握图的深度优先搜索与宽度优先搜索的方法和算法；掌握求图的连通分量的方法。3明确图的生成树和最小生成树的概念；掌握构造图的生成树和最小生成树的方法；能初步应用求解最小生成树的问题。4明确图的最短路径的概念；掌握求图的单源点最短路径的方法，能初步应用求解最短路径的问题。5 明确图的拓扑排序和关键路径的概
8、念；掌握求图的拓补排序和关键路径的方法；能初步应用关键路径的技术进行工程计划。重点：图的邻接矩阵和邻接表表示方法和算法；图的按深度优先搜索遍历方法和按广度优先搜索遍历方法和算法；构造最小生成树的方法；求最短路径的方法，拓补排序和关键路径的方法进行工程计划。难点：建立图的邻接表的算法；深度优先搜索遍历和按广度优先搜索遍历算法；构造最小生成树、求最短路径、求拓补排序和关键路径的方法；自主学习内容：明确图的抽象数据类型定义；了解最小生成树、求最短路径、求拓补排序和关键路径的算法(8 学时)。（五）查找1 明确查找的有关概念；掌握顺序查找、二分查找查找的方法及算法；掌握顺序查找、二分查找查找中比较次数
9、的计算和查找的时间复杂度分析方法。 2 明确二叉排序树的概念；掌握二叉排序树查找、构造、插入结点和删除结点的方法、掌握二叉排序树查找、构造和插入结点的算法，二叉排序树中删除结点的方法。3 明确哈希查找的概念；掌握常用的哈希函数构造哈希表的方法，掌握用线性探测法和链地址法解决冲突构造哈希表的方法及进行查找长度的计算。重点：顺序查找、二分查找的方法、算法和时间复杂度的分析方法；构造二叉排序树的方法及算法；二叉排序树中查找和插入结点的方法和算法，二叉排序树中删除结点的方法，用线性探测法和链地址法解决冲突构造哈希表的方法。难点：顺序查找、二分查找的时间复杂度及分析方法；构造二叉排序树、二叉排序树中查找
10、、插入结点的算法，二叉排序树中删除节点的方法，用线性探测法和链地址法解决冲突构造哈希表的查找长度的计算。自学内容：平衡二叉排序树的方法；了解二叉排序树中删除结点的算法(4 学时)。（六）排序1 明确排序的有关概念；明确内部排序的时间复杂度、空间复杂度及算法稳定性的概念；基本掌握常用排序的时间复杂度、空间复杂度和算法稳定性。2 掌握插入排序、二分插入排序、冒泡排序、选择排序、希尔排序的方法和特性；初步掌握插入排序、二分插入排序、希尔排序的算法；掌握快速排序、堆排序、归并排序、基数排序的方法。重点：常用排序的时间复杂度计算；插入排序、二分插入排序、希尔排序的方法和算法、快速排序、堆排序、二路归并排
11、序、基数排序的方法。难点：常用排序的时间复杂度计算；快速排序、堆排序的方法。自学内容：了解快速排序、堆排序、二路归并排序的算法；掌握常用排序的时间复杂度和空间复杂度(6 学时)。实验：实验教学的目的：本课程是一门实践性较强的软件技术基础课程，它在计算机软件教学中起着承上启下的作用，通过实验使学生巩固理论课中讲授的知识和技能。学习选择合适的逻辑结构和存储结构，数据组织方法，并在此基础上掌握对这些数据对象的操作技术，在线性表、栈、队列等结构通过高级语言编程，进行结构设计和实现训练，巩固和提高结构应用、算法设计与实现的能力，同时培养学生科学的思想方法，编写结构清晰，正确易读，效率较高的算法的能力。
12、实验一 大整数相加1 实验目的：线性表的存储结构及基本运算、实现方法和技术的训练。程序设计训练。2 实验内容：给定两个非负整数 A 和 B, 计算出 A+B 的值。整数 A 和 B 的位数可能超过整数类型数据能存储的范围。要求计算并输出 A+B 的值。3 实验基本要求：(1) 正确输入两个大整数；(2) 利用线性表的存储结构存储两个大整数；(3) 对存储于线性表的两个大整数，根据数据加法的要求，通过对线性表的操作，使两个大整数的和存储于线性表，并考虑尽量使用原线性表的存储空间；(4) 输出两个大整数的和，即输出和线性表中的内容。实验二 栈序列匹配1 实验目的：栈的存储结构及其基本运算、实现方法
13、和技术的训练。2 实验内容：对于给出的入栈序列和出栈序列，判断这两个序列是否相容，即能否利用栈操作将入栈序列转换为出栈序列。3 实验基本要求：入栈序列和出栈序列均为字符型数据，由键盘输入，其长度不超过 10 个字符。若入栈序列和出栈序列相容( 即能利用栈操作将入栈序列转换为出栈序列) ，则输出 yes，否则输出 no。在判断栈序列的匹配过程中，输出入栈、出栈的过程和栈中的元素。实验三 二叉排序树(可选，与程序设计基础有关)1 实验目的：非线性结构二叉树的存储及其遍历、搜索方法、技术和算法的训练，二叉树知识和技能应用的设计训练。2 实验内容：输入一个整数关键字序列 L，生成一棵用链式存储结构存储
14、的二叉排序树，对该二叉排序树能进行查找和插入结点的操作，并对该二叉排序树中结点的关键字按递增和递减顺序输出。3 实验基本要求：输入数据的第一行为一个正整数 T, 表示测试数据的组数。然后是 T 组测试数据。每组测试数据的第一行输入正整数 n(5n20)，第二行输入 n 个整数，要求依次完成以下工作：(1) 以这 n 个整数生成(建立)一棵用链式存储结构存储的二叉排序树；(2) 按递增顺序输出该二叉排序树中的整数( 关键字)；(3) 输入一个整数 key，对该二叉排序树进行查找，若在该二叉排序树中存在这个整数 key，则输出find，否则输出 not find；(4) 输入一个整数 key，若该
15、二叉排序树中不存在这个整数 key，则将 key 插入到该二叉排序树中，使插入后仍为原性质的二叉排序树；否则不必插入；(5) 在(4)的基础上，按递减顺序输出该二叉排序树中的整数(关键字)。四、学时分配总学时 64 学时，其中理论 48 学时，实践 16 学时。自主学习 32 小时。学时分配如下：教学内容 理论学时 实践学时 合计基本概念 3 3线性结构 12 10 22树结构 8 3 11图结构 10 10查找 7 3 10排序 8 8合计 48 16 64序号 实验名称 学时 实验要求 实验类型1 大整数加法 8 必修 验证2 栈序列匹配 8 必修 验证3 二叉排序树 8 选修 综合自主学
16、习内容 建议时间各结构的抽象数据类型 4线性结构链式存储结构的基本算法，串的概念，串的基本算法。 6二叉树的初步应用及算法；树、森林与二叉树的转换方法；树与森林的常用遍历方法。 4图的最小生成树、求最短路径、求拓补排序和关键路径的算法。 8平衡二叉排序树的方法；二叉排序树中删除结点的算法。 4快速排序、堆排序、二路归并排序的算法 6合计 32五、学业评价和课程考核过程考核与结果性考核相结合： 平时成绩( 书面作业、含实验、在线编程练习)占 30%，期末闭卷考核成绩占 70%。六、教学反馈1书面作业批改后反馈不少于 12 次；2实验过程中学生提问而进行的对话指导式的反馈(动态) 。七、教材与参考书教 材：严蔚敏 等编著.数据结构(C 语言版).北京：人民邮电出版社.2011 年 2 月 参考资料：1 严蔚敏 等编著.数据结构(C 语言版). 北京：清华大学出版社.1997 年 4 月2 许卓群 等编著.数据结构.北京：高等教育出版社.1987 年 5 月3 严蔚敏 等编著.数据结构题集.北京：清华大学出版社 .1999 年 2 月4 李春葆 编著.数据结构(C 语言篇) 习题与解析.北京：清华大学出版社.2002 年 8 月八、说明实践时间课内外学时比至少为 1:2
