教学大纲数据结构本科.doc

数据结构与数据库技术本科教学大纲一、 课程性质、地位和作用课程类别：学科大类基础课课程性质：必修课数据结构是计算机应用专业的一门专业技术基础必修课程。主要研究数据的抽象数据类型定义、逻辑结构关系、物理表示以及基本操作及相应算法实现。要求学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。二、 课程教学对象、目的和要求教学对象： 本课程理论性强，同时要求较高实践，知识点多、实践内容烦杂，要求学生在学完本课程后，能够分析较复杂的应用问题，并能独立对问题进行数据抽象，针对实际问题进行抽象数据类型定义，并进行相应基本算法设计及实现。因此，教学中在深入阐述有关理论的基础上，应重视分析方法和综合设计的能力培养，教学中重点强调与实际相关的应用举例，同时应加强对实践环节的力度。三、 相关课程及关系学生在学习本课程之前应当具有C语言程序设计、高等数学、以及计算机硬件等方面的预备知识。同时，本课程是计算机网络、计算机操作系统、计算机方法以及其他Windows平台程序设计课程的基础课程。四、 课程内容及学时分配总学时：54 （课堂讲授： 50 ；习题： 2 ；考试：2）第 1 章 绪论1本章节的基本要求与基本知识点：（1）数据结构课程性质。（2）熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。（3）了解抽象数据类型的定义、表示和实现方法。（4）熟悉本课程使用的算法描述工具类C语言。（5）掌握计算语句频度和估算算法时间复杂度的方法。2要求学生应掌握的基本概念、基本理论、基本技能：通过本章学习，应当对数据结构在计算机学习体系中的地位和作用，熟悉相关的基本术语及概念有较清楚的了解，深刻理解抽象数据类型内涵，掌握抽象数据类型的定义、表示和实现方法，掌握类C语言算法描述工具，掌握算法估量的方法。3教学的重点、难点：重点：理解数据、数据元素、数据项，逻辑结构和数据结构，运算的概念，存储结构及其三个组成部分。掌握类C语言描述方法，重点掌握抽象数据类型内涵及抽象数据类型定义、表示和实现方法，以及算法估量方法。难点：在概念上逻辑结构和数据结构的联系与区别；区别算法与程序；逻辑结构、存储结构的联系与区别；区别抽象数据类型和数据类型，抽象数据类型定义、表示和实现；算法的时间复杂度分析。4课时分配：6节理论5对实践教学内容：无上机。第 2 章 线性表1本章节的基本要求与基本知识点：（1）了解线性表的概念，掌握线性表抽象数据类型定义方法。（2）了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构，掌握线性表的逻辑结构与物理结构对应关系。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。（3）熟练掌握线性表在存储结构上实现基本操作：初始化、查找、插入和删除等算法算法。（4）熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。（5）能够利用线性表解决一些实际问题。2要求学生应掌握的基本概念、基本理论、基本技能：通过本章学习，应掌握线性结构的特点及概念，熟悉线性表的逻辑结构，掌握线性表的抽象数据类型表示，掌握线性表的顺序表示和链式表示方法以及相应表示下的操作及实现3教学的重点、难点：重点：线性表的定义及逻辑上的特点；线性表存储表示及相应操作。难点：线性表与线性结构的联系区别；线性表的物理映射；存储表示；操作实现。4课时分配：12节理论5对实践教学内容：无上机。第 3 章 栈和队列1本章节的基本要求与基本知识点：（1）掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。（2）熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。（3）递归实现的方法和过程。（4）熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的的描述方法。（5）栈和队列的实际应用分析和举例。 2要求学生应掌握的基本概念、基本理论、基本技能：通过本章学习，应当掌握栈和队列两种特殊线性表的概念及操作特性，熟悉它们在实际中的应用方法，能够利用栈和队列解决一些实际问题，能够基于栈的思想，深刻理解递归的实现过程和方法。3教学的重点、难点：重点：栈的定义及逻辑特点；队列定义及逻辑特点；栈和队列的表示及操作。难点：顺序栈的溢出判断条件；顺序队列假溢出问题；栈和队列应用。 4课时分配：4节理论5对实践教学内容：无上机。第 5 章 数组1本章节的基本要求与基本知识点：（1）了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。（2）掌握对特殊矩阵进行压缩存储时的下标变换公式。（3）了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。2要求学生应掌握的基本概念、基本理论、基本技能：本章主要要求学会数组的表示方法，掌握数组中的地址计算方法，能够利用数组对特殊矩阵进行压缩存储。3教学的重点、难点：重点：多维数组的逻辑结构；特殊矩阵压缩存储；难点：矩阵元素与数组元素的对应关系； 4课时分配：4节理论5对实践教学内容：无上机。第 6 章 树1本章节的基本要求与基本知识点：（1）树的概念（2）树的表示（3）树的基本操作与存储和树的应用2要求学生应掌握的基本概念、基本理论、基本技能：本章主要要求理解树的概念，掌握树抽象数据类型定义方法，重点掌握树的性质及基本操作，3教学的重点、难点：重点：握树的性质及基本操作；难点：抽象数据类型定义方法； 4课时分配：4节理论5对实践教学内容：无上机。第 7 章 二叉树1本章节的基本要求与基本知识点：（1）熟练掌握二叉树的结构特性，了解相应的证明方法。（2）熟悉二叉树的各种存储结构的特点及适用范围。（3）遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。不仅要熟练掌握各种遍历二叉树策略的递归和非递归算法，了解遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。（4）掌握树和二叉树相互转换方法。（5）掌握Huffman编码方法。2要求学生应掌握的基本概念、基本理论、基本技能：本章主要要求理解二叉树的概念，掌握二叉树的抽象数据类型定义方法，重点掌握二叉树的性质及基本操作，熟悉树和二叉树、树和森林等相互转换方法，掌握Huffman编码技术，能够进行较复杂的算法设计和分析。3教学的重点、难点：重点：二叉树性质及其推论；二叉树遍历；线索二叉树；Huffman编码；树和二叉树、森林和树的转换关系。难点：二叉树性质；线索二叉树。4课时分配：8节理论5对实践教学内容：无上机。第 8 章 图1本章节的基本要求与基本知识点：（1）悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切关系。（2）熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索的两种形式（递归和非递归）和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略。（3）应用图的遍历算法求解各种简单路径问题。（4）应用图的遍历算法求解最短路径。2要求学生应掌握的基本概念、基本理论、基本技能：通过本章学习，要求掌握图的基本概念、术语及主要应用，掌握图的表示方法，熟悉图的基本操作，能够计算简单路径和最短路径。3教学的重点、难点：重点：图的定义及特点；图的存储表示及基本操作；图的遍历。难点：正确理解与区别图的常用术语；掌握图的存储结构；图的联通问题；最短路径计算。4课时分配：4节理论5对实践教学内容：无上机。第 9 章 查找1本章节的基本要求与基本知识点：（1）静态查找表概念，运算方法。（2）掌握顺序表、有序表、索引顺序表的查找方法。（3）掌握二叉排序树和平衡二叉树的生成以及其他操作方法。（4）B树和B树特点及运算方法。（5）哈希表特点以及哈希构造方法。2要求学生应掌握的基本概念、基本理论、基本技能：通过本章学习，应该对查找表有一个较深的认识，应掌握静态查找表、二叉排序树和平衡二叉树、B树以及哈希构造方法。3教学的重点、难点：重点：查找表的概念以及查找表的构造；静态查找表的操作；二叉排序树和平衡二叉树的构造、特点及运算；B树和B树的构造及特点；哈希表的特点以及哈希函数构造方法及冲突处理方法。难点：哈希函数的构造及冲突处理；二叉排序树和平衡二叉树的构造、特点及运算。4课时分配：4节理论5对实践教学内容：无上机。第 10 章 排序1本章节的基本要求与基本知识点：（1）掌握内部排序概念及作用。（2）掌握插入排序、快速排序以及简单选择排序的方法及算法。（3）了解归并排序及基数排序的特点。（4）能够对给定算法进行分析比较。2要求学生应掌握的基本概念、基本理论、基本技能：通过本章学习，应掌握一些简单的排序方法，熟悉各种内部排序方法特点，分析相应排序算法性能。3教学的重点、难点：重点：内部排序概念及特点；各种排序方法及实现。难点：排序算法的分析。4课时分配：4节理论5对实践教学内容：无上机。 五、 实践教学环节 无六、 作业（习题）要求第一章 讨论：类C语言对C语言主要有哪些扩充？对于基本操作运行次数与数据输入有关的情况，有哪几种时间复杂度？在实际中通常采用哪种时间复杂度？在程序设计中，常用下列三种不同的出错处理方式：用exit语句终止执行并报告错误；以函数的返回值区别正确返回或错误返回；设置一个整型变量的函数参数以区别正确返回或某种错误返回。试讨论这三种方法各自的优缺点。第二章 讨论：在什么情况下用顺序表比链表好?讨论线性表的顺序存储结构的插入与删除算法的时间复杂度。讨论合并有序线性表的算法的时间复杂度。讨论线性链表的相关算法的时间复杂度。讨论循环链表的算法特点。第三章 讨论：讨论栈的特点。讨论数制转换的数学基础。如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag,并以tag的值为0或1来区分尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好?）。讨论队列与栈的相同点及不同点。第五章 讨论：讨论数组的顺序存储表示与实现中算法现实及所涉及的语法现象。讨论广义表的存储结构的实现。第六章 第七章 讨论：一棵度为2的树与一棵二叉树有何区别?怎样求表达式的波兰式、中缀表示及逆波兰式表示。讨论怎样将一棵二叉树进行线索化。讨论树的先根遍历与后根遍历与二叉树的先序遍历与中序遍历之间的关系。讨论怎样构造赫夫曼树。第八章 讨论：已知有向图的邻接矩阵为Ann,试问每一个Ann(k)(k=1,2,.,n)各具有何种实际含义？讨论怎样求一棵树的连通分量。怎样构造图的邻接矩阵，邻接表及十字链表及邻接多重表。无向图的生成树及其算法与图的深度优搜索的关系。用普里姆算法与克鲁斯卡尔算法求最小生成树的步骤。（1）偏序及全序与拓扑排序的关系求关键路径的关键是什么？Dijkstra算法与Floyd算法的本质是什么？求最短路有哪些方面的应用？第九章 讨论：若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？查找不成功，即表中没有关键字等于给定值K的记录。查找成功且表中只有一个关键字等于给定值K的记录。查找成功且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记录。此时的平均查找长度应考虑找到所有记录时所用的比较次数。主关键字与次关键字的区别是什么？B-树与B+树与异同。有哪些构造哈希函数的方法与处理冲突的方法。第十章 讨论：试问:对初始状态如下(长度为n)的各序列进行直接插入排序时，至多需进行多少次关键字间的比较(要求排序后的序列按关键字自小至大顺序有序)? 关键字(自小至大)顺序有序; (key1key2key2keyn) 序号为奇数的关键字顺序有序，序号为偶数的关键字顺序有序;(key1key3,key2key4) 前半个序列中的关键字顺序有序，后半个序列中的关键字逆序有序;(key1key2keyn) 直接插入排序与折半插入排序各有何特点与联系。选择排序的稳定性。并排序与基数排序的稳定性。七、 主要教学方法及考核方式（黑体 五号）1、 本课程的教学包括课堂讲授、学生自学、作业、辅导答疑、期末考试等教学环节。