第5章_內(nèi)部排序_習(xí)題答案

1、第第5章章 內(nèi)部排序內(nèi)部排序習(xí)題及答案習(xí)題及答案一、單項(xiàng)選擇題一、單項(xiàng)選擇題( ) 1. 一組記錄的關(guān)鍵碼為一組記錄的關(guān)鍵碼為( 46, 79, 56, 38, 40, 84 ) 利用快速排序方法，以第一個(gè)記錄為基準(zhǔn)得利用快速排序方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為。到的一次劃分結(jié)果為。A. 38, 40, 46, 56, 79, 84B. 40, 38, 46, 79, 56, 84C. 40, 38, 46, 56, 79, 84D. 40, 38, 46, 84, 56, 79C( ) 2. 已知已知10個(gè)數(shù)據(jù)元素為個(gè)數(shù)據(jù)元素為（ 54, 28, 16, 34, 73, 62,

2、95, 60, 26, 43 ）對(duì)該數(shù)列按從小到大排序，經(jīng)過(guò)一趟冒泡排序?qū)υ摂?shù)列按從小到大排序，經(jīng)過(guò)一趟冒泡排序(大數(shù)下沉大數(shù)下沉)后的序列為。后的序列為。A. 16, 28, 34, 54, 73, 62, 60, 26, 43, 95B. 28, 16, 34, 54, 62, 73, 60, 26, 43, 95C. 28, 16, 34, 54, 62, 60, 73, 26, 43, 95D. 16, 28, 34, 54, 62, 60, 73, 26, 43, 95B( ) 3. 下列關(guān)鍵碼序列中，屬于堆的是。下列關(guān)鍵碼序列中，屬于堆的是。A.（15, 30, 22, 93, 5

3、2, 71）B.（15, 71, 30, 22, 93, 52）C.（15, 52, 22, 93, 30, 71）D.（93, 30, 52, 22, 15, 71）A( ) 4直接插入排序算法的時(shí)間復(fù)雜性為。直接插入排序算法的時(shí)間復(fù)雜性為。A. O(1)B. O(n)C. O(nlog2n)D. O(n2)( ) 5.下列排序方法中下列排序方法中,屬于穩(wěn)定的排序方法是。屬于穩(wěn)定的排序方法是。A. 希爾排序希爾排序B. 快速排序快速排序C. 冒泡排序冒泡排序D. 堆排序堆排序DC( ) 6. 若對(duì)序列若對(duì)序列（ 15, 30, 26, 22, 69, 50, 53, 87 ）采用二路歸并法排

4、序，則進(jìn)行一趟歸并后產(chǎn)生采用二路歸并法排序，則進(jìn)行一趟歸并后產(chǎn)生的序列為。的序列為。A. 15, 22, 26, 30, 50, 53, 69, 87B. 15, 30, 22, 26, 50, 69, 53, 87C. 15, 26, 30, 22, 50, 69, 53, 87D. 15, 26, 22, 30, 50, 53, 69, 87B( ) 7. 排序算法中，第一趟排序后，任排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是。一元素都不能確定其最終位置的算法是。A.選擇排序選擇排序B.快速排序快速排序C.冒泡排序冒泡排序D.插入排序插入排序D( ) 8.采用排序算法對(duì)

5、采用排序算法對(duì) n 個(gè)元素進(jìn)行個(gè)元素進(jìn)行排序，其排序趟數(shù)肯定為排序，其排序趟數(shù)肯定為 n-1 趟的排序趟的排序方法是。方法是。A.插入和快速插入和快速B.冒泡和快速冒泡和快速C.選擇和插入選擇和插入D.選擇和冒泡選擇和冒泡C二、填空題二、填空題1.在最好的情況下，對(duì)于具有在最好的情況下，對(duì)于具有n個(gè)元素的有個(gè)元素的有序序列，若采用冒泡排序，所需的比較次序序列，若采用冒泡排序，所需的比較次數(shù)為數(shù)為_(kāi)次。次。2.對(duì)于具有對(duì)于具有n個(gè)元素的有序序列，若采用冒個(gè)元素的有序序列，若采用冒泡排序，最多需要進(jìn)行泡排序，最多需要進(jìn)行_趟起泡。趟起泡。n-1n-13. 在插入排序和選擇排序中，若原始記錄已在插入

6、排序和選擇排序中，若原始記錄已基本有序，則較適合選用基本有序，則較適合選用_。4. 在對(duì)一組記錄在對(duì)一組記錄 （54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時(shí)，當(dāng)把進(jìn)行直接插入排序時(shí)，當(dāng)把 記錄記錄 60 插入到插入到前面的有序表中時(shí)，為尋找插入位置需比較前面的有序表中時(shí)，為尋找插入位置需比較_次。次。5. 堆排序的時(shí)間復(fù)雜性為堆排序的時(shí)間復(fù)雜性為_(kāi) 。插入排序插入排序3O(n log2n)三、應(yīng)用題三、應(yīng)用題1. 已知關(guān)鍵碼序列已知關(guān)鍵碼序列（83, 40, 63, 13, 84, 35, 96, 57）分別畫(huà)出用分別畫(huà)出用直接插入排序、簡(jiǎn)單選擇排序直接插入排序、簡(jiǎn)

7、單選擇排序、快速排序快速排序?qū)ι鲜鲂蛄羞M(jìn)行操作的各趟結(jié)果。對(duì)上述序列進(jìn)行操作的各趟結(jié)果。（1）直接插入排序）直接插入排序12345678初始初始 83 40631384359657i=240 83i=3406383i=413406383i=51340638384i=6 133540638384i=713354063838496i=8133540576383849601234567初始初始8340631384359657第第1趟趟13 40638384359657第第2趟趟1335638384409657第第3趟趟1335408384639657第第4趟趟1335405784639683第第5趟

8、趟1335405763849683第第6趟趟1335405763839684第第7趟趟1335405763838496（2）簡(jiǎn)單選擇簡(jiǎn)單選擇排序排序(3) 快速排序第快速排序第一一趟過(guò)程趟過(guò)程12345678初始初始8340 631384359657第第1次交換次交換57 40 631384359683第第2次交換次交換5740 63 13 833596 84第第3次交換次交換5740 6313 35 8396 8412345678第第1趟趟5740631335 839684第第2趟趟3540135763 838496第第3趟趟1335405763838496第第4趟趟133563576383

9、8496（3）各趟）各趟快速快速排序過(guò)程排序過(guò)程2. 判別以下序列是否為堆判別以下序列是否為堆, 如果不是如果不是 , 把它調(diào)把它調(diào)整為堆整為堆; 再進(jìn)行堆排序。再進(jìn)行堆排序。 ( 6, 56, 20, 3, 23, 40, 38, 29, 61 )6562032961234038( 6, 56, 20, 3, 23, 40, 38, 29, 61） 不是堆不是堆63202956612340383620295661234038是小堆是小堆6162029563234038輸出輸出6232029563614038輸出輸出5623202963614038輸出輸出2023382963614056輸出輸

10、出5623382963614020輸出輸出2329385663614020輸出輸出4029385663612320輸出輸出2940385663612320輸出輸出6140385663292320輸出輸出3840615663292320輸出輸出5640613863292320輸出輸出4056613863292320輸出輸出6156403863292320輸出輸出5661403863292320輸出輸出6156403863292320輸出輸出6156403863292320輸出輸出四、算法設(shè)計(jì)題四、算法設(shè)計(jì)題 設(shè)有關(guān)鍵碼序列設(shè)有關(guān)鍵碼序列 ( 7, 1, 9, 5, 3 )存放在一個(gè)順序表：整型數(shù)

11、組存放在一個(gè)順序表：整型數(shù)組e6中的中的e1e5。 編寫(xiě)程序?qū)崿F(xiàn)：編寫(xiě)程序?qū)崿F(xiàn)： (1)先采用一種簡(jiǎn)單排序法先采用一種簡(jiǎn)單排序法(如直接插入排序、冒泡排如直接插入排序、冒泡排序、簡(jiǎn)單選擇排序序、簡(jiǎn)單選擇排序)，把該順序表調(diào)整為有序表：，把該順序表調(diào)整為有序表： void InsertSort ( int r , int n ) (2) 再用折半查找法，在有序表中查找值為再用折半查找法，在有序表中查找值為 key 的元的元素素 ：int Search_Bin ( int e , int n, int key )參考程序?yàn)椋簠⒖汲绦驗(yàn)椋?include using namespace std;/直

12、接插入排序法直接插入排序法void InsertSort ( int r , int n ) for ( int i=2; i=n; i+ ) if (ri ri-1) r0 = ri; / 復(fù)制為監(jiān)視哨復(fù)制為監(jiān)視哨 for ( int j = i-1 ; r0 rj; j- ) rj+1 = rj; / 記錄后移記錄后移 rj+1 = r0; / 插入到正確位置插入到正確位置 /折半查找法折半查找法int Search_Bin ( int e , int n, int key ) int low, high, mid ; low = 1; high = n ; / 置區(qū)間初值置區(qū)間初值 wh

13、ile ( low = high ) mid = ( low + high ) / 2; if ( key = emid ) return mid; / 找到待查元素找到待查元素 else if ( key = emid ) high = mid - 1; / 在前半?yún)^(qū)間進(jìn)行查找在前半?yún)^(qū)間進(jìn)行查找 else low = mid + 1; / 在后半?yún)^(qū)間進(jìn)行查找在后半?yún)^(qū)間進(jìn)行查找 return 0; / 順序表中不存在待查元素順序表中不存在待查元素 void main ( ) int i , j, key , e6= 0, 7, 1, 9, 5, 3 ; InsertSort ( e , 5 ) ;