《数据结构及应用算法》教学大纲

1、数据结构及应用算法教学大纲课程编号课程性质专业选修课学 时48学 分3适用专业信息管理与信息系统 大纲本文一、课程内容（一）绪论1.什么是数据结构2.基本概念和术语3.抽象数据类型的表示与展现4.算法和算法分析（二）线性表1.线性表的类型和定义2.线性表的顺序表示和实现3.线性表的链式表示和实现（三）栈和队列1.栈2.栈的应用举例3.栈与递归的实现4.队列（四）串1.串类型的定义2.串的表示和实现（五）数组与广义表1.数组的定义2.数组的顺序表示和实现3.广义表的定义4.广义表的存储结构（六）树和二叉树1.树的定义和基本术语2.二叉树3.遍历二叉树和线索二叉树4.树和森林5.赫夫曼树极其应用（

2、七）动态存储管理1.概述2.可利用空间表及分配方法3.边界标识法4.伙伴系统（八）查找1.静态表查找2.动态表查找3.哈希表（九）内部排序1.概述2.插入排序3.快速排序4.选择排序5.归并排序（十）外部排序1.外存信息的存取2.外部排序的方法（十一）文件1.有关文件的概念2.顺序文件3.索引文件4.直接存取文件5.多关键字文件二、课外作业与习题（一）每一章布置25道习题供学生课外练习，以巩固所学内容。习题来源可从教材或相关参考书中选取。题型包含选择题、填空题、是非题、问答题、应用题、编程题等。（二）对于每次作业中出现的问题，教师应及时在课堂上予以讲解，必要时安排专门的习题课。教师在授课过程中

3、应随时提问，注意学生的反馈信息，针对课程中的某些重点和难点问题灵活组织课堂讨论，以调动学生的积极性，并巩固教学内容。三、实验 无四、实习或上机内容 无五、课程设计内容 无六、建议选用的教材及主要参考书教 材：数据结构及应用算法教程，严蔚敏等编，清华大学出版社，2000参考书：数据结构与算法导论，徐绪松编，电子工业出版社，1996 大纲说明一、课程的目的和任务数据结构及应用算法是一门专业课程，是计算机程序设计的重要理论基础，对进一步学习计算机领域其它课程或者从事软件开发，具有重要作用。二、课程的具体要求（一）掌握数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念的含义，抽象数据类型的定

4、义、表示和实现方法，描述算法的类C语言。（二）掌握线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法、在线性表的两类存储结构上实现基本操作； （三）掌握栈和队列的结构特性，在两中存储结构上如何实现栈和队列的基本操作以及栈和队列在程序设计中的应用。（四）掌握串的数据类型定义，串的三种存储表示，串的各种基本操作的实现及其应用。（五）掌握数组的类型定义和表示方式，广义表的逻辑结构和存储结构。（六）掌握二叉树的定义、性质和存储结构二叉树的遍历，树和森林的定义、存储结构与二叉树的转换、遍历。（七）了解系统程序设计中采用的几种动态存储管理的策略和方法；掌握使用可利用空间表进行动态存储管理的分配

5、策略，操作系统中用以进行动态存储管理的边界标志法。（八）掌握静态查找表和动态查找表的各种实现方法。（九）掌握插入排序、交换排序、选择排序、归并排序的基本思想、算法特点。（十）掌握外部排序的基本方法。（十一）掌握顺序文件、索引顺序文件、直接存取文件的构造方法及文件操作的实现。三、本课程着重讲解的内容（一）数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念的含义；抽象数据类型的定义、表示和实现方法；描述算法的类C语言。（二）线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法、在线性表的两类存储结构上实现基本操作； （三）栈和队列的结构特性；在两中存储结构上如何实现栈和队列的基

6、本操作以及栈和队列在程序设计中的应用。（四）串的数据类型定义；串的三种存储表示：定长顺序存储结构、块链存储结构和堆分配存储结构；串的各种基本操作的实现及其应用。（五）数组的类型定义和表示方式；广义表的逻辑结构和存储结构。（六）二叉树的定义、性质和存储结构二叉树的遍历；树和森林的定义、存储结构与二叉树的转换、遍历；树的多种应用。（七）系统程序设计中采用的几种动态存储管理的策略和方法；使用可利用空间表进行动态存储管理的分配策略；操作系统中用以进行动态存储管理的边界标志法。（八）静态查找表和动态查找表的各种实现方法：顺序表、有序表、树表和哈息表。（九）比较各种内部排序的方法，插入排序、交换排序、选择

7、排序、归并排序的基本思想、算法特点。（十）实现外部排序的基本方法。（十一）顺序文件、索引顺序文件、直接存取文件的构造方法及文件操作的实现。四、本课程与其它课程的联系与分工本课程以计算机原理，C程序设计，计算机基础等计算机类课程为先修课。本课程的后续课程有电子商务、Web系统开发、供应链管理系统。五、课外作业的要求针对课程中的各重要概念、原理和方法，均须布置若干道课外习题，题目总量控制在15题左右为宜。每次作业均要求学生认真按时完成，要求解题思路清晰，概念和结果正确，书写工整，图表规范。教师应按要求认真批改每次课外作业，对其中的问题应及时在课堂上进行讲解。对一些比较重要的普遍存在的问题要及时安排习题课或组织课堂讨论。习题课的次数为23次，课堂讨论的时间和次数可灵活掌握。六、实验要求 无七、实习要求 无八、课程设计要求 无九、学时分配表内 容课堂讲授课堂习作实验实习上机其它教学环节小 计（一）绪论33（二）线性表66（三）栈和队列66（四）串3