數(shù)據(jù)結(jié)構(gòu)排序部分練習題

1、一、單選題12設(shè)有500個0無序的元素，希望用最快的速度挑選出其中前50個最大的元素，最好選用(法。A冒泡排序.快速排序.堆排序.歸并排序1已知持排序的n個元素可分為n/k個組，每個組包含k個元素，各組間分塊有序，若采用基于比較的排序，其時間下界應(yīng)為：()AO(nlog2n)BO(nlog2k)CO(klog2n)DO(klog2k)最好和最壞時間復雜度均為O(nlogn)且穩(wěn)定的排序方法是()。A.快速排序B.堆排序2C.歸并排序D.基數(shù)排序3下列排序算法中，當初始數(shù)據(jù)有序時，花費時間反而最多的是()。A.起泡排序B.希爾排序C.堆排序D.快速排序)D.直接插入排序4.若需在O(nlog2n

2、)的時間內(nèi)完成排序，且要求穩(wěn)定，則可選擇(A.快速排序B.堆排序)D.直接插入排序5排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是()排序法。A.插入B.選擇C.希爾D.快速6已知數(shù)據(jù)表每個元素距離其最終位置不遠，則最省時間的排序算法是()。A.堆排序B.直接插入排序C.快速排序D.直接選擇排序7關(guān)鍵字比較次數(shù)與數(shù)據(jù)的初始狀態(tài)無關(guān)的排序算法是()。A.直接選擇排序B.冒泡排序C.直接插入排序D.希爾排序若一個元素序列基本有序，則選用()方法較快。A.直接插入排序B.直接選擇排序C.堆排序D.快速排序若要從1000個元素中得到4個最小值元素，最好采用()方法。A.直接插入排序B.直接選擇排序C.堆排序

3、D.快速排序若要對1000個元素排序，要求既快又穩(wěn)定，則最好采用()方法。A.直接插入排序B.歸并排序C.堆排序D.快速排序若要對1000個元素排序，要求既快又節(jié)省存儲空間，則最好采用()方法。A.直接插入排序B.歸并排序C.堆排序D.快速排序在下列排序方法中，空間復雜性為O(log2n)的方法為()。A.直接選擇排序B.歸并排序C.堆排序D.快速排序在平均情況下速度最快的排序方法為()。A.直接選擇排序B.歸并排序C.堆排序D.快速排序設(shè)有關(guān)鍵字初始序列Q,H,C,Y,P,A,M,S,R,D,F,X,則用下列哪種排序方法進行第一趟掃描的結(jié)果為F,H,C,D,P,A,M,Q,R,S,Y,X？A

4、.直接插入排序B.二路歸并排序C.以第一兀素為基準的快速排序D.基數(shù)排序15從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法稱為()排序法。A.插入B.選擇C.希爾D.二路歸并16下面排序法中，()排序法是不穩(wěn)定的。TOC o 1-5 h zA.插入B.冒泡C.二路歸并D.堆下列排序方法中，不穩(wěn)定的是()A.直接插入排序B.冒泡排序C.歸并排序D.直接選擇排序在直接插入排序的第i趟排序前，有序表中的兀素個數(shù)為()。AiBi+1Ci-1D1在直接插入排序的第i趟排序時，為尋找插入位置最多需要進行()次元素的比較，假定第0號元素作監(jiān)視哨。

5、AiBi-1Ci+1D1若對n個元素進行直接插入排序，在進行第i趟排序時，假定元素ri+l的插入位置為rj,則需要移動元素的次數(shù)為()。Aj-iBi-j-lCi-jDi-j+l對n個元素進行直接插入排序，則各趟排序中尋找插入位置的平均時間復雜性為()。AO(l)BO(n)CO(n2)DO(log2n)TOC o 1-5 h z在對n個元素進行直接插入排序的過程中，共需要進行()趟。AnBn+1Cn-1D2n對n個元素進行直接插入排序時間復雜性為()。AO(1)BO(n)CO(n2)DO(log2n)n個記錄直接插入排序時所需的記錄最小比較次數(shù)是()An-1BnCn(n-1)/2Dn(n+1)/

6、2對n個元素進行直接插入排序，空間復雜性為()。)對相鄰元素之間的交換。AO(1)BO(log2n)CO(n2)DO(nlog2)對相鄰元素之間的交換。對n個元素進行冒泡排序，第一趟至多需要進行(AnBn-1Cn+1Dn/2對n個元素進行冒泡排序，最好情況下的時間復雜性為()。AO(1)BO(log2n)CO(n2)DO(n)對n個元素進行冒泡排序，至少需要()趟完成。A1BnCn-1Dn/2ZO)小于)次元素，假定包括基準和臨時量之間的移Dn+16快速排序的記錄移動次數(shù)()ZO)小于)次元素，假定包括基準和臨時量之間的移Dn+1對n個元素進行快速排序，第一次劃分最多需要移動(動。TOC o

7、1-5 h zAn/2Bn-1Cn30.對序列(3,7,5,9,1)進行快速排序，則第一次劃分時需要移動元素的次數(shù)為()，假定不包括基準和臨時量之間的移動。A1B2C3D431.對n個元素進行快速排序，最好情況下需要進行()趟。AnBn/2Clog2n最壞情況下需要進行()趟。D2n32.對n個元素進行快速排序，AnBn-1Cn/2Dlog2n33.對n個元素進行快速排序，平均情況下的時間復雜性為()。2TOC o 1-5 h zAO(1)BO(log2n)CO(n2)DO(nlog2n)對n個元素進行快速排序，最壞情況下的時間復雜性為()。AO(1)BO(log2n)CO(n2)DO(nlo

8、g2n)對n個元素進行快速排序，平均情況下的空間復雜性為()。AO(1)BO(log2n)CO(n2)DO(nlog2n)對n個元素進行快速排序，最壞情況下的空間復雜性為()。AO(1)BO(log2n)CO(n2)DO(nlog2n)對下列四個序列進行快速排序，各以第一個元素為基準進行第一次劃分，則在該次劃分過程中需要移動元素次數(shù)最多的序列為()。A1,3,5,7,9B9,7,5,3,1C5,3,1,7,9D5,7,9,1,338.假定對元素序列(7,3,5,9,1,12,8,15)進行快速排序，則進行第一次劃分后，得到的左區(qū)間中元素的個數(shù)為()。TOC o 1-5 h zA2B3C4D53

9、9對n個元素進行直接選擇排序，需要進行()趟選擇和交換。AnBn+1Cn-1Dn/240對n個元素進行直接選擇排序，在第i趟需要從()個元素中選擇最小者。An-i+1Bn-ICIDi+1對n個元素進行直接選擇排序，則各趟尋找最小值元素所需時間復雜性為()。AO(1)BO(log2n)CO(n2)DO(n)5堆排序在最壞情況下，其時間復雜性為()。A)(nlogn)B)(n2)C)(logn2)D)(logn)對n個元素進行堆排序，在構(gòu)成初始堆的過程中需要進行()次篩運算。TOC o 1-5 h zA1Bn/2CnDn-1對n個元素進行堆排序，建初始堆后，還要進行()次篩選運算。An+1Bn/2

10、CnDn-1對n個元素進行堆排序，每次篩運算的時間復雜性為()。AO(1)BO(log2n)CO(n2)DO(n)對n個元素進行堆排序，時間復雜性為()。AO(1)BO(log2n)CO(n2)DO(nlog2n)對n個元素進行堆排序，空間復雜性為()。AO(1)BO(log2n)CO(n2)DO(nlog2n)12對排序碼(4、77、86、133、39、80用)堆排序的方法建立的初始堆為(。)假定用小根堆對(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,7假定初始堆為(1,5,3,9

11、,12,7,15,10)，則第一趟堆排序后的結(jié)果為()TOC o 1-5 h zA3,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個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是()AnB2n1C2nDn-1若對n個元素進行歸并排序，則進行歸并的趟數(shù)為()。A.nB.n-1C.n/2D.log2n,若對n個元素進行歸并排序，則進行每一趟歸并的時間復雜性為()。A.O(1)B.O(log2n)C.O(n)D.O(n2)二、判斷題如果某種排序算法是不穩(wěn)定的，則該方法沒有實際的應(yīng)用

12、價值。對數(shù)據(jù)按關(guān)鍵字進行排序能夠有效地提高查找速度。直接插入排序是穩(wěn)定的，而Shell排序就是調(diào)用若干趟直接插入排序，所以也是穩(wěn)定的。用直接選擇排序方法分別對序列Sl=(l,2,3,4,5,6,7)和序列S2=(7,5,3,2,4,l,6)進行排序，兩者的比較次數(shù)不相同。直接選擇排序的比較次數(shù)與序列的初始狀態(tài)無關(guān)。堆排序法在最好和最壞情況下時間復雜性都是O(nlog2n)。堆的存儲表示是順序的。以中序方式遍歷一個堆，則得到一個有序序列。二路歸并排序的核心操作是把兩個有序序列合并為一個有序序列?？焖倥判蚍偸切首罡叩呐判蚍āｎ櫭剂x，快速排序法是在所有情況下，速度最快的排序方法。三、填空題11

13、最簡單的交換排序方法是排_序_。11直接插入排序需要個_記_錄_的_輔_助空間。12在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用；_若_初_始_數(shù)_據(jù)基本反序，則選用。評價排序效率的主要標準是。在時間復雜性為O(n2)的所有排序方法中，直接選擇排序方法是不穩(wěn)定的。在所有排序方法中，快速排序方法采用的是二分法的思想。在所有排序方法中，堆排序方法使數(shù)據(jù)的組織采用的是完全二叉樹的結(jié)構(gòu)。在所有排序方法中，歸并排序方法采用的是兩兩有序表合并的思想。3采用冒泡排序?qū)τ袀€記錄的表按鍵值遞增排序，若的初始狀態(tài)是按鍵值遞增，則排序過程中記錄的比較次數(shù)為。若初始狀態(tài)為遞減排列，則記錄的交換次數(shù)為。冒泡排序方法使

14、鍵值大的記錄逐漸下沉，使鍵值小的記錄逐漸上浮。直接插入排序方法能夠每次使無序表中的第一個記錄插入到有序表中。直接選擇排序方法能夠每次從無序表中順序查找出一個最小值。每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做_插入_排序；每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做_選擇_排序。每次直接或通過基準元素間接比較兩個元素，若出現(xiàn)逆序排列時就交換它們的位置，此種排序方法叫做_交換_排序；每次使兩個相鄰的有序表合并成一個有序表的排序方法叫做_歸并_排序。對n個數(shù)據(jù)進行直接插入排序，最少比較次數(shù)為。若對一組記錄(46,79,56,38,4

15、0,80,35,50,74)進行直接插入排序，當把第8個記錄插入到前面已排序的有序表時，為尋找插入位置需比較4次。取增量為3,對記錄(46,79,56,38,40,80,35,50,74)進行一趟希爾排序的結(jié)果為對n個記錄進行冒泡排序時，最多比較次數(shù)為、最少的比較次數(shù)為_n-1_，最少的趟數(shù)為1_。用起泡法對n個關(guā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進行排序，交換次序較少的是序列。對(46,7

16、9,56,38,40,84)進行冒泡排序，第一趟排序后的結(jié)果為(46,56,38,40,79,84)_。對(46,79,56,64,38,40,84,43)進行冒泡排序，第一趟排序時，元素79將最終下沉到其后第_4個元素的位置。TOC o 1-5 h z19.快速排序的平均時間復雜性為_O(nlog2n)_，最壞時間復雜性為O(n2)。20快速排序的平均空間復雜性為_O(log2n)_，最壞空間復雜性為O(n)。21快速排序每次劃分時，是從當前待排序區(qū)間的_兩端_向_中間_依次查找出處于逆序的元素并交換之最后將基準元素交換到一個確定位置，從而以該位置把當前區(qū)間劃分為前后兩個子區(qū)間。22.對(4

17、6,79,56,38,40,80)進行快速排序，對應(yīng)判定樹的深度為，分支結(jié)點數(shù)為。23.對(46,79,56,38,40,80)進行快速排序，共需要3趟排序。24.對(46,79,56,38,40,80)進行快速排序，含有兩個或兩個以上元素的排序區(qū)間的個數(shù)為4個。25.對(46,79,56,25,76,38,40,80)進行快速排序，第一次劃分后，右區(qū)間內(nèi)元素的個數(shù)為4。26對(46,79,56,38,40,80)進行快速排序，第一次劃分后的結(jié)果為_403846567980_。27在直接選擇排序中，記錄比較次數(shù)的時間復雜度為_O(n2)_，記錄移動次數(shù)的時間復雜度為_O(n)_。28.對記錄(

18、46,79,56,38,40,80,35,50,74)進行直接選擇排序，用k表示最小值元素的下標，k初值為1,則在第一趟選擇最小值的過程中，k的值被修改_2次。29.在堆排序的過程中，對n個記錄建立初始堆需要進行_n/2_次篩運算，由初始堆到堆排序結(jié)束，需要對樹根結(jié)點進行_n-1_次篩運算。30在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復雜性為_O(log2n)，整個堆排序過程的時間復雜性為_O(nlog2n)_。31對n個元素建立初始堆時，最多進行次關(guān)鍵字比較。32對(46,79,56,38,40,84)進行堆排序，初始小根堆為_(38,40,56,79,46,84)_，大根堆為。33

19、對(76,38,62,53,80,74,83,65,85)進行堆排序，已知除第一個元素外，以其余元素為根的子樹都已是堆，則對第一個元素進行篩運算時，它將最終被篩到下標為_8_的位置。34假定一個堆為(38,40,56,79,46,84)，則利用堆排序方法進行第一趟交換和對根結(jié)點篩運算后得到的結(jié)果為_(40,46,56,79,84,38)_。在一個堆的順序存儲中，若一個元素的下標為i,則它的左孩子元素的下標為_2i_，右孩子元素的下標為_2i+1_。在一個小根堆中，堆頂結(jié)點的值是所有結(jié)點中的_最小的_，在一個大根堆中，堆頂結(jié)點的值是所有結(jié)點中的_最大的_。將長度分別為m和n(mn)的有序表歸并成

20、一個有序表，至少進行n_次鍵值比較。在二路歸并排序中，對n個記錄進行歸并的趟數(shù)為log2n_。在歸并排序中，進行每趟歸并的時間復雜性為_O(n)_，整個排序過程的時間復雜性為_O(nlog2n)_，空間復雜性為_O(n)_。對20個記錄進行歸并排序時，共需要進行_5_趟歸并，在第三趟歸并時是把長度為_4_的有序表兩兩歸并為長度為_8_的有序表。假定一組記錄為(46,79,56,38,40,80,46,75)，對其進行歸并排序的過程中，第二趟歸并后的第2個子表為_40467580_。假定一組記錄為(46,79,56,38,40,80,46,75,28,46)，對其進行歸并排序的過程中，第二趟歸并后的子表個數(shù)為_3_。假定一組記錄為(46,79,56,38,40,80,46,75,28,46)，對其進行歸并排序的過程中，第三趟歸并后的第2個子表為_2846_。假定一組記錄為(46,79,56,38,40,80,46,75,28,46)，對其進行歸并排序的過程中，供需要_4_趟完成。假定一組記錄為(46,79,56,38,40,80)，對其進行歸并排序的過程中，第二趟歸并后的結(jié)果為_384656794080_。在時間復雜性為O(nlog2n)的所