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

一、单选题12设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用( )法。A冒泡排序B快速排序C堆排序D归并排序1已知持排序的n个元素可分为n/k个组，每个组包含k个元素，各组间分块有序，若采用基于比较的排序，其时间下界应为：( )AO(nlog2n)BO(nlog2k)CO(klog2n)DO(klog2k)2最好和最坏时间复杂度均为O()且稳定的排序方法是( )。A快速排序B堆排序C归并排序D基数排序 3下列排序算法中，当初始数据有序时，花费时间反而最多的是( )。A起泡排序B希尔排序C堆排序D快速排序4若需在O（nlog2n）的时间内完成排序，且要求稳定，则可选择（ ）A快速排序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(log2n)的方法为（ ）。A直接选择排序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趟排序前，有序表中的元素个数为（ ）。 AiBi+1Ci-1D119. 在直接插入排序的第i趟排序时，为寻找插入位置最多需要进行（ ）次元素的比较，假定第0号元素作监视哨。AiBi-1Ci+1D120. 若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素ri+1的插入位置为rj，则需要移动元素的次数为（ ）。Aj-iBi-j-1Ci-jDi-j+121. 对n个元素进行直接插入排序，则各趟排序中寻找插入位置的平均时间复杂性为（ ）。AO(1)BO(n)CO(n2)DO(log2n)22. 在对n个元素进行直接插入排序的过程中，共需要进行（ ）趟。AnBn+1Cn-1D2n23. 对n个元素进行直接插入排序时间复杂性为（ ）。AO(1)BO(n)CO(n2)DO(log2n)24、n个记录直接插入排序时所需的记录最小比较次数是( )An-1BnCn(n-1)/2Dn(n+1)/225. 对n个元素进行直接插入排序，空间复杂性为（ ）。AO(1)BO(log2n)CO(n2)DO(nlog2n)26. 对n个元素进行冒泡排序，第一趟至多需要进行（ ）对相邻元素之间的交换。AnBn-1Cn+1Dn/227. 对n个元素进行冒泡排序，最好情况下的时间复杂性为（ ）。AO(1)BO(log2n)CO(n2)DO(n)28. 对n个元素进行冒泡排序，至少需要（ ）趟完成。A1BnCn-1Dn/26快速排序的记录移动次数（ ）比较次数，其总执行时间为0（nlog2n）。A）大于B）大于等于C）小于等于D）小于29. 对n个元素进行快速排序，第一次划分最多需要移动（ ）次元素，假定包括基准和临时量之间的移动。An/2Bn-1CnDn+130.对序列（3, 7, 5, 9, 1）进行快速排序，则第一次划分时需要移动元素的次数为（ ），假定不包括基准和临时量之间的移动。A1B2C3D431. 对n个元素进行快速排序，最好情况下需要进行（ ）趟。AnBn/2Clog2nD2n32. 对n个元素进行快速排序，最坏情况下需要进行（ ）趟。AnBn-1Cn/2Dlog2n33. 对n个元素进行快速排序，平均情况下的时间复杂性为（ ）。AO(1)BO(log2n)CO(n2)DO(nlog2n)34. 对n个元素进行快速排序，最坏情况下的时间复杂性为（ ）。AO(1)BO(log2n)CO(n2)DO(nlog2n)35. 对n个元素进行快速排序，平均情况下的空间复杂性为（ ）。AO(1)BO(log2n)CO(n2)DO(nlog2n)36. 对n个元素进行快速排序，最坏情况下的空间复杂性为（ ）。AO(1)BO(log2n)CO(n2)DO(nlog2n)37. 对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（ ）。A1, 3, 5, 7, 9B 9, 7, 5, 3, 1C5, 3, 1, 7, 9D5, 7, 9, 1, 338. 假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（ ）。A2B3C4D539对n个元素进行直接选择排序，需要进行（ ）趟选择和交换。AnBn+1Cn-1Dn/240对n个元素进行直接选择排序，在第i趟需要从（ ）个元素中选择最小者。An-i+1Bn-ICIDi+141. 对n个元素进行直接选择排序，则各趟寻找最小值元素所需时间复杂性为（ ）。AO(1)BO(log2n)CO(n2)DO(n)5堆排序在最坏情况下，其时间复杂性为（ ）。A）B）C）D）42. 对n个元素进行堆排序，在构成初始堆的过程中需要进行（ ）次筛运算。A1Bn/2CnDn-143. 对n个元素进行堆排序，建初始堆后，还要进行( )次筛选运算。An+1Bn/2CnDn-144. 对n个元素进行堆排序，每次筛运算的时间复杂性为( )。AO(1)BO(log2n)CO(n2)DO(n)45. 对n个元素进行堆排序，时间复杂性为（ ）。AO(1)BO(log2n)CO(n2)DO(nlog2n)46. 对n个元素进行堆排序，空间复杂性为（ ）。AO(1)BO(log2n)CO(n2)DO(nlog2n)12对排序码(47、78、61、33、39、80)用堆排序的方法建立的初始堆为( )。A78、47、61、33、39、80B80、78、61、33、39、47C80、78、61、47、39、33D80、61、78、39、47、3347. 假定用小根堆对（7, 3, 5, 9, 1, 12）进行堆排序，则初始堆为（ ）。A1, 3, 5, 7, 9, 12B1, 3, 5, 9, 7, 12C1, 5, 3, 7, 9, 12D1, 5, 3, 9, 12, 748. 假定初始堆为(1, 5, 3, 9, 12, 7, 15, 10)，则第一趟堆排序后的结果为（ ）。A3, 5, 7, 9, 12, 10, 15, 1B3, 5, 9, 7, 12, 10, 15, 1A3, 7, 5, 9, 12, 10, 15, 1B3, 5, 7, 12, 9, 10, 15, 149将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）AnB2n1C2nDn-150. 若对n个元素进行归并排序，则进行归并的趟数为（ ）。AnBn-1Cn/2Dlog2n51. 若对n个元素进行归并排序，则进行每一趟归并的时间复杂性为（ ）。AO(1)BO(log2n)CO(n)DO(n2)二、判断题如果某种排序算法是不稳定的，则该方法没有实际的应用价值。对数据按关键字进行排序能够有效地提高查找速度。直接插入排序是稳定的，而Shell排序就是调用若干趟直接插入排序，所以也是稳定的。用直接选择排序方法分别对序列S1=(1,2,3,4,5,6,7)和序列S2=(7,5,3,2,4,1,6)进行排序，两者的比较次数不相同。直接选择排序的比较次数与序列的初始状态无关。堆排序法在最好和最坏情况下时间复杂性都是O(nlog2n)。堆的存储表示是顺序的。以中序方式遍历一个堆，则得到一个有序序列。二路归并排序的核心操作是把两个有序序列合并为一个有序序列。快速排序法总是效率最高的排序法。顾名思义，快速排序法是在所有情况下，速度最快的排序方法。三、填空题11最简单的交换排序方法是_排序。11直接插入排序需要_个记录的辅助空间。12在插入和选择排序中，若初始数据基本正序，则选用_；若初始数据基本反序，则选用_。1评价排序效率的主要标准是_。2在时间复杂性为O(n2)的所有排序方法中，_直接选择_排序方法是不稳定的。3在所有排序方法中，_快速_排序方法采用的是二分法的思想。4在所有排序方法中，_堆排序_方法使数据的组织采用的是完全二叉树的结构。5在所有排序方法中，_归并排序_方法采用的是两两有序表合并的思想。3采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为_3_。若A初始状态为递减排列，则记录的交换次数为_4_。6_冒泡_排序方法使键值大的记录逐渐下沉，使键值小的记录逐渐上浮。7_直接插入_排序方法能够每次使无序表中的第一个记录插入到有序表中。8_直接选择_排序方法能够每次从无序表中顺序查找出一个最小值。9每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做_插入_排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做_选择_排序。10每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做_交换_排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做_归并_排序。11对n个数据进行直接插入排序，最少比较次数为_。12. 若对一组记录(46,79,56,38,40,80,35,50,74)进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较_4_次。13取增量为3，对记录(46,79,56,38,40,80,35,50,74)进行一趟希尔排序的结果为。14. 对n个记录进行冒泡排序时，最多比较次数为_、最少的比较次数为_ n-1_，最少的趟数为_1_。15用起泡法对n个关键码排序，在最好情况下，只需做 n-1 次比较和 0 次移动；在最坏的情况下要做_次比较。16.两个序列：L1=25,57,48,37,92,86,12,33、L2=25,37,33,12,48,57,86,92用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列_。17. 对(46,79,56,38,40,84)进行冒泡排序，第一趟排序后的结果为_(46,56,38,40,79,84)_。18. 对(46,79,56,64,38,40,84,43)进行冒泡排序，第一趟排序时，元素79将最终下沉到其后第_4_个元素的位置。19. 快速排序的平均时间复杂性为_O(nlog2n)_，最坏时间复杂性为_O(n2)_。20快速排序的平均空间复杂性为_O(log2n)_，最坏空间复杂性为_O(n)_。21快速排序每次划分时，是从当前待排序区间的_两端_向_中间_依次查找出处于逆序的元素并交换之，最后将基准元素交换到一个确定位置，从而以该位置把当前区间划分为前后两个子区间。22. 对(46,79,56,38,40,80)进行快速排序，对应判定树的深度为_，分支结点数为_。23. 对(46,79,56,38,40,80)进行快速排序，共需要_3_趟排序。24. 对(46,79,56,38,40,80)进行快速排序，含有两个或两个以上元素的排序区间的个数为_4_个。25. 对(46,79,56,25,76,38,40,80)进行快速排序，第一次划分后，右区间内元素的个数为_4_。26对(46,79,56,38,40,80)进行快速排序，第一次划分后的结果为_40 384656 79 80_。27在直接选择排序中，记录比较次数的时间复杂度为_O(n2)_，记录移动次数的时间复杂度为_O(n)_。28. 对记录(46,79,56,38,40,80,35,50,74)进行直接选择排序，用k表示最小值元素的下标，k初值为1，则在第一趟选择最小值的过程中，k的值被修改_2_次。29. 在堆排序的过程中，对n个记录建立初始堆需要进行_n/2_次筛运算，由初始堆到堆排序结束，需要对树根结点进行_n-1_次筛运算。30在堆排序的过程中，对任一分支结点进行筛运算的时间复杂性为_O(log2n) _，整个堆排序过程的时间复杂性为_O(nlog2n) _。31对n个元素建立初始堆时，最多进行_次关键字比较。32对(46,79,56,38,40,84)进行堆排序，初始小根堆为_(38,40,56,79,46,84)_，大根堆为_。33对(76,38,62,53,80,74,83,65,85)进行堆排序，已知除第一个元素外，以其余元素为根的子树都已是堆，则对第一个元素进行筛运算时，它将最终被筛到下标为_8_的位置。34假定一个堆为(38,40,56,79,46,84)，则利用堆排序方法进行第一趟交换和对根结点筛运算后得到的结果为_(40,46,56,79,84,38)_。35在一个堆的顺序存储中，若一个元素的下标为i，则它的左孩子元素的下标为_2i_，右孩子元素的下标为_2i+1_。36在一个小根堆中，堆顶结点的值是所有结点中的_最小的_，在一个大根堆中，堆顶结点的值是所有结点中的_最大的_。37.将长度分别为m和n（mn）的有序表归并成一个有序表，至少进行_n_次键值比较。38在二路归并排序中，对n个记录进行归并的趟数为_log2n_。39. 在归并排序中，进行每趟归并的时间复杂性为_O(n) _，整个排序过程的时间复杂性为_O(nlog2n)_，空间复杂性为_O(n)_。40对20个记录进行归并排序时，共需要进行_5_趟归并，在第三趟归并时是把长度为_4_的有序表两两归并为长度为_8_的有序表。41假定一组记录为(46,79,56,38,40,80,46,75)，对其进行归并排序的过程中，第二趟归并后的第2个子表为_40 46 75 80_。42假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第二趟归并后的子表个数为_3_。43假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第三趟归并后的第2个子表为_28 46_。44假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，供需要_4_趟完成。45假定一组记录为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的结果为_38 46 56 7940 80_。46. 在时间复杂性为O(nlog2n)的所有排序方法中，_归并_排序方法是稳定的。四、应用题、综合题1试给出由5个数据1，2，3，4，5组成的一个序列，使得在快速排序的第一趟划分时，移动次数最多。 2试给出由5个数据1，2，3，4，5组成的一个序列，使得用直接选择排序时，移动次数最多。3、设有50个值不同的元素存于内存一片连续单元中，若用顺序选择的方法，选出这50个元素的最大值和最小值则至少需要97次比较。请给出另一种选出最大值和最小值的方法，其比较次数一定少于97次，说明该方法的操作过程和比较次数。4、快速排序在什么情况下，所需记录之关键码的比较次数为最多？此时记录之关键码比较次数应为多少？5. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用直接插入排序法进行排序时每一趟的排序结果。 (0) 46 74 53 14 26 38 86 65 27 34 (1) 46 74 53 14 26 38 86 65 27 34 (2) 46 53 74 14 26 38 86 65 27 34 (3) 14 46 53 74 26 38 86 65 27 34 (4) 14 26 46 53 74 38 86 65 27 34 (5) 14 26 38 46 53 74 86 65 27 34 (6) 14 26 38 46 53 74 86 65 27 34 (7) 14 26 38 46 53 65 74 86 27 34 (8) 14 26 27 38 46 53 65 74 86 34 (9) 14 26 27 34 38 46 53 65 74 866. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用冒泡排序法进行排序时每一趟的排序结果。 (0) 46 74 53 14 26 38 86 65 27 34 (1) 46 53 14 26 38 74 65 27 34 86 (2) 46 14 26 38 53 65 27 34 74 86 (3) 14 26 38 46 53 27 34 65 74 86 (4) 14 26 38 46 27 34 53 65 74 86 (5) 14 26 38 27 34 46 53 65 74 86 (6) 14 26 27 34 38 46 53 65 74 86 (7) 14 26 27 34 38 46 53 65 74 867. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用快速排序法进行排序时每一趟的排序结果。 (0) 46 74 53 14 26 38 86 65 27 34 (1) 34 27 38 14 26 46 86 65 53 74 (2) 26 27 14 34 38 46 74 65 53 86 (3) 14 26 27 34 38 46 53 65 74 86 (4) 14 26 27 34 38 46 53 65 74 868. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用直接选择排序法进行排序时每一趟的排序结果。 (0) 46 74 53 14 26 38 86 65 27 34 (1) 14 74 53 46 26 38 86 65 27 34 (2) 14 26 53 46 74 38 86 65 27 34 (3) 14 26 27 46 74 38 86 65 53 34 (4) 14 26 27 34 74 38 86 65 53 46 (5) 14 26 27 34 38 74 86 65 53 46 (6) 14 26 27 34 38 46 86 65 53 74 (7) 14 26 27 34 38 46 53 65 86 74 (8) 14 26 27 34 38 46 53 65 86 74 (9)