数据结构复习要求相关8761.PPT

数据结构 复习 考试要求 掌握基本概念 掌握常见算法的基本思想 第一章 绪论 基本概念和术语。例如数据、数据元素、数据对象等。 逻辑结构 集合、线性结构、树状结构、网状结构 物理结构 顺序存储结构、链式存储结构 算法和算法分析 第二章 线性表 线性表的定义及运算 存取、插入、删除、查找、合并、分解、排序、求线性表的长度 顺序存储结构(顺序表) 优点： (1)无须为表示结点间的逻辑关系而增加额外的存储空间。 (2)可以方便地随机存储表中的任一结点。 缺点： (1)插入和删除平均须移动一半结点。 (2)存储分配只能预先进行（静态）。 链式存储结构(链表:带头结点链表) 优点： 动态、合理地利用内存空间 插入、删除等操作时无需大量的数据移动，只是修改指针 缺点： 每一结点附加指针域 非随机存取结构，查找定位操作需从头指针出发顺着链表扫描。 当线性表的长度变化较大，难以估计其存储规模时， 宜采用动态链表作为存储结构为佳；当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。（基于空间的考虑） 顺序表是一种随机存取结构，对表中任一结点都可在O(1)时间内直接存取。而链表中的结点则需用从头指针开始顺链扫描。 若线性表的操作主要是查找，很少涉及到插入、删除操作时，可采用顺序表结构。 若要频繁地进行插入和删除操作，宜采用链表作为存储结构。 若表的插入、删除操作主要发生在表的两端，则宜采用有尾指针的单循环链表。 第三章 栈和队列 栈的定义和术语 “后进先出”(LIFO)线性表 限制在一端进行插入、删除操作的线性表 顺序栈、链栈 队列的定义和术语 “先进先出”(FIFO)线性表 限定插入操作只能在队尾进行，而删除操作只能在队首进行 顺序队列（主要是循环队列）和链队列 第五章 数组 数据元素可为结构类型的线性表 数组通常采用顺序存储方式来实现 n维数组的数据元素的存储 行序为主序 列序为主序 矩阵的压缩存储 特殊矩阵 稀疏矩阵 第六章 树 树的定义及术语 二叉树的定义及性质 满二叉树、完全二叉树 顺序存储结构 链式存储结构 二叉链表 三叉链表 二叉树的遍历：先序遍历、中序遍历、后序遍历 树和森林 树的存储结构 双亲表示法、孩子表示法、孩子兄弟表示法 树的遍历操作 先(根次)序遍历，相当于对应二叉树的先序遍历 后(根次)序遍历，相当于对应二叉树的中序遍历 层序遍历 树(森林)与二叉树的对应关系 Huffman树及其应用 基本概念：两个结点间的路径、路径长度、树的路径长度、结点的带权路径长度、树的带权路径长度 赫夫曼树（最优二叉树） 前缀编码（Huffman编码） 第七章 图 基本概念 顶点、弧、有向图、边、无向边、连通、连通图、连通分量、强连通图 图的存储结构 邻接矩阵法（*） 邻接表法（*） 图的遍历 深度优先有哪些信誉好的足球投注网站(DFS) 深度优先有哪些信誉好的足球投注网站过程的实现需借助栈机制 广度优先有哪些信誉好的足球投注网站(BFS) 广度优先有哪些信誉好的足球投注网站过程的实现需借助队列机制 图的应用 连通网的最小生成树 普里姆算法，适用于稠密图 克鲁斯卡尔算法，适用于稀疏图 两点之间的最短路径问题 迪杰斯特拉(Dijkstra)算法 弗洛伊德(Floyd)算法 第八章 查找 静态查找表 顺序表的查找 有序表的查找 索引顺序表的查找 哈希(Hash)表 Hash函数的构造 处理冲突的方法 第九章 排序 概念 稳定的排序方法、不稳定的排序方法 内部排序、外部排序 排序方法概述 插入排序 直接插入排序 折半插入排序 交换排序 起泡排序 快速排序 选择排序 简单选择排序 * * 去掉了拓扑排序和关键路径 去掉了动态查找表 去掉了希尔排序