数据结构

位置:IT落伍者 >> 数据结构 >> 浏览文章

自学考试《数据结构》复习指导-2


发布日期:2019年04月19日
 
自学考试《数据结构》复习指导-2

第五章

概念一个图G由两个集合V和E组成V是有限的非空顶点集E是用顶点对表示的边集

无向图有向图

邻接关联邻接到(于)关联于孤立顶点

顶点的度图G中关联于顶点V的边的数目称为V的度

所有顶点的度等于边的两倍

子图

完全图每对顶点之间都有一条边相连的图在有向图中每对顶点之间都有两条有向边相互关联的图

在无向完全图中边的总数为Cn=n(n)/

在有向完全图中边的总数为Pn=n(n

路径由边组成

回路

连通图对于无向图如果图中任何两顶点都是可达的则称此图为连能图

对于有向图如果图中任何两个顶点都是相互可达的则此有向图是强连通的如果图中任何两顶点至少有一个顶点另一个顶点可达则称此有向图是单向连通的

强连通分量有向图的最大强连通子图称为它的强连通分量 树图其本质特征是连通性和无圈性把不含圈的无向连通图称为树图

网络是每条边上带有数量指标的连通图

邻接矩阵邻接表

第六章 查找

查找就是确定一个已给的数据是否出现在某个数据表中

域(字段)组成记录的每个数据项

关键字通常记录中总存在某个或某组数据项它们的值能唯一标识一个记录这个(组)数据项称为关键字

方法顺序

二分

线性插值

分区

二叉排序树如果将记录的键码按二叉树的结构来组织并且假定树中任意非叶子结点的键码大于其左子树所有结点的键码(若左子树存在的话)而小于其右子树所有结点的键码(如右子树存在的话)这样的二叉树叫二叉排序树(二叉查找树) 哈 希查找

哈希函数能把关键字映射成记录存贮地址的函数

哈希表假定数组HT[··m]为存贮记录的地址空间哈希函数H以每个记录的关键字值K作为输入产生一个落在[··m]内的整数H(K)并以它作为K所标识的记录在表HT中的地址或索引号这样产生的记录表H(K)叫做 ··]

构造哈希函数的方法

直接定址法

除留余数法

平方取中法

折叠法与移位法

数字分析法

沖突处理

开放定址法 线性探测法 伪随机探测法

链地址法

第七章排序

内部排序

外部排序

内部冒泡 选择 插入 归并 堆排序 快速排序 基数

每个非终端结点的关键字大于等于它的孩子结点的关键字

第八章文件

基本概念

[] []

               

上一篇:数据结构之链栈

下一篇:数据结构数组和广义表之多维数组