自学考试《数据结构》各章复习要点总结_自考数据结构导论总结
自学考试《数据结构》各章复习要点总结由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“自考数据结构导论总结”。
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=0.618
·随机数法：hash=random(x)。
处理冲突的方法：
开放定址法： 一般形式为hi=(h(key)+di)%m1≤i≤m-1，开放定址法要求散列表的装填因子α≤1。
·开放定址法类型：
·线性探查法：addre=(hash(x)+i)%m;·二次探查法：addre=(hash(x)+i^2)%m;
·双重散列法：addre=(hash(x)+i*hash(y))%m;
·拉链法： 是将所有关键字为同义词的结点链接在同一个单链表中。
·拉链法的优点：
·拉链法处理冲突简单，且无堆积现象;
·链表上的结点空间是动态申请的适于无法确定表长的情况;
·拉链法中α可以大于1，结点较大时其指针域可忽略，因此节省空间;
·拉链法构造的散列表删除结点易实现。
·拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。
第十章 文件
文件是性质相同的记录的集合。记录是文件中存取的基本单位，数据项是文件可使用的最小单位，数据项有时称字段或者属性。
文件
·逻辑结构是一种线性结构。
·操作有：检索和维护。并有实时和批量处理两种处理方式。
文件
·存储结构是指文件在外存上的组织方式。
·基本的组织方式有：顺序组织、索引组织、散列组织和链组织。
·常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。
评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。
检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。
顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。主关键字有序称顺序有序文件，否则称顺序无序文件。
一切存储在顺序存储器(如磁带)上的文件都只能顺序文件，只能按顺序查找法存取。顺序文件的插入、删除和修改只能通过复制整个文件实现。
索引文件的组织方式：通常是在主文件之外建立一张索引表指明逻辑记录和物理记录之间一一对应的关系，它和主文件一起构成索引文件。
索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。
若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。是一种静态索引。
索引顺序文件常用的有两种：
·ISAM索引顺序存取方法：是专为磁盘存取文件设计的，采用静态索引结构。
·VSAM虚拟存储存取方法：采用B+树作为动态索引结构，由索引集、顺序集、数据集组成。
散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。
散列文件
·优点是：文件随机存放，记录不需要排序;插入删除方便;存取速度快;不需要索引区，节省存储空间。
·缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件。
多重表文件：对需要查询的次关键字建立相应的索引，对相同次关键字的记录建一个链表并将链表头指针、长度、次关键字作为索引表的索引项。
倒排表：次关键字索引表称倒排表，主文件和倒排表构成倒排文件。
