您当前位置：公务员考试网 > 国家公务员考试网 > 备考 > 面试 > > 2016年国家公务员面试银监会-计算机专业之数据结构

2016年国家公务员面试银监会-计算机专业之数据结构考点(3)

2016-01-08 11:08:23 公务员考试网文章来源：华图教育

资料分析题型
资料分析公式
数资易错点
数量关系公式
常识百年党史
全年时政热点

*资料包涵盖但不限于以上内容

扫码领福利

保存小程序码至
手机进行扫码

　　快速排序

　　快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。(1)如果不多于1个数据，直接返回。(2)一般选择序列最左边的值作为支点数据。(3) 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。(4)对两边利用递归排序数列。快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。

　　归并排序(MergeSort)

　　归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序相对堆排序稍微快一点，但是需要多一倍的内存空间，因为它需要一个额外的数组。

　　堆排序(HeapSort)

　　堆排序适合于数据量非常大的场合(百万数据)。堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数.据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。

　　Shell排序(ShellSort)

　　Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。 Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。

　　插入排序(InsertSort)

　　插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。

　　冒泡排序(BubbleSort)

　　冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。它是O(n^2)的算法。 7 交换排序(ExchangeSort)和选择排序(SelectSort)这两种排序方法都是交换方法的排序算法，效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段，在实际中使用较少。8 基数排序(RadixSort)基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法，但是它只能用于整数的排序，如果我们要把同样的办法运用到浮点数上，我们必须了解浮点数的存储格式，并通过特殊的方式将浮点数映射到整数上，然后再映射回去，这是非常麻烦的事情，因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。

　　数组 (Array)

　　在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中，数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。

　　栈(Stack)

　　是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据，英文名FILO(First In Last Out)，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

　　队列(Queue)

　　一种特殊的线性表，英文名FIFO(First In First Out)，它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

　　链表(Linked List)

　　是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

　　树(Tree)

　　是包含n(n>0)个结点的有穷集合K，且在K中定义了一个关系N，N满足以下条件：(1)有且仅有一个结点 k0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根(root)。(2)除K0外，k中的每个结点，对于关系N来说有且仅有一个前驱。(3)K中各结点，对关系N来说可以有m个后继(m>=0)。

　　图(Graph)

　　图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。