第3章排序答案

1、1第3章排序排序自測卷自測卷答案答案姓名姓名班級班級題號題號一二三四五總分總分題分題分241836814100得分得分一、填空題（每空一、填空題（每空1分，共分，共24分）分）1.大多數(shù)排序算法都有兩個基本的操作：大多數(shù)排序算法都有兩個基本的操作：比較（兩個關(guān)鍵字的大?。┍容^（兩個關(guān)鍵字的大小）和移動（記錄或改變指向記錄的移動（記錄或改變指向記錄的指針）指針）。2.在對一組記錄（在對一組記錄（54，38，96，23，15，72，60，4

2、5，83）進行直接插入排序時，當把第）進行直接插入排序時，當把第7個記錄個記錄60插入到插入到有序表時，為尋找插入位置有序表時，為尋找插入位置至少至少需比較需比較3次。次。(可約定為，從后向前比較可約定為，從后向前比較)3.在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用插入排序（到尾部）插入排序（到尾部）；若初始數(shù)據(jù)基本反序，則；若初始數(shù)據(jù)基本反序，則選用選用選擇排序選擇排序。4.在堆排序和

3、快速排序中，若初始記錄接近正序或反序，則選用在堆排序和快速排序中，若初始記錄接近正序或反序，則選用堆排序堆排序；若初始記錄基本無序，則最好選；若初始記錄基本無序，則最好選用快速排序快速排序。5.對于對于n個記錄的集合進行冒泡排序，在最壞的情況下所需要的時間是個記錄的集合進行冒泡排序，在最壞的情況下所需要的時間是O(n2)。若對其進行快速排序，在。若對其進行快速排序，在最壞的情況下所需要的時間是最壞的情況下所需要的時間是O(n2)。6.對

4、于對于n個記錄的集合進行歸并排序，所需要的平均時間是個記錄的集合進行歸并排序，所需要的平均時間是O(nlog2n)，所需要的附加空間是，所需要的附加空間是O(n)。7【計研題【計研題2000】對于對于n個記錄的表進行個記錄的表進行2路歸并排序，整個歸并排序需進行路歸并排序，整個歸并排序需進行l(wèi)og2n趟（遍）趟（遍），共計移，共計移動nlog2n次記錄。次記錄。(即移動到新表中的總次數(shù)！共即移動到新表中的總次數(shù)！共log2nlog2n趟

5、，每趟都要移動趟，每趟都要移動n個元素個元素)8.設(shè)要將序列（設(shè)要將序列（QHCYPAMSRDFX）中的關(guān)鍵碼按字母序的升序重新排列，則：）中的關(guān)鍵碼按字母序的升序重新排列，則：冒泡排序一趟掃描的結(jié)果是冒泡排序一趟掃描的結(jié)果是HCQPAMSRDFXY；初始步長為初始步長為4的希爾（的希爾（shell）排序一趟的結(jié)果是）排序一趟的結(jié)果是PACSQDFXRHMY；二路歸并排序一趟掃描的結(jié)果是二路歸并排序一趟掃描的結(jié)果是HQCY，APMSDR

6、FX；快速排序一趟掃描的結(jié)果是快速排序一趟掃描的結(jié)果是FHCDPAMQRSY，X；堆排序初始建堆的結(jié)果是堆排序初始建堆的結(jié)果是ADCRFQMSY，PHX。9.在堆排序、快速排序和歸并排序中，在堆排序、快速排序和歸并排序中，若只從存儲空間考慮，則應(yīng)首先選取若只從存儲空間考慮，則應(yīng)首先選取堆排序堆排序方法，其次選取方法，其次選取快速排序快速排序方法，最后選取方法，最后選取歸并排序歸并排序方法；方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)若只從排序

7、結(jié)果的穩(wěn)定性考慮，則應(yīng)選取選取歸并排序歸并排序方法；方法；若只從平均情況下最快考慮，則應(yīng)選取若只從平均情況下最快考慮，則應(yīng)選取快速排序快速排序方法；方法；若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取堆排序堆排序方法。方法。二、單項選擇題（每小題二、單項選擇題（每小題1分，共分，共18分）分）（C）1將將5個不同的數(shù)據(jù)進行排序，至多需要比較個不同的數(shù)據(jù)進行排序，至多需要比較次。次。3（B

8、）15若一組記錄的排序碼為（若一組記錄的排序碼為（467956384084），則利用堆排序的方法建立的初始堆為，則利用堆排序的方法建立的初始堆為Ａ.794656384084Ｂ.847956384046Ｃ.847956464038Ｄ.845679404638（B）16下述幾種排序方法中，平均查找長度（下述幾種排序方法中，平均查找長度（ASL）最小的是）最小的是Ａ.插入排序插入排序Ｂ.快速排序快速排序Ｃ.歸并排序歸并排序Ｄ.選擇排序選擇排序

9、（C）17下述幾種排序方法中，要求內(nèi)存最大的是下述幾種排序方法中，要求內(nèi)存最大的是Ａ.插入排序插入排序Ｂ.快速排序快速排序Ｃ.歸并排序歸并排序Ｄ.選擇排序選擇排序（B）18目前以比較為基礎(chǔ)的內(nèi)部排序方法中，其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無關(guān)的是目前以比較為基礎(chǔ)的內(nèi)部排序方法中，其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無關(guān)的是Ａ.插入排序插入排序Ｂ.二分插入排序二分插入排序Ｃ.快速排序快速排序Ｄ.冒泡排序冒泡排序三、簡答題（每小題三

10、、簡答題（每小題4分，共分，共36分）分）1.1.【全國專升本題】【全國專升本題】已知序列基本有序，問對此序列最快的排序方法是多少，此時平均復(fù)雜度是多少？已知序列基本有序，問對此序列最快的排序方法是多少，此時平均復(fù)雜度是多少？答：插入排序和冒泡應(yīng)該是最快的。因為只有比較動作，無需移動元素。此時平均時間復(fù)雜度為答：插入排序和冒泡應(yīng)該是最快的。因為只有比較動作，無需移動元素。此時平均時間復(fù)雜度為O(n)2.設(shè)有設(shè)有1000個無序的元素，希望

11、用最快的速度挑選出其中前個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好采用哪種排序方法？個最大的元素，最好采用哪種排序方法？答：用堆排序或錦標賽排序最合適，因為不必等全部元素排完就能得到所需結(jié)果，時間效率為答：用堆排序或錦標賽排序最合適，因為不必等全部元素排完就能得到所需結(jié)果，時間效率為O(O(O(nnlogloglog22nn))；若用冒泡排序則需時若用冒泡排序則需時n!(n10)!3.用某種排序方法對線性表（用某種

12、排序方法對線性表（2584，21471527683520）進行排序時，元素序列的變化情況如下：）進行排序時，元素序列的變化情況如下：2584，21471527683520→20152125，4727683584→15202125，3527476884→15202125，2735476884，問采用的是什么排序方法？問采用的是什么排序方法？答：用的是快速排序方法。注意每一趟要振蕩完全部元素才算一個中間結(jié)果。答：用的是快速排序方法。注意每一

13、趟要振蕩完全部元素才算一個中間結(jié)果。4.對于整數(shù)序列對于整數(shù)序列100，99，98，…，…3，2，1，如果將它完全倒過來，分別用冒泡排序和快速排序法，它們的比較，如果將它完全倒過來，分別用冒泡排序和快速排序法，它們的比較次數(shù)和交換次數(shù)各是多少？次數(shù)和交換次數(shù)各是多少？答：冒泡排序的比較和交換次數(shù)將最大，都是答：冒泡排序的比較和交換次數(shù)將最大，都是12…n1=n(n1)2＝5099=4545次快速排序則看按什么數(shù)據(jù)來分子表?？焖倥判騽t看按

14、什么數(shù)據(jù)來分子表。如果按如果按100來分，則很慘，也會是來分，則很慘，也會是n(n1)2！若按中間數(shù)據(jù)若按中間數(shù)據(jù)50或51來分表來分表，則：，則：第1輪能確定輪能確定1個元素，即在個元素，即在1個子表中比較和交換了個子表中比較和交換了n－1個元素；個元素；n－（－（211）第2輪能再確定輪能再確定2個元素，即在個元素，即在2個子表中比較和交換了個子表中比較和交換了n－3個元素；個元素；n－（－（221）第3輪能再確定輪能再確定4個元素

15、，即在個元素，即在4個子表中比較和交換了個子表中比較和交換了n－7個元素；個元素；n－（－（231）第4輪能再確定輪能再確定8個元素，即在個元素，即在8個子表中比較和交換了個子表中比較和交換了n－15個元素；個元素；n－（－（241）…………第6輪能再確定輪能再確定32個元素，即在個元素，即在32個子表中比較和交換了個子表中比較和交換了n－65個元素；個元素；n－（－（261）第7輪則能全部確定，輪則能全部確定，（因為（因為27=128