《数据结构与算法分析》理论教学大纲（供四年制本科信息与计算科学(医学信息学)、医学信息工程专业使用）

PAGE《数据结构与算法分析》理论教学大纲（供四年制本科信息与计算科学(医学信息学)、医学信息工程专业使用）Ⅰ前言数据结构与算法分析是信息与计算科学(医学信息学)专业及医学信息工程专业学生的一门重要专业课程。随着计算机技术的迅猛发展，计算机已深入到人类社会的各个领域，计算机的应用已不再局限于科学计算，而是更多地应用于控制、管理及数据处理等非数值计算的处理工作。与此相应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据。因此分析待处理对象的特性以及各处理对象之间存在的关系，是编制高质量的程序、开发各种应用软件和系统软件、搞好计算机应用中必须解决的重要问题。数据结构这门课程的开设正是为此目的服务的。学习数据结构旨在使学生了解各种数据对象的特性，学会数据组织的方法和把现实世界中的问题在计算机内部的表示方法，以培养学生基本的、良好的算法设计能力和程序设计技能。本大纲适合信息与计算科学(医学信息学)、医学信息工程专业使用，现将大纲使用中的有关问题说明如下：一为了使教师和学生更好地掌握教材，大纲每一章节均由教学目的、教学要求和教学内容三部分组成。教学目的注明教学目标，教学要求分掌握、熟悉和了解三个级别，教学内容与教学要求级别相对应，并统一标示(核心内容即知识点以下划实线，重点内容以下划虚线，一般内容不标示)便于学生重点学习。二教师在保证大纲核心内容的前提下，可根据不同教学手段，讲授重点内容和介绍一般内容，有的内容可留给学生自学。三总教学参考时数72学时，其中理论60学时，实验12学时，理论/实验为5:1。四教材：《数据结构》，清华大学出版社，严蔚敏，1版，1997年。Ⅱ正文第一章绪论一教学目的通过本章的教学，使学生了解学习数据结构的必要性，掌握数据结构的定义，使学生深刻认识该课程的重要地位；使学生了解算法分析的方法。二教学要求（一）了解学习数据结构的必要性，掌握数据结构的定义。（二）了解算法分析的方法。（三）掌握时间和空间权衡的意义。三教学内容（一）数据结构的原则和地位。（二）抽象数据类型和数据结构。（三）问题、算法和程序。（四）算法的效率，最佳、最差和平均情况。（五）渐近分析和程序运行时间的计算。（六）时间和空间权衡。第二章线性表一教学目的本章的目的是使学生掌握线性表的实现方式与应用。二教学要求（一）掌握线性表的顺序存储结构的特点及描述方法和各种操作的基本思路、步骤及实现算法。（二）掌握线性表的各种链式存储结构的特点、描述及各种链表的建立和各种操作的基本思路、步骤及实现算法。三教学内容（一）顺序表1顺序表的插入。2顺序表的删除。（二）链表1链表的插入。2链表的删除。第三章栈和队列一教学目的本章的目的是使学生掌握栈和队列及其实现方式与应用。二教学要求（一）熟悉栈的定义、特征及在其上所定义的基本运算。（二）掌握在两种存储结构上对栈所施加的基本运算的实现。（三）熟悉队列的定义、特征及在其上所定义的基本运算。（四）掌握在两种存储结构上对队列所施加的基本运算的实现。三教学内容（一）堆栈1堆栈的定义。2堆栈的存储结构与实现。3堆栈的应用。（二）队列1队列的定义。2队列的存储结构与实现。3队列的应用。第四章数组和广义表一教学目的使学生熟悉数组和广义表的概念及值的顺序存贮及链式存贮；掌握数组和广义表的基本运算。二教学要求（一）了解数组的定义。（二）熟悉和领会数组的存储方式。（三）掌握常用的数组运算。三教学内容（一）数组的概念。（二）数组的顺序存贮。（三）数组的算法1三元组数组。2数组的转置。3数组的快速转置。第六章树和二叉树一教学目的本章的目的是使学生掌握树、二叉树、线索二叉树、Huffman编码树及其实现方式，并应用。二教学要求（一）掌握树的定义，基本运算和存储结构。（二）掌握二叉树的定义，性质，基本运算和存储结构。（三）掌握二叉树的遍历和线索二叉树。（四）熟悉树，二叉树与森林的转换；树与森林的遍历。（五）掌握二叉树的应用（Huffman树）。三教学内容（一）树、二叉树的概念及有关术语。（二）二叉树的性质。（三）二叉树存储。1顺序存储。2链式存储。（四）二叉树的遍历1前序递归遍历。2中序递归遍历。3后序递归遍历。4中序非递归遍历。5层次遍历。（五）线索二叉树的概念、存储表示、算法。（六）树转换为二叉树的方法。（七）哈夫曼树、哈夫曼编码的概念、算法。第七章图一教学目的本章的目的是使学生掌握图及其实现方式与相关算法，并应用。二教学要求（一）掌握图的基本概念与术语。（二）掌握图的各种存贮方法（重点是邻接矩阵和邻接表）及其描述。（三）掌握图的深度优先、广度优先遍历算法。（四）掌握生成树与最小生成树的概念，构造最小生成树算法的思路、步骤及算法执行过程。（五）领会拓扑排序、关键路径、最短路径的算法思想。三教学内容（一）图的定义。（二）图的存储结构。1邻接矩阵。2邻接链表。（三）图的遍历。1深度优先遍历。2广度优先遍历。（四）生成树及最小生成树。1生成树概念及算法。2最小生成树概念及算法。（五）有向无环图及其应用。1拓扑排序。2关键路经。（六）最短路径。第九章查找一教学目的本章的目的是使学生了解各种查找算法，并应用。二教学要求（一）了解查找的基本思想及查找成功和不成功的概念。（二）掌握在顺序表、有序表、索引表上的查找方法和算法，并能求出相应的平均查找长度。（三）熟悉并掌握二叉排序树、平衡二叉树的各种算法。三教学内容（一）查找、平均查找长度的概念。（二）各种静态查找表（顺序表、有序表、索引顺序表）的查找方法及实现算法。（三）二叉排序树的概念、查找算法及二叉查找树的生成。（四）平衡二叉树的概念及构造平衡二叉树时的四种旋转技术。第十章内部排序一教学目的本章的目的是使学生掌握各种内部排序算法。二教学要求（一）熟悉有关排序的概念。（二）掌握各种排序方法的基本思路、实现步骤、算法。（三）熟悉各种排序算法的特点、时间复杂度、稳定性。三教学内容（一）排序的术语与记号。（二）插入排序。1直接插入排序。2Shell排序。（三）交换排序1快速排序。2起泡排序。（四）选择排序。1简单选择排序。2堆排序。（五）归并排序。（六）基数排序。Ⅲ教学组织与方法一实施机构：由医学信息工程系卫生信息工程教研室执行。二组织内容：教案讲义审核、多媒体课件(Flash)演示。三教学方法：1．理论教学：采用启发式课堂教学方式，辅助现代教育技术和手段。核心内容以讲授为主，重点内容以介绍为主，一般内容以自学为主。2．实验教学：布置实验内容，每位学生独立完成。3．辅导形式：辅导讲义，课堂答疑，网络查询等。四考核办法：考试采