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

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

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

3、. 歸并排序 b. 希爾排序 c. 快速排序 d. 基數(shù)排序 9、在對(duì)n個(gè)元素的序列進(jìn)行排序時(shí)，堆排序所需要的附加存儲(chǔ)空間是（ ）。 a. o(log 2 n) b. o(1) c. o(n) d. o(nlog 2 n) 10、用某種排序方法對(duì)線性表（ 25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，元素序列的變化狀況如下： 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、排序時(shí)掃描待排序記錄序列，順次比較相鄰的兩個(gè)元素的大小，逆序時(shí)就交換位置的方法，稱為_。 5、從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為_。 6、對(duì)于直接插入排序，希爾排序，冒泡排序，快速

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

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