第章排序練習(xí)題及答案第章排序練習(xí)題及答案第章排序練習(xí)題及答案V:1.0精細(xì)整理，僅供參考第章排序練習(xí)題及答案日期：20xx年X月第十章排序一、選擇題1．某內(nèi)排序方法的穩(wěn)定性是指(

D

)。A．該排序算法不允許有相同的關(guān)鍵字記錄

B．該排序算法允許有相同的關(guān)鍵字記錄C．平均時(shí)間為0（nlogn）的排序方法

D．以上都不對(duì)2．下列排序算法中，其中（

D

）是穩(wěn)定的。A.堆排序，冒泡排序

B.

快速排序，堆排序

C.直接選擇排序，歸并排序

D.

歸并排序，冒泡排序3．穩(wěn)定的排序方法是（

B

）A．直接插入排序和快速排序

B．折半插入排序和起泡排序C．簡(jiǎn)單選擇排序和四路歸并排序

D．樹(shù)形選擇排序和shell排序4．下列排序方法中，哪一個(gè)是穩(wěn)定的排序方法（

B）A．直接選擇排序

B．二分法插入排序

C．希爾排序

D．快速排序5．若要求盡可能快地對(duì)序列進(jìn)行穩(wěn)定的排序，則應(yīng)選（B）。A．快速排序

B．歸并排序

C．冒泡排序6．如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。（

CE

）就是不穩(wěn)定的排序方法。A．起泡排序

B．歸并排序

C．Shell排序

D．直接插入排序

E．簡(jiǎn)單選擇排序7．若需在O(nlog2n)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（

C

）。

A.快速排序

B.

堆排序

C.

歸并排序

D.

直接插入排序8．下面的排序算法中，不穩(wěn)定的是（

CDF

）A.起泡排序

B.折半插入排序

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

D.希爾排序

E.基數(shù)排序

F.堆排序。9．下列內(nèi)部排序算法中：A．快速排序

B.直接插入排序

C.二路歸并排序

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

E.起泡排序

F.

堆排序（1）其比較次數(shù)與序列初態(tài)無(wú)關(guān)的算法是（CDF

）

（2）不穩(wěn)定的排序算法是（ADF

）（3）在初始序列已基本有序（除去n個(gè)元素中的某k個(gè)元素后即呈有序，k<<n）的情況下，排序效率最高的算法是（

B

）（4）排序的平均時(shí)間復(fù)雜度為O(n?logn)的算法是（

ACF

）為O(n?n)的算法是（BDE

）。

10．?dāng)?shù)據(jù)序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的(

C

)的兩趟排序后的結(jié)果。A．選擇排序

B.冒泡排序

C.插入排序

D.堆排序11．?dāng)?shù)據(jù)序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的(

A

)的兩趟排序后的結(jié)果。A.快速排序

B.

冒泡排序

C.

選擇排序

D.

插入排序12．對(duì)一組數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過(guò)程中的變化為（1）8447251521

（2）1547258421

（3）1521258447

（4）1521254784則采用的排序是

(

A

)。A.選擇

B.

冒泡

C.

快速

D.

插入13．對(duì)序列{15，9，7，8，20，-1，4}進(jìn)行排序，進(jìn)行一趟后數(shù)據(jù)的排列變?yōu)閧4，9，-1，8，20，7，15}；則采用的是（

C

）排序。A.選擇

B.

快速

C.

希爾

D.

冒泡14．若上題的數(shù)據(jù)經(jīng)一趟排序后的排列為{9，15，7，8，20，-1，4}，則采用的是（

C

）排序。A．選擇

B.

堆

C.

直接插入

D.

冒泡15．下列排序算法中(

B

)不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。A.快速排序

B.shell排序

C.堆排序

D.冒泡排序

16．下列排序算法中(

C)排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。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，73]18．有一組數(shù)據(jù)（15，9，7，8，20，-1，7，4）用快速排序的劃分方法進(jìn)行一趟劃分后數(shù)據(jù)的排序?yàn)?

A)（按遞增序）。A．下面的B，C，D都不對(duì)。

B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7

D.9，4，7，8，7，-1，15，2019．一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(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.

堆排序

C.

選擇排序

D.

歸并排序

21．下列排序算法中，在待排序數(shù)據(jù)已有序時(shí)，花費(fèi)時(shí)間反而最多的是(

C

)排序。

A．冒泡

B.希爾

C.快速

D.堆22.下列排序算法中，在每一趟都能選出一個(gè)元素放到其最終位置上，并且其時(shí)間性能受數(shù)據(jù)初始特性影響的是：（

B

）。A.

直接插入排序

B.

快速排序

C.

直接選擇排序

D.

堆排序23.對(duì)初始狀態(tài)為遞增序列的表按遞增順序排序，最省時(shí)間的是（C

）算法，最費(fèi)時(shí)間的是（B

）算法。

A.

堆排序

B.

快速排序

C.

插入排序

D.

歸并排序

31.就平均性能而言，目前最好的內(nèi)排序方法是(

D)排序法。A.冒泡

B.

希爾插入

C.

交換

D.快速24．如果只想得到1000個(gè)元素組成的序列中第5個(gè)最小元素之前的部分排序的序列，用（

D）方法最快。A．起泡排序

B．快速排列

C．Shell排序

D．堆排序

E．簡(jiǎn)單選擇排序二、判斷題：1．當(dāng)待排序的元素很大時(shí)，為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜度的主要因素。（

√

）2．內(nèi)排序要求數(shù)據(jù)一定要以順序方式存儲(chǔ)。

（

╳

）3．排序算法中的比較次數(shù)與初始元素序列的排列無(wú)關(guān)。（

╳）4．排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。（

╳

）5．在執(zhí)行某個(gè)排序算法過(guò)程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動(dòng)，則該算法是不穩(wěn)定的。（

╳）6．直接選擇排序算法在最好情況下的時(shí)間復(fù)雜度為O（N）。（

╳）7．兩分法插入排序所需比較次數(shù)與待排序記錄的初始排列狀態(tài)相關(guān)。（

╳）8．在初始數(shù)據(jù)表已經(jīng)有序時(shí)，快速排序算法的時(shí)間復(fù)雜度為O(nlog2n)。（

╳

）9．在待排數(shù)據(jù)基本有序的情況下，快速排序效果最好。（

╳

）10．當(dāng)待排序記錄已經(jīng)從小到大排序或者已經(jīng)從大到小排序時(shí)，快速排序的執(zhí)行時(shí)間最省。（

）11．快速排序的速度在所有排序方法中為最快,而且所需附加空間也最少。（

╳

）12．堆肯定是一棵平衡二叉樹(shù)。（

╳

）13．堆是滿二叉樹(shù)。（

╳

）14．（101，88，46，70，34，39，45，58，66，10）是堆。（√）15．在用堆排序算法排序時(shí)，如果要進(jìn)行增序排序，則需要采用“大根堆”。（√

）16．堆排序是穩(wěn)定的排序方法。（

╳

）17．歸并排序輔助存儲(chǔ)為O（1）。（

╳

）18．在分配排序時(shí)，最高位優(yōu)先分配法比最低位優(yōu)先分配法簡(jiǎn)單。（

╳

）19．冒泡排序和快速排序都是基于交換兩個(gè)逆序元素的排序方法,冒泡排序算法的最壞時(shí)間復(fù)雜性是O(n*n),而快速排序算法的最壞時(shí)間復(fù)雜性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。

（

╳

）20．交換排序法是對(duì)序列中的元素進(jìn)行一系列比較，當(dāng)被比較的兩個(gè)元素逆序時(shí)，進(jìn)行交換，冒泡排序和快速排序是基于這類方法的兩種排序方法，冒泡排序算法的最壞時(shí)間復(fù)雜性是O（n*n），而快速排序算法的最壞時(shí)間復(fù)雜性是O（