數(shù)據(jù)結(jié)構第10章,內(nèi)部排序習題

1、本文格式為word版，下載可任意編輯數(shù)據(jù)結(jié)構第10章,內(nèi)部排序習題 第十章 內(nèi)部排序 一、選擇題 1、若需要在o(nlog 2 n)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（ ）。 a. 快速排序 b. 堆排序 c. 歸并排序 d. 直接插入排序 2、下列排序方法中（ ）方法是不穩(wěn)定的。 a. 冒泡排序 b. 選擇排序 c. 堆排序 d. 直接插入排序 3、一個序列中有10000個元素，若只想得到其中前10個最小元素，則最好采納（ ）方法。 a. 快速排序 b. 堆排序 c. 插入排序 d. 歸并排序 4、設有1024個無序的元素，盼望用最快的速度選擇出其中前5個最大

2、的元素，最好選用（ ）。 a. 冒泡排序 b. 選擇排序 c. 快速排序 d. 堆排序 5、快速排序方法在（ ）狀況下最不利于發(fā)揮其特長。 a. 要排序的數(shù)據(jù)量太大 b. 要排序的數(shù)據(jù)中有多個相同值 c. 要排序的數(shù)據(jù)已基本有序 d. 要排序的數(shù)據(jù)個數(shù)為奇數(shù) 6、下列排序方法中，平均時間性能為o(nlogn)且空間性能最好的是（ ）。 a. 快速排序 b. 堆排序 c. 歸并排序 d. 基數(shù)排序 7、在任何狀況下，時間簡單度均為o(nlogn)的不穩(wěn)定的排序方法是（ ）。 a.直接插入 b. 快速排序 c. 堆排序 d. 歸并排序 8、假如將全部中國人根據(jù)生日來排序，則使用（ ）算法最快。 a

3、. 歸并排序 b. 希爾排序 c. 快速排序 d. 基數(shù)排序 9、在對n個元素的序列進行排序時，堆排序所需要的附加存儲空間是（ ）。 a. o(log 2 n) b. o(1) c. o(n) d. o(nlog 2 n) 10、用某種排序方法對線性表（ 25，84，21，47，15，27，68，35，20）進行排序時，元素序列的變化狀況如下： 25，84，21，47，15，27，68，35，20 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采納的排序方法是（ ）。 a.

4、選擇排序 b. 希爾排序 c. 歸并排序 d. 快速排序 二、填空題 1、在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用_，若初始數(shù)據(jù)基本反序，則選用_。 2、在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，排序是不穩(wěn)定的有_。 3、一組待排序序列為（46,79,56,38,40,84），則利用堆排序的方法建立的初始堆為_。 4、排序時掃描待排序記錄序列，順次比較相鄰的兩個元素的大小，逆序時就交換位置的方法，稱為_。 5、從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為_。 6、對于直接插入排序，希爾排序，冒泡排序，快速

5、排序，直接選擇排序，堆排序和歸并排序等排序方 法，則平均時間簡單度低于 o（n2）的排序方法是_。 7、對于直接插入排序，希爾排序，冒泡排序，快速排序，直接選擇排序，堆排序和歸并排序等排序方法，則所需幫助空間最多的排序方法是_。 8、若一組記錄的排序碼值序列為50，80，30，40，70，60利用快速排序方法，以第一個記錄為基準，得到一趟快速排序的結(jié)果為_。 9、從未排序序列中選擇最小(最大)元素，并將其依次放到已排序序列的一端，稱為_排序。 10、對一組整數(shù)60，40，90，20，10，70，50，80進行直接插入排序時，當把第 7 個整數(shù) 50 插入到有序表中時，為查找插人位置需比較_次。

6、 三、推斷題 1、直接選擇排序是一種穩(wěn)定的排序方法。 2、快速排序在全部排序方法中最快，而且所需附加空間也最少。 3、直接插入排序是不穩(wěn)定的排序方法。 4、選擇排序是一種不穩(wěn)定的排序方法。 5、希爾排序的增量序列必需是遞增的。 四、綜合題 1、寫出用直接插入排序?qū)㈥P鍵字序列54,23,89,48,64,50,25,90,34排序過程的每一趟結(jié)果。 2、設待排序序列為10,18,4,3,6,12,1,9,15,8請寫出希爾排序每一趟的結(jié)果。增量序列為 5，3，2，1。 3、已知關鍵字序列418，347，289，110，505，333，984，693，177，按遞增排序，求初始堆（畫出初始堆的狀態(tài)）。 4、有一關鍵字序列（265，301，751，129，937，863，742，694，076，438），寫出希爾排序的每趟排序結(jié)果。（取增量為 5，