第九章 排序

1、第九章第九章排序排序一、選擇題一、選擇題1當(dāng)待排序列基本有序的情況下，最佳的排序方法是()。A.插入排序B.選擇排序B.歸并排序D.快速排序2設(shè)有1000個(gè)無序元素，希望選出10個(gè)最小元素，效率最高的排序方法是（）。A.快速排序B基數(shù)排序D.堆排序D.希爾排序3若待排序按關(guān)鍵字基本有序，不能選擇哪種排序方法（）。A.冒泡排序B.直接選擇排序C.直接插入排序D.快速排序4在下列排序方法，比較次數(shù)與待排序列初始狀態(tài)無關(guān)的是（）。A.選擇排序

2、B.插入排序C.希爾排序D.冒泡排序5下列排序方法中，不穩(wěn)定的排序方法是（）。A.歸并排序B.直接插入排序C.冒泡排序D.直接選擇排序6下列排序方法中，空間復(fù)雜度為Ｏ（１）的算法的是（）。A.歸并排序B.堆排序C.快速排序C.基數(shù)排序7下列排序方法中不屬于就地排序算法的是（）。A.希爾排序B.歸并排序C.冒泡排序D.堆排序8初始關(guān)鍵字序列為（46，56，18，73，44，30，57，34），經(jīng)過一趟排序后關(guān)鍵字序列為（34，30，18，

3、44，46，73，57，56），所采用的排序方法是（）。A.歸并排序B.堆排序C.快速排序C.基數(shù)排序5在堆排序和快速排序中，若初始關(guān)鍵字序列基本有序，應(yīng)選用，若初始序列無序選用。6初始關(guān)鍵字序列為（12，33，54，27，34，55，2，12，37，68，8）進(jìn)行一趟希爾排序（設(shè)增量為3）則結(jié)果為：。7通常在排序算法中的兩個(gè)基本操作是和。8對(duì)n個(gè)元素進(jìn)行冒泡排序，最多的比較次數(shù)是；最少的比較次數(shù)是。9初始關(guān)鍵字序列為（12，33，54

4、，27，34，55，2，12，37，68，8），進(jìn)行直接插入排序，當(dāng)把34插入有序序列需比較的次數(shù)是。10若待排序列元素?cái)?shù)n較大時(shí)一般選擇快速排序、堆排序或歸并排序。若要求時(shí)間特性好應(yīng)選擇，要求空間特性好應(yīng)選擇；若要求算法是穩(wěn)定的有選擇。三、簡(jiǎn)答題三、簡(jiǎn)答題1.簡(jiǎn)單選擇排序算法是否穩(wěn)定，試舉例說明。2.初始關(guān)鍵字序列為23，12，43，8，45，50，35，調(diào)整其為堆結(jié)構(gòu)。3.初始關(guān)鍵字序列為21，34，14，56，25，73，34，6

5、5，79，86，3，7，18寫出希爾排序過程（增量序列為5，3，1）。4.初始關(guān)鍵字序列為23，12，43，8，45，50，35，寫出歸并排序過程。5.有n個(gè)不同的英文單詞，長(zhǎng)度相等，均為m若n＞50m5，則采用什么排序方法最好，為什么？6對(duì)關(guān)鍵字序列(72，87，61，23，94，16，05，58)進(jìn)行堆排序，使之按關(guān)鍵字遞減次序排列。請(qǐng)寫出排序過程中得到的初始堆和前三趟的序列狀態(tài)。四、程序閱讀題四、程序閱讀題1.下列程序是插入排序算