數(shù)據(jù)結(jié)構(gòu)考研試題精選及答案第10章排序

1、第10章排序、選擇題1.某內(nèi)排序方法的穩(wěn)定性是指（）?！灸暇├砉ご髮W(xué)1997、10（2分）】A.該排序算法不允許有相同的關(guān)鍵字記錄B.該排序算法允許有相同的關(guān)鍵字記錄C.平均時(shí)間為0（nlogn）的排序方法D.以上都不對(duì)2.下面給出的四種排序法中（）10（2分）】排序法是不穩(wěn)定性排序法?！颈本┖娇蘸教齑髮W(xué)1999A.插入B.冒泡C.路歸并D.堆積3.下列排序算法中，其中（A.堆排序，冒泡排序）是穩(wěn)定的。【福州大學(xué)1998、3（2分）B.快速排序，堆排序C.直接選擇排序，歸并排序4.穩(wěn)定的排序方法是（）A.直接插入排序和快速排序D.歸并排序，冒泡排序【北方交通大學(xué)2000二、3（2分）】B.折半

2、插入排序和起泡排序C.簡(jiǎn)單選擇排序和四路歸并排序D.樹形選擇排序和shell排序5 .下列排序方法中，哪一個(gè)是穩(wěn)定的排序方法？（）【北方交通大學(xué)2001一、8（2分）A.直接選擇排序B.二分法插入排序C.希爾排序D.快速排序6 .若要求盡可能快地對(duì)序列進(jìn)行穩(wěn)定的排序，則應(yīng)選（A.快速排序B.歸并排序C.冒泡排序）?！颈本┼]電大學(xué)2001一、5（2分）】7 .如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒,則稱該排序算法是不穩(wěn)定的。（）就是不穩(wěn)定的排序方法?！厩迦A大學(xué)1998一、3（2分）】A.起泡排序B.歸并排序C.Shell排序D.直接插入排序E.簡(jiǎn)單選擇排序8

3、.若要求排序是穩(wěn)定的，且關(guān)鍵字為實(shí)數(shù)，則在下列排序方法中應(yīng)選（）排序?yàn)橐?。A.直接插入B.直接選擇C.堆D.快速E.基數(shù)【中科院計(jì)算所2000-5（2分）】9 .若需在O（nlog2n）的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方A.快速排序B.堆排序C.歸并排序D.直接插入排序【中國(guó)科技大學(xué)1998二、4（2分）】【中科院計(jì)算所1998二、4（2分）】10 .下面的排序算法中，不穩(wěn)定的是（）【北京工業(yè)大學(xué)1999一、2（2分）】A.起泡排序B.折半插入排序C.簡(jiǎn)單選擇排序D.希爾排序E.基數(shù)排序F.堆排序。11 .下列內(nèi)部排序算法中：【北京工業(yè)大學(xué)2000、1（10分每問2

4、分）】A.快速排序B.直接插入排序C.二路歸并排序D.簡(jiǎn)單選擇排序E.起泡排序F.堆排序（1）其比較次數(shù)與序列初態(tài)無關(guān)的算法是（）（2）不穩(wěn)定的排序算法是（）（3）在初始序列已基本有序（除去n個(gè)元素中的某k個(gè)元素后即呈有序，k<<n）的情況下，排序效率最高的算法是（）（4）排序的平均時(shí)間復(fù)雜度為O（n?logn）的算法是（）為O（n?n）的算法是（）12.排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是（）排序法。【北京航空航天大學(xué)1999一、9（2分）】.插入B.選擇C.冒泡D.13.卜面給出的四種排序方法中，排序過程中的比較次數(shù)與排序方法無關(guān)的是。A.選擇排序法B.插入排序法C.快速排

5、序法D.快速（）堆積排序法14.【北京航空航天大學(xué)2000、10（2分）】對(duì)下列四種排序方法，在排序中關(guān)鍵字比較次數(shù)同記錄初始排列無關(guān)的是A.直接插入【南京理工大學(xué)B.2000二分法插入C.快速排序D.（）歸并排序、7（1.5分）】15.在下列排序算法中六、4】A.直接插入排序,哪一個(gè)算法的時(shí)間復(fù)雜度與初始排序無關(guān)B.氣泡排序C.16.比較次數(shù)與排序的初始狀態(tài)無關(guān)的排序方法是（2分）快速排序（）A.直接插入排序17.數(shù)據(jù)序列（8,序后的結(jié)果。A.選擇排序【合肥工業(yè)大學(xué)18.數(shù)據(jù)序列（2,的結(jié)果。A.快速排序9,B.起泡排序10,4,5,6,20,B.199914,B.（）?！颈本├砉ご髮W(xué)200

6、1D.直接選擇排序2000二、2冒泡排序、3（2分）】C.快速排序D.簡(jiǎn)單選擇排序只能是下列排序算法中的（）的兩趟排插入排序D.堆排序9,8,10,6,20）只能是下列排序算法中的）的兩趟排序后2000冒泡排序C.一、3（2分）】選擇排序D.插入排序19.對(duì)一組數(shù)據(jù)(84,47,25,15,21)排序,數(shù)據(jù)的排列次序在排序的過程中的變化為(1)84472515214784則采用的排序是(A.選擇20.對(duì)序列15,9,1547258421(3)1521258447(4)152125)B.782020,7,15;則采用的是（A.選擇B.【南京理工大學(xué)冒泡C.1997一、2快速(2分)D.-1,4進(jìn)

7、行排序，進(jìn)行一趟后數(shù)據(jù)的排列變?yōu)椋┡判颉！灸暇├砉ご髮W(xué)1998快速21.若上題的數(shù)據(jù)經(jīng)一趟排序后的排列為C.9,15希爾D.插入4,9,-1,8,、8（2分）】冒泡7,8,20,-1,4,則采用的是(排序。A.選擇B.分）】22 .下列排序算法中A.快速排序B.（2分）23 .下列排序算法中A.選擇I()shell()B.2001C.直接插入D.冒泡【南京理工大學(xué)1998一、9（2不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。排序C.堆排序D.冒泡排序【合肥工業(yè)大學(xué)2001排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。冒泡C.歸并D.、7（1.5分）】【哈爾濱工業(yè)大學(xué)24.下列序

8、列中，（）是執(zhí)行第一趟快速排序后所得的序列。堆2001二、4（2分）】【福州大學(xué)1998（2分）】A.68,11,18,6923,93,73B.68,11,69,2318,93,73C.93,7368,11,69,23,18D.68,11,69,23,1893,7325 .有一組數(shù)據(jù)（15,9,7,8,20,-1,7,4）用快速排序的劃分方法進(jìn)行一趟劃分后數(shù)據(jù)的排序?yàn)椋ǎò催f增序）。【南京理工大學(xué)1996一、4（2分）】A.下面的B,C,D都不對(duì)。B.9,7,8,4,-1,7,15,20C.20,15,8,9,7,-1,4,7D.9,4,7,8,7,-1,15,2026 .一組記錄的關(guān)鍵碼為

9、（46,79,56,38,40,84）,則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（【燕山大學(xué)2001一、4（2分）】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）27 .在下面的排序方法中，輔助空間為O（n）的是（）?！灸暇├砉ご髮W(xué)1999一、17（1分）A.希爾排序B.堆排序C.選擇排序D.歸并排序28 .下列排序算法中，在待排序數(shù)據(jù)已有序時(shí)，花費(fèi)時(shí)間反而最多的是（）排序。A,冒泡B.希爾C.快速D.堆【南京理工大學(xué)2001一、12（1.5分）】29

10、.下列排序算法中，在每一趟都能選出一個(gè)元素放到其最終位置上，并且其時(shí)間性能受數(shù)據(jù)初始特性影響的是：（）。A.直接插入排序B.快速排序C.直接選擇排序D.堆排序30 .對(duì)初始狀態(tài)為遞增序列的表按遞增順序排序，最省時(shí)間的是（）算法，最費(fèi)時(shí)間的是（）算法。A.堆排序B.快速排序C.插入排序D.歸并排序【南開大學(xué)2000一、531 .就平均性能而言，目前最好的內(nèi)排序方法是（）排序法。【西安電子科技大學(xué)1998一、9（2分）】A.冒泡B.希爾插入C.交換D.快速32.如果只想得到1000個(gè)元素組成的序列中第5個(gè)最小元素之前的部分排序的序列，用（）方法最快。A.起泡排序B.快速排列C.Shell排序D.堆

11、排序E.簡(jiǎn)單選擇排序【清華大學(xué)1998、2（2分）】類似本題的另外敘述有：（1）設(shè)有5000個(gè)無序白元素，希望用最快的速度挑選出其中前十個(gè)最大的元素，在以下的排序方法中（）最好？為什么？【山東工業(yè)大學(xué)1995二、4（3分）】A.快速排序B.堆排序C.歸并排序D.基數(shù)排序E.SHELL#序（2）數(shù)據(jù)表中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用（）算法最節(jié)省時(shí)間。A.堆排序B.希爾排序C.快速排序D.直接選擇排序【北京理工大學(xué)2000一、5（2分）（3）設(shè)有1000個(gè)無序的元素，希望用最快的速度挑選出其中前十個(gè)最大的元素，在以下的排序方法中采用哪一種最好？（）【東北大學(xué)199

12、9一、5（3分）】A.快速排序B.歸并排序C.堆排序D.基數(shù)排序E.shell排序33.在文件“局部有序”或文件長(zhǎng)度較小的情況下，最佳內(nèi)部排序的方法是（）A.直接插入排序B.冒泡排序C.簡(jiǎn)單選擇排序【山東工業(yè)大學(xué)1995二、1（2分）】類似本題的另外敘述有：（1）在文件"局部有序”或文件長(zhǎng)度較小的情況下，最佳內(nèi)部排序的方法是（A,直接插入排序B,冒泡排序C,簡(jiǎn)單選擇排序D.快速排序【山東大學(xué)20012（1分）】）?！疚錆h大學(xué)（2）在待排序的元素序列基本有序的前提下，效率最高的排序方法是（2000二、6】A.插入排序B.選擇排序C.快速排序D.歸并排序34 .下列排序算法中，（）算法可

13、能會(huì)出現(xiàn)下面情況：在最后一趟開始之前，所有元素都不在其最終的位置上。【南開大學(xué)2000一、4】【西北大學(xué)2001二、1】A.堆排序B.冒泡排序C.快速排序D.插入排序35 .下列排序算法中，占用輔助空間最多的是：（）【廈門大學(xué)2002五、2（8分）】A.歸并排序B.快速排序C.希爾排序D.堆排序36 .從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（）排序法?！颈本┖娇蘸教齑髮W(xué)1999一、8（2分）A.插入B.選擇C.希爾D.二路歸并37.在排序算法中，每次從未排序的記錄中挑出最?。ɑ蜃畲螅╆P(guān)鍵碼字的記錄，加入到已排序記錄的末尾

14、，該排序方法是（）?！局猩酱髮W(xué)1999一、11A.選擇B.冒泡C.插入D.堆38 .用直接插入排序方法對(duì)下面四個(gè)序列進(jìn)行排序（）。A.94,32,40,90,80,46,21,69BC.21,32,46,40,80,69,90,94D【北方交通大學(xué)2001一、15（2分）】39 .直接插入排序在最好情況下的時(shí)間復(fù)雜度為（分）】A.O（logn）B.O（n）C(由小到大)，元素比較次數(shù)最少的是32,40,21,46,69,94,90,8090,69,80,46,21,32,94,40)【北京郵電大學(xué)1999一、5(2O(n*logn)D.O(n2)40.若用冒泡排序方法對(duì)序列A.3B.10C.1

15、5分）】類似本題的另外敘述有：（1）若用冒泡排序?qū)﹃P(guān)鍵字序列鍵字比較總次數(shù)是（）A.10B.15C.2110,14,26,29,41,52D.2518,16,14,12,10,8,【北京工商大學(xué)2001D.34從大到小排序，需進(jìn)行（）次比較。【南京理工大學(xué)1999一、11（4進(jìn)行從小到大的排序，所需進(jìn)行的關(guān)、4（3分）()?！灸暇├砉ご髮W(xué)2000、180(n*n),0(n)D.0(nlogn),0(n)A.lB.4C.3D.241 .采用簡(jiǎn)單選擇排序，比較次數(shù)與移動(dòng)次數(shù)分別為（1.5分）A.On）,O（logn）B.O（logn）,0（n*n）C.42 .對(duì)序列15,9,7,8,20,-1,4

16、,用希爾排序方法排序，經(jīng)一趟后序列變?yōu)?5,-l,4,8,20,9,7則該次采用的增量是（）【南京理工大學(xué)1999一、15（1分）】43 .對(duì)下列關(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速度最快的情形是（）。A.21,25,5,17,9,23,30B.25,23,30,17,21,5,9C.21,9,17,30,25,23,5D.5,9,17,21,23,25,30【北方交通大學(xué)2001、18（2分）44 .對(duì)關(guān)鍵碼序列28,16,32,12,60,2,5,72快速排序，從小到大一次劃分結(jié)果為（）。A.(2,5,12,16)26(60,32,72)B.(5,16,2,12)28(60,32,72)C

17、.(2,16,12,5)28(60,32,72)D.(5,16,2,12)28(32,60,72)【青島大學(xué)2000三、4(2分)】45.對(duì)n個(gè)記錄的線性表進(jìn)行快速排序?yàn)闇p少算法的遞歸深度，以下敘述正確的是()A.每次分區(qū)后，先處理較短的部分B.每次分區(qū)后，先處理較長(zhǎng)的部分C.與算法每次分區(qū)后的處理順序無關(guān)D.以上三者都不對(duì)【北方交通大學(xué)2000二、5(2分)】46 .當(dāng)n個(gè)整型數(shù)據(jù)是有序時(shí)，對(duì)這n個(gè)數(shù)據(jù)用快速排序算法排序，則時(shí)間復(fù)雜度是(6),當(dāng)用遞歸算法求n!時(shí)，算法的時(shí)間復(fù)雜度是(7)，則：(6)-(7)=()【南京理工大學(xué)1999一、(6-7)(4分)】A.O(n)B.O(nlogn)

18、C.O(n*n)D.O(logn)47 .快速排序在最壞情況下的時(shí)間復(fù)雜度是(),比()的性能差。A.O(NlogN)B.O(N2)C.O(N3)D.堆排序E.冒泡排序F.選擇排序【山東工業(yè)大學(xué)1995二、2(4分)】48.快速排序方法在()情況下最不利于發(fā)揮其長(zhǎng)處?！狙嗌酱髮W(xué)2001一、3(2分)】A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)中含有多個(gè)相同值C.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)D.要排序的數(shù)據(jù)已基本有序49 .在含有n個(gè)關(guān)鍵字的小根堆(堆頂元素最小)中，關(guān)鍵字最大的記錄有可能存儲(chǔ)在()位置上。A.n/2JB.n/2J-1C.1D.ji/2+2【中科院計(jì)算所2000、4(2分)50 .以下序列

19、不是堆的是()?！疚靼搽娮涌萍即髮W(xué)2001應(yīng)用一、5(2分)】A.(100,85,98,77,80,60,82,40,20,10,66)B.(100,98,85,82,80,77,66,60,40,20,10)C.(10,20,40,60,66,77,80,82,85,98,100)D.(100,85,40,77,80,60,66,98,82,10,20)51 .下列四個(gè)序列中，哪一個(gè)是堆()。【北京工商大學(xué)2001、8(3分)】A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,

20、65,10,25,30,20,1552 .堆排序是()類排序，堆排序平均執(zhí)行的時(shí)間復(fù)雜度和需要附加的存儲(chǔ)空間復(fù)雜度分別是()A.插入B.交換C.歸并D.基數(shù)E.選擇F.O(n2)和O(1)G.O(nlogzn)和O(1)H.O(nlogzn)和O(n)I.O(n2)和O(n)【西北大學(xué)2001二、2】53.在對(duì)n個(gè)元素的序列進(jìn)行排序時(shí)，堆排序所需要的附加存儲(chǔ)空間是()。A.O(log2n)B.O(1)C.O(n)D.O(nlog2n)【西安電子科技大學(xué)2001應(yīng)用一、10(2分)】54 .對(duì)n個(gè)記錄的文件進(jìn)行堆排序，最壞情況下的執(zhí)行時(shí)間是多少？()A.O(log2n)B.O(n)C.O(nlo

21、g2n)D.O(n*n)【北方交通大學(xué)2001、9(2分)55 .有一組數(shù)據(jù)(15,9,7,8,20,-1,7,4),用堆排序的篩選方法建立的初始堆為()A.-1,4,8,9,20,7,15,7B,-1,7,15,7,4,8,20,9C.-1,4,7,8,20,15,7,9D.A,B,C均不對(duì)?！灸暇├砉ご髮W(xué)1996二、5(2分)】56 .歸并排序中，歸并的趟數(shù)是()?！灸暇├砉ご髮W(xué)2000一、19(1.5分)】A.O(n)B,O(logn)C.O(nlogn)D,O(n*n)類似本題的另外敘述有：(1)歸并排序的時(shí)間復(fù)雜性是()?！局猩酱髮W(xué)1999一、12A.O(N*N)B.O(N)C.O(

22、N*LOG(N)D.O(LOG(N)57 .在排序算法中每一項(xiàng)都與其它各項(xiàng)進(jìn)行比較，計(jì)算出小于該項(xiàng)的項(xiàng)的個(gè)數(shù)，以確定該項(xiàng)的位置叫()A.插入排序B.枚舉排序C.選擇排序D.交換排序【北京郵電大學(xué)2000二、6(20/8分)】58 .就排序算法所用的輔助空間而言，堆排序，快速排序，歸并排序的關(guān)系是()A.堆排序快速排序歸并排序B.堆排序歸并排序快速排序C.堆排序歸并排序快速排序D.堆排序>快速排序>歸并排序E.以上答案都不對(duì)【西安交通大學(xué)1996三、1(3分)】59 .排序方法有許多種，(1)法從未排序的序列中依次取出元素,與已排序序列(初始時(shí)為空)中的元素作比較，將其放入已排序序列

23、的正確位置上；(2)法從未排序的序列中挑選元素，并將其依次放入已排序序列(初始時(shí)為空)的一端；交換排序方法是對(duì)序列中的元素進(jìn)行一系列比較，當(dāng)被比較的兩元素逆序時(shí)，進(jìn)行交換；(3)和(4)是基于這類方法的兩種排序方法，而(4)是比(3)效率更高的方法;(5)法是基于選擇排序的一種排序方法，是完全二叉樹結(jié)構(gòu)的一個(gè)重要應(yīng)用?！颈狈浇煌ù髮W(xué)1999一、3(5分)】(1) -(5):A.選擇排序B.快速排序C.插入排序D.起泡排序E.歸并排序F.shell排序G.堆排序H.基數(shù)排序類似本題的另外敘述有：(1)排序的方法有很多種，()法從未排序的序列中依次取出元素與已排序序列中的元素比較，將其放在已排序序

24、列的正確位置上；()法從未排序序列中挑選元素，并將其依次放入已排序序列的一端；交換排序法是對(duì)序列中的元素進(jìn)行一系列比較，當(dāng)被比較的兩元素逆序時(shí)，進(jìn)行交換。()和()是基于這類方法的兩種排序方法，而()是比()效率更高的方法。供選擇的答案：A.快速排序B.選擇排序C.歸并排序D.冒泡排序E.直接插入排序【山東大學(xué)1998三、2(5分)【山東工業(yè)大學(xué)2000三、2(7分)】60 .設(shè)要將序列(q,h,c,y,p,a,m,s,r,d,f,x)中的關(guān)鍵碼按字母升序重新排序，(1)()是初始步長(zhǎng)為4的shell排序一趟掃描的結(jié)果；(2)()是對(duì)排序初始建堆的結(jié)果；(3)()是以第一個(gè)元素為分界元素的快速

25、一趟掃描的結(jié)果。從下面供選擇的答案中選出正確答案填入括號(hào)內(nèi)。【廈門大學(xué)2000六、3(16%/3分)】A.f,h,c,d,p,a,m,q,r,s,y,xB.p,a,c,s,q,d,f,x,r,h,m,yC. a,d,c,r,f,q,m,s,y,p,h,xD.h,c,q,p,a,m,s,r,d,f,x,yE.h,q,c,y,a,p,m,s,d,r,f,x類似本題的另外敘述有：(1)在內(nèi)排序的過程中，通常需要對(duì)待排序的關(guān)鍵碼進(jìn)行多編掃描，采用不同重新排序方法，會(huì)產(chǎn)生不同的排序中間結(jié)果。設(shè)要將序列<Q,H,C,Y,P,A,M,S,R,D,F,X>中的關(guān)鍵碼按字母序的升序排列，則(1)是冒

26、泡排序一趟掃描的結(jié)果,(2)是初始步長(zhǎng)為4的希爾(SHELL)排序一趟掃描的結(jié)果,(3)是合并排序一趟掃描的結(jié)果,(4)是以第一個(gè)元素為分界元素的快速排序一趟掃描的結(jié)果,(5)是堆排序初始建堆的結(jié)果。供選擇的答案【上海海運(yùn)學(xué)院1997二、3（5分）】1-5:A.f,h,c,d,p,a,m,q,r,s,y,xB.p,a,c,s,q,d,f,x,r,h,m,yC.a,d,c,r,f,q,m,s,y,p,h,xD. h,c,q,p,a,m,s,r,d,f,x,yE.h,q,c,y,a,p,m,s,d,r,f,x61.對(duì)由n個(gè)記錄所組成的表按關(guān)鍵碼排序時(shí)，下列各個(gè)常用排序算法的平均比較次數(shù)分別是：二路

27、歸并排序?yàn)椋?）,直接插入排序?yàn)椋?）,快速排序?yàn)椋?）,其中，歸并排序和快速排序所需要的輔助存儲(chǔ)分別是（4）和（5）。【上海海運(yùn)學(xué)院1998二、4（5分）】1-5:A.O（1）B.O（nlogzn）C.O（n）D.O（njE.O（n（log2n）2）F.O（log2n）62 .將兩個(gè)各有N個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）A.NB.2N-1C.2ND.N-1【中科院計(jì)算所1998二、7（2分）】【中國(guó)科技大學(xué)1998二、7（2分）】63 .基于比較方法的n個(gè)數(shù)據(jù)的內(nèi)部排序。最壞情況下的時(shí)間復(fù)雜度能達(dá)到的最好下界是（）。A.O（nlogn）B.O（logn）C.O（n）D.

28、O（n*n）【南京理工大學(xué)1996、2（2分）】64 .已知待排序的n個(gè)元素可分為n/k個(gè)組，每個(gè)組包含k個(gè)元素，且任一組內(nèi)的各元素均分別大于前一組內(nèi)的所有元素和小于后一組內(nèi)的所有元素，若采用基于比較的排序，其時(shí)間下界應(yīng)為（）。A.O（nlog2n）B.O（nlog2k）C.O（klog2n）D.O（klog2k）【中國(guó)科技大學(xué)1998二、9（2分）】類似本題的另外敘述有：（1）已知待排序的N個(gè)元素可分為N/K個(gè)組，每個(gè)組包含K個(gè)元素，且任一組內(nèi)的各元素均分別大于前一組內(nèi)的所有元素和小于后一組內(nèi)的所有元素，若采用基于比較的排序，其時(shí)間下界應(yīng)為()A.O(klog2k)B.O(klog2n)C.

29、O(nlog2k)D.O(nlog2n)【中科院計(jì)算所1998二、9(2分)】65 .采用敗者樹進(jìn)行A.有關(guān)B66 .采用敗者樹進(jìn)行A.有關(guān)二、判斷題：k路平衡歸并的外部排序算法，其總的歸并效率與k.無關(guān)【北京工業(yè)大學(xué)2000、2（3分）】K路平衡歸并時(shí)，總的（包括訪外）歸并效率與.無關(guān)【北京工業(yè)大學(xué)2001K(、4(2）°分）】1 .當(dāng)待排序的元素很大時(shí)，為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜度的主要因素。（）【長(zhǎng)沙鐵道學(xué)院1998一、10（1分）】2 .內(nèi)排序要求數(shù)據(jù)一定要以順序方式存儲(chǔ)。（）【南京理工大學(xué)1997二、2（2分）】3 .排序算法中的比較次數(shù)

30、與初始元素序列的排列無關(guān)。（）【南京航空航天大學(xué)1997一、8（1分）】4 .排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。（）【南京航空航天大學(xué)1996六、9（1分）】5 .在執(zhí)行某個(gè)排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動(dòng)，則該算法是不穩(wěn)定的。（）【上海交通大學(xué)1998一、186 .直接選擇排序算法在最好情況下的時(shí)間復(fù)雜度為O（Nh（）【合肥工業(yè)大學(xué)2001二、10（1分）】7 .兩分法插入排序所需比較次數(shù)與待排序記錄的初始排列狀態(tài)相關(guān)。（）【上海交通大學(xué)1998、15】8 .在初始數(shù)據(jù)表已經(jīng)有序時(shí)，快速排序算法的時(shí)間復(fù)雜度為O（nlog2n）。（）【合

31、肥工業(yè)大學(xué)2000二、9（1分）】9 .在待排數(shù)據(jù)基本有序的情況下，快速排序效果最好。（）【南京理工大學(xué)1997二、4（2分）】10 .當(dāng)待排序記錄已經(jīng)從小到大排序或者已經(jīng)從大到小排序時(shí)，快速排序的執(zhí)行時(shí)間最省。（）【上海交通大學(xué)1998一、1611 .快速排序的速度在所有排序方法中為最快，而且所需附加空間也最少。（）【北京郵電大學(xué)1998、7（2分）】12 .堆肯定是一棵平衡二叉樹。（）【南京航空航天大學(xué)1997一、6（1分）】13 .堆是滿二叉樹。（）【南京航空航天大學(xué)1996六、6（1分）】14 .（101,88,46,70,34,39,45,58,66,10）是堆。（）【北京郵電大學(xué)1

32、999二、1（2分）】15 .在用堆排序算法排序時(shí)，如果要進(jìn)行增序排序，則需要采用“大根堆”。（）【合肥工業(yè)大學(xué)2000二、10（1分）】16 .堆排序是穩(wěn)定的排序方法。（）【上海交通大學(xué)1998一、1917 .歸并排序輔助存儲(chǔ)為O（1）。（）【青島大學(xué)2000四、9（1分）】18 .在分配排序時(shí)，最高位優(yōu)先分配法比最低位優(yōu)先分配法簡(jiǎn)單。（）【上海交通大學(xué)1998一、20】19 .冒泡排序和快速排序都是基于交換兩個(gè)逆序元素的排序方法，冒泡排序算法的最壞時(shí)間復(fù)雜性是O（n*n）,而快速排序算法的最壞時(shí)間復(fù)雜性是O（nlog2n）,所以快速排序比冒泡排序算法效率更高。（）【上海海運(yùn)學(xué)院1997一、

33、9（1分）】20 .交換排序法是對(duì)序列中的元素進(jìn)行一系列比較，當(dāng)被比較的兩個(gè)元素逆序時(shí)，進(jìn)行交換，冒泡排序和快速排序是基于這類方法的兩種排序方法，冒泡排序算法的最壞時(shí)間復(fù)雜性是O（n*n）,而快速排序算法的最壞時(shí)間復(fù)雜性是O（nlog2n）;所以快速排序比冒泡排序效率更高。（）【上海海運(yùn)學(xué)院1998、10（1分）】【上海海運(yùn)學(xué)院1995一、10（1分）】21 .快速排序和歸并排序在最壞情況下的比較次數(shù)都是O（nlog2n）。（）【上海海運(yùn)學(xué)院1996、9（1分）】22 .在任何情況下，歸并排序都比簡(jiǎn)單插入排序快。（）【北京郵電大學(xué)2000一、4（1分）】23 .歸并排序在任何情況下都比所有簡(jiǎn)單

34、排序速度快。（）【北京郵電大學(xué)2002一、9（1分）24 .快速排序總比簡(jiǎn)單排序快。（）【東南大學(xué)2001一、9（1分）】25 .中序周游（遍歷）平衡的二叉排序樹，可得到最好排序的關(guān)鍵碼序列。（）【中山大學(xué)1994一、4（2分）】26 .外部排序是把外存文件調(diào)入內(nèi)存，可利用內(nèi)部排序的方法進(jìn)行排序，因此排序所花的時(shí)間取決于內(nèi)部排序的時(shí)間。（）【北京郵電大學(xué)1998、8（2分）】27 .在外部排序時(shí)，利用選擇樹方法在能容納m個(gè)記錄的內(nèi)存緩沖區(qū)中產(chǎn)生的初始?xì)w并段的平均長(zhǎng)度為2m個(gè)記錄。（）【上海海運(yùn)學(xué)院1999一、10（1分）】28 .為提高在外排序過程中，對(duì)長(zhǎng)度為N的初始序列進(jìn)行“置換一選擇”排序

35、時(shí)，可以得到的最大初始有序段的長(zhǎng)度不超過N/2。（）29 .排序速度，進(jìn)行外排序時(shí)，必須選用最快的內(nèi)排序算法。30 .在完成外排序過程中，每個(gè)記錄的I/O次數(shù)必定相等。()【大連海事大學(xué)2001一、20(每題1分)31 .影響外排序的時(shí)間因素主要是內(nèi)存與外設(shè)交換信息的總次數(shù)。()【東北大學(xué)1997二、5(2分)】三、填空題1 .若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的和記錄的。【北京郵電大學(xué)2001二、7(4分)】2 .外排序的基本操作過程是和?！疚靼搽娮涌萍即髮W(xué)1998二、3(3分)】類似本題的另外敘述有：(1)外部排序中兩個(gè)相對(duì)獨(dú)立的階段是和?！疚靼搽娮涌萍即髮W(xué)1

36、999軟件一、8(2分)3 .屬于不穩(wěn)定排序的有。1青島大學(xué)2002三、5(2分)】4 .分別采用堆排序，快速排序，冒泡排序和歸并排序，對(duì)初態(tài)為有序的表，則最省時(shí)間的是算法，最費(fèi)時(shí)間的是算法。【福州大學(xué)1998二、10(2分)】類似本題的另外敘述有：(1)設(shè)表中元素的初始狀態(tài)是按健值遞增的，分別用堆排序，快速排序，冒泡排序和歸并排序方法對(duì)其進(jìn)行排序(按遞增順序)，排序最省時(shí)間，排序最費(fèi)時(shí)間?！緩B門大學(xué)2001一、5(14%/5分)】5 .不受待排序初始序列的影響，時(shí)間復(fù)雜度為O(N2)的排序算法是,在排序算法的最后一趟開始之前，所有元素都可能不在其最終位置上的排序算法是。【中國(guó)人民大學(xué)2001

37、一、3(2分)】6 .直接插入排序用監(jiān)視哨的作用是?！灸暇├砉ご髮W(xué)2001二、8(2分)】7 .對(duì)n個(gè)記錄的表r1.n進(jìn)行簡(jiǎn)單選擇排序，所需進(jìn)行的關(guān)鍵字間的比較次數(shù)為?！救A中理工大學(xué)2000一、10(1分)】8 .用鏈表表示的數(shù)據(jù)的簡(jiǎn)單選擇排序，結(jié)點(diǎn)的域?yàn)閿?shù)據(jù)域data,指針域next;鏈表首指針為head,鏈表無頭結(jié)點(diǎn)。selectsort(head)p=head;while(p(1)q=p;r=(2)while(3)if(4)q=r;r=(5);tmp=q->data;q->data=p->data;p->data=tmp;p=(6);【南京理工大學(xué)2000三、2(

38、6分)】9 .下面的c函數(shù)實(shí)現(xiàn)對(duì)鏈表head進(jìn)行選擇排序的算法，排序完畢，鏈表中的結(jié)點(diǎn)按結(jié)點(diǎn)值從小到大鏈接。請(qǐng)?jiān)诳湛蛱幪钌线m當(dāng)內(nèi)容，每個(gè)空框只填一個(gè)語句或一個(gè)表達(dá)式：#include<stdio.h>typedefstructnodechardata;structnode*link;node;node*select(node*head)node*p,*q,*r,*s;p=(node*)malloc(sizeof(node);p->link=head;head=p;while(p->link!=null)q=p->link;r=p;while(1)if(q->

39、link->data<r->link->data)r=q;q=q->link;if()s=r->link;r->link=s->link;s->link=(3);(4)=);(5)_);p=head;head=head->link;free(p);return(head);【復(fù)旦大學(xué)1999六(15分)】10 .下面的排序算法的思想是：第一趟比較將最小的元素放在r1中，最大的元素放在rn中，第二趟比較將次小的放在r2中，將次大的放在rn-1中，依次下去，直到待排序列為遞增序。(注：<->)代表兩個(gè)變量的數(shù)據(jù)交換)。void

40、sort(SqList&r,intn)i=1;while(11_)min=max=1;for(j=i+1;(2);+j)if(3)min=j;elseif(rj.key>rmax.key)max=j;if(4)rmin<->rj;if(max!=n-i+1)if(5)rmin<->rn-i+1;else(6)_);i+;/sort【南京理工大學(xué)2001三、2(10分)】11 .表插入排序的基本思想是在結(jié)點(diǎn)中設(shè)一指針字段，插入Ri時(shí)Rl到Ri-1己經(jīng)用指針按排序碼不減次序鏈結(jié)起夾，這時(shí)采用順序比較的方法找到Ri應(yīng)插入的位置，做鏈表插入。如此反復(fù)，直到把Rn插

41、入為止。(1)(6分)請(qǐng)完成下列表插人的算法；【山東工業(yè)大學(xué)2000五(16分)】【山東大學(xué)1998五】 .R0.LINK(1;RN.LINK_; .循環(huán)，I以-1為步長(zhǎng)，從(3)_到_執(zhí)行(1) R0.LINK;Q-0(2)循環(huán)，當(dāng)P>0且囪M,反復(fù)執(zhí)行QP;P(6)(3)RQ.LINKI;RI.LINKP(2) (2分)表插入排序的最大比較次數(shù)是(7)_;(3) (2分)表插入排序的最小比較次數(shù)是(8);(4) (2分)記錄移動(dòng)的次數(shù)是(9);(5) (2分)需要附加的存儲(chǔ)空間是(10);(6) (2分)該排序算法是否是穩(wěn)定的(11)。12 .設(shè)用希爾排序?qū)?shù)組98,36,-9,0,

42、47,23,1,8,10,7進(jìn)行排序，給出的步長(zhǎng)(也稱增量序列)依次是4,2,1則排序需趟，寫出第一趟結(jié)束后，數(shù)組中數(shù)據(jù)的排列次序?！灸暇├砉ご髮W(xué)1997三、5(2分)】13 .從平均時(shí)間性能而言，排序最佳。【青島大學(xué)2001六、5(3分)】14 .對(duì)于7個(gè)元素的集合1,2,3,4,5,6,7)進(jìn)行快速排序，具有最小比較和交換次數(shù)的初始排列次序?yàn)??！鹃L(zhǎng)沙鐵道學(xué)院1997二、1(2分)】15 .快速排序在的情況下最易發(fā)揮其長(zhǎng)處。【長(zhǎng)沙鐵道學(xué)院1998二、5(2分)】類似本題的另外敘述有：(1)快速排序法在情況下最不利于發(fā)揮其長(zhǎng)處，在情況下最易發(fā)揮其長(zhǎng)處?！旧綎|大學(xué)2001三、5(2分)16 .在

43、數(shù)據(jù)表有序時(shí)，快速排序算法的時(shí)間復(fù)雜度是?！竞戏使I(yè)大學(xué)2001三、10(2分)】17 .堆排序的算法時(shí)間復(fù)雜度為：?！竞戏使I(yè)大學(xué)1999三、10(2分)】18 .PROCsift(VARr：listtype;k,m:integer);假設(shè)rk+1.m中各元素滿足堆的性質(zhì)，本算法調(diào)整rk使整個(gè)序列rk.m中各元素滿足堆的性質(zhì)。)i:=k;j:=(1);x:=rk.key;finished:=false;t:=rk;WHILE(j<=m)ANDNOTfinishedDOIF(j<m)AND(2)_)THENj:=j+1;IFx<=rj.keyTHENfinished:=(3)

44、_ELSEri:=(4);i:=j;j:=(5);ri：=t;ENDP;sift)【燕山大學(xué)1998四、2(15分)】19 .設(shè)n為結(jié)點(diǎn)個(gè)數(shù)，datatype為結(jié)點(diǎn)信息類型。為了進(jìn)行堆排序，定義：TYPEnode=RECORDkey：integer;info:datatypeEND;VARheap:ARRAY1.nOFnode1 ,r,i,j:0.n;x:node;在下面的算法描述中填入正確的內(nèi)容，使其實(shí)現(xiàn)1964年Floyd提出的建堆篩選法，要求堆建成后便找到了最小的關(guān)鍵碼。篩選算法sift(l,r,heap):步1.準(zhǔn)備i-l;j一(1)_;xheapi步2.過篩循環(huán)：當(dāng)時(shí)反復(fù)執(zhí)行.若j&

45、lt;r且heapj.key>heapj+1.key則.若則heapi-heapj;(5);(6)否則跳出循環(huán)步3.結(jié)束heapi【山東工業(yè)大學(xué)1996三、2(7分)】20 .以下程序的功能是利用堆進(jìn)行排序。請(qǐng)?jiān)诳瞻滋幪钌线m當(dāng)語句，使程序完整。PROCEDUREsift(VARr:arr;k,m:integer);VARi,j,x:integer;t:rec;finished:boolean;BEGINi:=k;(1);x:=ri.key;(2);t:=rk;WHILE(j<=m)ANDNOTfinishedDOBEGINIF(j<m)ANDTHENj:=j+1;IFx<

46、;=rj.keyTHENfinished:=trueELSEBEGIN(4);(5);(6)END;END;一END;PROCEDUREheapsort(VARr:arr);VARi:integer;x:rec;BEGINFORi:=nDIV2DOWNTO1DO(8);FORi:=nDOWNTO2DOBEGINx:=r1;(9);ri:=x;(10)END;END;【北方交通大學(xué)2000四(20分)】21 .堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。試判斷下面的關(guān)鍵碼序列中哪一個(gè)是堆。16,72,31,23,94,5394,53,31,72,16,2316,53,23,94,31,7216,31,23,94,5

47、3,7294,31,53,23,16,72堆排序是一種(1)類型的排序,它的一個(gè)基本問題是如何建堆，常用的建堆算法是1964年Floyd提出的(2),對(duì)含有n個(gè)元素的序列進(jìn)行排序時(shí)，堆排序的時(shí)間復(fù)雜度是(3),所需要的附加結(jié)點(diǎn)是(4)?！旧綎|工業(yè)大學(xué)1994一、2(5分)】22 .堆是一種有用的數(shù)據(jù)結(jié)構(gòu).堆排序是一種。)排序,堆實(shí)質(zhì)上是一棵(2)結(jié)點(diǎn)的層次序列。對(duì)含有N個(gè)元素的序列進(jìn)行排序時(shí)，堆排序的時(shí)間復(fù)雜度是(3),所需的附加存儲(chǔ)結(jié)點(diǎn)是(4)。關(guān)鍵碼序列05,23,16,68,94,72,71,73是否滿足堆的性質(zhì)(5)?！旧綎|工業(yè)大學(xué)1996三、1(5分)】23 .將如下的堆排序算法補(bǔ)寫

48、完整。說明如下：TYPEheaptype=ARRAY1.nOFinteger;過程heapsort的功能是將數(shù)組h中的前n個(gè)記錄按關(guān)鍵字遞減的次序排序。heapsort調(diào)用過程sift時(shí)的參數(shù)h,k,r有如下定義：以hk+1,hk+2,hr為根的子樹已經(jīng)是堆；執(zhí)行sift后，以hk,hk+1,hk+2,hr為根的子樹都成為堆。PROCsift(VARh：heaptype;k,r：integer);VARi,j,x：integer;finish:boolean;BEGINi:=k;x:=hi;j:=2*j;(1_);WHILE(j<=r)ANDNOTfinishDOIF(j<r)AN

49、D(hj>hj+1)THENj:=j+1;IFx>hjTHEN(2)ELSEfinish:=true;(3) END;PROCheapsort(VARh:heaptype;n:integer);VARk,r,i,j:integer;BEGINFORk:=nDIV2DOWNTO1DOsift(4)lFORr:=nDOWNTO2DOx：=h1;h1:=hr;hr:=x;(5)END;【北京工業(yè)大學(xué)1997五、2(16分)】24 .設(shè)有字母序列Q,D,F,X,A,P,N,B,Y,M,C,W),請(qǐng)寫出按2路歸并排序方法對(duì)該序列進(jìn)行一趟掃描后的結(jié)果。【北方交通大學(xué)2001二、7】25 .閱讀

50、下列程序說明和PASCALS序，把應(yīng)填入其中處的字句寫在答題紙上。程序說明：本題給出的是將數(shù)組a的元素a,a2,an從大到小排序的子程序。子程序采用改進(jìn)的選擇排序方法，該方法基于以下思想：在選擇第一大元過程中，a與aj(j=n,n-1,2)逐個(gè)比較，若發(fā)現(xiàn)aj1>a1,則向1與a1變換，變換后新的剛有性質(zhì)a1>at(j1<t<n),若再有aj2>a1(j2<j1),aj2與a1交換，則交換后的卻也有性質(zhì)aj2>at(j2<twn)。如在挑選第一大元過程中，與a1交換的元素有k(k>0)個(gè)，依次為aj1,aj2,ajk,則它們都滿足這一性質(zhì)，

51、它們的下標(biāo)滿足n刁1>j2>,>jk>1。有了這些下標(biāo)，在確定第二大元時(shí)，可只考慮a2與aj(j=jk,jk-1,3)逐個(gè)比較。倘若jk=2,則可不經(jīng)比較就知道它是第二大元。在選擇第二大元過程中，將與a2交換過的元素下標(biāo)也標(biāo)記下來，可供選擇其他大元使用，但在選擇第二大元時(shí)，應(yīng)保證與a2交換的那些位置上的新值也都滿足上述性質(zhì)，依次類推，順序選擇第一，第二，第n-1大元，實(shí)現(xiàn)對(duì)a的排序。設(shè)程序包含有常量和類型定義：CONSTmaxn=1000;TYPEvector=ARRAY1.maxnOFinteger;index=1.maxn;PROCEDUREsort(VARa:ve

52、ctor;n:index)VARp:vector;i,j,k,m,t:integer;BEGINk:=0;i:=1;m:=n;WHILEi<nDOBEGINFORj:=mDOWNTOi+1DOIFai<ajTHENBEGINt:=ai;ai:=aj;aj:=t;k:=k+1;(1)END;REPEAT(2).);IF(3)THEN(4)ELSEBEGINm:=pk;k:=k-1;END;UNTIL(i<m)OR(i=n);IF(5)BEGINt:=ai;(6);(7)ENDENDEND;【上海海運(yùn)學(xué)院1997七(14分)】26 .下列算法為奇偶交換排序，思路如下：第一趟對(duì)所有

53、奇數(shù)的i,將ai和ai+1進(jìn)行比較，第二趟對(duì)所有偶數(shù)的i,將ai和ai+1進(jìn)行比較，每次比較時(shí)若ai>ai+1,將二者交換；以后重復(fù)上述二趟過程，直至整個(gè)數(shù)組有序。程序.(a)PROCEDUREoesort(VARa:ARRAY1.nOFinteger);VARflag:boolean;i,t:integer;BEGINREPEATflag:=false;FORi:=1TOnstep2DOIF(ai>ai+1)THENflag:=(1);t:=ai+1;ai+1:=ai;(2)FORi:=(3)DOIF(ai>ai+1)THENflag:=(4);t:=ai+1;ai+1:=

54、ai;ai:=t;UNTIL(5);END;程序(b)voidoesort(intan)intflag,i,t;doflag=0;for(i=1;i<n;i+,i+)if(ai>ai+1)flag=(1).;t=ai+1;ai+1=ai;(2);for(3)if(ai>ai+1)flag=(4);t=ai+1;ai+1=ai;ai=t;while(5)【上海大學(xué)2000一、1(10分)】27 .關(guān)鍵碼序列(Q,H,C,Y,QA,M,S,R,D,F,X),要按照關(guān)鍵碼值遞增的次序進(jìn)行排序，若采用初始步長(zhǎng)為4的Shell排序法，則一趟掃描的結(jié)果是;若采用以第一個(gè)元素為分界元素的快速排序法，則掃描一趟的結(jié)果是?！颈本┐髮W(xué)1997一、4(4分)類似本題的另外敘述有：(1)設(shè)有字符序列QHC、Y、P、A、MSRD、F、X要求按字符升序排序，采用初始步長(zhǎng)為4的希爾(shell)排序，一趟掃描的結(jié)果是;采用以首元素為分界元素的快速排序，一趟掃描的結(jié)果是?！颈本┕I(yè)大學(xué)1999一、7