Date: 2019-08-10

1.  快速排序总比简单排序快()    错

解释：  当原有数列是有序的，快排和简单选择时间复杂度都为O(n^2)    

2.  在索引顺序表中,实现分块查找,在等概率查找情况下,其平均查找长度不仅与表中元素个数有关,而且与每块中元素个数有关()  对

解释：  

假设有n个数，分块查找，每个块有k个数，这样可以分成n/k块； 对每个块检索，可以有klogk； 这样所有的数，共有n/k * klogk = nlogk

3.  计算算法的时间复杂度是属于一种()   事前分析估算的方法

解释：  算法时间复杂度是运行实际程序前通过分析和估算衡量算法的效率。

4.  下面给出的四种排序法中()排序法是不稳定性排序法 D

解释：冒泡排序、基数排序、归并排序、插入排序算法都是稳定性算法（冒归基插）。不稳定的：快排，堆排，希尔，选择

5.   对有 n 个记录的表作快速排序，在最坏情况，算法的时间复杂度是   （O(n^2)） ;最坏情况即是基本有序的情况下。

6.  下面的哪种排序算法在算复杂度平均不是O(nlogn)的?   B

A.快速排序

B.桶排序

C.归并排序

D.二叉树排序树排序

E.堆排序

解释;

桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。

7.   对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是 （）。 D

解释;折半插入排序，是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。 所以，很明显比较的次数减少了。

补充： 

1、算法复杂度与初始状态无关的有：选择排序、堆排序、归并排序、基数排序。

2、元素总比较次数与初始状态无关的有：选择排序、基数排序。

3、元素总移动次数与初始状态无关的有：归并排序、基数排序。

8.  

假设小明用某个排序算法对整数序列（82,45,25,15,21）进行排序。一下为排序过程中序列状态的变化过程：

输入：82 45 25 15 21

第一步：45 82 25 15 21

第二步：25 45 82 15 21

第三步：15 25 45 82 21

······

请问小明用的是什么排序算法？  插入排序算法（插入排序，特点是，第n轮，前n个数字会有序。 ）

解释：  

该题考查的是不同排序方法的原理，从题目中可以得出是逐步将待排序的元素插入到已排序序列的对应位置，属于插入排序。

选择排序：将第一个元素作为基准，后面的元素依次和第一个元素做比较选出最小元素，并和第一个元素交换位置，所以经过第一步排序可以确定整个序列的最小元素。A不正确。

归并排序：两两合并排序，第一步的元素25，15应该交换位置作为子序列，所以B不正确。

快速排序：需要枢轴值为比较对象，第一步排序后会将序列分为大于枢轴和小于枢轴两部分，题目选项后三个元素均小于枢轴而没有放到枢轴之前

9.  将两个各有n个元素的有序表归并成一个有序表,其最多的比较次数是()  2n-1

解释：  最多的比较次数是当两个有序表的数据刚好是插空顺序的时候，比如：第一个序列是1,3,5，第二个序列是2,4,6，把第二个序列插入到第一个序列中，先把第二个序列中的第一个元素2和第一个序列依次比较，需要比较2次（和1，3比较），第二个元素4需要比较2次（和3,5比较，因为4比2大，2之前的元素都不用比较了），第三个元素6需要比较1次（只和5比较），所以最多需要比较5次。即2n-1次。

10.  输入若已经是排好序的（升序），下列排序算法最快的是（）   A

解释： 

快速排序在元素基本无序的情况下是最好的选择，在基本递增或递减中时间复杂度是O（n^2）

归并排序时间复杂度稳定在O（nlogn）

希尔排序很难说，跟选择的增量有关，一般小于O（n^2），大于O（n）

插入排序是在序列已有序的情况下最快的，时间复杂度是O（n），另外在数数据规模较小时插入排序效果也很好。

一般不选择传统的冒泡排序，如果题目中有一个选项是冒泡排序，要想一下是否隐含着改进冒泡排序的含义。

11.  在外部排序时,利用选择树方法在能容纳m个记录的内存缓冲区中产生的初始归并段的平均长度为2m个记录()  对

解释：

内排序：我们常用的选择、交换、插入、归并、基数排序都属于内排序，只用在内存读一次原始数据即可完成排序。

外部排序：指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行多路归并排序。

由于利用选择树选择出来后，就是将两个长度为m的子节点数组归并成一个长度为2m的根节点数组，然后再取数据，依次向上递归，如下图。

         X

       /    \

    a[m]  a[m]              由于最后一个可能不够m，所以那一个初始归并X段会稍微小，但是最后求所有X平均的话应该是2m附近。

12.  以下哪种排序算法对[1, 3, 2, 4, 5, 6, 7, 8, 9]进行排序最快  ？ 基本有序：插入排序或者改进的冒泡排序算法

堆排序无论排序序列有序还是无序，时间复杂度都为O(nlogn)，但改良的冒泡排序可以将时间复杂度降到O(n)。其次，归并排序无论有序还是无序其时间复杂度也是O(nlogn)，归并排序在归并的时候，如果右路最小值比左路最大值还大，那么只需要比较n次，但如果右路每个元素分别比左路对应位置的元素大，那么需要比较2*n-1次，该序列明显满足第二个条件，所以其时间复杂度为O(2n)

13.  在下列排序算法中,哪一个算法的时间复杂度与初始序列无关（ ）  一堆（堆）乌龟（归并）选（选择）基（基数）友

解释： 

需要和前面都有序序列对比插入的位置，如果本身有序，则每次对比一个即可。

最坏情况，则需要一直对比到第一个元素

最好时间复杂度O(n),最坏时间复杂度O(n^2)

假设递增冒泡，需要每次把无序部分最大的移动到无序部分的最右边，如果本身就是递增，则无序移动，遍历一遍就完成了。

最好时间复杂度为O(n),最坏时间复杂度为O(n^2);

大家都知道，最差为O(n^2)，平均为O(nlogn)

每次需要遍历一遍选择无序部分最大的，无论是否有序，都要遍历才能找到，所以其时间复杂度与初始序列无关。

14.   以下排序算法中，最坏情况时间复杂度与其他选项不同的是（）D

15. 为实现快速排序算法，待排序序列宜采用的存储方式是（）。  A（快速排序中元素进行比较，需要快速查询，而顺序存储适用于频繁快速查询）

A. 顺序存储

B.散列存储

C. 链式存储

D.索引存储

补充解释： 

1、顺序存储方式：顺序存储方式就是在一块连续的存储区域（物理）一个接着一个的存放数据。一般采用数组或结构数组来描述。

 2、链式存储方式：链式存储方式比较灵活，节点逻辑上相邻，但不要求节点在物理位置上（存储区域）相邻，一个节点的引用字段往往指向下一个节点的存放位置，比如链表；

 3、索引存储方式：索引存储方式是采用附加的索引表的方式来存储节点信息的一种存储方式。索引表由若干索引项组成。索引存储方式中索引项的一般形式为(关键字、地址)；

 4、散列存储方式：散列存储方式是根据节点o的关键字，利用散列函数直接计算出该节点的存储地址的一种存储方式。

16.   用希尔(Shell)方法排序时,若关键字的初始排序杂乱无序,则排序效率就低()   错

时间复杂度受增量序列的影响明显大于其他因素，最坏的情况是o(n2)，好的情况在o(n1.3)，与增量序列选择有关。

17.  下列程序的时间复杂度是（o(n^2)）