數(shù)據(jù)結(jié)構(gòu)Ch習(xí)題答案

1、第十章 內(nèi)部排序一、擇題1用直接插入排序法對(duì)下面四個(gè)表進(jìn)行（由小到大）排序，比較次數(shù)最少的是（B）。A（94，32，40，90，80，46，21，69） 插32，比2次插40，比2次插90，比2次插80，比3次插46，比4次插21，比7次插69，比4次B（21，32，46，40，80，69，90，94）插32，比1次插46，比1次插40，比2次插80，比1次插69，比2次插90，比1次插94，比1次C（32，40，21，46，69，94，90，80） 插40，比1次插21，比3次插46，比1次插69，比1次插94，比1次插90，比2次插80，比3次D（90，69，80，46，21，32，94，

2、40）插69，比2次插80，比2次插46，比4次插21，比5次插32，比5次插94，比1次插40，比6次2下列排序方法中，哪一個(gè)是穩(wěn)定的排序方法（BD）。 A希爾排序 B直接選擇排序 C堆排序 D冒泡排序下列3題基于如下代碼： for(i=2;i<=n;i+) x=Ai; j=i-1;while(j>0&&Aj>x) Aj+1=Aj; j-;Aj+1=x3這一段代碼所描述的排序方法稱作（A）。 A插入排序 B冒泡排序 C選擇排序 D快速排序4這一段代碼所描述的排序方法的平均執(zhí)行時(shí)間為（D） AO(log2n) BO(n) C O(nlog2n) DO(n2)5

3、假設(shè)這段代碼開始執(zhí)行時(shí)，數(shù)組A中的元素已經(jīng)按值的遞增次序排好了序，則這段代碼的執(zhí)行時(shí)間為（B）。 AO(log2n) BO(n) CO(nlog2n) DO(n2)6在快速排序過程中，每次被劃分的表（或了表）分成左、右兩個(gè)子表，考慮這兩個(gè)子表，下列結(jié)論一定正確是（B）。A左、右兩個(gè)子表都已各自排好序 B左邊子表中的元素都不大于右邊子表中的元素C左邊子表的長度小于右邊子表的長度 D左、右兩個(gè)子表中元素的平均值相等7對(duì)n個(gè)記錄進(jìn)行堆排序，最壞情況下的執(zhí)行時(shí)間為（C）。 AO(log2n) BO(n) CO(nlog2n) DO(n2)8、設(shè)待排序關(guān)鍵碼序列為（25、18、9、33、67、82、53

4、、95、12、70），要按關(guān)鍵碼值遞增的順序排序，采取以第一個(gè)關(guān)鍵碼為分界元素的快速排序法，第一趟排序完成后關(guān)鍵碼表33被放到了第幾個(gè)位置（D）。 A3 B5 C7 D99若對(duì)一個(gè)已經(jīng)排好了序的序列進(jìn)行排序，在下列四方法中，哪種方法比較好（C）。A冒泡排序法 B直接選擇排序法 C直接插入排序法 D堆排序法10快速排序的時(shí)間復(fù)雜度是（A） AO(nlog2n) BO(n2) C O(n3) DO(log2n)11以下關(guān)鍵字序列用快速排序法進(jìn)行排序，速度最慢的是（C）A23，27，7，19，11，25，32 B23，11，19，32，27，35，7C7，11，19，23，25，27，32 D27，

5、25，32，19，23，7，1112在所有排序方法中，關(guān)鍵碼比較的次數(shù)與記錄的初始排序次序無關(guān)的是（D）。A希爾排序 B冒泡排序 C直接插入排序 D直接選擇排序13用冒泡排序算法對(duì)下列數(shù)據(jù)12，37，42，19，27，35，56，44，10進(jìn)行從小到大排序，在將最大的數(shù)“沉”到最后時(shí)，數(shù)的順序是（C）。 A12，37，42，19，27，35，44，10，56 B12，37，42，19，27，35，10，44，56C12，37，19，27，35，42，44，10，56 D10，12，19，27，35，37，42，44，5614快速排序方法在（C）情況下最不利于發(fā)揮其長處。A被排序的數(shù)據(jù)量太大 B

6、被排序的數(shù)據(jù)中含有多個(gè)相同值C排序數(shù)據(jù)已基本有序 D被排序數(shù)據(jù)的數(shù)目為奇數(shù)15具有12個(gè)記錄的序列，采用冒泡排序最少的比較次數(shù)是（C）。 A1 B144 C11 D6616若用冒泡排序法對(duì)序列18,14,6,27,8,12,16,52,10,26,47,29,41,24從小到大進(jìn)行排序，其要進(jìn)行（C）次比較。 A33 B45 C70 D9114 6 18 8 12 16 27 10 26 47 29 41 24 52 比13次6 14 8 12 16 18 10 26 27 29 41 24 47 比12次6 8 12 14 16 10 18 26 27 29 24 41 比11次6 8 12

7、 14 10 16 18 26 27 24 29 比10次6 8 12 10 14 16 18 26 24 27 比9次6 8 10 12 14 16 18 24 26 比8次6 8 10 12 14 16 18 24 比7次17在任何情況下，快速排序方法的時(shí)間性能總是最優(yōu)的這種說法（B）。 A正確 B錯(cuò)誤18排序的重要目的是為了以后對(duì)已排序的數(shù)據(jù)元素進(jìn)行（C）。 A打印輸出 B分類 C查找 D合并19當(dāng)初始序列已經(jīng)按鍵值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為（D） An2 Bnlog2n Clog2n Dn-120用10萬個(gè)無序且互不相等的正整數(shù)序列，采用順序列存儲(chǔ)方式組織，希望能

8、最快地找出前10個(gè)最大的正整數(shù)，采用（D）方法較好。 A快速排序 Bshell排序 C選擇排序 D堆排序21下面四種排序方法中，平均查找長度最小的是（C）。 A插入排序 B選擇排序 C快速排序 D堆排序22在文件局部有序或文件長度較小的情況下，最佳的排序方法是（A）A直接插入排序 B冒泡排序 C簡單選擇排序 D都不對(duì)23若用某種排序（分類）方法對(duì)線性表（25，48，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，結(jié)點(diǎn)序列的變化情況如下：（1）25 84 21 47 15 27 68 35 20；（2）20 15 21 25 47 27 68 35 84；（3）15 20 21 25 35

9、 27 47 68 84；（4）15 20 21 25 27 35 47 68 84。那么，所采用的排序方法是（D）。 A選擇排序 B希爾排序 C堆排序 D快速排序24快速排序在最壞的情況下的時(shí)間復(fù)雜度是（B）。 AO(nlog2n） BO(n2) CO(n3) D都不對(duì)25若待排序列已基本有序，要使它完全有序，從關(guān)鍵碼比較次數(shù)的移動(dòng)次數(shù)和移動(dòng)次數(shù)考慮，應(yīng)當(dāng)使用的排序方法是（B）。A堆排序 B直接插入排序 C直接選擇排序 D快速排序26已知一個(gè)單鏈表中有3000個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)存放一個(gè)整數(shù)（A）可用于解決這3000個(gè)整數(shù)的排序問題且不需要對(duì)算法做大的變動(dòng)。A直接插入排序方法 B簡單選擇排序方法

10、 C快速排序方法 D堆排序方法27設(shè)有1000個(gè)無序的元素，希望用最快的速度挑選出其中10個(gè)最大的元素，最好的方法是（C）。A起泡排序 B快速排序 C堆排序 D基數(shù)排序 28在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A）。A插入排序 B選擇排序 C快速排序 D堆排序29一組記錄的排序碼為（46，79，56，38，40，84）。則利用堆排序的方法，建立的初始堆為(B)。A79，46，56，38，40，84 B84，79，56，38，40，46 C84，79，56，46，40，38 D84，56，79，40，46，3830一組記錄的排序碼為（46，79，56，38，40，84），則

11、利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（C）。A38,40,46,56,79,84 B40,38,46,79,56,84 C40,38,46,56,79,84 D40,38,46,84,56,7931排序方法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法稱為（D）。 A希爾排序 B起泡排序 C插入排序 D選擇排序 32排序方法中，從未排序序列中挑選元素，并將其放入已排序序列（初始為空）的一端的方法，稱為（D）。A希爾排序 B起泡排序 C插入排序 D選擇排序33對(duì)5個(gè)不同的數(shù)排序至少需要比較（A）次。 A4 B5

12、C6 D734一個(gè)序列中有若干個(gè)元素，若只想得到其中第i個(gè)元素之前的部分排序，最好采用（C）排序方法。A快速排序 B堆排序 C插入排序 Dshell排序35對(duì)一組記錄的關(guān)鍵碼46，79，56，38，40，84采用堆，則初始化堆后最后一個(gè)元素是（BA）。A84 B46 C56 D3836在供選擇的答案中填入正確答案：(1)排序（分類）的方法有許多種： 法從未排序序列中依次取出元素，與排序序列中的元素作比較，將其放入已排序列的正確位置上； 法從未排序序列中挑選元素，并將其依次放入已排序序的一端；交換排序法是對(duì)序列中元素進(jìn)行一系列的比較，當(dāng)被比較的兩元素逆序時(shí)進(jìn)行交換。供選擇答案 選擇排序

13、  快速排序  插入排序  冒泡排序 (2)一組記錄的關(guān)鍵字為（46，79，56，38，40，84），利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為 C 。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，79(3)下列排序算法中，  C  算法可能會(huì)出現(xiàn)下面情況：初始數(shù)據(jù)有序時(shí)，花費(fèi)時(shí)間反而最多。A、堆排序     B、冒泡排序    

14、 C、快速排序      D、SHELL 排序二、填空題1對(duì)下列兩個(gè)表：L1=（55，61，68，70，75，65，78，81，93，98，84），L2=（75，70，65，84，98，78，93，55，61，81，68），使用簡單選擇排序和直接插入排序兩種方法進(jìn)行排序，哪一種方法對(duì)兩個(gè)表排序所花費(fèi)的時(shí)間相同（簡單選擇排序）。2目前內(nèi)部排序的時(shí)間復(fù)雜度T(n)的范圍是（O(nLogn)至O(n2)）。3內(nèi)部排序?qū)⒋判虻挠涗浄旁冢ㄓ?jì)算機(jī)隨機(jī)存儲(chǔ)器）中進(jìn)行排序，按排序過程中工作量來區(qū)分，可分為（簡單的排序方法）、（先進(jìn)的排序方法）和（基數(shù)排序）三

15、類。4 對(duì)n個(gè)元素進(jìn)行起泡排序時(shí)，最少的比較次數(shù)是（n-1）。5在堆排序和快速排序中，若原始記錄接近正序或反序，則選用（堆排序）。若原始記錄無序，則選用（快速排序）。6在插入排序和選擇排序中，若初始數(shù)據(jù)基本正序，則選用(插入排序)，若數(shù)據(jù)基本反序,則選用(選擇排序)。7在插入排序、希爾排序、選擇排序、冒泡排序、快速排序、堆排序中，排序是不穩(wěn)定的有（希爾排序、快速排序、堆排序）。8已知關(guān)鍵字序列51，28，86，70，90，7，30，用冒泡排序，前三趟排序的結(jié)果依次為（28，51，70，86，7，30，90）、（28，51，70，7，30，86，90）、（28，51，7，30，70，86，90）

16、。9、設(shè)有9個(gè)元素的關(guān)鍵字序列為26，5，71，1，61，11，59，15，48，按堆排序思想選出當(dāng)前序列的最大值71和61之后，所余7個(gè)元素的關(guān)鍵字構(gòu)成的堆是（59，48，26，15，5，11，1）。10對(duì)一組記錄（54，38，96，23，15，2，60，45，83）進(jìn)行直接插入排序，當(dāng)把第7個(gè)記錄60 插入到有序表時(shí)，為尋找位置需比較(2)次。2，15，23，38，54，96，60，45，8311在利用快速排序方法對(duì)一組記錄（54，38，96，23，15，2，60，45，83）進(jìn)行快速排序進(jìn)，遞歸調(diào)用而使用的棧所能達(dá)到的最大深度為（4）、共需遞歸調(diào)用的次數(shù)為（5），其中第二次遞歸調(diào)用是對(duì)（

17、15，38，2，23）一組記錄進(jìn)行快速排序。12快速排序在平均情況下的時(shí)間復(fù)雜度為O( nlog2n )。13快速排序在最壞情況下的空間復(fù)雜度為O( n )。14在堆排序中，對(duì)n個(gè)對(duì)象建立初始堆需要調(diào)用 n/2 次調(diào)整算法。 15每次使兩個(gè)相鄰的有序表合并成一個(gè)有序表，這種排序方法叫做 歸并 排序。16給定一組數(shù)據(jù)對(duì)象的排序碼為 46, 79, 56, 38, 40, 84，對(duì)其進(jìn)行一趟快速排序，結(jié)果為 40,38,46,79,56,84。17下列程序是按關(guān)鍵字的值從大到小進(jìn)行直接選擇排序的算法，將算法補(bǔ)充完整。Select(SqList L)for(i=1;i<=L.length-1;

18、i+)k=i；for(j=i+1;j<=L.length;j+)if(L.rj.key<L.rk.key) k=j;if(k!=i)L.rk<->L.ri);      /*rk與ri交換*/18在堆排序中，如果n個(gè)對(duì)象的初始堆已經(jīng)建好，那么到排序結(jié)束，還需要從堆頂結(jié)點(diǎn)出發(fā)調(diào)用 (n-1) 次調(diào)整算法。 19在直接選擇排序中，數(shù)據(jù)對(duì)象移動(dòng)次數(shù)的時(shí)間復(fù)雜度為O( n )。 20第i (i = 0, 1, , n-2) 趟從參加排序的序列中第i個(gè)第n-1個(gè)元素中挑選出一個(gè)最?。ù螅┰?，把它交換到第i個(gè)位置，此種排序方法叫做

19、 簡單選擇 排序。 21對(duì)n個(gè)數(shù)據(jù)對(duì)象進(jìn)行堆排序，總的時(shí)間復(fù)雜度為O( nlog2n )。 22每次直接或通過基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列，就交換它們的位置，這種排序方法叫做 交換 排序。 23給定一組數(shù)據(jù)對(duì)象的排序碼為 46, 79, 56, 38, 40, 84 ，則利用堆排序方法建立的初始堆（最大堆）為 84,79,56,38,40,46 。 24在直接選擇排序中，排序碼比較次數(shù)的時(shí)間復(fù)雜度為O( n2 )。 25第i (i = 1, 2, , n-1) 趟從參加排序的序列中取出第i個(gè)元素，把它插入到由第0個(gè)第i-1個(gè)元素組成的有序表中適當(dāng)?shù)奈恢?，此種排序方法叫做 直接插入 排序。 26快速排序在平均情況下的空間復(fù)雜度為O( log2n )。 27快速排序在最壞情況下的時(shí)間復(fù)雜度為O( n2 )。 三、判斷題1( × )在任何情況下，快速排序需要進(jìn)行的排序碼比較的次數(shù)都是O(nlog2n)。 2( × )若將一批雜亂無章的數(shù)據(jù)按堆結(jié)構(gòu)組織