第10章 排序

1、1第10章排序排序自測卷自測卷一、填空題（每空一、填空題（每空1分，共分，共24分）分）1.大多數(shù)排序算法都有兩個基本的操作：大多數(shù)排序算法都有兩個基本的操作：和。2.在對一組記錄（在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第）進行直接插入排序時，當把第7個記錄個記錄60插入到有序表時，為尋找插入位置至少需比較入到有序表時，為尋找插入位置至少需比較次。次。3.在插入和選擇排序中，若初始數(shù)

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

3、序，在。若對其進行快速排序，在最壞的情況下所需要的時間是最壞的情況下所需要的時間是。6.對于對于n個記錄的集合進行歸并排序，所需要的平均時間是個記錄的集合進行歸并排序，所需要的平均時間是，所需要的附加空間是，所需要的附加空間是。7對于對于n個記錄的表進行個記錄的表進行2路歸并排序，整個歸并排序需進行路歸并排序，整個歸并排序需進行趟（遍）趟（遍）。8.設(shè)要將序列（設(shè)要將序列（QHCYPAMSRDFX）中的關(guān)鍵碼按字母序的升序重新排列，則：

4、）中的關(guān)鍵碼按字母序的升序重新排列，則：冒泡排序一趟掃描的結(jié)果是冒泡排序一趟掃描的結(jié)果是；初始步長為初始步長為4的希爾（的希爾（shell）排序一趟的結(jié)果是）排序一趟的結(jié)果是；二路歸并排序一趟掃描的結(jié)果是二路歸并排序一趟掃描的結(jié)果是；快速排序一趟掃描的結(jié)果是快速排序一趟掃描的結(jié)果是；堆排序初始建堆的結(jié)果是堆排序初始建堆的結(jié)果是。9.在堆排序、快速排序和歸并排序中，在堆排序、快速排序和歸并排序中，若只從存儲空間考慮，則應(yīng)首先選取若只從存儲

5、空間考慮，則應(yīng)首先選取方法，其次選取方法，其次選取方法，最后選取方法，最后選取方法；方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取選取方法；方法；若只從平均情況下最快考慮，則應(yīng)選取若只從平均情況下最快考慮，則應(yīng)選取方法；方法；若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取方法。方法。二、單項選擇題（每小題二、單項選擇題（每小題1分，共分，共18分）分）（）1將

6、將5個不同的數(shù)據(jù)進行排序，至多需要比較個不同的數(shù)據(jù)進行排序，至多需要比較次。次。Ａ.8Ｂ.9Ｃ.10Ｄ.25（）2排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為較，將其放入已排序序列的正確位置上的方法，稱為Ａ.希爾排序希爾排序Ｂ.冒泡排序冒泡排序Ｃ.插入排序插入排序Ｄ.選擇排序選擇排

7、序（）3從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方法，稱為從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方法，稱為Ａ.希爾排序希爾排序Ｂ.歸并排序歸并排序Ｃ.插入排序插入排序Ｄ.選擇排序選擇排序（）4對ｎ個不同的排序碼進行冒泡排序，在下列哪種情況下比較的次數(shù)最多。對ｎ個不同的排序碼進行冒泡排序，在下列哪種情況下比較的次數(shù)最多。Ａ.從小到大排列好的從小到大排列好的Ｂ.從大到小排列好的從

8、大到小排列好的Ｃ.元素?zé)o序元素?zé)o序Ｄ.元素基本有序元素基本有序（）5對ｎ個不同的排序碼進行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為對ｎ個不同的排序碼進行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為2Ａ.n1Ｂ.nＣ.n1Ｄ.n(n1)2（）6快速排序在下列哪種情況下最易發(fā)揮其長處?？焖倥判蛟谙铝心姆N情況下最易發(fā)揮其長處。Ａ.被排序的數(shù)據(jù)中含有多個相同排序碼被排序的數(shù)據(jù)中含有多個相同排序碼Ｂ.被排序的數(shù)據(jù)已基本有序被排序的數(shù)據(jù)已基本有序Ｃ.被

9、排序的數(shù)據(jù)完全無序被排序的數(shù)據(jù)完全無序Ｄ.被排序的數(shù)據(jù)中的最大值和最小值相差懸殊被排序的數(shù)據(jù)中的最大值和最小值相差懸殊（）7對有對有n個記錄的表作快速排序，在最壞情況下，算法的時間復(fù)雜度是個記錄的表作快速排序，在最壞情況下，算法的時間復(fù)雜度是AO(n)BO(n2)CO(nlog2n)DO(n3)（）8若一組記錄的排序碼為（若一組記錄的排序碼為（467956384084），則利用快速排序的方法，以第一個記錄為基，則利用快速排序的方法，以第

10、一個記錄為基準得到的一次劃分結(jié)果為準得到的一次劃分結(jié)果為Ａ.384046567984Ｂ.403846795684Ｃ.4038，46567984Ｄ.403846845679（）9下列關(guān)鍵字序列中，下列關(guān)鍵字序列中，是堆。是堆。Ａ.167231239453Ｂ.942331721653Ｃ.16532394，3172Ｄ.162353319472（）10堆是一種堆是一種排序。排序。Ａ.插入插入Ｂ.選擇選擇Ｃ.交換交換Ｄ.歸并歸并（）11堆的形狀是

11、一棵堆的形狀是一棵Ａ.二叉排序樹二叉排序樹Ｂ.滿二叉樹滿二叉樹Ｃ.完全二叉樹完全二叉樹Ｄ.平衡二叉樹平衡二叉樹（）12若一組記錄的排序碼為（若一組記錄的排序碼為（467956384084），則利用堆排序的方法建立的初始堆為，則利用堆排序的方法建立的初始堆為Ａ.794656384084Ｂ.847956384046Ｃ.847956464038Ｄ.845679404638（）17下述幾種排序方法中，要求內(nèi)存最大的是下述幾種排序方法中，要求內(nèi)存