嚴(yán)魏敏課后習(xí)題 選擇題

1. 從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，這種排序方法稱為（ ）。

   

   創(chuàng)新互聯(lián)建站長(zhǎng)期為上千余家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為集安企業(yè)提供專業(yè)的網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站制作，集安網(wǎng)站改版等技術(shù)服務(wù)。擁有10年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

   A. 歸并排序
   B. 冒泡排序
   C. 插入排序
   D. 選擇排序

2. 從未排序序列中挑選元素，并將其依次插入已排序序列（初始時(shí)為空）末端的方法，稱為（ ）。
   A. 歸并排序
   B. 冒泡排序
   C. 插入排序
   D. 選擇排序

3. 對(duì)n個(gè)不同的關(guān)鍵字由小到大進(jìn)行冒泡排序，在下列（ ）情況下比較的次數(shù)最多。
   A. 從小到大排列好的
   B. 從大到小排列好的
   C. 元素?zé)o序
   D. 元素基本有序

4. 對(duì)n個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為（ ）。
   A. n+1
   B. n
   C. n?1
   D. n(n?1)/2

5. 快速排序在下列（ ）情況下最易發(fā)揮其長(zhǎng)處。
   A. 被排序的數(shù)據(jù)中含有多個(gè)相同排序碼
   B. 被排序的數(shù)據(jù)已基本有序
   C. 被排序的數(shù)據(jù)完全無(wú)序
   D. 被排序的數(shù)據(jù)中的大值和最小值相差懸殊

6. 對(duì)n個(gè)關(guān)鍵字做快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是（ ）。
   A. O(n)
   B. O(n2)
   C. O(nlog2n)
   D. O(n3)

7. 若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用快速排序的方法，以第一個(gè)記錄為基準(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

8. 下列關(guān)鍵字序列中，（ ）是堆。
   A. 16, 72, 31, 23, 94, 53
   B. 94, 23, 31, 72, 16, 53
   C. 16, 53, 23, 94, 31, 72
   D. 16, 23, 53, 31, 94, 72

9. 堆是一種（ ）排序。
   A. 插入
   B. 選擇
   C. 交換
   D. 歸并

10. 堆的形狀是一棵（ ）。
    A. 二叉排序樹
    B. 滿二叉樹
    C. 完全二叉樹
    D. 平衡二叉樹

11. 若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用堆排序的方法建立的初始堆為（ ）。
    A. 79, 46, 56, 38, 40, 84
    B. 84, 79, 56, 38, 40, 46
    C. 84, 79, 56, 46, 40, 38
    D. 84, 56, 79, 40, 46, 38

12. 下述幾種排序方法中，要求內(nèi)存大的是（ ）。
    A. 希爾排序
    B. 快速排序
    C. 歸并排序
    D. 堆排序

13. 下述幾種排序方法中，（ ）是穩(wěn)定的排序方法。
    A. 希爾排序
    B. 快速排序
    C. 歸并排序
    D. 堆排序

14. 數(shù)據(jù)表中有10000個(gè)元素，如果僅要求求出其中大的10個(gè)元素，則采用（ ）算法最節(jié)省時(shí)間。
    A. 冒泡排序
    B. 快速排序
    C. 簡(jiǎn)單選擇排序
    D. 堆排序

15. 下列排序算法中，不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上的排序方法是（ ）。
    A. 希爾排序
    B. 快速排序
    C. 冒泡排序
    D. 堆排序

答案：
1-5 CDCDC 6-10 BADBC 11-15 BCCCB

應(yīng)用題

1. 設(shè)待排序的關(guān)鍵字序列為{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}，試分別寫出使用以下排序方法，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。
   ① 直接插入排序
   9趟
   

2，12，16， 30，28，10，16*，20，6，18
2，12，16， 30，28，10，16*，20，6，18
2，12，16， 30，28，10，16*，20，6，18
2，12，16，28，30，10，16*，20，6，18
2，10，12，16，28，30，16*，20，6，18
2，10，12，16，16*，28，30，20，6，18
2，10，12，16，16*，20，28，30，6，18
2，6，10，12，16，16*，20，28，30，18
2，6，10，12，16，16*，18，20，28，30

② 折半插入排序

折半插入排序中的排序功能其實(shí)就是直接插入排序，則同①

③ 希爾排序（增量選取5、3和1）

12，2，16， 30，28，10，16*，20，6，18
10，2，16，6，18，12，16*，20，30，28（增量：5）
6，2，12，10，18，16，16*，20，30，28 （增量：3）
2，6，10，12，16，16*，18，20，30，28 （增量：1）

④ 冒泡排序

12，2，16， 30，28，10，16*，20，6，18
2，12，16，28，10，16*，20，6，18，30
2，12，16，10，16*，20，6，18，28，30
2，12，10，16，16*，6，18，20，28，30
2，10，12，16，6，16*，18，20，28，30
2，10，12，6，16，16*，18，20，28，30
2，10，6，12，16，16*，18，20，28，30
2，6，10，12，16，16*，18，20，28，30
2，6，10，12，16，16*，18，20，28，30

⑤ 快速排序
前面空開，先從后面找

12，2，16， 30，28，10，16*，20，6，18
6，2，10，12，28，30，16，20，16，18
2，6，10，12，18，16，16*，20，28，30
2，6，10，12，16*，16，18，20，28，30
2，6，10，12，16*，16，18，20，28，30

⑥ 簡(jiǎn)單選擇排序
寫全，最后一行。

12，2，16， 30，28，10，16*，20，6，18
2，12，16， 30，28，10，16*，20，6，18
2，6，16， 30，28，10，16*，20，12，18
2，6，10， 30，28，16，16*，20，12，18
2，6，10，12，28，16，16*，20， 30，18
2，6，10，12，16，28，16*，20， 30，18
2，6，10，12，16，16*，28，20， 30，18
2，6，10，12，16，16*，18，20， 30，28
2，6，10，12，16，16*，18，20， 28，30
2，6，10，12，16，16*，18，20， 28，30

⑦ 堆排序｛畫圖｝

12，2，16， 30，28，10，16*，20，6，18
2，6，12，10，20，18，16，16*，28，30
2，6，10，12，16*，20，18，16，30，20
2，6，10，12，20，16*，28，18，16，30
2，6，10，12，16*，20，16，28，18，30
2，6，10，12，16*，16，20，30，28，18
2，6，10，12，16*，16，18，20，30，28
2，6，10，12，16*，16，18，20，28，30
2，6，10，12，16*，16，18，20，28，30

⑧ 二路歸并排序
兩兩對(duì)比
2，12，16，30，10，28，16*，20，6，18
2，12，16，30，10，16*，20，28，6，18
2，10，12，16，16*，20，28，30，6，18
2，6，10，12，16，16*，18，20，28，30

3. 給出如下關(guān)鍵字序列{321, 156, 57, 46, 28, 7, 331, 33, 34, 63}，試按鏈?zhǔn)交鶖?shù)排序方法，列出每一趟分配和收集的過(guò)程。
   盡快做一下
4. 對(duì)輸入文件（101，51，19，61，3，71，31，17，19，100，55，20，9，30，50，6，90）；當(dāng)k=6時(shí)，使用置換-選擇算法，寫出建立的初始敗者樹及生成的初始?xì)w并段。
   盡快做一下

算法設(shè)計(jì)題

1. 試以單鏈表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)簡(jiǎn)單選擇排序算法。
   盡快做一下
2. 有n個(gè)記錄存儲(chǔ)在帶頭結(jié)點(diǎn)的雙向鏈表中，利用雙向冒泡排序法對(duì)其按升序進(jìn)行排序，請(qǐng)寫出這種排序的算法。（注：雙向冒泡排序即相鄰兩趟排序向相反方向冒泡）
   盡快做一下
3. 設(shè)有順序放置的n個(gè)桶，每個(gè)桶中裝有一粒礫石，每粒礫石的顏色是紅、白、藍(lán)之一。要求重新安排這些礫石，使得所有紅色礫石在前，所有白色礫石居中，所有藍(lán)色礫石在后，重新安排時(shí)對(duì)每粒礫石的顏色只能看一次，并且只允許交換操作來(lái)調(diào)整礫石的位置。
   盡快做一下
4. 編寫算法，對(duì)n個(gè)關(guān)鍵字取整數(shù)值的記錄序列進(jìn)行整理，以使所有關(guān)鍵字為負(fù)值的記錄排在關(guān)鍵字為非負(fù)值的記錄之前，要求：① 采用順序存儲(chǔ)結(jié)構(gòu)，至多使用一個(gè)記錄的輔助存儲(chǔ)空間；② 算法的時(shí)間復(fù)雜度為O(n)。
   盡快做一下
5. 借助于快速排序的算法思想，在一組無(wú)序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組r[1…n]中。若查找成功，則輸出該記錄在r數(shù)組中的位置及其值，否則顯示“not find”信息。請(qǐng)簡(jiǎn)要說(shuō)明算法思想并編寫算法。
   盡快做一下
6. 有一種簡(jiǎn)單的排序算法，叫做計(jì)數(shù)排序。這種排序算法對(duì)一個(gè)待排序的表進(jìn)行排序，并將排序結(jié)果存放到另一個(gè)新的表中。必須注意的是，表中所有待排序的關(guān)鍵字互不相同，計(jì)數(shù)排序算法針對(duì)表中的每個(gè)記錄，掃描待排序的表一趟，統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵字比該記錄的關(guān)鍵字小。假設(shè)針對(duì)某一個(gè)記錄，統(tǒng)計(jì)出的計(jì)數(shù)值為c，那么，這個(gè)記錄在新的有序表中的合適的存放位置即為c。
   ① 給出適用于計(jì)數(shù)排序的順序表定義；
   ② 編寫實(shí)現(xiàn)計(jì)數(shù)排序的算法；
   ③ 對(duì)于有n個(gè)記錄的表，關(guān)鍵字比較次數(shù)是多少？
   ④ 與簡(jiǎn)單選擇排序相比較，這種方法是否更好？為什么？
   盡快做一下

總結(jié)

以下全部復(fù)制書上內(nèi)容。

得出以下幾點(diǎn)結(jié)論：
（1）當(dāng)待排序的記錄個(gè)數(shù)n較小時(shí)，n2和nlog2n的差別不大，可選用簡(jiǎn)單的排序方法。
而當(dāng)關(guān)鍵字基本有序時(shí)，可選用直接插入排序或冒泡排序，排序速度很快，其中直接插入排序最為簡(jiǎn)單常用、性能最佳。
（2）當(dāng)n較大時(shí)，應(yīng)該選用先進(jìn)的排序方法。對(duì)于先進(jìn)的排序方法，從平均時(shí)間性能而言，快速排序最佳，是目前基于比較的排序方法中最好的方法。但在最壞情況下，即當(dāng)關(guān)鍵字基本有序時(shí)，快速排序的遞歸深度為n，時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(n)。
堆排序和歸并排序不會(huì)出現(xiàn)快速排序的最壞情況，但歸并排序的輔助空間較大。這樣，當(dāng)n較大時(shí)，具體選用的原則是：
① 當(dāng)關(guān)鍵字分布隨機(jī)，穩(wěn)定性不做要求時(shí)，可采用快速排序；
② 當(dāng)關(guān)鍵字基本有序，穩(wěn)定性不做要求時(shí)，可采用堆排序；
③ 當(dāng)關(guān)鍵字基本有序，內(nèi)存允許且要求排序穩(wěn)定時(shí)，可采用歸并排序。
（3）可以將簡(jiǎn)單的排序方法和先進(jìn)的排序方法結(jié)合使用。
例如，當(dāng)n較大時(shí)，可以先將待排序序列劃分成若干子序列，分別進(jìn)行直接插入排序，然后再利用歸并排序，將有序子序列合并成一個(gè)完整的有序序列。
或者，在快速排序中，當(dāng)劃分子區(qū)間的長(zhǎng)度小于某值時(shí)，可以轉(zhuǎn)而調(diào)用直接插入排序算法。
（4）基數(shù)排序的時(shí)間復(fù)雜度也可寫成O(d·n)。因此，它最適用于n值很大而關(guān)鍵字較小的序列。
若關(guān)鍵字也很大，而序列中大多數(shù)記錄的“最高位關(guān)鍵字”均不同，則亦可先按“最高位關(guān)鍵字”不同將序列分成若干“小”的子序列，而后進(jìn)行直接插入排序。
但基數(shù)排序使用條件有嚴(yán)格的要求：需要知道各級(jí)關(guān)鍵字的主次關(guān)系和各級(jí)關(guān)鍵字的取值范圍，即只適用于像整數(shù)和字符這類有明顯結(jié)構(gòu)特征的關(guān)鍵字，當(dāng)關(guān)鍵字的取值范圍為無(wú)窮集合時(shí)，則無(wú)法使用基數(shù)排序。
（5）從方法的穩(wěn)定性來(lái)比較，基數(shù)排序是穩(wěn)定的內(nèi)排方法，所有時(shí)間復(fù)雜度為O(n2)的簡(jiǎn)單排序法也是穩(wěn)定的，然而，快速排序、堆排序和希爾排序等時(shí)間性能較好的排序方法都是不穩(wěn)定的。一般來(lái)說(shuō)，如果排序過(guò)程中的“比較”是在“相鄰的兩個(gè)記錄關(guān)鍵字”間進(jìn)行的，則排序方法是穩(wěn)定的。
（6）在本章討論的排序方法中，多數(shù)是采用順序表實(shí)現(xiàn)的。若記錄本身信息量較大，為避免移動(dòng)記錄耗費(fèi)大量時(shí)間，可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。比如直接插入排序、歸并排序都易于在鏈表上實(shí)現(xiàn)。但像折半插入排序、希爾排序、快速排序和堆排序，卻難于在鏈表上實(shí)現(xiàn)。

對(duì)于外部排序，常用的方法是歸并方法，這種方法主要由兩個(gè)獨(dú)立的階段組成：
第一，把待排序的文件劃分成若干個(gè)子文件；
第二，逐趟歸并子文件，最后形成對(duì)整個(gè)文件的排序。
為減少歸并中外存讀寫的次數(shù)，提高外排序的效率，一般通過(guò)增大歸并路數(shù)和減少初始?xì)w并段個(gè)數(shù)兩種方案對(duì)歸并算法進(jìn)行改進(jìn)，其中，“多路平衡歸并”的方法可以增加歸并段的個(gè)數(shù)，“置換-選擇”的方法可以減少初始?xì)w并段的個(gè)數(shù)。

學(xué)完本章后，要求掌握與排序相關(guān)的基本概念，
如：關(guān)鍵字比較次數(shù)、數(shù)據(jù)移動(dòng)次數(shù)、穩(wěn)定性、內(nèi)部排序、外部排序。深刻理解各種內(nèi)部排序方法的基本思想、特點(diǎn)、實(shí)現(xiàn)方法及其性能分析，能從時(shí)間、空間、穩(wěn)定性各個(gè)方面對(duì)各種排序方法做綜合比較，并能加以靈活應(yīng)用。掌握外部排序方法中敗者樹的建立及歸并方法，掌握置換-選擇排序的過(guò)程和最佳歸并樹的構(gòu)造方法。

選用哪種排序一般綜合考慮以下因素：
（1）待排序的記錄個(gè)數(shù)；
（2）記錄本身的大小；
（3）關(guān)鍵字的結(jié)構(gòu)及初始狀態(tài)；
（4）對(duì)排序穩(wěn)定性的要求；
（5）存儲(chǔ)結(jié)構(gòu)。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章標(biāo)題：嚴(yán)魏敏-習(xí)題-排序-08-創(chuàng)新互聯(lián)
分享鏈接：http://www.chinadenli.net/article2/dccoic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供服務(wù)器托管、網(wǎng)站營(yíng)銷、ChatGPT、用戶體驗(yàn)、微信小程序、動(dòng)態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)