排序作業(yè) 選擇題（每題2分，共22分）。 1．若表R在排序前已按鍵值遞增順序排列，則（?? ）算法的比較次數(shù)最少。 A．直接插入排序??????????? B．快速排序?????C．歸并排序??????????????? D．選擇排序 2．對(duì)各種內(nèi)部排序方法來說，（?? ）。 A．快速排序時(shí)間性能最佳????????????????????????? ?? B．歸并排序是穩(wěn)定的排序方法 C．快速排序是一種選擇排序????????????????????? ??? D．堆排序所用的輔助空間比較大 3.? 排序算法的穩(wěn)定性是指（?? ）。 A．經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的相對(duì)位置不變。 B．經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的絕對(duì)位置不變。 C．排序算法的性能與被排序元素的數(shù)量關(guān)系不大 D．排序算法的性能與被排序元素的數(shù)量關(guān)系密切 4. 如下序列中，（?? ）序列是大頂堆。 A.? {4,5,3,2,1}?????????????? B.? {5,3,4,1,2}??????? C.? {1,2,3,4,5}?????????????? D.? {1,2,3,5,4} 5. 若將{3,2,5,4,1}排為升序，則實(shí)施快速排序一趟后的結(jié)果是（?? ）（其中，樞軸記錄取首記錄）。 A.? {1,2,3,4,5}????????????????? B.? {1,2,4,5,3}??????? C.? {1,3,5,4,2}????????????????? D.? {2,5,4,1,3} . 若將{1,2,3,4,5,6,7,9,8}排為升序，則（?? ）排序方法的“比較記錄”次數(shù)最少。 A.? 快速排序?????????????????? B.? 簡(jiǎn)單選擇排序???? C.? 直接插入排序?????????????? D.? 冒泡排序 7. 若將{5,4,3,2,1}排為升序，則（?? ）排序方法的“移動(dòng)記錄”次數(shù)最多。 A.? 快速排序??????????????????????????????? B.? 冒泡排序 C.? 直接插入排序?????????????????????? D.? 簡(jiǎn)單選擇排序 8. 用簡(jiǎn)單選擇排序?qū)㈨樞虮韠2,3,1 ,3′,2′}排為升序，實(shí)施排序1趟后結(jié)果是{1 ,3,2 ,3′,2′}，則排序3趟后的結(jié)果是（?? ）。 A.? {1 ,2,3 ,3′,2′}?????????????????????? B.? {1 ,2 ,2′,3 ,3′} C.? {1 ,2′,2 ,3 ,3′}????????????????????? D.? {1 ,2 ,2′,3′,3 } 9．下列排序算法中，（??? ）排序在某趟結(jié)束后不一定選出一個(gè)元素放到其最終的位置上。 A．選擇???????????? B．冒泡?????????? C．歸并?????????? D．堆 10．下列排序算法中，穩(wěn)定的排序算法是（? ）。 A．堆排序??????????????? B．直接插入排序?? C．快速排序????????????? D．希爾排序 11．堆排序的時(shí)間復(fù)雜度是（??? ）。 A．O(n*n)???????????????? B．O(n*log n)?????? C．O(n)?????????????????? D．O(log n) 填空題（每空4分，共4分）。 對(duì)n個(gè)元素進(jìn)行歸并排序，空間復(fù)雜度為???????? 。 綜合題（共24分）。 1. （共12分）有一組待排序的關(guān)鍵字如下： (54，38，96，23，15，72，60，45，83) 分別寫出希爾排序(d=5)、快速排序、堆排序、歸并排序第一趟升序排序后的結(jié)果（其中堆排序的第一趟指序列完成初始建堆、將堆頂元素置為最末位置后其余元素調(diào)整為堆的結(jié)果）（每個(gè)3分）。 希爾排序：?? 快速排序： 堆排序： 歸并排序：? 2. （共12分）已知數(shù)據(jù)序列為（12，5，9，20，6，31，24），對(duì)該項(xiàng)數(shù)據(jù)序列進(jìn)行排序，分別寫出直接插入排序、簡(jiǎn)單選擇排序、快速排序、堆排序、二路歸并排序及基數(shù)排序第一趟升序排序結(jié)果（其中堆排序的第一趟指序列完成初始建堆、將堆頂元素置為最末位置后其余元素調(diào)整為堆的結(jié)果）（每個(gè)2分）。 直接插入排序： 簡(jiǎn)單選擇排序： 快速排序： 堆排序： 二路歸并排序： 基數(shù)排序：