《数据结构》课程教学大纲

《数据结构》课程教学大纲--2012版一、课程基本信息课程名称：数据结构英文名称：DataStructure课程编码:11107C/11207C课程类别：专业主干课总学时:64学时（含实验16学时）总学分:4适用专业：计算机科学与技术/网络工程方向先修课程：高级语言程序设计，离散数学，概率论与数理统计开课系部:计算机科学与技术系二、课程的性质和任务《数据结构》是计算机科学与技术专业的一门专业必修课程。它系统地介绍线性表、栈、队列、字符串、数组、广义表、树、二叉树、图、查找表等常用数据结构的基本概念、操作及其典型应用例子。在知识方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法，使学生了解数据对象的特性，数据组织的基本方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。通过学习，初步具备分析问题、解决问题的能力，养成良好的程序设计风格，积聚和提高基本的分析设计能力，为后续课程的学习打下坚实的基础。三、课程教学基本要求（一）理论教学内容和基本要求第一章绪论?数据结构的基本概念；算法设计；时间和空间复杂度?本章知识点：理解相关的基本概念；掌握算法五大要素；掌握计算语句频度和估算算法时间复杂度的方法。?重点：基本概念难点：算法的时间和空间复杂度，数据结构的概念第二章线性表?线性表的逻辑结构；线性表的存储结构及操作的实现；一元多项式的表示；习题讨论课本章知识点：掌握线性表的逻辑结构、线性表的存储结构、线性表在顺序结构和链式结构上实现基本操作的方法；理解从时间和空间复杂度的角度比较线性表两种存储结构的不同特点及其适用场合。重点：线性表的概念难点：线性表的表示及实现第三章栈和队列?栈的定义，表示及实现；表达式求值；栈与递归过程；队列的定义，表示及实现；本章知识点：了解栈和队列的特点；掌握在两种存储结构上栈的基本操作的实现；掌握循环队列和链队列的基本运算；掌握递归算法执行过程中栈状态的变化过程。?重点：栈和队列的表示和实现难点：循环队列第四章串?串的逻辑结构，存储结构；串的应用；本章知识点：理解串的基本运算的定义，掌握利用这些基本运算来实现串的其它各种运算的方法；掌握在顺序存储结构上实现串的各种操作的方法；重点掌握串上实现的模式匹配算法。重点：串的各种运算方法难点：串的模式匹配算法第五章数组和广义表?数组的存储结构；稀疏矩阵的表示及操作的实现；广义表的定义和存储结构；广义表的递归算法；本章知识点：掌握数组在以行为主的存储结构中的地址计算方法；掌握矩阵实现压缩存储时的下标变换；理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵时进行运算采用的处理方法；掌握广义表的定义及其存储结构，学会广义表的表头，表尾分析方法。重点:稀疏矩阵存储，矩阵元素地址的计算难点：矩阵的三元组存储时算法第六章树和二叉树?树的基本概念；二叉树的性质和存储结构；遍历二叉树和线索二叉树；树的存储结构和遍历；树和森林；哈夫曼树及其应用；习题讨论课?本章知识点：理解二叉树的结构特点；掌握二叉树的各种存储结构的特点及适用范围；深入掌握按各种次序遍历二叉树的递归和非递归算法；掌握二叉树的线索化，在中序线索树上找给定结点的前驱和后继的方法；掌握树的各种存储结构及其特点；掌握建立最优二叉树和哈夫曼编码的方法。?重点：二叉树概念，性质，遍历算法难点：二叉树线索化，二叉树的非递归算法第七章图?图的基本概念；图的存储结构；图的遍历及应用：最小生成树、最短路径等、拓扑排序。本章知识点：熟悉图的各种存储结构，了解实际问题与采用何种存储结构和算法有密切联系；掌握遍历图的递归和非递归算法；掌握应用图的遍历算法求各种简单路径问题，比如，最小生成树、最短路径、拓扑排序等。?重点：图的相关概念，图的遍历算法难点：最小生成树，最短路径，拓扑排序第九章查找?静态查找表(顺序表,有序表,索引顺序表)；动态查找表(二叉排序树,平衡二叉树,B-树和B+树)的建立和查找；哈希表的建立，查找及分析；习题讨论课。?本章知识点：理解顺序查找，折半查找和索引查找的方法，并能灵活应用；掌握二叉排序树的构造方法及算法；掌握二叉平衡树的建立方法；了解B-树，B+树的特点以及它们的建立过程；掌握哈希表的构造方法；按定义计算各种查找方法在等概率情况下查找成功时和失败时的平均查找长度，理解哈希表在查找不成功时的平均查找长度的计算方法。重点：折半查找，二叉排序树，哈希表难点：二叉平衡树的建立方法，B-树，B+树第十章内部排序?概念；插入排序；交换排序(起泡,排序)；选择排序(简单选择,堆)；归并排序；基数排序。本章知识点：理解各种排序方法的特点并能灵活应用；掌握各种方法的排序过程和各种排序方法的时间复杂度分析。重点掌握快速排序、堆排序、归并排序和基数排序的基本思想及排序过程，难点是这四个排序算法的实现。??重点：插入排序，交换排序，快速排序，堆排序难点：快速排序，堆排序，归并排序（二）实验教学内容和基本要求实验教学内容及要求见《数据结构》实验教学大纲四、课程教学要求及形式1、课程概念多、抽象、涉及面广，因此课程教学采用课堂讲授+CAI辅助教学讲授方式、课堂讨论、习题课、课程网站教学资源等多种形式进行课程教学，积极引导学生，激发学生的思维，让学生参与到教学中。2、每章布置3-6道习题以巩固教学；另外安排6个上机实验使理论与实际相结合（参考实验大纲），训练学生的实际动手能力。3、考试采用闭卷、平时成绩相结合的形式。闭卷部分的考试题包括基本概念、理解掌握、分析问题等，题型可采用选择题、填空题、简答题、分析应用题等多种形式。考核形式：平时成绩：20%，期末成绩：80%五、学时分配章节主要内容各教学学时分配备注讲授习题实验讨论合计第1章绪论22第2章线性表82212第3章栈和队列426第4章串22第5章数组和广义表44第6章树和二叉树82212第7章图8412第8章动态存储管理自学第9章查找4610课程设计第10章内部排序44合计44H4H16H64H六、建议教材及参考书建议教材：《数据结构》严蔚敏主编，清华大学出版社参考书目：[1]《数据结构与程序设计》(C语言第二版)，(美)RobertL.Kuse等著，敖富江译，清华大学出版社.[2]《实用数据结构》,谭浩强主编，中国铁道出版社.[3]《数据结构习题与解析》(C语言版)，李春葆等，清华大学出版社.[4]《数据结构习题集》(C语言版)，严蔚敏等，清华大学出版社.