課程課件作業(yè)空chapter10

1復(fù)習(xí)題1.

在下列排序方法中，時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(nlog2n)的是_____。

A.堆排序 B.起泡排序

C.簡(jiǎn)單選擇排序 D.快速排序2.在下列排序方法中，某一趟排序結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是_____。

A.堆排序 B.起泡排序

C.直接插入排序 D.快速排序2復(fù)習(xí)題3.

下列排序方法中，在待排序的數(shù)據(jù)已經(jīng)為有序時(shí)，花費(fèi)時(shí)間反而最多的是_____。

A.快速排序 B.希爾(Shell)排序

C.起泡排序 D.堆排序4.若表R在排序前已按關(guān)鍵字正序排列，則_____方法的比較次數(shù)最少。

A.直接插入排序 B.快速排序

C.歸并排序 D.簡(jiǎn)單選擇排序3復(fù)習(xí)題5.

在下列排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是_____。

A.直接插入排序 B.希爾(Shell)排序

C.起泡排序 D.簡(jiǎn)單選擇排序6.快速排序方法在_____情況下最不利于發(fā)揮其長(zhǎng)處。

A.要排序的數(shù)據(jù)量很大

B.要排序的數(shù)據(jù)中含有多個(gè)相同值

C.要排序的數(shù)據(jù)已基本有序

D.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)4復(fù)習(xí)題7.

內(nèi)排序方法的穩(wěn)定性是指_____。

A.該排序方法不允許有相同的關(guān)鍵字記錄 B.該排序方法允許有相同的關(guān)鍵字記錄

C.平均時(shí)間為O(nlog2n)的排序方法 D.以上均不對(duì)8.以下各排序方法中，_____是穩(wěn)定的排序方法。

A.直接插入和快速排序

B.快速排序和堆排序

C.簡(jiǎn)單選擇和歸并排序

D.歸并排序和起泡排序5復(fù)習(xí)題9.

以下各排序方法中，輔助空間為O(n)的是_____。

A.堆排序 B.歸并排序

C.希爾排序 D.快速排序10.若一組記錄的排序碼為{46,79,56,38,40,84}，則利用堆排序的方法建立的初始堆為_____。

A.79,46,56,38,40,80 B.84,79,56,38,40,46C.84,79,56,46,40,38 D.84,56,79,40,46,386復(fù)習(xí)題11.

若一組記錄的關(guān)鍵字為{46,79,56,38,40,84},則利用快速排序的方法，以第一個(gè)記錄為樞軸得到的一次劃分結(jié)果為

_____。

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，797復(fù)習(xí)題12.

一組記錄的關(guān)鍵字為{25,48,16,35,79,82,23,40,36,72},其中，含有5個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列再進(jìn)行一趟歸并后的結(jié)果為

_____。

A.16，25，35，48，23，40，79，82，36，72B.16，25，35，48，79，82，23，36，40，72 C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，828復(fù)習(xí)題13.

以下排序方法中，最好情況下時(shí)間復(fù)雜度為O(n)的依次是

、

。

A.直接插入排序

B.簡(jiǎn)單選擇排序

C.起泡排序

D.快速排序9復(fù)習(xí)題14.判斷以下敘述的正確性。

1)對(duì)一個(gè)堆，按二叉樹層次進(jìn)行遍歷應(yīng)該得到一個(gè)有序序列。

2)任何情況下，歸并排序都比直接插入排序快。

3)折半插入排序所需關(guān)鍵字比較次數(shù)與待排序記錄的初始排列狀態(tài)有關(guān)。

4)對(duì)n個(gè)元素進(jìn)行直接選擇排序，關(guān)鍵字的比較次數(shù)總是n(n-1)/2次。()()()()如果是2-路插入排序呢？10復(fù)習(xí)題

5)只有在線性表的初始狀態(tài)為反序的情況下，直接插入排序過程中，元素的移動(dòng)次數(shù)才會(huì)達(dá)到最大值。

6)