第6章 排序教材

第6章排序[能力要求]計算機基礎(chǔ)知識：掌握各種排序算法的思想和實現(xiàn)。分析問題：針對具體的排序問題，要能夠運用各種排序方法去進行分析，找到最優(yōu)的算法。解決方法和建議：在具體工程應(yīng)用中，發(fā)現(xiàn)了關(guān)于排序的問題，要能夠解決問題，并提出合理的建議。設(shè)計過程的分段與方法：采取不同的階段去設(shè)計（概念設(shè)計、詳細設(shè)計）一個具體的排序算法。軟件實現(xiàn)過程：了解系統(tǒng)中各個模塊中的關(guān)于排序的問題；討論算法（數(shù)據(jù)結(jié)構(gòu)、控制流程、數(shù)據(jù)流程）；使用編程語言實施低層設(shè)計（編程）。6.1知識點：直接插入排序一、選擇題1②用直接插入排序方法對下面四個序列進行排序（由小到大），元素比較次數(shù)最少的是（）。A．94，32，40，90，80，46，21，69B．32，40，21，46，69，94，90，80C．21，32，46，40，80，69，90，94D．90，69，80，46，21，32，94，402②直接插入排序在最壞情況下的時間復(fù)雜度為（）A．O（）B．O（n）C．O（）D．O（）3②若對n個元素進行直接插入排序，則進行第I趟排序過程前，有序表中的元素個數(shù)為（）A．IB．I+1C．I-1D．1二、填空題1②直接插入排序用監(jiān)視哨的作用是_____________________。【南京理工大學(xué)2001】三、判斷題（）1②直接選擇排序算法在最好情況下的時間復(fù)雜度為O（n）?！竞戏使I(yè)大學(xué)2001】四、簡答題1③算法模擬：設(shè)待排序的記錄共7個，排序碼分別為8，3，2，5，9，1，6。用直接插入排序以排序碼序列的變化描述形式說明排序全過程（動態(tài)過程）要求按遞減順序排序?！旧綎|工業(yè)大學(xué)1997】五、算法題1③請編寫直接插入排序算法。（用C語言寫）Structrcdtype{Intkey;Elementotheritem;}ARRAY[0..n];【北京輕工業(yè)學(xué)院1998】6.2知識點：希爾排序一、選擇題1③對序列{15，9，7，8，20，-1，4}，用希爾排序方法排序，經(jīng)一趟后序列變?yōu)閧15，-l，4，8，20，9，7}，則該次采用的增量是（）A.lB.4C.3D.2二、填空題1③設(shè)用希爾排序?qū)?shù)組{98，36，-9，0，47，23，1，8，10，7}進行排序，給出的步長（也稱增量序列）依次是4，2，1則排序需__________趟，寫出第一趟結(jié)束后，數(shù)組中數(shù)據(jù)的排列次序__________。2③關(guān)鍵碼序列{Q，H，C，Y，Q，A，M，S，R，D，F(xiàn)，X}，要按照關(guān)鍵碼值遞增的次序進行排序，若采用初始步長為4的Shell排序法，則一趟掃描的結(jié)果是_______________________________；若采用以第一個元素為分界元素的快速排序法，則掃描一趟的結(jié)果是________________________________。【北京大學(xué)1997】三、簡答題1③對下面數(shù)據(jù)表，寫出采用SHELL排序算法排序的每一趟的結(jié)果，并標(biāo)出數(shù)據(jù)移動情況。（125，11，22，34，15，44，76，66，100，8，14，20，2，5，1）。【合肥工業(yè)大學(xué)1999】6.3知識點：冒泡排序一、選擇題1③若用冒泡排序方法對序列{10，14，26，29，41，52}從大到小排序，需進行（）次比較。A.3B.10C.15D.252③若用冒泡排序?qū)﹃P(guān)鍵字序列{18，16，14，12，10，8}，進行從小到大的排序，所需進行的關(guān)鍵字比較總次數(shù)是（）。A.10B.15C.21D.343②對ｎ個不同的排序碼進行冒泡排序，在下列哪種情況下比較的次數(shù)最多。（）Ａ.從小到大排列好的Ｂ.元素逆序Ｃ.元素?zé)o序Ｄ.元素基本有序4②對ｎ個不同的排序碼進行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為（）Ａ.n+1Ｂ.nＣ.n-1Ｄ.n（n-1）/2三、簡答題1②設(shè)要求從大到小排序。問在什么情況下冒泡排序算法關(guān)鍵字交換的次數(shù)為最多。2③設(shè)與記錄R1，R2，…，Rn對應(yīng)的關(guān)鍵詞分別是K1，K2，…，Kn。如果存在Ri和Rj使得j<i且Ki<Kj成立，試證明經(jīng)過一趟冒泡后，一定有記錄與Ri進行交換?！炯执髮W(xué)1996】四、算法題1④冒泡排序算法是把大的元素向上移（氣泡的上?。部梢园研〉脑叵蛳乱疲馀莸南鲁粒┱埥o出上浮和下沉過程交替的冒泡排序算法?！炯执髮W(xué)2001】6.4知識點：快速排序一、選擇題1③有一組數(shù)據(jù){15，9，7，8，20，-1，7，4}，用快速排序的劃分方法進行一趟劃分后數(shù)據(jù)的排序為（）（按遞增序）。A．下面的B，C，D都不對。B．{9，7，8，4，-1，7，15，20}C．{20，15，8，9，7，-1，4，7}D.{9，4，7，8，7，-1，15，20}2③一組記錄的關(guān)鍵碼為{46，79，56，38，40，84}，則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。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}3③對下列關(guān)鍵字序列用快速排序法進行排序時，速度最快的情形是（）。A．{21，25，5，17，9，23，30}B．{25，23，30，17，21，5，9}C．{21，9，17，30，25，23，5}Ｄ．{5，9，17，21，23，25，30}4③對關(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.{2，16，12，5}28{60，32，72}D.{5，16，2，12}28{32，60，72}5③當(dāng)n個整型數(shù)據(jù)是有序時，對這n個數(shù)據(jù)用快速排序算法排序，則時間復(fù)雜度是（），當(dāng)用遞歸算法求n！時，算法的時間復(fù)雜度是（）。A.O（n）B.O（）C.O（）D.O（）6②快速排序在最壞情況下的時間復(fù)雜度是（），比（）的性能差。A．O（）B．O（）C．O（）D．堆排序E．冒泡排序F．選擇排序7①快速排序方法在（）情況下最不利于發(fā)揮其長處。A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)中含有多個相同值C.要排序的數(shù)據(jù)個數(shù)為奇數(shù)D.要排序的數(shù)據(jù)已基本有序8②在對n個元素進行直接選擇排序過程中，第I趟需從（）個元素中選擇出最小值元素。A.n-I+1B.n-IC.ID.I+1二、填空題1②對于7個元素的集合{1，2，3，4，5，6，7}進行快速排序，具有最小比較和交換次數(shù)的初始排列次序為_____________________________。2②在數(shù)據(jù)表有序時，快速排序算法的時間復(fù)雜度是____________?！竞戏使I(yè)大學(xué)2001】三、判斷題（）1②快速排序的速度在所有排序方法中為最快，而且所需附加空間也最少。（）2②在初始數(shù)據(jù)表已經(jīng)有序時，快速排序算法的時間復(fù)雜度為O（）。（）3②在待排數(shù)據(jù)基本有序的情況下，快速排序效果最好?！灸暇├砉ご髮W(xué)1997】四、簡答題1③我們知道，對于n個元素組成的線性表進行快速排序時，所需進行的比較次數(shù)與這n個元素的初始排序有關(guān)。問：【西安電子科技大學(xué)2001】【中國礦業(yè)大學(xué)2000】（1）當(dāng)n=7時，在最好情況下需進行多少次比較？請說明理由。（2）當(dāng)n=7時，給出一個最好情況的初始排序的實例。（3）當(dāng)n=7時，在最壞情況下需進行多少次比較？請說明理由。（4）當(dāng)n=7時，給出一個最壞情況的初始排序的實例。2③快速排序（quicksorting）的效率與原始序列有關(guān)，現(xiàn)用快速排序算法對關(guān)鍵字分別為1—15的15個元素進行排序：（1）在最好情況下要進行幾遍比較，給出一種原始序列實例；（2）在最壞情況下要進行幾遍比較，給出一種原始序列實例?！菊憬髮W(xué)1995】五、算法題1④寫出一趟快速排序算法?！旧綎|師范大學(xué)2000】2③借助于快速排序的算法思想，在一組無序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組r[l..h]中。若查找成功，則輸出該記錄在r數(shù)組中的位置及其值，否則顯示“notfind”信息。請編寫出算法并簡要說明算法思想?！颈本┼]電大學(xué)1998】6.5知識點：直接選擇排序一、選擇題1③采用簡單選擇排序，比較次數(shù)與移動次數(shù)分別為（）。A.O（n），O（）B.O（），O（）C.O（），O（n）D.O（），O（n）二、填空題1③對n個記錄的表r[1..n]進行簡單選擇排序，所需進行的關(guān)鍵字間的比較次數(shù)為_______。2③用鏈表表示的數(shù)據(jù)的簡單選擇排序，結(jié)點的域為數(shù)據(jù)域data，指針域next；鏈表首指針為head，鏈表無頭結(jié)點。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】3③下面的c函數(shù)實現(xiàn)對鏈表head進行選擇排序的算法，排序完畢，鏈表中的結(jié)點按結(jié)點值從小到大鏈接。請在空框處填上適當(dāng)內(nèi)容，每個空框只填一個語句或一個表達式：#include<stdio.h>typedefstructnode{chardata;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->link->data<r->link->data）r=q;q=q->link;}if（（2）___________）{s=r->link;r->link=s->link;s->link=（3）____________;（4）____________;}（5）___________;}p=head;head=head->link;free（p）;return（head）;}【復(fù)旦大學(xué)1999】4④下面的排序算法的思想是：第一趟比較將最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比較將次小的放在r[2]中，將次大的放在r[n-1]中，…，依次下去，直到待排序列為遞增序。（注：<-->）代表兩個變量的數(shù)據(jù)交換）。voidsort（SqList&r，intn）{i=1;while（（1）_____________）{min=max=1;for（j=i+1;（2）_______________;++j）{if（（3）_______________）min=j;elseif（r[j].key>r[max].key）max=j;}if（（4）________________）r[min]<-->r[j];if（max!=n-i+1）{if（（5）______________）r[min]<-->r[n-i+1];else（6）_____________;}i++;}}【南京理工大學(xué)2001】三、簡答題1②算法模擬：設(shè)待排序的記錄共7個，排序碼分別為8，3，2，5，9，1，6。用直接選擇排序以排序碼序列的變化描述形式說明排序全過程（動態(tài)過程）要求按遞減順序排序?！旧綎|工業(yè)大學(xué)1997】四、算法題1④輸入50個學(xué)生的記錄（每個學(xué)生的記錄包括學(xué)號和成績），組成記錄數(shù)組，然后按成績由高到低的次序輸出（每行10個記錄）。排序方法采用選擇排序?！颈本煼洞髮W(xué)1999】6.6知識點：堆排序一、選擇題1③在含有n個關(guān)鍵字的小根堆（堆頂元素最?。┲?，關(guān)鍵字最大的記錄有可能存儲在（）位置上。A．n/2B．n/2-1C．1D．n/2+22②以下序列不是堆的是（）。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}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，65，10，25，30，20，154②堆排序是（）類排序，堆排序平均執(zhí)行的時間復(fù)雜度是（）和需要附加的存儲空間復(fù)雜度是（）A.插入B.交換C.歸并D.基數(shù)E.選擇F.O（）和O（1）G.O（）和O（1）H.O（）和O（n）I.O（）和O（n）5②對n個記錄的文件進行堆排序，最壞情況下的執(zhí)行時間是多少？（）A．O（）B．O（n）C．O（）D．O（）6③有一組數(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均不對。二、填空題1③堆是一種有用的數(shù)據(jù)結(jié)構(gòu).堆排序是一種________排序，堆實質(zhì)上是一棵________結(jié)點的層次序列。對含有N個元素的序列進行排序時，堆排序的時間復(fù)雜度是________，所需的附加存儲結(jié)點是________。關(guān)鍵碼序列{05，23，16，68，94，72，71，73}是否滿足堆的性質(zhì)________?！旧綎|工業(yè)大學(xué)1996】2②已知一關(guān)鍵碼序列為：3，87，12，61，70，97，26，45。試根據(jù)堆排序原理，填寫完整下示各步驟結(jié)果。建立堆結(jié)構(gòu)：_____________________交換與調(diào)整：（1）877026614512397;（2）____________________________;（3）614526312708797;（4）____________________________;（5）261234561708797;（6）____________________________;（7）312264561708797;【首都經(jīng)貿(mào)大學(xué)1998】三、判斷題（）1②堆肯定是一棵平衡二叉樹。（）2②堆是滿二叉樹。（）3③{101，88，46，70，34，39，45，58，66，10}是堆。【北京郵電大學(xué)1999】（）4②在用堆排序算法排序時，如果要進行增序排序，則需要采用“大根堆”?！竞戏使I(yè)大學(xué)2000】（）5②堆排序是穩(wěn)定的排序方法?！旧虾＝煌ù髮W(xué)1998】四、簡答題1③關(guān)于堆排序方法，完成如下工作：（1）簡述該方法的基本思想。（2）分析該算法的時間復(fù)雜度。【西南財經(jīng)大學(xué)1999】2②判別序列{12，70，33，65，24，56，48，92，86，33}是否是堆（大頂堆），如果不是，則把它調(diào)整為堆。【燕山大學(xué)2001】3③根據(jù)給定的關(guān)鍵字集合{20，15，40，35，45，25，50，30，10}。（1）構(gòu)造一棵完全二叉樹；（2）畫出整理好的一棵堆樹；（3）畫出一棵輸出一個排序記錄后的二叉樹；（4）畫出重新調(diào)整好的堆樹?！敬筮B海事大學(xué)2001】4③一最小最大堆（minmaxheap）是一種特定的堆，其最小層和最大層交替出現(xiàn)，根總是處于最小層。最小最大堆中的任一結(jié)點的關(guān)鍵字值總是在以它為根的子樹中的所有元素中最?。ɑ蜃畲螅?。如圖6.1所示為一最小最大堆。7777777777777045750302012309101540minlevelmaxlevelminlevelmaxlevel圖6.11題圖（1）畫出在上圖中插入關(guān)鍵字為5的結(jié)點后的最小最大堆。（2）畫出在上圖中插入關(guān)鍵字為80的結(jié)點后的最小最大堆；【浙江大學(xué)1996】6.7知識點：歸并排序一、選擇題1②歸并排序中，歸并的趟數(shù)是（）。A．O（n）B．O（）C．O（）D．O（）2②歸并排序的時間復(fù)雜性是（）。A.O（）B.O（n）C.O（）D.O（）二、填空題1③設(shè)有字母序列{Q，D，F(xiàn)，X，A，P，N，B，Y，M，C，W}，請寫出按2路歸并排序方法對該序列進行一趟掃描后的結(jié)果。2①外部排序的基本方法是歸并排序，但在之前必須先生成?！颈本┼]電大學(xué)2001】3②磁盤排序過程主要是先生成，然后對合并，而提高排序速度很重要的是，我們將采用方法來提高排序速度。【山東工業(yè)大學(xué)1995】三、判斷題（）1②歸并排序輔助存儲為O（1）。6.8知識點：基數(shù)排序一、簡答題1③對整數(shù)序列{179，208，93，306，55，859，984，9，271，33}圖示其基數(shù)排序的全過程。6.9綜合習(xí)題一、選擇題1②某內(nèi)排序方法的穩(wěn)定性是指（）。A．該排序算法不允許有相同的關(guān)鍵字記錄B．該排序算法允許有相同的關(guān)鍵字記錄C．平均時間為O（）的排序方法D．以上都不對2①下面給出的四種排序法中（）排序法是不穩(wěn)定性排序法。A.插入B.冒泡C.二路歸并D.堆3①下列排序算法中，其中（）是穩(wěn)定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接選擇排序，歸并排序D.歸并排序，冒泡排序4②若要求盡可能快地對序列進行穩(wěn)定的排序，則應(yīng)選（）。A．快速排序B．歸并排序C．冒泡排序5②若需在O（）的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）。A.快速排序B.堆排序C.歸并排序D.直接插入排序6②下列內(nèi)部排序算法中：（1）其比較次數(shù)與序列初態(tài)無關(guān)的算法是（）（2）不穩(wěn)定的排序算法是（）（3）在初始序列已基本有序（除去n個元素中的某k個元素后即呈有序，k<<n）的情況下，排序效率最高的算法是（）（4）排序的平均時間復(fù)雜度為O（）的算法是（）（5）為O（）的算法是（）A．快速排序B.直接插入排序C.歸并排序D.直接選擇排序E.冒泡排序F.堆排序7②排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是（）排序法。A．插入B.選擇C.冒泡D.快速8③數(shù)據(jù)序列{8，9，10，4，5，6，20，1，2}只能是下列排序算法中的（）的兩趟排序后的結(jié)果。A．選擇排序B.冒泡排序C.插入排序D.堆排序9③數(shù)據(jù)序列{2，1，4，9，8，10，6，20}只能是下列排序算法中的（）的兩趟排序后的結(jié)果。A.快速排序B.冒泡排序C.選擇排序D.插入排序10③對一組數(shù)據(jù){84，47，25，15，21}排序，數(shù)據(jù)的排列次序在排序的過程中的變化為：（1）8447251521（2）1547258421（3）1521258447（4）1521254784則采用的排序是（）。A.選擇B.冒泡C.快速D.插入11③對序列{15，9，7，8，20，-1，4}進行排序，進行一趟后數(shù)據(jù)的排列變?yōu)閧4，9，-1，8，20，7，15}；則采用的是（）排序。A.選擇B.快速C.希爾D.冒泡12③若對序列{15，9，7，8，20，-1，4}進行排序經(jīng)一趟排序后的排列為{9，15，7，8，20，-1，4}，則采用的是（）排序。A．選擇B.堆C.直接插入D.冒泡13③下列排序算法中（）不能保證每趟排序至少能將一個元素放到其最終的位置上。A.快速排序B.希爾排序C.堆排序D.冒泡排序14③下列排序算法中（）排序在一趟結(jié)束后不一定能選出一個元素放在其最終位置上。A.選擇B.冒泡C.歸并D.堆15②在下面的排序方法中，輔助空間為O（n）的是（）。A．希爾排序B.堆排序C.選擇排序D.歸并排序16②下列排序算法中，在待排序數(shù)據(jù)已有序時，花費時間反而最多的是（）排序。A．冒泡B.希爾C.快速D.堆17②下列排序算法中，在每一趟都能選出一個元素放到其最終位置上，并且其時間性能受數(shù)據(jù)初始特性影響的是：（）。A.直接插入排序B.快速排序C.直接選擇排序D.堆排序18②對初始狀態(tài)為遞增序列的表按遞增順序排序，最省時間的是（）算法，最費時間的是（）算法。A.堆排序B.快速排序C.插入排序D.歸并排序19②就平均性能而言，目前最好的內(nèi)排序方法是（）排序法。A.冒泡B.希爾排序C.直接插入D.快速20③如果只想得到1000個元素組成的序列中第5個最小元素之前的部分排序的序列，用（）方法最快。A．冒泡排序B．快速排序C．希爾排序D．堆排序E．直接選擇排序21②在文件“局部有序”或文件長度較小的情況下，最佳內(nèi)部排序的方法是（）A．直接插入排序B．冒泡排序C．直接選擇排序22③下列排序算法中，（）算法可能會出現(xiàn)下面情況：在最后一趟開始之前，所有元素都不在其最終的位置上。A.堆排序B.冒泡排序C.快速排序D.插入排序23③下列排序算法中，占用輔助空間最多的是：（）A.歸并排序B.快速排序C.希爾排序D.堆排序24②從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（）排序法。A.插入B.選擇C.希爾D.歸并25②在排序算法中，每次從未排序的記錄中挑出最?。ɑ蜃畲螅╆P(guān)鍵碼字的記錄，加入到已排序記錄的末尾，該排序方法是（）。A.選擇B.冒泡C.插入D.堆26②在排序算法中每一項都與其它各項進行比較，計算出小于該項的項的個數(shù)，以確定該項的位置叫（）A．插入排序B．枚舉排序C．選擇排序D．交換排序27②就排序算法所用的輔助空間而言，堆排序，快速排序，歸并排序的關(guān)系是（）A．堆排序<快速排序<歸并排序B．堆排序<歸并排序<快速排序C．堆排序>歸并排序>快速排序D．堆排序>快速排序>歸并排序E．以上答案都不對28③設(shè)要將序列{q，h，c，y，p，a，m，s，r，d，f，x}中的關(guān)鍵碼按字母升序重新排序，（（1））是初始步長為4的shell排序一趟掃描的結(jié)果；（（2））是對排序初始建堆的結(jié)果；（（3））是以第一個元素為分界元素的快速一趟掃描的結(jié)果。從下面供選擇的答案中選出正確答案填入括號內(nèi)。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，x29③將兩個各有N個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（）A．NB．2N-1C．2N