年自学考试《数据结构》各章复习要点总结3篇(数据结构第二章知识点总结)

　　下面是范文网小编收集的年自学考试《数据结构》各章复习要点总结3篇(数据结构第二章知识点总结)，供大家阅读。

年自学考试《数据结构》各章复习要点总结1

　　2010年自学考试《数据结构》各章复习要点总结(5)龙耒为你整理：

　　第九章 查找

　　查找的同时对表做修改操作(如插入或删除)则相应的表称之为动态查找表，否则称之为静态查找表。

　　衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数(即平均查找长度ASL)。

　　线性表查找的方法：

·顺序查找：逐个查找，ASL=(n+1)/2;

·二分查找：取中点int(n/2)比较，若小就比左区间，大就比右区间。用二叉判定树表示。ASL=(∑(每层结点数*层数))/N;·分块查找：要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中的最大关键字及其位置建立有序索引表。

　　二叉排序树(BST)定义是二叉排序树是空树或者满足如下性质的二叉树：

·若它的左子树非空，则左子树上所有结点的值均小于根结点的值;

·若它的右子树非空，则右子树上所有结点的值均大于根结点的值;

·左、右子树本身又是一棵二叉排序树。

　　二叉排序树的插入、建立、删除的算法平均时间性能是O(nlog2n)。

　　二叉排序树的删除操作可分三种情况进行处理：

·*P是叶子，则直接删除*P，即将*P的双亲*parent中指向*P的指针域置空即可。

·*P只有一个孩子*child，此时只需将*child和*p的双亲直接连接就可删去*p。

·*p有两个孩子，则先将*p结点的中序后继结点的数据到*p，删除中序后继结点。

　　关于B-树(多路平衡查找树)。它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。建立的方式是从下向上拱起。散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。

　　散列函数的选择有两条标准：简单和均匀。

　　常见的散列函数构的造方法：

·平方取中法：hash=int((x^2)0)

·除余法：表长为m，hash=x%m

·相乘取整法：hash=int(m*(x*A-int(x*A));A=

·随机数法：hash=random(x)。

　　处理冲突的方法：

　　开放定址法： 一般形式为hi=(h(key)+di)%m1≤i≤m-1，开放定址法要求散列表的装填因子α≤1。

·开放定址法类型：

·线性探查法：address=(hash(x)+i)%m;·二次探查法：address=(hash(x)+i^2)%m;

·双重散列法：address=(hash(x)+i*hash(y))%m;

·拉链法： 是将所有关键字为同义词的结点链接在同一个单链表中。

·拉链法的优点：

·拉链法处理冲突简单，且无堆积现象;

·链表上的结点空间是动态申请的适于无法确定表长的情况;

·拉链法中α可以大于1，结点较大时其指针域可忽略，因此节省空间;

·拉链法构造的散列表删除结点易实现。

·拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。

　　第十章 文件

　　文件是性质相同的记录的集合。记录是文件中存取的基本单位，数据项是文件可使用的最小单位，数据项有时称字段或者属性。

　　文件

·逻辑结构是一种线性结构。

·操作有：检索和维护。并有实时和批量处理两种处理方式。

　　文件

·存储结构是指文件在外存上的组织方式。

·基本的组织方式有：顺序组织、索引组织、散列组织和链组织。

·常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。

　　评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。

　　检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。

　　顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。主关键字有序称顺序有序文件，否则称顺序无序文件。

　　一切存储在顺序存储器(如磁带)上的文件都只能顺序文件，只能按顺序查找法存取。顺序文件的插入、删除和修改只能通过复制整个文件实现。

　　索引文件的组织方式：通常是在主文件之外建立一张索引表指明逻辑记录和物理记录之间一一对应的关系，它和主文件一起构成索引文件。

　　索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。

　　若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。是一种静态索引。

　　索引顺序文件常用的有两种：

·ISAM索引顺序存取方法：是专为磁盘存取文件设计的，采用静态索引结构。

·VSAM虚拟存储存取方法：采用B+树作为动态索引结构，由索引集、顺序集、数据集组成。

　　散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。

　　散列文件

·优点是：文件随机存放，记录不需要排序;插入删除方便;存取速度快;不需要索引区，节省存储空间。

·缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件。

　　多重表文件：对需要查询的次关键字建立相应的索引，对相同次关键字的记录建一个链表并将链表头指针、长度、次关键字作为索引表的索引项。

　　倒排表：次关键字索引表称倒排表，主文件和倒排表构成倒排文件。

年自学考试《数据结构》各章复习要点总结2

　　2010年自学考试《数据结构》各章复习要点总结(3)龙耒为你整理：

　　第五章 多维数组和广义表

　　数组一般用顺序存储的方式表示。存储的方式有：

·行优先顺序，也就是把数组逐行依次排列。PASCAL、C

·列优先顺序，就是把数组逐列依次排列。FORTRAN

　　地址的计算方法：

·按行优先顺序排列的数组：LOCa(ij)=LOCa(11)+((i-1)*n+(j-1))*d.·按列优先顺序排列的数组：LOCa(ij)=LOCa(11)+((j-1)*n+(i-1))*d.矩阵的压缩存储：为多个相同的非零元素分配一个存储空间;对零元素不分配空间。

　　特殊矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。

　　稀疏矩阵的概念：一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。

　　特殊矩阵的类型：

·对称矩阵：满足a(ij)=a(ji)。元素总数n(n+1)/=max(i，j)，J=min(i，j)，LOCa(ij)=LOC(sa[0])+(I*(I+1)/2+J)*d.·三角矩阵：

·上三角阵：k=i*(2n-i+1)/2+j-i，LOCa(ij)=LOC(sa[0])+k*d.·下三角阵：k=i*(i+1)/2+j，LOCa(ij)=LOC(sa[0])+k*d.·对角矩阵：k=2i+j，LOCa(ij)=LOC(sa[0])+k*d.稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表来表示。但这种压缩存储方式将失去随机存储功能。加入行表记录每行的非零元素在三元组表中的起始位置，即带行表的三元组表。

　　广义表是n(n≥0)个元素的有限序列，其中的元素是原子或者是一个广义表。

　　广义表表头和表尾的概念：

·若广义表LS非空(n≥1)，则这个广义表的第一个元素就是表头。

·其余的元素组成的表称为LS的表尾，所以表尾必是一个子表。

　　广义表有两种表示法，一种是括号表示法，一种是图形表示法。

　　广义表与树(形结构)相对应，这个广义表就是纯表。

　　如果一个广义表的结点又可以被其他结点所共享，则这个表称为再入表。

　　允许递归的表称为递归表。

　　线性表∈纯表(树)∈再入表∈递归表。可见，广义表是对线性表和树的推广。

　　广义表有两个特殊的基本运算：

·取表头head(LS)：取表中的第一个数据元素，不能对空表操作。

·取表尾tail(LS);取除表头外，其余数据元素构成的子表，不能对空表操作。

　　第六章 树

　　树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点;其余结点形成m个不相交的子集，并称根的子树。

　　根是开始结点;结点的子树数称度;度为0的结点称叶子(终端结点);度不为0的结点称分支结点(非终端结点);除根外的分支结点称内部结点;

　　有序树是子树有左，右之分的树;无序树是子树没有左，右之分的树;森林是m个互不相交的树的集合;

　　树的四种不同表示方法：

·树形表示法;

·嵌套集合表示法;

·凹入表示法;

·广义表表示法。

　　二叉树的定义：是n≥0个结点的有限集，它是空集(n=0)或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。

　　二叉树不是树的特殊情形，与度数为2的有序树不同。

　　二叉树的4个重要性质：

·二叉树上第i层上的结点数目最多为2^(i-1)(i≥1);

·深度为k的二叉树至多有(2^k)-1个结点(k≥1);

·在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1;

·具有n个结点的完全二叉树的深度为int(log2n)+1。满二叉树是一棵深度为k，结点数为(2^k)-1的二叉树;完全二叉树是满二叉树在最下层自右向左去处部分结点;

　　二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。(存储前先将其画成完全二叉树)

　　树的存储结构多用的是链式存储。BinTNode的结构为lchild|data|rchild，把所有BinTNode类型的结点，加上一个指向根结点的BinTree型头指针就构成了二叉树的链式存储结构，称为二叉链表。它就是由根指针root唯一确定的。共有2n个指针域，n+1个空指针。

　　根据访问结点的次序不同可得三种遍历：先序遍历(前序遍历或先根遍历)，中序遍历(或中根遍历)、后序遍历(或后根遍历)。时间复杂度为O(n)。

　　利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为“线索”，加上线索的二叉链表就称为线索链表。线索使得查找中序前趋和中序后继变得简单有效，但对于查找指定结点的前序前趋和后序后继并没有什么作用。

　　树和森林及二叉树的转换是唯一对应的。

　　转换方法：

·树变二叉树：兄弟相连，保留长子的连线。

·二叉树变树：结点的右孩子与其双亲连。

·森林变二叉树：树变二叉树，各个树的根相连。

　　树的存储结构：

·有双亲链表表示法：结点data | parent，对于求指定结点的双亲或祖先十分方便，但不适于求指定结点的孩子及后代。

·孩子链表表示法：为树中每个结点data | next设置一个孩子链表firstchild，并将data | firstchild存放在一个向量中。

·双亲孩子链表表示法：将双亲链表和孩子链表结合。

·孩子兄弟链表表示法：结点结构leftmostchild |data | rightsibing，附加两个分别指向该结点的最左孩子和右邻兄弟的指针域。树的前序遍历与相对应的二叉树的前序遍历一致;树的后序遍历与相对应的二叉树的中序遍历一致。

　　树的带权路径长度是树中所有叶结点的带权路径长度之和。树的带权路径长度最小的二叉树就称为最优二叉树(即哈夫曼树)。

　　在叶子的权值相同的二叉树中，完全二叉树的路径长度最短。

　　哈夫曼树有n个叶结点，共有2n-1个结点，没有度为1的结点，这类树又称为严格二叉树。

　　变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性。如00、01、0001这三个码无法在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀，这种码称为前缀码(其实是非前缀码)。

　　哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的最优前缀码。哈夫曼编码的构造很容易，只要画好了哈夫曼树，按分支情况在左路径上写代码0，右路径上写代码1，然后从上到下到叶结点的相应路径上的代码的序列就是该结点的最优前缀码。

年自学考试《数据结构》各章复习要点总结3

　　11-12-2数据结构复习指导

　　第一章：

　　知识点：数据结构的定义；数据元素关系的基本结构类型；数据元素的不同存储结构；算法的重要特性；评价算法的重要指标； 如何由程序代码估算算法的复杂度（大O描述）。

　　第二章：

　　知识点：线性表不同的存储方式及其各自特点；顺序表及链表的基本操作（插入、删除等）与其具体代码实现。

　　第三章：

　　知识点：栈和队列的结构特点；二者基本操作的思想；链队列和循环队列的基本操作；循环队列如何判空和判满。

　　第四章：

　　知识点：串的相关定义与基本操作；模式匹配的定义与思想。

　　第五章：

　　知识点：数组的定义与顺序实现方式；数组顺序存储中元素地址的计算；稀疏矩阵的压缩存储方式与元素地址的特点；广义表的定义与基本操作（表头，表尾，判长度、深度）。

　　第六章：

　　知识点：树的基本术语；（满/完全）二叉树的定义与各种性质特点；二叉树不同的存储与遍历方式；一般树的存储结构；树与森林的遍历方式；赫夫曼树与编码的求法。

　　第七章：

　　知识点：（有向/无向/完全）图的概念与其特点；（强）联通图的定义与特点；图的不同存储结构及其操作；图的不同方式的遍历；最小生成树的定义与其不同的求解方法；拓扑排序的定义与思想；关键（最短）路径的定义与思想。

　　第九章：

　　知识点：顺序查找、折半查找的思想及其具体代码实现和复杂度分析；索引查找的思想；二叉排序树的思想及操作；平衡二叉树的定义与操作；B-树的定义与特点；哈希表（函数）的定义；哈希函数的构造方法与处理冲突的方法。

　　第十章：

　　知识点：各种排序方法的思想与其复杂度、稳定性分析。

　　注：以上涉及到的复杂度分析，其推导过程不做要求。

年自学考试《数据结构》各章复习要点总结3篇(数据结构第二章知识点总结)相关文章：