第3章排序答案

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

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

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

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

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

6、FX；快速排序一趟掃描的結(jié)果是快速排序一趟掃描的結(jié)果是FHCDPAMQRSY，X；堆排序初始建堆的結(jié)果是堆排序初始建堆的結(jié)果是ADCRFQMSY，PHX。9.在堆排序、快速排序和歸并排序中，在堆排序、快速排序和歸并排序中，若只從存儲(chǔ)空間考慮，則應(yīng)首先選取若只從存儲(chǔ)空間考慮，則應(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)選取堆排序堆排序方法。方法。二、單項(xiàng)選擇題（每小題二、單項(xiàng)選擇題（每小題1分，共分，共18分）分）（C）1將將5個(gè)不同的數(shù)據(jù)進(jìn)行排序，至多需要比較個(gè)不同的數(shù)據(jù)進(jìn)行排序，至多需要比較次。次。3（B

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

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

10、、簡(jiǎn)答題（每小題4分，共分，共36分）分）1.1.【全國(guó)專升本題】【全國(guó)專升本題】已知序列基本有序，問(wèn)對(duì)此序列最快的排序方法是多少，此時(shí)平均復(fù)雜度是多少？已知序列基本有序，問(wèn)對(duì)此序列最快的排序方法是多少，此時(shí)平均復(fù)雜度是多少？答：插入排序和冒泡應(yīng)該是最快的。因?yàn)橹挥斜容^動(dòng)作，無(wú)需移動(dòng)元素。此時(shí)平均時(shí)間復(fù)雜度為答：插入排序和冒泡應(yīng)該是最快的。因?yàn)橹挥斜容^動(dòng)作，無(wú)需移動(dòng)元素。此時(shí)平均時(shí)間復(fù)雜度為O(n)2.設(shè)有設(shè)有1000個(gè)無(wú)序的元素，希望

11、用最快的速度挑選出其中前個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好采用哪種排序方法？個(gè)最大的元素，最好采用哪種排序方法？答：用堆排序或錦標(biāo)賽排序最合適，因?yàn)椴槐氐热吭嘏磐昃湍艿玫剿杞Y(jié)果，時(shí)間效率為答：用堆排序或錦標(biāo)賽排序最合適，因?yàn)椴槐氐热吭嘏磐昃湍艿玫剿杞Y(jié)果，時(shí)間效率為O(O(O(nnlogloglog22nn))；若用冒泡排序則需時(shí)若用冒泡排序則需時(shí)n!(n10)!3.用某種排序方法對(duì)線性表（用某種

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

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

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

15、，即在個(gè)元素，即在4個(gè)子表中比較和交換了個(gè)子表中比較和交換了n－7個(gè)元素；個(gè)元素；n－（－（231）第4輪能再確定輪能再確定8個(gè)元素，即在個(gè)元素，即在8個(gè)子表中比較和交換了個(gè)子表中比較和交換了n－15個(gè)元素；個(gè)元素；n－（－（241）…………第6輪能再確定輪能再確定32個(gè)元素，即在個(gè)元素，即在32個(gè)子表中比較和交換了個(gè)子表中比較和交換了n－65個(gè)元素；個(gè)元素；n－（－（261）第7輪則能全部確定，輪則能全部確定，（因?yàn)椋ㄒ驗(yàn)?7=128