《数据结构与算法》理论教学大纲

1、数据结构与算法理论教学大纲(2004年制订)课程编号：210142英 文 名：Data Structure and Algorithm课程类别：文化技能课前 置 课：计算机导论、C程序设计基础、高等数学、线性代数、离散数学后 置 课： 学 分：4学分课 时：72课时(其中理论教学36课时，实验教学36课时)主讲教师：曹骢、杨小宁等选定教材：严蔚敏,陈文博.数据结构及应用算法教程.北京：清华大学出版社,2001年.课程概述： 随着计算机应用领域的不断扩大，软件需求量也不断增大，程序设计知识普及率也随之增高。在这种情况下，数据结构与算法课程，已经由原来计算机专业的特有课程，逐步发展成为众多理工专业

2、的文化基础课。本课程面向数学专业学生讲授。本课程内容的选取，定位于以数据结构知识为主，同时介绍算法设计和分析方法的内容，这对那些在非计算机专业不开设算法设计课程，而又需要了解和掌握一部分算法设计和分析基本技能的学生群是非常合适的。本课程内容包括：第一部分绪论；第二部分线性表；第三部分栈和队列；第四部分串；第五部分数组和广义表；第六部分树和二叉树；第七部分图；第八部分查找；第九部分排序。第二至四部分集中介绍基础顺序结构是本课程的基础。第六、七部分是本课程重点，也是难点。第八、九部分为算法设计奠定基础。教学目的： 数据结构与算法的教学目的是培养学生在问题的分析中抽象出数据、数据集合和数据关系，并以

3、此为基础设计算法，把算法分解成为对数据集上的数据结构和各种运算。在语言支持下，实现算法和数据集上的运算。因此要求学生学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构，存储结构及其相应的操作算法，并初步掌握时间和空间分析技术。为此本课程从基本数据结构入手，讲授基本数据结构：线性表、栈、队列、矩阵、字符串、广义表并予以基本操作和实验，以增加学生对基础知识的理解和认识。讲授递归知识，为算法设计提供一种思路。树、图的讲授使线性表应用、变形得以充分扩展，为分析、解决和处理问题的思路和方法奠定了基础。查找、排序是全课程内容的高潮，精彩、经典的算法不失为学生的算法

4、设计入门和创新思维的平台。本课程在讲述数据、数据结构、存储方法、实现算法和应用基础上，着重培养学生对数据对象的特性及组织方式的学习和分析，提高对有关数据的存储操作、算法及应用的技能。教学方法： 本课程采用立体化教学模式。课堂教学以讲授教材内容为主线，同时讲授实验方法和内容，适时安排作业分析和习题课，还结合程序设计基础与数据结构课程设计讲述有关课程设计的知识和重点。鉴于数学系专业特性，考虑到数学系学生的课程设置，本课程的理论课时与实验课时适时增加，同时加强学生对数据结构知识理性认识与感性认识的有机结合。为后续课程奠定基础。各章教学要求及教学要点第一章 绪论课时分配：2课时教学要求：本章是课程的入

5、门，主要介绍数据结构的基本知识和概念。掌握数据结构及其相关概念。熟悉数据的四种基本结构类型。熟悉四种不同存储结构。熟悉算法的五个重要特征。掌握算法的设计要求。掌握算法的两种效率量度。了解大O表示法及大O运算规则。本章要注意算法的时间复杂度和空间复杂度、大O表示法这两个教学难点的分散化解。教学内容：第一节 什么是数据结构一、什么是数据结构。第二节 基本概念和术语一、数据结构的基本概念。二、数据结构的逻辑结构。三、数据结构的存储结构。第三节 抽象数据类型的表示与实现一、数据结构中的C语法和常用表示方法。二、基本操作。第四节 算法和算法分析一、算法的定义。二、算法的重要特性。三、算法设计的要求。四、

6、算法效率的度量。五、大O表示法及大O运算规则。六、算法的存储空间需求。思考题： 1.数据结构由哪几部分组成？2.数据的物理结构和逻辑结构分别包括哪几种类型？3.算法的五个重要特性是什么？第二章 线性表课时分配：6课时教学要求： 了解线性表的逻辑结构特性是数据元素之间存在着线性关系。理解在计算机中，表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。了解从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。本章要注意线性链表的基本运算、循环

7、链表的实现、双向链表的实现这三个教学难点的分散化解。教学内容： 第一节 线性表的类型定义一、线性表的类型定义。二、线性表的操作。第二节 线性表的顺序表示和实现一、线性表的顺序存储结构及基本概念。二、线性表的元素、位置的确定与计算。三、线性表的C语言描述。四、线性表的基本操作。五、线性表的引入操作。六、线性表操作的应用。第三节 线性表的链式表示和实现一、线性链表的定义。二、线性链表的相关概念。三、线性链表结构的C语言定义。四、单链表的操作实现。五、静态链表的定义和基本操作。六、循环链表的定义和基本操作。七、双向链表的定义和基本操作。思考题： 1.线性表的逻辑结构特征是什么？当顺序表和链表作为其存

8、储结构时，线性表中结点之间的关系分别用什么来表示？2.顺序表中插入和删除一个结点平均需要移动多少个结点，具体移动的结点个数取决于哪两个参数？3.写出从顺序表中删除所有值为x值的算法。4.从顺序表中删除重复的元素，并使剩余元素的相对次序保持不变，试写出算法。5.编写一个在带头结点的单链表中删除一个最小节点的算法。第三章 栈和队列课时分配：4课时教学要求：本章在线性表的基础上，进一步介绍限定性操作的线性结构及其之上的操作运算。掌握栈和队列类型的特点，了解在相应的应用问题中如何正确选用它们。熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。熟练掌握循环队列和链队列的基本操作

9、实现算法，特别注意队满和队空的描述方法。了解递归算法执行过程中栈的状态变化过程。本章要注意递归算法、递归与非递归过程的转换这两个教学难点的分散化解。教学内容：第一节 栈一、栈的定义和栈的抽象数据类型。二、栈的相关概念。三、栈的两种存储表示方法顺序栈。四、栈的两种存储表示方法链栈。第二节 栈与递归的实现一、递归的概念。二、递归实现的例子。三、递归算法与非递归算法的转换。第三节 队列一、队列的抽象数据类型定义。二、队列的性质。三、链队列队列的链式表示和实现。四、循环队列队列的顺序表示和实现。思考题：1.编写一个算法，利用栈的基本运算，将指定栈中的内容进行逆转。2.编写一个算法，利用栈的基本运算，返

10、回指定栈中的栈底元素。3.编写一个算法，利用队列和栈的基本算法，将指定队列中的内容进行逆转。4.在HQ的链队中，编写求该链队中结点个数的算法思路与描述。5.已知一递归函数，分别写出一个递归算法和一个非递归算法。第四章 串课时分配：2课时教学要求： 本章的目的是介绍串的逻辑结构、存储结构及串上的基本运算。熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。掌握在串的定长顺序存储结构上实现串的各种操作的方法。了解串的堆存储结构以及在其上实现串操作的基本方法。了解串的匹配操作。本章要注意串的模式匹配这个教学难点的分散化解。教学内容： 第一节 串类型的定义一、串的相关概念及其

11、定义。二、串的抽象数据类型定义。第二节 串的表示和实现一、定长顺序存储表示。二、串联接操作。三、求子串操作。四、堆分配存储表示。五、串的块链存储表示。思考题：1.顺序串表示串位有哪两种表示方法？2.链串的优点、缺点各是什么？3.编写一个算法计算一个子串在一个字符串中出现的次数，如果该子串不出现则为0。第五章 数组和广义表课时分配：2课时教学要求：掌握数组的两种存储表示方法。掌握数组在以行为主的存储结构中的地址计算方法。了解对特殊矩阵进行压缩存储时的下标变换公式。了解稀疏矩阵的两类压缩存储方法的特点和适用范围。领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。掌握广义表的结构特点及其存储表示

12、方法。了解一种结构的链表。了解对非空广义表进行分解的方法：即将一个非空广义表分解为表头和表尾两部分。本章要注意二维数组的以行序为主序存储的方式与以列序为主序的存储方式、广义表的存储结构、矩阵的压缩存储方式这三个教学难点的分散化解。教学内容：第一节 数组的定义一、数组的抽象数据类型定义。二、数组和线性表的对比。三、数组的操作。第二节 数组的顺序表示和实现一、数组的存储结构。二、数组元素存储位置的计算。三、数组的顺序表示和实现。第三节 广义表的类型定义一、广义表的类型定义。二、广义表的相关概念。三、广义表的基本操作。思考题：1.设二维数组A58的每个元素占8个字节，存储器按字节编址，已知A的基地址

13、为100，则A的终端节点A47的存储地址是多少？若按行存储时A25的地址是多少？按列存储时A25的存储地址是多少？2.假定数组An的n个元素中有多个零元素，将A中的所有非零元素依次移到A的前端，设计算法的基本思路和步骤。3.分别按行优先和列优先的顺序，编写输出数组的转值函数。4.广义表的长度、深度、极表头、标尾如何确定？5.写一个算法，判断广义表中左右括号是否配对，可将广义表视为一个字符串。第六章 树和二叉树课时分配：8课时教学要求：熟练掌握二叉树的结构特性。了解相应的证明方法。熟悉二叉树的各种存储结构的特点及适用范围。掌握各种遍历策略的递归算法，运用遍历算法，实现二叉树的其它操作。遍历二叉树

14、是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。层次遍历是按另一种搜索策略进行的遍历。理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系。了解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。熟悉树的各种存储结构及其特点。掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，要求掌握一至二种建立二叉树和树的存储结构的方法。理解编写实现树的各种操作的算法。了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。本章要注意二叉树的遍历的非递归算法、Huffman树及Huffman编码、二叉树的线索化、线索二叉树这四个教学难点

15、的分散化解。教学内容：第一节 树的定义和基本术语一、树的定义。二、树的抽象数据类型定义。三、树的基本操作。四、树的基本术语。第二节 二叉树一、二叉树的定义。二、二叉树的抽象数据类型定义。三、二叉树的基本操作。四、二叉树的基本形态。五、二叉树的性质。六、二叉树的顺序存储结构。七、二叉树的链式存储结构。第三节 遍历二叉树和线索二叉树一、遍历的定义。二、遍历二叉树的定义。三、先序遍历二叉树。四、中序遍历二叉树。五、后序遍历二叉树。六、遍历二叉树的非递归算法。第四节 树和森林一、树的存储结构双亲表示法。二、树的存储结构孩子表示法。三、树的存储结构二叉链表法。四、树、森林、二叉树的相互转换。五、树的遍历

16、。六、森林的遍历。第五节 哈夫曼树及其应用一、最优二叉树（哈夫曼树）的定义。二、哈夫曼树的构建方法。三、哈夫曼编码的定义。四、哈夫曼编码的设计。五、哈夫曼编码的算法。思考题：1.假设二叉树采用链接存储方式存储，编写一个二叉树先序遍历的非递归算法。2.假设二叉树采用链接存储方式存储，编写一个二叉树中序遍历的非递归算法。3.如何判断二叉树是否为满二叉树。4.高度为h的严格二叉树至少有多少个结点？最多有多少个结点（设根的层数为1）？5.一棵2n+1个结点的二叉树中，若无1度结点，则它有多少个度为2的结点？6.已知5个字符的哈夫曼编码中，3个字符编码分别为01、10、11，其余两个字符的编码长度为3，

17、则这两个字符的编码分别是多少？7.若某二叉树的先序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵树。第七章 图课时分配：4课时教学要求：熟悉图的各种存储结构及其构造算法。了解实际问题的求解效率与采用何种存储结构和算法有密切联系。掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。了解应用图的遍历算法求解各种简单路径问题。了解教科书中讨论的各种图的算法。本章要注意深度优先搜索的非递归方法、广度优先搜索算法这两个教学难点的分散化解。教学内容：第一节 图的定义和术语一、图的抽象数据类型。二、图

18、的基本操作。三、图的定义及相关概念。第二节 图的存储结构一、图的数组表示法。二、图的邻接表表示法。三、图的逆邻接表表示法。第三节 图的遍历一、图的遍历定义。二、图的深度优先搜索。三、图的广度优先搜索。思考题：1.图有哪几种表示方法？给出一个图用不同的方法表示出来。2.使用普里姆算法构造出图的一棵最小生成树。3.使用克鲁斯卡尔算法构造出图的一棵最小生成树。4.在一个图中，所有顶点的度数之和等于所有边数的多少倍？5.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是多少？6.编写一个算法将一个无向图的邻接矩阵转换成邻接表。第八章 查找课时分配：4课时教学要求： 理解顺序表和有序表的

19、查找方法及其平均查找长度的计算方法。掌握静态查找树的构造方法和查找算法。理解静态查找树和折半查找的关系。熟练掌握二叉排序树的构造和查找方法，以及插入删除操作。掌握哈希表的构造方法。理解哈希表与其它结构的表的实质性的差别。了解按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。本章要注意二叉排序树的插入和删除、二叉排序树的查找分析这两个教学难点的分散化解。教学内容：第一节 静态查找表一、静态查找表的定义。二、顺序表的查找。三、查找操作的性能分析。四、有序表的查找。第二节 动态查找表一、动态查找表的定义。二、二叉排序树的定义。三、二叉排序树的插入和删除操作。第三节 哈希表一、什么是哈希表

20、。二、哈希函数的构造方法直接定址法。三、哈希函数的构造方法数字分析法。四、哈希函数的构造方法平方取数法。五、哈希函数的构造方法折叠法。六、哈希函数的构造方法除留余数法。七、哈希函数的构造方法随机数法。八、处理冲突的方法开放地址法。九、处理冲突的方法再哈希法。十、处理冲突的方法链地址法。十一、处理冲突的方法建立一个公共溢出区。十二、哈希表的查找及其分析。思考题：1.顺序查找在成功时的平均查找长度为多少？在失败时的关键字比较次数为多少？2.在分块查找中，若用折半查找确定块，则查找成功时的平均查找长度约为多少？若用顺序查找确定块，则查找成功时的平均查找长度为多少？3.设计一个二叉查找的递归算法思路。

21、4.判定给定的二叉树是否是二叉排序树。5.设计一个算法，求出指定的结点在二叉排序树中的层次。第九章 内部排序课时分配：4课时教学要求：了解排序的定义和各种排序方法的特点。熟悉各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和基数排序等五类。掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：O(n2)的简单排序方法，O(nlogn)的高效排序方法 和 O(dn)的基数排序方法。理解排序方法“稳定”或“不

22、稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。了解外部排序的基本过程及其时间分析。本章要注意希尔排序的算法、各种排序算法在不同情况下的算法复杂度这两个教学难点的分散化解。教学内容： 第一节 概述一、排序的定义。二、排序的稳定性和不稳定性定义。三、排序过程所需的两种基本操作。第二节 插入排序一、直接插入排序。二、折半插入排序。三、希尔排序。第三节 快速排序一、冒泡排序算法。二、快速排序算法。 第四节 各种内部排序方法的比较一、各种排序算法在性能方面的比较。二、各种排序算法在稳定性方面的比较。思考题：1.已知序列17，18，60，40，7，32，73，65，85，请给出采用冒泡排

23、序法对该序列作升序排序时的每一趟结果。2.已知序列503，87，512，61，908，170，897，275，653，462，请给出采用快速排序法对该序列作升序时的每一趟结果。3.已知序列17，18，60，40，7，32，73，65，85，请给出采用折半排序法对该序列作升序排序时的每一趟结果。4.已知序列503，87，512，61，908，170，897，275，653，462，请给出采用希尔排序法对该序列作升序时的每一趟结果。附 录：参考书目1Robert L.Kruse，Alexander J.Ryba. Data Structures and Program Design InC+M. Prentice Hall.北京：高等教育出版社，2001年影印版2李春葆数据结构习题与解析（C语言篇）M北京：清华