排序練習(xí)習(xí)題及答案

1、第十章 排序一、選擇題1某內(nèi)排序方法的穩(wěn)定性是指(D )。A該排序算法不允許有相同的關(guān)鍵字記錄 B該排序算法允許有相同的關(guān)鍵字記錄C平均時間為0（n log n）的排序方法 D以上都不對2下列排序算法中，其中（D）是穩(wěn)定的。A. 堆排序，冒泡排序 B.快速排序，堆排序C. 直接選擇排序，歸并排序 D.歸并排序，冒泡排序3穩(wěn)定的排序方法是（B）A直接插入排序和快速排序 B折半插入排序和起泡排序C簡單選擇排序和四路歸并排序 D樹形選擇排序和shell排序4下列排序方法中，哪一個是穩(wěn)定的排序方法（B）A直接選擇排序 B二分法插入排序 C希爾排序 D快速排序5若要求盡可能快地對序列進(jìn)行穩(wěn)定的排序，則應(yīng)

2、選（B）。A快速排序B歸并排序C冒泡排序6如果待排序序列中兩個數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。（CE）就是不穩(wěn)定的排序方法。A起泡排序 B歸并排序 CShell排序 D直接插入排序 E簡單選擇排序7若需在O(nlog2n)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（C）。A. 快速排序 B.堆排序 C.歸并排序 D.直接插入排序8下面的排序算法中，不穩(wěn)定的是（CDF）A.起泡排序 B.折半插入排序 C.簡單選擇排序 D.希爾排序 E.基數(shù)排序 F.堆排序。9下列內(nèi)部排序算法中：A快速排序 B.直接插入排序C. 二路歸并排

3、序D. 簡單選擇排序E. 起泡排序 F.堆排序（1） 其比較次數(shù)與序列初態(tài)無關(guān)的算法是（CDF）（2）不穩(wěn)定的排序算法是（ADF）（3）在初始序列已基本有序（除去n個元素中的某k個元素后即呈有序，kn）的情況下，排序效率最高的算法是（B）（4）排序的平均時間復(fù)雜度為O(nlogn)的算法是（ACF）為O(nn)的算法是（BDE）。10數(shù)據(jù)序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的(C )的兩趟排序后的結(jié)果。A選擇排序 B.冒泡排序 C.插入排序 D.堆排序11數(shù)據(jù)序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的(A )的兩趟排序后的結(jié)果。A. 快速排序

4、 B.冒泡排序 C.選擇排序 D.插入排序12對一組數(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 )。A. 選擇 B.冒泡 C.快速 D.插入13對序列15，9，7，8，20，-1，4進(jìn)行排序，進(jìn)行一趟后數(shù)據(jù)的排列變?yōu)?，9，-1，8，20，7，15；則采用的是（C）排序。A. 選擇 B.快速 C.希爾 D.冒泡14若上題的數(shù)據(jù)經(jīng)一趟排序后的排列為9，15，7，8，20，-1，4，則采用的是（C）排序

5、。A選擇 B.堆 C.直接插入 D.冒泡15下列排序算法中(B )不能保證每趟排序至少能將一個元素放到其最終的位置上。A.快速排序B. shell排序C. 堆排序 D.冒泡排序16下列排序算法中(C )排序在一趟結(jié)束后不一定能選出一個元素放在其最終位置上。A. 選擇 B.冒泡 C.歸并 D.堆17下列序列中，（C）是執(zhí)行第一趟快速排序后所得的序列。 A. 68，11，18，69 23，93，73 B. 68，11，69，23 18，93，73 C. 93，73 68，11，69，23，18 D. 68，11，69，23，18 93，7318有一組數(shù)據(jù)（15，9，7，8，20，-1，7，4） 用

6、快速排序的劃分方法進(jìn)行一趟劃分后數(shù)據(jù)的排序?yàn)?(A )（按遞增序）。A下面的B，C，D都不對。 B9，7，8，4，-1，7，15，20C20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，2019一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為（C）。A(38,40,46,56,79,84) B. (40,38,46,79,56,84)C(40,38,46,56,79,84) D. (40,38,46,84,56,79)20. 在下面的排序方法中，輔助空間為O（n）的是(D )。 A希爾排序 B.堆排

7、序 C.選擇排序 D.歸并排序21下列排序算法中，在待排序數(shù)據(jù)已有序時，花費(fèi)時間反而最多的是(C )排序。 A 冒泡B. 希爾C. 快速D. 堆22.下列排序算法中，在每一趟都能選出一個元素放到其最終位置上，并且其時間性能受數(shù)據(jù)初始特性影響的是：（B）。A.直接插入排序 B.快速排序 C.直接選擇排序 D.堆排序23. 對初始狀態(tài)為遞增序列的表按遞增順序排序，最省時間的是（C）算法，最費(fèi)時間的是（B）算法。 A.堆排序 B.快速排序 C.插入排序 D.歸并排序31. 就平均性能而言，目前最好的內(nèi)排序方法是(D )排序法。A. 冒泡 B.希爾插入 C.交換D. 快速24如果只想得到1000個元素

8、組成的序列中第5個最小元素之前的部分排序的序列，用（D）方法最快。A起泡排序 B快速排列CShell排序D堆排序E簡單選擇排序二、判斷題：1當(dāng)待排序的元素很大時，為了交換元素的位置，移動元素要占用較多的時間，這是影響時間復(fù)雜度的主要因素。（）2內(nèi)排序要求數(shù)據(jù)一定要以順序方式存儲。（）3排序算法中的比較次數(shù)與初始元素序列的排列無關(guān)。（）4排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。（）5在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的。（）6直接選擇排序算法在最好情況下的時間復(fù)雜度為O（N）。（ ）7兩分法插入排序所需比較次數(shù)與待排序記

9、錄的初始排列狀態(tài)相關(guān)。（）8在初始數(shù)據(jù)表已經(jīng)有序時，快速排序算法的時間復(fù)雜度為O(nlog2n )。（）9在待排數(shù)據(jù)基本有序的情況下，快速排序效果最好。（）10當(dāng)待排序記錄已經(jīng)從小到大排序或者已經(jīng)從大到小排序時，快速排序的執(zhí)行時間最省。（）11快速排序的速度在所有排序方法中為最快,而且所需附加空間也最少。（）12堆肯定是一棵平衡二叉樹。（）13堆是滿二叉樹。（）14（101，88，46，70，34，39，45，58，66，10）是堆。（ ）15在用堆排序算法排序時，如果要進(jìn)行增序排序，則需要采用“大根堆”。（）16堆排序是穩(wěn)定的排序方法。（）17歸并排序輔助存儲為O（1）。（）18在分配排序時，最高位優(yōu)先分配法比最低位優(yōu)先分配法簡單。（）19 冒泡排序和快速排序都是基于交換兩個逆序元素的排序方法,冒泡排序算法的最壞時間復(fù)雜性是O(n*n),而快速排序算法的最壞時間復(fù)雜性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。（）20交換排序法是對序列中的元素進(jìn)行一系列比較，當(dāng)被比較的兩個元素逆序時，進(jìn)行交換，冒泡排序和快速排序是基于這類方法的兩種排序方法，冒泡排序算法的最壞時間復(fù)雜性是O（n*n） ，而快速排序算法的最壞時間復(fù)雜性是O（nlog2n）；所以快速排