《数据结构》课程教学资源：期末复习

數据结构期末篓习

数据结构期末复习

教学任务 针对大量的信息处理对象,介绍对象信息与数据表 示的各种抽象的、基本的逻辑结构及其上的基本运 算操作 通过研究各种基本数据结构内在的逻辑关系和它们 在计算机中的存储表示方式,初步建立数据结构上 基本运算操作的正确性概念。 结合各种典型问题讨论其上的各种基本运算操作及 其基本算法,讲授备种数据结构的特点、适用范围 以及对一些基本算法效率的定性和定量分析方法, 为后续课程提供必要的数据结构基础。 配合实验课程的教学,学生应理论联系实际;理论 指导实践,通过规范地完成一系列数据结构实验进 一步巩固所学的相关书本知识,在知识、能力、素 质上得到进一步的提高。 2005.zxlxmu

2005.zxl.xmu 教学任务  针对大量的信息处理对象，介绍对象信息与数据表 示的各种抽象的、基本的逻辑结构及其上的基本运 算操作。  通过研究各种基本数据结构内在的逻辑关系和它们 在计算机中的存储表示方式，初步建立数据结构上 基本运算操作的正确性概念。  结合各种典型问题讨论其上的各种基本运算操作及 其基本算法，讲授各种数据结构的特点、适用范围， 以及对一些基本算法效率的定性和定量分析方法， 为后续课程提供必要的数据结构基础。  配合实验课程的教学，学生应理论联系实际，理论 指导实践，通过规范地完成一系列数据结构实验进 一步巩固所学的相关书本知识，在知识、能力、素 质上得到进一步的提高

课程肉容 【重点】各种常用的数据表示抽象的逻辑结构、存储 结构及其上基本的运算操作、算法及其效率分析。 〔基本要求】较好地掌握课程的主要内容,能够运用 数据结构的理论、方法与技术解决相应的、一般的 实际问题。 『说明』重点内容用白色文字标示,非重点内容用蓝色文字标 刀。 2005.zxlxmu

2005.zxl.xmu 课程内容 【重点】各种常用的数据表示抽象的逻辑结构、存储 结构及其上基本的运算操作、算法及其效率分析。 【基本要求】较好地掌握课程的主要内容，能够运用 数据结构的理论、方法与技术解决相应的、一般的 实际问题。 『说明』重点内容用白色文字标示，非重点内容用蓝色文字标 示

第1章绪论 ■数据结构的概念;数据的逻辑结枃:数据的存储结 构 线性结构与非线性结构; 四种基本的存储映像方法:顺序、链接、索引、散 列 数据的基本运算:检索、插入、删除、更新和排序 可支撑算法运行的计算模型; ■算法及其特性;算法的描述形式;数据结构的选择 和评价标准 面向对象表示法 2005.zxlxmu

2005.zxl.xmu 第1章 绪论  数据结构的概念；数据的逻辑结构；数据的存储结 构；  线性结构与非线性结构；  四种基本的存储映像方法：顺序、链接、索引、散 列；  数据的基本运算：检索、插入、删除、更新和排序；  可支撑算法运行的计算模型；  算法及其特性；算法的描述形式；数据结构的选择 和评价标准；  面向对象表示法

第2章线性表 ■向量及其运算;(顺序表的存储结构及其基本运算) ·在顺序表中实现插入、删除算法的思想; ·求T(n)的方法;等概率情形下,在顺序表中插入、删除算 法平均约需移动多少结点? ■单链表的存储结构及其基本运算; 链表的特点是怎样的?(静态ws动态) 开始结点、头结点、头指针、空表等概念 在链表中引入头结点有什么好处? 单链表的插入、删除、查找算法的思想(前插入、后插 入、前删、后删、按值查找) 2005.zxlxmu

2005.zxl.xmu 第2章 线性表  向量及其运算；（顺序表的存储结构及其基本运算）  在顺序表中实现插入、删除算法的思想；  求T(n)的方法；等概率情形下，在顺序表中插入、删除算 法平均约需移动多少结点？  单链表的存储结构及其基本运算；  链表的特点是怎样的？（静态 vs. 动态）  开始结点、头结点、头指针、空表等概念  在链表中引入头结点有什么好处？  单链表的插入、删除、查找算法的思想（前插入、后插 入、前删、后删、按值查找）

第2章线性表(2) ■循环表及其基本运算 头指针ws.尾指针 n双链表及其基本运算 双链表的的插入、删除、查找算法的思想(前插入、后 插入、前删、后删、按值查找) 与单链表相比较,有何特点? 对称表及其基本运算(一般了解 2005.zxlxmu

2005.zxl.xmu 第2章 线性表（2）  循环表及其基本运算；  头指针 vs. 尾指针  双链表及其基本运算；  双链表的的插入、删除、查找算法的思想（前插入、后 插入、前删、后删、按值查找）  与单链表相比较，有何特点？  对称表及其基本运算（一般了解）；

第3章栈和队列 ■栈及其运算 ·栈(顺序,链栈)、栈顶、栈底、空栈 ·栈的基本运算(主要考虑顺序栈)进栈、退栈、空栈 取栈顶元素。 什么是栈满?栈的上溢和下溢。 栈的应用; ■栈与递归的关系:递归的概念、利用栈实现递归过 程到非递归过程的转换 2005.zxlxmu

2005.zxl.xmu 第3章 栈和队列  栈及其运算；  栈（顺序，链栈）、栈顶、栈底、空栈  栈的基本运算（主要考虑顺序栈）：进栈、退栈、空栈、 取栈顶元素。  什么是栈满？栈的上溢和下溢。  栈的应用；  栈与递归的关系：递归的概念、利用栈实现递归过 程到非递归过程的转换；

第3章栈和队列(2) ■队列及其基本运算 ·队列、队尾、队首、空队列 入队、出队、取队头、判队列空的运算描述。 什么是队列的上溢(假上溢)、下溢?克服假上溢有什 么方法? 何为循环队列?循环意义下队满、队空的条件是怎样的? 循环队列的入队、出队算法。 其它限制存取点的表:双端队列、双栈超队列 超栈; 栈和队列的链接存储表示及其基本运算 ·何为链队列? 2005.zxlxmu

2005.zxl.xmu 第3章 栈和队列（2）  队列及其基本运算；  队列、队尾、队首、空队列  入队、出队、取队头、判队列空的运算描述。  什么是队列的上溢（假上溢）、下溢？克服假上溢有什 么方法？  何为循环队列？循环意义下队满、队空的条件是怎样的？ 循环队列的入队、出队算法。  其它限制存取点的表：双端队列、双栈、超队列、 超栈；  栈和队列的链接存储表示及其基本运算；  何为链队列？

第4章串 ■串的基本概念 串的长度、空串、空格串、子串、位置、串的相等 ■串的存储表示:顺序存储、索引存储及链式存储; 顺序:定长、堆分配 ·索引:(见《许》P78~79) ·链式:块链(结点大小) 串的基本运算及其实现; 最小操作子集;如何用最小操作子集来实现其它操作? 模式匹配:朴素的匹配算法、无回溯的匹配算法 (KMP算法) KMP的改进* 2005.zxlxmu

2005.zxl.xmu 第4章 串  串的基本概念；  串的长度、空串、空格串、子串、位置、串的相等  串的存储表示：顺序存储、索引存储及链式存储；  顺序：定长、堆分配  索引： （见《许》 P78～79）  链式：块链（结点大小）  串的基本运算及其实现；  最小操作子集；如何用最小操作子集来实现其它操作？  模式匹配：朴素的匹配算法、无回溯的匹配算法 （KMP算法）；  KMP的改进*

第5章数组和广义表 多维数组:多维数组的行优先和列优先顺序序列 多维数组的存储位置计算公式 ■稀疏矩阵:稀疏硫矩阵的顺序存储、链式存储和散列 存储;稀疏矩阵的乘法(一般了解) 特殊矩阵的压缩存储 广义表:广义表、再入表(共享)、递归表(递归) 的概念; 广义表的存储:广义表的单链表示法、广义表的双 链表示法; 2005.zxlxmu

2005.zxl.xmu 第5章 数组和广义表  多维数组：多维数组的行优先和列优先顺序序列；  多维数组的存储位置计算公式  稀疏矩阵：稀疏矩阵的顺序存储、链式存储和散列 存储；稀疏矩阵的乘法（一般了解）；  特殊矩阵的压缩存储  广义表：广义表、再入表（共享）、递归表（递归） 的概念；  广义表的存储：广义表的单链表示法、广义表的双 链表示法；