数据结构排序部分练习题.pdf

一、单选题12．设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用(法。)A．冒泡排序B．快速排序C．堆排序D．归并排序1．已知持排序的n个元素可分为n/k个组，每个组包含k个元素，各组间分块有序，若采用基于比较的排序，其时间下界应为：()A．O(nlogn)B．O(nlogk)C．O(klogn)D．O(klogk)22222．最好和最坏时间复杂度均为O(nlogn)且稳定的排序方法是()。2A．快速排序B．堆排序C．归并排序D．基数排序3．下列排序算法中，当初始数据有序时，花费时间反而最多的是()。A．起泡排序B．希尔排序C．堆排序D．快速排序4．若需在O（nlogn）的时间内完成排序，且要求稳定，则可选择（）2A．快速排序B．堆排序C．归并排序D．直接插入排序5．排序趟数与序列的原始状态有关的排序方法是()排序法。A．插入B．选择C．希尔D．快速6．已知数据表每个元素距离其最终位置不远，则最省时间的排序算法是()。A．堆排序B．直接插入排序C．快速排序D．直接选择排序7．关键字比较次数与数据的初始状态无关的排序算法是()。A．直接选择排序B．冒泡排序C．直接插入排序D．希尔排序8.若一个元素序列基本有序，则选用（）方法较快。A．直接插入排序B．直接选择排序C．堆排序D．快速排序9.若要从1000个元素中得到4个最小值元素，最好采用（）方法。A．直接插入排序B．直接选择排序C．堆排序D．快速排序10.若要对1000个元素排序，要求既快又稳定，则最好采用（）方法。A．直接插入排序B．归并排序C．堆排序D．快速排序11.若要对1000个元素排序，要求既快又节省存储空间，则最好采用（）方法。A．直接插入排序B．归并排序C．堆排序D．快速排序12.在下列排序方法中，空间复杂性为O(logn)的方法为（）。2A．直接选择排序B．归并排序C．堆排序D．快速排序13.在平均情况下速度最快的排序方法为（）。A．直接选择排序B．归并排序C．堆排序D．快速排序14、设有关键字初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X}，则用下列哪种排序方法进行第一趟扫描的结果为{F,H,C,D,P,A,M,Q,R,S,Y,X}？A．直接插入排序B．二路归并排序C．以第一元素为基准的快速排序D．基数排序15．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为()排序法。A．插入B．选择C．希尔D．二路归并16．下面排序法中，()排序法是不稳定的。A．插入B．冒泡C．二路归并D．堆17.下列排序方法中，不稳定的是（）A．直接插入排序B．冒泡排序C．归并排序D．直接选择排序18.在直接插入排序的第i趟排序前，有序表中的元素个数为（）。A．iB．i+1C．i-1D．119.在直接插入排序的第i趟排序时，为寻找插入位置最多需要进行（）次元素的比较，假定第0号元素作监视哨。A．iB．i-1C．i+1D．120.若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（）。A．j-iB．i-j-1C．i-jD．i-j+121.对n个元素进行直接插入排序，则各趟排序中寻找插入位置的平均时间复杂性为（）。A．O(1)B．O(n)C．O(n2)D．O(logn)222.在对n个元素进行直接插入排序的过程中，共需要进行（）趟。A．nB．n+1C．n-1D．2n23.对n个元素进行直接插入排序时间复杂性为（）。A．O(1)B．O(n)C．O(n2)D．O(logn)224、n个记录直接插入排序时所需的记录最小比较次数是()A．n-1B．nC．n(n-1)/2D．n(n+1)/225.对n个元素进行直接插入排序，空间复杂性为（）。A．O(1)B．O(logn)C．O(n2)D．O(nlogn)2226.对n个元素进行冒泡排序，第一趟至多需要进行（）对相邻元素之间的交换。A．nB．n-1C．n+1D．n/227.对n个元素进行冒泡排序，最好情况下的时间复杂性为（）。A．O(1)B．O(logn)C．O(n2)D．O(n)228.对n个元素进行冒泡排序，至少需要（）趟完成。A．1B．nC．n-1D．n/26．快速排序的记录移动次数（）比较次数，其总执行时间为0（nlog2n）。A）大于B）大于等于C）小于等于D）小于29.对n个元素进行快速排序，第一次划分最多需要移动（）次元素，假定包括基准和临时量之间的移动。A．n/2B．n-1C．nD．n+130.对序列（3,7,5,9,1）进行快速排序，则第一次划分时需要移动元素的次数为（），假定不包括基准和临时量之间的移动。A．1B．2C．3D．431.对n个元素进行快速排序，最好情况