数据结构与算法教学大纲_数据结构与算法总复习
数据结构与算法教学大纲由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构与算法总复习”。
《数据结构》教学大纲
一、课程基本信息
课程名称：数据结构
总学时：64(理论课内学时48，上机课内学时16)课程设计：24 课程类型：必修课
考试形式：半开卷考试 讲课对象：计算机本科
建议教材：《数据结构》(C语言版)陈明 编著 清华大学出版社
课程简介：数据结构课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：数组、链接表、栈和队列、串、树与森林、图、排序、查找、索引与散列结构等。课程以结构化程序设计语言C语言作为算法的描述工具，强化数据结构基本知识和结构化程序设计基本能力的双基训练。为后续计算机专业课程的学习打下坚实的基础。
二、课程的教学目标
“数据结构”是计算机相关专业的一门重要专业基础课，是计算机学科的公认主干课。课程内容由数据结构和算法分析初步两部分组成。
数据结构是针对处理大量非数值性程序问题而形成的一门学科，内涵丰富、应用范围广。它既有完整的学科体系和学科深度，又有较强的实践性。通过课程的学习，应使学生理解和掌握各种数据结构(物理结构和逻辑结构)的概念及其有关的算法；熟悉并了解目前常用数据结构在计算机诸多领域中的基本应用。
算法分析强调最基本的算法设计技术和分析方法。要求学生从算法和数据结构的相互依存关系中把握应用算法设计的艺术和技能。
经过上机实习和课程设计的训练，使学生能够编制、调试具有一定难度的中型程序；以培养良好的软件工程习惯和面向对象的软件思维方法。
“数据结构”的前序课是《离散数学》、《C语言程序设计与算法初步》。
三、理论教学内容的基本要求及学时分配
1、序论(2学时)学习目标：熟悉各类文件的特点，构造方法以及如何实现检索，插入和删除等操作。
重点与难点：本章无。
知识点：数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂度、空间复杂度。
2、线性表(4学时)
学习目标：
(1)了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表；
(2)熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现；
(3)能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合；
(4)结合线性表类型的定义增强对抽象数据类型的理解。
重点与难点：链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针 p 和结点 *p 之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。
知识点：线性表、顺序表、链表、有序表。
3、栈和队列(4学时)
学习目标：
(1)掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们；
(2)熟练掌握栈类型的两种实现方法；
(3)熟练掌握循环队列和链队列的基本操作实现算法；(4)理解递归算法执行过程中栈的状态变化过程。
重点与难点：栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。
知识点：顺序栈、链栈、循环队列、链队列。
4、串(2学时)
学习目标：(1)理解串类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作；
(2)理解串类型的各种存储表示方法；(3)理解串匹配的各种算法。
重点和难点：相对于其它各个知识点而言，本章非整个课程的重点，鉴于串已是多数高级语言中已经实现的数据类型，因此本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。本章的难点是理解实现串匹配的KMP算法的思想。
知识点：串的类型定义、串的存储表示、串匹配、KMP算法。
5、数组和广义表(4学时)
学习目标：
(1)理解数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主”的存储表示中的地址计算方法；
(2)掌握特殊矩阵的存储压缩表示方法；
(3)理解稀疏矩阵的两类存储压缩方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。
重点和难点：本章重点是学习数组类型的定义及其存储表示。
知识点：数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、随机稀疏矩阵的压缩存储表示方法。
6、树和二叉树(8学时)
学习目标：
(1)领会树和二叉树的类型定义，理解树和二叉树的结构差别；(2)熟记二叉树的主要特性，并掌握它们的证明方法；
(3)熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作；
(4)理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法；
(5)熟练掌握二叉树和树的各种存储结构及其建立的算法；(6)学会编写实现树的各种操作的算法；
(7)了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。
重点和难点：二叉树和树的遍历及其应用是本章的学习重点，而编写实现二叉树和树的各种操作的递归算法也恰是本章的难点所在。
知识点：树的类型定义、二叉树的类型定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、线索二叉树、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码。
7、图(8学时)
学习目标：
(1)领会图的类型定义；
(2)熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则；
(3)熟练掌握图的两种遍历算法；(4)理解各种图的应用问题的算法。
重点和难点：图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。
知识点：图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径。
8、查找(6学时)
学习目标：
(1)理解“查找表”的结构特点以及各种表示方法的适用性；(2)熟练掌握以顺序表或有序表表示静态查找表时的查找方法；
(3)熟悉静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系；
(4)熟练掌握二叉查找树的构造和查找方法；(5)理解二叉平衡树的构造过程；
(6)熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；
(7)掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
重点和难点：本章重点在于理解查找表的结构特点及其各种表示方法的特点和适用场合。
知识点：顺序表、有序表、索引顺序表、静态查找树、二叉查找树、二叉平衡树、哈希表。
9、内部排序(6学时)
学习目标：
(1)理解排序的定义和各种排序方法的特点，并能加以灵活应用。排序方法有不同的分类方法，基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类；
(2)掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：O(n2)的简单排序方法，O(n*logn)的高效排序方法和O(d*n)的基数排序方法；
(3)理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。
重点和难点：希尔排序、快速排序、堆排序和归并排序等高效方法是本章的学习重点和难点。
知识点：排序、直接插入排序、折半插入排序、表插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序、基数排序、排序方法的综合比较。
10、文件(4学时)
学习目标：熟悉各类文件的特点，构造方法以及如何实现检索，插入和删除等操作。
重点和难点：本章重点在于了解各种文件的结构特点及其适用场合。知识点：顺序文件、索引文件、B-树、B+树、索引顺序文件、VSAM文件、散列文件、多关键字文件。
四、实验教学内容的基本要求及学时分配
1、线性表(1学时)实验一 顺序表的应用 实验二 链表的应用
要求：理解线性表的定义及其运算；理解顺序表和链表的定义，组织形式，结构特征和类型说明；掌握在这两种表上实现的插入，删除和按值查找的算法；了解循环链表，双(循环)链表的结构特点和在其上施加的插入，删除等操作。
2、栈(0.5学时)实验三 栈的应用
要求：理解栈的定义，特征及在其上所定义的基本运算；掌握在两种存储结构上对栈所施加的基本运算的实现。
3、队列(0.5学时)实验四 队列的应用
要求：理解队列的定义，特征及在其上所定义的基本运算；掌握在两种存储结构上对队列所施加的基本运算的实现。
4、串(0.5学时)实验五 串的应用
要求：了解串的定义；理解和领会串的存储方式；掌握常用的串运算。
5、数组和广义表(0.5学时)实验六 稀疏矩阵的应用
要求：理解多维数组的结构特点和在内存中的两种顺序存储方式；理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算；领会稀疏矩阵的压缩方式和简单运算；了解广义表的定义和基本运算。
6、树与二叉树(4学时)实验七 树与二叉树的应用
要求：理解树的定义，术语；领会并掌握树的各种存储结构；熟练掌握森林与二叉树间的相互转换；领会树和森林的遍历；了解树的简单应用。深刻理解二叉树的定义，性质及其存储方法；熟练掌握二叉树的二叉链表存储方式，结点结构和类型定义；理解并掌握二叉树的三种遍历算法；掌握二叉树的线索化方法；灵活运用二叉树的遍历方法解决相关的应用问题。
7、图(3学时)实验八 图的应用
要求：理解图的基本概念及术语；掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法；熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想，步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树的概念，能按Prim算法构造最小生成树；领会并掌握拓扑排序，关键路径，最短路径的算法思想。
8、查找(3学时)实验九 顺序查找 实验十 折半查找 实验十一 哈希表的应用 实验十二 二叉排序树的综合练习 要求：了解查找的基本思想及查找成功和不成功的概念；掌握在顺序表，有序表，索引表，散列表等上的查找方法和算法，并能求出相应的平均查找长度；理解并掌握二叉排序树，平衡二叉树B-树的各种算法。
9、排序(3学时)实验十三 插入排序 实验十四 选择排序 实验十五 排序综合练习
要求：领会排序的基本思想和基本概念；理解并掌握插入排序，冒泡排序，快速排序，直接选择排序，堆排序，归并排序和基数排序的基本思想，步骤，算法及时空效率分析；了解外排序的定义和基本方法。
五、大纲说明
1、课堂讲述的论题只是核心或有特色的知识内容，还有相当数量的篇章内容留给学生自学，所确定的自学部分内容亦属考查范围。
2、“数据结构”课注重上机训练，所有作业都必须配有规范的文档。上机训练由平时的上机训练和小学期的实训课程设计两部分组成。
3、课内学时安排说明：前8周每周4学时全为理论课，从第9周开始理论和上机为1：1，也即2学时理论，2学时上机训练。
4、本课强调能力的培养，期末采用半开卷考试(允许同学携带一页A4纸的总结资料)。本课成绩由平时作业、上机成绩(30%)和期末考试(70%)合成得到，有独到见解的作业予以适当加分。
5、主要参考书：
[1]《数据结构与算法教程》邹永林 周蓓 唐晓阳 杨剑勇 编著 机械工业出版社
[2]《数据结构(C语言版)》(含CD)严蔚敏 吴为民 编著 清华大学出版社
[3]《数据结构习题集(C语言版)》严蔚敏 编著 清华大学出版社
[4]《数据结构习题解析与实训》张世和 编著 清华大学出版社
《算法与数据结构》教学大纲一、使用说明（一）课程性质《数据结构》是一门专业基础课，在计算机软件的各个领域中均会使用到数据结构的有关知识。本课程的先修课程为C程序设计或C......
教学大纲数据结构与算法 （Data Structures）计算机技术已成为现代化发展的重要支柱和标志，并逐步渗透到人类生活的各个领域。随着计算机硬件的发展，对计算机软件的发展也提出了越......
《数据结构与算法》课程设计教学大纲 （Data Structures & Algorithms）一、基本信息课程编号：E1132107 课程类别：学科基础课必修课 适用层次：本科适用专业：计算机科学与技术、网络......
《数据结构与算法》推荐信美国UIUC大学博士生梅俏竹数据结构是美国所有一流计算机系的本科核心课程之一，上承计算引论与初级程序设计，下启高级算法和计算理论，向来是计算机本科......
算法与数据结构总结算法与数据结构这一门课程，就是描述了数据的逻辑结构，数据的存储结构，以及数据的运算集合在计算机中的运用和体现。数据的逻辑结构就是数据与数据之间的逻辑......
