数据结构-总复习2015华中科技

总复习数据结构主讲教师：周时阳2《数据结构》是计算机科学与技术类各专业的一门基础课。课程主要对于线性结构、树型结构和图型结构三类基本结构，讨论它们的逻辑结构、逻辑结构上定义的运算、物理结构、逻辑结构与物理结构对应关系、运算的实现算法与效率分析，给出了实际应用的实例。此外，专题讨论了查找和排序运算的各种实现算法。其中，排序包括内部排序和外部排序的两种运算。内容摘要3重点讲解一、知识归纳二、试卷题型三、考试安排4目录一、知识归纳第一章绪论1.基本概念数据、数据元素、逻辑结构、物理结构、算法和复杂度等。2.逻辑结构的描述方法3.数据元素的存储结构4.算法分析方法5目录第二章线性表1.基本概念线性表、表长、空表、前驱、后继、序号、有序表、存储结点、溢出、头结点和头指针等。2.存储结构顺序表(动态与静态分配、寻址公式)

链表(单/双、头结点/非头结点、循环/非循环)

静态链表3.重要运算插入、删除4.应用实例有序表的归并、集合运算和多项式加法6目录第三章栈和队列1.基本概念栈、队列、空栈/空队、栈长/对长、头尾指针和溢出等。2.存储结构顺序栈、链式栈循环队列(标志位、头尾指针、头指针队长)、链式队列3.重要运算入栈/出栈、入队/出队、判空4.栈队的基本特性5.应用实例数制转换、括弧配对、表达式求值、递归算法实现7第四章串1.基本概念串、空串、串长、串大小、子串、空格串和存储密度等。2.存储结构定长顺序存储结构

堆分配顺序存储结构块连式存储结构3.重要运算求串长、判空串、串链接、求子串和串替换等4.应用实例文本编辑*、词索引*8第五章数组和广义表1.基本概念数组、下标、广义表、表长、深度、特殊矩阵和稀疏矩阵等。2.存储结构数组：顺序存储结构(行/列优先、寻址公式)

广义表：链式存储结构(一)、链式存储结构(二)3.应用实例

特殊矩阵压缩存储(寻址公式)

稀疏矩阵压缩存储：三元组顺序表、行逻辑链接顺序表*和十字链表9第六章树和二叉树1.基本概念树、有序树、树高度、树的度、森林、二叉树、线索二叉树、满二叉树、二叉树路径长度和带权路径长度WPL等。2.存储结构二叉树：顺序表、二叉链表(带/不带双亲)、线索二叉链表树：双亲法、多重链表(同构/异构)、孩子链表法(带/不带双亲)、孩子兄弟法森林：孩子兄弟法3.重要运算：遍历(递归/非递归算法)、二叉树构造4.

二叉树的性质、遍历的特点5.应用实例赫夫曼树构造与编码、树带权路径长度计算、二叉树静态链表10…第七章图1.基本概念图、顶点度、连通图、连通分量、路径长度、生成树等。2.存储结构邻接矩阵法、邻接表/逆邻接表、十字链表、邻接多重表3.重要运算：遍历4.

应用实例生成树与连通性、最小生成树、重连通分量*、拓扑排序、关键路径*、最短路径*111.基本概念查找、关键字、平均查找长度ASL、查找成功/失败、判定树、哨兵技术、二叉排序树、平衡二叉树、散列表散列函数、同义字与哈希冲突等。2.ASL计算、二叉排序树构造、二叉树平衡化3.查找算法思想及效率顺序法折半法(取中法、菲波那契序列法*

、线性插值法*)

分块查找法二叉排序树法

B-树法*和B+树法*、键树法*哈希法(哈希函数、处理冲突方法)第九章查找121.基本概念排序、次关键字、算法稳定性、正序与逆序等。2.堆构造3.查找算法思想及效率直接插入排序、折半插入排序、2-路插入排序*、表插入排序*、希尔排序、冒泡排序、快速排序、简单选择排序、树形选择排序*堆排序、归并排序、基数排序第十章内部排序131.基本概念外部排序、外部设备、归并树、最佳归并树等。2.I/O访问时间3.查找算法思想及效率初始段生成(内部排序、置换排序)、k路归并第十一章外部排序*14二、试卷题型1.单选题2.填空题3.判