計算機專業(yè)基礎綜合數(shù)據(jù)結構（排序）歷年真題試卷匯編3（總分：72.00，做題時間：90分鐘）一、 單項選擇題（總題數(shù)：15，分數(shù)：36.00）下面給出的四種排序法中，（）排序法是不穩(wěn)定性排序法?！颈本┖娇蘸教齑髮W1999一、10（2分）】插入冒泡二路歸并堆丿下列排序算法中，其中（）是穩(wěn)定的。【福州大學1998一、3（2分）】堆排序，冒泡排序快速排序，堆排序直接選擇排序，歸并排序歸并排序，冒泡排序丿穩(wěn)定的排序方法是（）?！颈狈浇煌ù髮W2000二、3（2分）】直接插入排序和快速排序折半插入排序和起泡排序V簡單選擇排序和四路歸并排序樹形選擇排序和Shell排序下列排序方法中，哪一個是穩(wěn)定的排序方法?（）?！颈狈浇煌ù髮W2001一、8（2分）】直接選擇排序二分法插入排序V希爾排序快速排序下列排序算法中，（）是穩(wěn)定排序?！颈本├砉ご髮W2007一、10（1分）】希爾排序快速排序堆排序直接插入排序V如果待排序序列中兩個數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。（）就是不穩(wěn)定的排序方法?！厩迦A大學1998一、3（2分）】起泡排序歸并排序Shell排序 V直接插入排序簡單選擇排序V若要求排序是穩(wěn)定的，且關鍵字為實數(shù)，則在下列排序方法中應選（）排序為宜?！局锌圃河嬎闼?000一、5（2分）】直接插入V直接選擇堆快速基數(shù)8?若需在0（nlog2n）的時間內完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）。【中國科技大學1998二、4（2分）】【中科院計算所1998二、4（2分）】快速排序堆排序歸并排序V直接插入排序下面的排序算法中，不穩(wěn)定的是()?！颈本┕I(yè)大學1999一、2(2分)】起泡排序折半插入排序簡單選擇排序丿希爾排序丿基數(shù)排序下列內部排序算法中：【北京工業(yè)大學2000一、1(10分每問2分)】A.快速排序B.直接插入排序C.二路歸并排序D.簡單選擇排序E.起泡排序(分數(shù)：8.00).其比較次數(shù)與序列初態(tài)無關的算法是()A.B.TOC\o"1-5"\h\z丿丿E..不穩(wěn)定的排序算法是()丿B.C.丿E..在初始序列已基本有序(除去n個元素中的某k個元素后即呈有序，k<A.丿C.D.E..排序的平均時間復雜度為O(n*10gn)的算法是()，為O(n*n)的算法是()TOC\o"1-5"\h\z丿丿丿丿丿排序趟數(shù)與序列的原始狀態(tài)有關的排序方法是()排序法。【北京航空航天大學1999一、9(2分)】插入選擇冒泡丿快速丿排序趟數(shù)和序列的初始狀態(tài)無關的排序方法有：直接插入排序，折半插入排序，希爾排序，簡單選擇排序，歸并排序，基數(shù)排序。而元素的比較次數(shù)和序列的初始狀態(tài)無關的排序方法有：折半插入排序，簡單選擇排序，歸并排序，基數(shù)排序。下面給出的四種排序方法中，排序過程中的比較次數(shù)與排序方法無關的是()?！颈本┖娇蘸教齑髮W2000一、10(2分)】選擇排序法丿插入排序法快速排序法堆排序法排序方法中，關鍵字比較的次數(shù)與記錄的初始排列無關的是()。【北京交通大學2013二、14(2分)】簡單選擇排序丿快速排序直接插入排序Shell排序對下列四種排序方法，在排序中關鍵字比較次數(shù)同記錄初始排列無關的是（）。【南京理工大學2000一、7（1．5分）】直接插入二分法插入丿快速排序歸并排序丿在下列排序算法中，哪一個算法的時間復雜度與初始排序無關?（）【北京理工大學2001六、4（2）】【北京工業(yè)大學2005一、4（2分）】直接插入排序氣泡排序快速排序直接選擇排序丿二、 填空題（總題數(shù)：5，分數(shù)：10.00）直接選擇排序算法在最好情況下所做的交換元素次數(shù)為 。【中南大學2005二、5（2分）】正確答案：（正確答案：0）一組記錄的排序碼為（25，48，16，35，79，82，23，40，36，72），其中含有5個長度為2的有序表，按2路歸并排序的方法對該序列進行一趟歸并后的結果 ?！颈本┙煌ù髮W2005二、8（2分）】正確答案：（正確答案：16，25，35，48，23，40，79，82，36，72。兩組（四個）長度為2的有序表進行歸并，第5個長度為2的有序表不動，等待和前面長度為8的有序表歸并。）設用希爾排序對數(shù)組｛98，36，一9，0，47，23，1，8，10，7）進行排序，給出的步長（也稱增量序列）依次是4，2，1，則排序需 趟，寫出第一趟結束后，數(shù)組中數(shù)據(jù)的排列次序 。【南京理工大學1997三、5（2分）】正確答案：（正確答案：3，（10，7，一9，0，47，23，1，8，98，36））設要將線性表（45，86，99，76，43，19，67，26，65，72，85，14）從小到大進行排序，則使用冒泡排序、初始步長為4的Shell排序、歸并排序和以第一個元素為分界元素的快速排序進行第一趟掃描的結果分別為（1），（2），（3），（4）?！旧虾：Ｊ麓髮W2005二、5（5分）】正確答案：（正確答案：初態(tài)：45，86，99，76，43，19，67，26，65，72，85，14（1）45，86，76，43，19，67，26，65，72，85，14，99（2）43，19，67，14，45，72，85，26，65，86，99，76（3）45，86，76，99，19，49，26，67，65，72，14，85（4）14，26，19，43，45，76，67，99，65，72，85，86）關鍵字序列（Q,HC,Y,Q,A,M,S,R,D，E,X），要按照關鍵字值遞增的次序進行排序，若采用初始步長為4的Shell排序法，則一趟掃描的結果是 ；若采用以第一個元素為分界元素的快速排序法，則掃描一趟的結果是 ?！颈本┐髮W1997一、4（4分）】正確答案：（正確答案:（Q，A，C，S,Q，D，F(xiàn),X,R，HM,Y），（F,E,H,C,D，Q，A，M,Q，R,S,Y,X））三、 判斷題（總題數(shù)：10,分數(shù)：20.00）用希爾（Shell）方法排序時，若關鍵字的初始排序雜亂無序，則排序效率就低。（）【中國海洋大學2005二、12（1分）】正確錯誤丿起泡排序的排序趟數(shù)與參加排序的序列原始狀態(tài)有關。（）【蘭州大學2000一、5（1分）】正確丿錯誤

22?對于n個記錄的集合進行冒泡排序，在最壞情況下所需要的時間是0(n2)。()【中國海洋大學2006二、15(1分)】正確丿錯誤23?直接選擇排序算法的時間復雜度為0(n2)，不受數(shù)據(jù)初始排列的影響。()【北京郵電大學2006二、3(1分)】正確丿錯誤直接選擇排序算法在最好情況下的時間復雜度為O(N)。()【合肥工業(yè)大學2001二、10(1分)】【北京交通大學2005三、7(2分)】正確錯誤丿直接選擇排序是不穩(wěn)定排序。()【北京郵電大學2006二、10(1分)】正確丿錯誤交換排序法是對序列中的元素進行一系列比較，當被比較的兩個元素逆序時，進行交換，冒泡排序和快速排序是基于這類方法的兩種排序方法，冒泡排序算法的最壞時間復雜性是O(n*n)，而快速排序算法的最壞時間復雜性是0(nlogn)；所以快速排序比冒泡排序效率更高。()【上海海事大學1998—、10(1分)19972一、9(1分)1995一、10(1分)】正確錯誤丿在初始數(shù)據(jù)表已經(jīng)有序時，快速排序算法的時間復雜度為0(nlogn)o()【合肥工業(yè)大學2000二、29(1分)】正確錯誤丿在數(shù)據(jù)基本有序時，快速排序蛻變?yōu)槠鹋菖判?，時間復雜度是0(n2)。在待排數(shù)據(jù)基本有序的情況下，快速排序效果最好。()【南京理工大學1997二、4(2分)】正確錯誤丿快速排序總比簡單排序快。()【東南大學2001一、9(1分)】正確錯誤V四、 綜合題(總題數(shù)：3，分數(shù)：6.00)對一個由n個關鍵字不同的記錄構成的序列，能否用比2n一3少的次數(shù)選出該序列中關鍵字取最大值和關鍵字取最小值的記錄?請說明如何實現(xiàn)?在最壞的情況下至少進行多少次比較?【東南大學2000一、5(8分)】正確答案：(正確答案：本題答案之一請參見第9章的四、8題，這里用分治法求解再給出另一參考答案。對于兩個數(shù)x和y，經(jīng)一次比較可得到最大值和最小值；對于三個數(shù)x、y、z，最多經(jīng)3次比較可得最大值和最小值;對于n(n>3)個數(shù)，將分成長為n一2和2的前后兩部分A和B,分別找出最大者和最小者:MaXA、MinA、MaxB、MinB，最后Max={MaXA，MaxB)和Min={MinA，MinB)。對A使用同樣的方法求出最大值和最小|3n上值，直到元素個數(shù)不超過3。設C(n)是所需的最多比較次數(shù)，根據(jù)上述原則，當n>3時有如下關系式：通過逐步遞推，可以得到：C(n)==|3n/2|一2。顯然，當n三3時，2，z一3>3n/2—2。事實上，/2|一|3n上利用比較的方法進行排序，在最壞的情況下，能達到的最好時間復雜性是什么?請給出詳細證明海交通大學2000六(8分)】正確答案：(正確答案：假定待排序的記錄有n個。由于含n個記錄的序列可能出現(xiàn)的狀態(tài)有n!個，則描述n個記錄排序過程的判定樹必須有n!個葉子結點。因為若少一個葉子，則說明尚有兩種狀態(tài)沒有分辨出來。我們知道，若二叉樹高度是h，則葉子結點個數(shù)最多為2k-i；反之，若有u個葉子結點，則二叉樹的高度至少為丨logu|+1。這就是說，描述n個記錄排序的判定樹必定存在一條長度為丨log(n!)|的22路徑。即任何一個借助“比較”進行排序的算法，在最壞情況下所需進行的比較次數(shù)至少是|log2(n!)|。2根據(jù)斯特林公式，有Ilog(n!)I=0(nlogn)。即借助于“比較”進