數据结构期末篓习
数据结构期末复习
教学任务 针对大量的信息处理对象,介绍对象信息与数据表 示的各种抽象的、基本的逻辑结构及其上的基本运 算操作 通过研究各种基本数据结构内在的逻辑关系和它们 在计算机中的存储表示方式,初步建立数据结构上 基本运算操作的正确性概念。 结合各种典型问题讨论其上的各种基本运算操作及 其基本算法,讲授备种数据结构的特点、适用范围 以及对一些基本算法效率的定性和定量分析方法, 为后续课程提供必要的数据结构基础。 配合实验课程的教学,学生应理论联系实际;理论 指导实践,通过规范地完成一系列数据结构实验进 一步巩固所学的相关书本知识,在知识、能力、素 质上得到进一步的提高。 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章 数组和广义表 多维数组：多维数组的行优先和列优先顺序序列； 多维数组的存储位置计算公式 稀疏矩阵：稀疏矩阵的顺序存储、链式存储和散列 存储；稀疏矩阵的乘法（一般了解）； 特殊矩阵的压缩存储 广义表：广义表、再入表（共享）、递归表（递归） 的概念； 广义表的存储：广义表的单链表示法、广义表的双 链表示法；