數(shù)據(jù)結(jié)構(gòu)-第七章排序例題

【例】若數(shù)據(jù)序列（8，9，10，4，5，6，20，1，2）是某種排序算法兩趟排序后的結(jié)果，則這種排序算法可能是A.選擇排序B.冒泡排序C.插入排序D.堆排序答案：C【例】要使數(shù)據(jù)序列（2，1，4，6，8，10，7，20）成為某種排序算法兩趟排序后的結(jié)果，下列選項(xiàng)中，正確的是快速排序B.冒泡排序C.選擇排序D.插入排序答案：A第一趟，6為樞軸第二趟，4，20為樞軸【例】對(duì)一組數(shù)據(jù)（84，47，25，15，21）排序，若數(shù)據(jù)的排列次序在排序的過程中的變化為（1）84,47,25,15,21（2）15,47,25,84,21（3）15,21,25,84,47（4）15,21,25,47,84則采用的排序算法是A.選擇B.冒泡C.快速D.插入答案：A【例】對(duì)序列15，9，7，8，20，-1，4進(jìn)行排序，進(jìn)行一趟后數(shù)據(jù)的排列變?yōu)?，9，-1，8，20，7，15則采用的排序算法是A.選擇B.快速C.希爾D.冒泡答案：C【例】對(duì)序列15，9，7，8，20，-1，4進(jìn)行排序，進(jìn)行一趟后數(shù)據(jù)的排列變?yōu)?/p>

9，15，7，8，20，-1，4則采用的排序算法是A．選擇B.堆C.直接插入D.冒泡答案：C【例】設(shè)一數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60若由不同排序方法進(jìn)行一遍排序后的結(jié)果分別如下：①12，13，15，18，20，60②13，15，18，12，20，60③13，15，20，18，12，60④12，13，20，18，15，60答案：則對(duì)應(yīng)的排序方法可能是①快速排序、Shell排序②起泡排序③插入排序④選擇排序【例】對(duì)7個(gè)元素做快速排序，至少需要的比較次數(shù)是A.9

B.10C.11D.12答案：B【例】對(duì)7個(gè)元素做快速排序，最多需要的比較次數(shù)是A.19

B.20C.21D.22答案：C【例】下列排序算法中，不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上的是A.快速排序B.shell排序C.堆排序D.冒泡排序答案：B【例】排序過程中的比較次數(shù)與序列初始狀態(tài)無關(guān)的是A.選擇排序B.插入排序C.快速排序D.冒泡排序答案：A【例】最壞、平均和最好情況下的時(shí)間復(fù)雜度都是一樣的排序方法是A.冒泡排序B.插入排序C.快速排序D.堆排序答案：D【例】下列排序算法中，排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上的是A.選擇B.冒泡C.歸并D.堆答案：C【例】在待排序的元素序列基本有序的前提下，效率最高的排序方法是A.插入排序B.選擇排序C.快速排序D.歸并排序答案：A【例】若在排序過程中可能會(huì)出現(xiàn)下面這種情況：在最后一趟開始之前，所有元素都不在其最終的位置上，則采用的排序算法是A.堆排序B.冒泡排序C.快速排序D.插入排序答案：D【例】下列排序算法中，占用輔助空間最多的是A.歸并排序B.快速排序C.希爾排序D.堆排序答案：A【例】將兩個(gè)各有N個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是A．NB．2N-1C．2ND．N-1答案：A【例】將兩個(gè)各有N個(gè)元素的有序表歸并成一個(gè)有序表，其最多的比較次數(shù)是A．NB．2N-1C．2ND．N-1答案：B[例]

若用某種排序方法對(duì)關(guān)鍵字序列

25，84，21，47，15，27，68，35，20進(jìn)行排序時(shí)，序列的變化情況如下：

25，84，21，47，15，27，68，35，20

20，15，21，25，47，27，68，35，84

15，20，21，25，35，27，47，68，84

15，20，21，25，27，35，47，68，84

則所采用的排序方法是

(A)選擇排序

(B)直接插入排序

(C)歸并排序

(D)快速排序答：D[例]

下列因素中，影響排序算法穩(wěn)定性的因素是Ⅰ.有排序碼朝著最終排序位置相反方向移動(dòng)的現(xiàn)象

Ⅱ.排序過程中是否發(fā)生了不相鄰元素的交換Ⅲ.是否有關(guān)鍵碼相同的元素Ⅳ.排序算法是否采用遞歸方式實(shí)現(xiàn)(A)僅Ⅰ(B)僅Ⅱ(C)Ⅰ和Ⅲ(D)Ⅰ和Ⅳ答案：B[例]

若需在O(nlog2n)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是(A)快速排序(B)堆排序(C)歸并排序(D)Shell排序答案：C[例]下列內(nèi)部排序算法中，其元素比較次數(shù)與序列初始狀態(tài)無關(guān)的算法是Ⅰ.快速排序Ⅱ.直接插入排序Ⅲ.起泡排序Ⅳ.直接選擇排序

(A)僅Ⅱ(B)僅Ⅳ(C)僅Ⅰ和Ⅱ2(D)僅Ⅲ和Ⅳ答案：B[例]

對(duì)序列

15，9，7，8，20，1，4用Shell排序方法進(jìn)行排序，若經(jīng)一趟處理后的結(jié)果為

15，l，4，8，20，9，7則該趟采用的增量是(A)l(B)2(C)3(D)4答案：D[例]

歸并排序方法用于內(nèi)部排序時(shí)，常采用二路歸并。若采用k路歸并（k>2），則能達(dá)到的最好的時(shí)間復(fù)雜度是(A)O(klog2n)(B)O(nlog2k)(C)O(nlog2n)(D)O(klog2k)答案：C[例]若數(shù)據(jù)元素序列：

11，12，13，7，8，9，23，4，5是采用下述排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是(A)起泡排序(B)直接插入排序(C)選擇排序(D)二路歸并排序答案：B[例]采用遞歸方式對(duì)順序表進(jìn)行快速排序。下列關(guān)于遞歸次數(shù)的敘述中，正確的是(A)遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)(B)每次劃分后，先處理較長(zhǎng)的分區(qū)可以減少遞歸次數(shù)(C)每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)(D)遞歸次數(shù)與每次劃分后得到的分區(qū)的處理順序無關(guān)答案：D[例]

對(duì)一組數(shù)據(jù)進(jìn)行排序，若前三趟排序結(jié)果如下：第一趟排序結(jié)果：2，12，16，5，10，88

第二趟排序結(jié)果：2，12，5，10，16，88

第三趟排序結(jié)果：2，5，10，12，16，88則采用的排序方法可能是(A)起泡排序(B)希爾排序(C)歸并排序(D)基數(shù)排序答案：A【問題】

設(shè)有一個(gè)無序的關(guān)鍵字序列K1、K2、…、Kn。現(xiàn)要求將X插入到序列排好序后的正確位置上。試編寫實(shí)現(xiàn)該功能的算法?！舅悸贰?/p>

仿照快速排序中的一趟劃分算法。將X作為序列的最后一個(gè)元素，并以此作為樞軸進(jìn)行劃分。

intPartition_r(intK[]，intm){

inti=0;int

j=m;

int

temp=K[j];

while(i<j){while(i<j&&K[i]<=temp)i++;if(i<j)K[j]=K[i];while(i<j&&K[j]>=temp)j--;if(i<j)K[i]=K[j];}//whileK[i]=temp;return

i;}//Partition_r

int

Place_k(intn，intx){

intK[n+1];

int

Pos；

輸入序列并順序放在K的0,…,n-1單元中；

輸入x并放在K的n單元中；

Pos=Partition_r(K,n);

輸出Pos；

}//Place_k【問題】對(duì)于一個(gè)關(guān)鍵碼均不相同的無序序列，試編寫一個(gè)算法，求其中從小到大的第k個(gè)元素，并分析算法的時(shí)間復(fù)雜度?！舅悸贰?/p>

可以先排序，再從排好序的序列中找出第k個(gè)元素，其平均時(shí)間復(fù)雜度不可能好于O(nlog2n)。借鑒快速排序算法的思想，不斷對(duì)序列進(jìn)行劃分。當(dāng)基準(zhǔn)元素的位置等于k-1時(shí)，基準(zhǔn)元素就是第k個(gè)元素；否則，選擇適當(dāng)子序列再做進(jìn)一步的劃分。voidSearch_k(intA[],intleft,intright,intk){intm=k-1;if(left<right&&right>=k)//元素序列長(zhǎng)度大于1且元素序列中含有第k小元素時(shí)

{intpivotPos;

pivotPos=Partition(A,left,right);//劃分

if(pivotPos==m) { printf(“第%d小元素為%d\n",m,A[pivotPos]);