数据结构教学大纲

-1-数据结构教学大纲课程编号：090010课程名称：数据结构英文名称：DataStructure学分：5学时：102，其中讲授68学时，实验34学时适用年级专业（学科类）：二年级数学类、数电类一、课程概述（一）课程性质《数据结构》是计算机及相关专业的一门综合性的专业基础课，是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，同时数据结构技术也被广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。本课程主要介绍如何合理的组织和表示数据、如何有效的存储和处理数据、如何正确的设计算法以及对算法的优劣作出分析和评价。（二）教学目标与要求通过本课程的学习，使学生深透理解各种常用数据结构的逻辑结构、存储结构及相关算法的实现；全面掌握处理数据的理论和方法，培养学生选用合适的数据结构，编写质量高、风格好的程序及初步评价算法的能力；使学生系统的科学的受到分析问题和解决问题的训练，提高运用数据结构解决实际问题的能力，为后续的软件课程奠定良好的基础。（三）重点和难点本课程的重点是：从数据结构的逻辑结构、存储结构、数据的运算三个方面去掌握线性表、栈、队列、串、数组、树、图等常用的数据结构；掌握常用的各种查找方法和排序算法；并培养对算法的时间空间复杂性的分析能力。本课程的难点有：逻辑结构与存储结构的关系，顺序表和链表的区别与联系，栈和队列的特点，模式匹配，矩阵的压缩存储，二叉树的性质，二叉树的各种遍历算法，哈夫曼树，最小生成树，关键路径，折半查找，二叉排序树，平衡二叉树，B-树，哈希表，各种排序方法及性能分析。（四）与其他课程的关系数据结构的先修课程有计算机导论、C语言程序设计、离散数学；后继课程有操作系统、编译原理、数据库原理、人工智能等。数据结构中存储结构及基本运算的实现需要程序设计的基本知识和编程的经验及能力，本课程的算法用C语言实现，因此要求学生较熟练地掌握C语言。（五）教材及教学参考书的选用1、《数据结构》，刘振鹏，中国铁道出版社，2003年9月；2、《数据结构与算法》，张晓莉，机械工业出版社，2002年9月；3、《数据结构（C语言版）》，严蔚敏，清华大学出版社，1997年4月；4、《DataStructures，Algorithms，andApplicationsinC＋＋》，（美）SartajSahni，机械工-2-业出版社，1999年。5、《数据结构与算法》，许卓群，高等教育出版社，2004年7月二、学时分配章课程内容学时1绪论22线型表83栈和队列44串45数组、特殊矩阵和广义表46二叉树107树和森林48图129查找1010排序10三、课程内容第一章绪论教学目的和要求：本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。重点和难点：1、教学重点：了解数据结构的逻辑结构、存储结构及数据运算等三方面的概念及相互关系，算法的性能评价。2、教学难点：抽象数据类型的概念的理解，算法时间复杂度的分析方法。主要内容：1、数据结构的概念；2、抽象数据类型；3、算法和算法分析。主要教学环节的组织：课堂讲授。思考题：1、试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算这三方面的内容。2、比较逻辑结构和存储结构的关系。3、比较数据结构的概念与程序设计语言中数据类型的概念的区别与联系。-3-第二章线性表教学目的和要求：本章目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算在相应的存储结构上的实现。要求在熟悉这些内容的基础上，能够针对具体的应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。重点和难点：1、教学重点：顺序表和单链表上实现的各种基本算法及相关的时间性能分析。2、教学难点：用本章所学到的基本知识设计算法解决与线性表相关的实际应用问题。主要内容：1、线性表的逻辑结构；2、线性表的顺序存储及运算实现；3、线性表的链式存储及运算实现；4、顺序表和链表的比较。主要教学环节的组织：课堂教学与实践。思考题：1、请比较顺序表与链表的优缺点。2、单链表具有随机存取的性质吗？顺序表呢？为什么？第三章栈和队列教学目的和要求：本章的目的是介绍栈和队列的逻辑结构定义及其在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下使用栈或队列，掌握在不同的存储结构上实现栈和队列的方法。重点和难点：1、教学重点：栈和队列在两种存储结构上基本操作的实现。2、教学难点：循环队列中对边界条件的处理及栈和队列的应用。主要内容：1、栈及其性质；2、栈的应用举例；3、队列及其性质；4、队列的应用举例。主要教学环节的组织：课堂教学与实践。思考题：1、栈和队列各有什么特点，什么情况下用到栈，什么情况下用到队列？-4-2、循环队列是如何实现“循环”的？第四章串教学目的和要求：本章目的是介绍串的逻辑结构、存储结构及其字符串上的基本运算，要求掌握串的各种存储结构、串的常用运算及模式匹配算法。重点和难点：1、教学重点：串的存储结构及基本运算。2、教学难点：模式匹配。主要内容：1、串及其基本运算；2、串的定长顺序存储及基本运算；3、串的堆存储结构。主要教学环节的组织：课堂教学与实践。思考题：1、KMP算法与朴素的模式匹配算法相比有何优越性？2、求模式串的next函数值有什么意义？第五章数组、特殊矩阵和广义表教学目的和要求：本章的目的是介绍多维数组的逻辑结构特征及存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念及存储实现方法。重点和难点：1、教学重点：多维数组的存储方式、矩阵的压缩存储方法、广义表的定义及基本运算。2、教学难点：特殊矩阵的压缩方法，稀疏矩阵的压缩存储及其运算的实现。主要内容：1、多维数组；2、特殊矩阵的压缩存储；3、稀疏矩阵；4、广义表。主要教学环节的组织：课堂教学与实践。思考题：1、如何用一维的空间表示多维的数组？2、为什么要对矩阵进行压缩存储？-5-3、广义表和一般的线性表有和异同？第六章二叉树教学目的和要求：本章目的是介绍二叉树的定义、性质、存储结构、遍历、线索化及二叉树的应用等内容，要求掌握二叉树的性质、存储结构，掌握二叉树的各种遍历算法及其应用，哈夫曼树等。重点和难点：1、教学重点：二叉树的性质，二叉树的遍历算法及其应用，哈夫曼树。2、教学难点：二叉树性质的证明，基于二叉树遍历解决实际问题，哈夫曼编码。主要内容：1、二叉树的定义与性质；2、二叉树的存储实现基本操作的实现；3、二叉树的遍历；4、线索二叉树；5、二叉树的应用。主要教学环节的组织：课堂教学与实践。思考题：1、一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？2、在结点数多于1的哈夫曼树中存在度为1的结点吗？3、遍历二叉树的方法有哪些？遍历二叉树的实质是什么？第七章树和森林教学目的和要求：本章介绍树和森林的定义、存储结构、和二叉树之间的转换、遍历及树的应用等内容，要求掌握树与二叉树之间的转换及其树的应用等。重点和难点：1、教学重点：树和森林的存储结构、遍历，树、森林和二叉树之间的转换。2、教学难点：树和森林的遍历及由遍历序列恢复树或森林，用相关知识解决与树的实际应用问题。主要内容：1、树的概念与表示；2、树的基本操作与存储；3、树、森林与二叉树的转换；4、树或森林的遍历；5、树的应用。主要教学环节的组织：-6-课堂教学与实践。思考题：1、树、森林和二叉树之间有什么关系？2、已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问该树中共有多少个叶子结点？有多少个非终端结点？第八章教学目的和要求：教学目的和要求：本章的目的是介绍图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法，在熟悉这些内容的基础上，重点和难点：1、教学重点：图的存储结构，图的遍历算法，图的几种应用算法。2、教学难点：最小生成树，最短路径，拓扑排序，关键路径。主要内容：1、图的基本概念；2、图的存储表示；3、图的遍历；4、生成树与最小生成树；5、最短路径；6、有向无环图及其应用。主要教学环节的组织：课堂教学与实践。思考题：1、比较Prim算法和Kruskal算法，当边数较少时用哪一个方法较好？2、用哪些方法可以判断有向图中有环路存在？3、加快一个关键活动，一定能缩短工期吗？第九章查找教学目的和要求：本章目的是介绍各种存储方式下的查找表的查找方法，以及各种查找方法的时间性能分析，重点和难点：1、教学重点：顺序查找、二分查找、二叉树排序树、平衡二叉树，B-树以及哈希表上的查找思想、算法实现及查找性能的分析。2、教学难点：二叉排序树的删除，平衡二叉树的调整，B-树的插入和删除，哈希表中处理冲突的方法。主要内容：-7-1、基本概念；2、静态查找表；3、动态查找表；4、哈希表查找(杂凑法)。主要教学环节的组织：课堂教学与实践。思考题：1、试推导含有12个结点的平衡二叉树的最大深度，并画出一棵这样的树。2、含有9个叶子结点的3阶B–树中至少有多少个非叶子结点？含有10个叶子结点的3阶B–树中至少有多少个非叶子结点？3、比较哈希查找方法与其他查找方法的区别。第十章排序教学目的和要求：本章目的介绍5类内部排序方法的基本思想、排序过程、算法事现、时间和空间性能的分析以及各种排序方法的比较和选择。重点和难点：1、教学重点：各种排序的思想、算法实现、稳定性、适用情况、时间空间复杂度分析。2、教学难点：希尔排序，快速排序，堆排序。主要内容：1、基本概念；2、插入排序；3、交换排序；4、选择排序；5、二路归并排序；6、基数排序；7、外排序。主要教学环节的组织：课堂教学与实践。思考题：1、如果只想得到一个序列中第k小元素前的部分排序序列，最好采用什么排序方法？为什么？2、有n个不同的英文单词，它们的长度相等，均为m，若n50,m5，试问采用什么排序方法时间复杂度最佳？为什么？四、教学方式课堂讲授、课堂讨论、上机实验等。-8-五、课程考核考核类型：考试计分办法：平时成绩占30-40%，考试成绩占60-70%。