数据结构与算法教学大纲.docx

《数据结构与算法教学大纲.docx》由会员分享，可在线阅读，更多相关《数据结构与算法教学大纲.docx（7页珍藏版）》请在优知文库上搜索。

1、数据结构教学大纲一、课程基本信息课程名称：数据结构总学时：64（理论课内学时48,上机课内学时16）课程设计：24课程类型：必修课考试形式：半开卷考试讲课对象：计算机本科建议教材：数据结构（C语言版）陈明编著清华大学出版社课程简介：数据结构课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：数组、链接表、栈和队列、串、树与森林、图、排序、查找、索引与散列结构等。课程以结构化程序设计语言C语言作为算法的描述工具，强化数据结构基本知识和结构化程序设计基本能力的双基训练。为后续计算机专业课程的学习打下坚实的基础。二、课程的教学目标“数据结构”是计算机相关专业的一门重要专业基础课，是计算机

2、学科的公认主干课。课程内容由数据结构和算法分析初步两部份组成。数据结构是针对处理大量非数值性程序问题而形成的一门学科，内涵丰富、应用范围广。它既有完整的学科体系和学科深度，又有较强的实践性。通过课程的学习，应使学生理解和掌握各种数据结构（物理结构和逻辑结构）的概念及其有关的算法；熟悉并了解目前常用数据结构在计算机诸多领域中的基本应用。算法分析强调最基本的算法设计技术和分析方法。要求学生从算法和数据结构的相互依存关系中把握应用算法设计的艺术和技能。经过上机实习和课程设计的训练，使学生能够编制、调试具有一定难度的中型程序；以培养良好的软件工程习惯和面向对象的软件思维方法。“数据结构”的前序课是离散

3、数学、C语言程序设计与算法初步。三、理论教学内容的基本要求及学时分配1、序论（2学时）学习目标：熟悉各类文件的特点，构造方法以及如何实现检索，插入和删除等操作。重点与难点：本章无。知识点：数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂度、空间复杂度。2、线性表(4学时)学习目标：(1)了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表；(2)熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现；(3)能够从

4、时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其合用场合；(4)结合线性表类型的定义增强对抽象数据类型的理解。重点与难点：链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针P和结点*p之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。知识点：线性表、顺序表、链表、有序表。3、栈和队列(4学时)学习目标：(1)掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们；(2)熟练掌握栈类型的两种实现方法；(3)熟练掌握循环队列和链队列的基本操作实现算法；(4)理解递归算法执行过

5、程中栈的状态变化过程。重点与难点：栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。知识点：顺序栈、链栈、循环队列、链队列。4、串(2学时)学习目标：(1)理解串类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作；(2)理解串类型的各种存储表示方法；(3)理解串匹配的各种算法。重点和难点：相对于其它各个知识点而言，本章非整个课程的重点，鉴于串己是多数高级语言中已经实现的数据类型，因此本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。本章的难点是理解实现串匹

6、配的KMP算法的思想。知识点：串的类型定义、串的存储表示、串匹配、KMP算法。5、数组和广义表(4学时)学习目标：(1)理解数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主”的存储表示中的地址计算方法；(2)掌握特殊矩阵的存储压缩表示方法；(3)理解稀疏矩阵的两类存储压缩方法的特点及其合用范围，领略以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。重点和难点：本章重点是学习数组类型的定义及其存储表示。知识点：数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、随机稀疏矩阵的压缩存储表示方法。6、树和二叉树(8学时)学习目标：(1)领略树和二叉树的类型定义

7、，理解树和二叉树的结构差别；(2)熟记二叉树的主要特性，并掌握它们的证明方法；(3)熟练掌握二叉树的各种遍历算法，并能灵便运用遍历算法实现二叉树的其它操作；(4)理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法；(5)熟练掌握二叉树和树的各种存储结构及其建立的算法；(6)学会编写实现树的各种操作的算法；(7)了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。重点和难点：二叉树和树的遍历及其应用是本章的学习重点，而编写实现二叉树和树的各种操作的递归算法也恰是本章的难点所在。知识点：树的类型定义、二叉树的类型定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、线索二叉树

8、、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码。7、图(8学时)学习目标：(1)领略图的类型定义；(2)熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则；(3)熟练掌握图的两种遍历算法；(4)理解各种图的应用问题的算法。重点和难点：图的应用极其广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。知识点：图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径。8、查找(6学时)学习目标：(1)理解“查找表”的结构特点以及各种表示方法的合用性；(2

9、)熟练掌握以顺序表或者有序表表示静态查找表时的查找方法；(3)熟悉静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系；(4)熟练掌握二叉查找树的构造和查找方法；(5)理解二叉平衡树的构造过程；(6)熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；(7)掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。重点和难点：本章重点在于理解查找表的结构特点及其各种表示方法的特点和合用场合。知识点：顺序表、有序表、索引顺序表、静态查找树、二叉查找树、二叉平衡树、哈希表。9、内部排序(6学时)学习目标：理解排序的定义和各种排

10、序方法的特点，并能加以灵便应用。排序方法有不同的分类方法，基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类；(2)掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：O(n2)的简单排序方法，O(n*lOgn)的高效排序方法和O(d*n)的基数排序方法；(3)理解排序方法“稳定”或者“不稳定”的含义，弄清晰在什么情况下要求应用的排序方法必须是稳定的。重点和难点：希尔排序、快速排序、堆排序和归并排序等高效方法是本章的学习重

11、点和难点。知识点：排序、直接插入排序、折半插入排序、表插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序、基数排序、排序方法的综合比较。10、文件(4学时)学习目标：熟悉各类文件的特点，构造方法以及如何实现检索，插入和删除等操作。重点和难点：本章重点在于了解各种文件的结构特点及其合用场合。知识点：顺叙文件、索引文件、B-树、B+树、索引顺叙文件、VSAM文件、散列文件、多关键字文件。四、实验教学内容的基本要求及学时分配1、线性表(1学时)实验一顺序表的应用实验二链表的应用要求：理解线性表的定义及其运算；理解顺序表和链表的定义，组织形式，结构特征和类型说明；掌握在这两种

12、表上实现的插入，删除和按值查找的算法；了解循环链表，双(循环)链表的结构特点和在其上施加的插入，删除等操作。2、栈(0.5学时)实验三栈的应用要求：理解栈的定义，特征及在其上所定义的基本运算；掌握在两种存储结构上对栈所施加的基本运算的实现。3、队列。5学时）实验四队列的应用要求：理解队列的定义，特征及在其上所定义的基本运算；掌握在两种存储结构上对队列所施加的基本运算的实现。4、串（0.5学时）实验五串的应用要求：了解串的定义；理解和领略串的存储方式；掌握常用的串运算。5、数组和广义表（0.5学时）实验六稀疏矩阵的应用要求：理解多维数组的结构特点和在内存中的两种顺序存储方式；理解并掌握矩阵和特殊

13、矩阵元素在存储区中地址的计算；领略稀疏矩阵的压缩方式和简单运算；了解广义表的定义和基本运算。6、树与二叉树（4学时）实验七树与二叉树的应用要求：理解树的定义，术语；领略并掌握树的各种存储结构；熟练掌握森林与二叉树间的相互转换；领略树和森林的遍历；了解树的简单应用。深刻理解二叉树的定义，性质及其存储方法；熟练掌握二叉树的二叉链表存储方式，结点结构和类型定义；理解并掌握二叉树的三种遍历算法；掌握二叉树的线索化方法；灵便运用二叉树的遍历方法解决相关的应用问题。7、图（3学时）实验八图的应用要求：理解图的基本概念及术语；掌握图的两种存储结构（邻接矩阵和邻接表）的表示方法；熟练掌握图的两种遍历（深度优先

14、搜索遍历和广度优先搜索遍历）的算法思想，步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树的概念，能按Prim算法构造最小生成树；领略并掌握拓扑排序，关键路径，最短路径的算法思想。8、查找（3学时）实验九顺序查找实验十折半查找实验H哈希表的应用实验十二二叉排序树的综合练习要求：了解查找的基本思想及查找成功和不成功的概念；掌握在顺序表，有序表，索引表，散列表等上的查找方法和算法，并能求出相应的平均查找长度；理解并掌握二叉排序树，平衡二叉树B-树的各种算法。9、排序（3学时）实验十三插入排序实验十四选择排序实验十五排序综合练习要求：领略排序的基本思想和基本概念；理解并掌握插

15、入排序，冒泡排序，快速排序，直接选择排序，堆排序，归并排序和基数排序的基本思想，步骤，算法及时空效率分析；了解外排序的定义和基本方法。五、大纲说明1、课堂讲述的论题只是核心或者有特色的知识内容，还有相当数量的篇章内容留给学生自学，所确定的自学部份内容亦属考查范围。2、“数据结构”课注重上机训练，所有作业都必须配有规范的文档。上机训练由平时的上机训练和小学期的实训课程设计两部份组成。3、课内学时安排说明：前8周每周4学时全为理论课，从第9周开始理论和上机为1：1,也即2学时理论，2学时上机训练。4、本课强调能力的培养，期末采用半开卷考试（允许同学携带一页A4纸的总结资料）。本课成绩由平时作业、上机成绩（30%）和期末考试（70%）合成得到，有独到见解的作业予以适当加分。5、主要参考书：1数据结构与算法教程邹永林周蒋唐晓阳杨剑勇编著机械工业出版社2数据结构（C语言版）（含CD）严蔚敏吴为民编著清华大学出版社3数据结构习题集（C语言版）严蔚敏编著清华大学出版社4数据结构习题解析与实训张世和编著清华大学出版社