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