数据结构小结.docVIP

算法是指解题方案的准确而完整的描述。 算法的四个基本特征是：可行性、确定性、有穷性和拥有足够的情报。 算法一般都可以用哪几种控制结构组合而成？顺序、选择、循环。4. 算法的时间复杂度是指指执行算法所需要的计算工作量。 算法的空间复杂度是指执行这个算法所需要的内存空间。 算法分析的目的是分析算法的效率以求改进数据结构作为计算机的一门学科，主要研究什么？主要研究数据的逻辑结构、对各种数据结构进行的运算，以及数据的存储结构。将n个数据元素按块有序划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须按块有序；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……。 依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。 快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。一般来说，假设线性中前j－1元素已经有序，现在要将线性表中第j个元素插入到前面的有序子表中，插入过程如下：将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中第j－1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上，有序子表的长度就变为j了。效率与冒泡法相同在最坏情况下，简单插入排序需要n（n－1）/2次比较。将整个无序序列分割成若干小的子序列分别进行插入排序。将相隔某个增量H的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当H减到1时，进行一次插入排序，排序就完成。增量序列一般取h=n/2k（k=1，2，…【log2n】，其中n为待排序序列的长度。 在待排序的元素序列基本有序的前提下，效率最高的排序方法是？假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为？n(n-1)/2若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是？dbehfca。 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为？350说明：完全二叉树总结点数为N，若N为奇数，则叶子结点数为（N+1）/2；若N为偶数，则叶子结点数为N/2。在深度为5的满二叉树中，叶子结点的个数为？在深度为5的满二叉树中，共有多少个结点？在一棵二叉树上第8层的结点数最多是？线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。 虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。顺序存储结构的主要优点是节省存储空间，结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)它不要求逻辑上相邻的元素在物理位置上也相邻快速排序法的关键是对线性表进行分割快速排序法可以实现通过一次交换而消除多个逆序。长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元